#### fall 2020 courses

## CS 380C *Compilers*

Prof. Keshav Pingali, M 10 am - 1 pm. Models of distributed systems; language issues, proving properties of distributed systems; time, clocks, partial ordering of events; deadlock and termination detection; diffusing computations; computing in hostile environments; distributed resource management. Three lecture hours a week for one semester. Prerequisite: Graduate standing and Computer Science 372.

## CS 380L *Advanced Operating Systems*

Prof. Chris Rossbach, TTh 9:30-11 am. Study of the formal structure, design principles, organization, implementation, and performance analysis of multiprogramming and/or multiprocessor computer systems. Prerequisites: Graduate standing, and consent of instructor.

## CS 383C *Numerical Analysis: Linear Algebra*

Prof. Robert Van de Geijn, TTh 9:30-11 am. Survey of numerical methods in linear algebra: floating-point computation, solution of linear equations, least squares problems, algebraic eigenvalue problems. Prerequisites: Graduate standing; Computer Science 367 or Mathematics 368K; and Mathematics 340L, 341, or consent of instructor.

## CS 386C *Dependable Computing Systems*

Prof. Al Mok, TTh 2-3:30 pm. System models from synchronous to asynchronous, with emphasis on in-between models such as the timed asynchronous model. Control structures such as timed state-transition systems, and constraints in temporal and real-time logics. Analysis techniques such as model checking of timed systems, and extended Presburger arithmetic. Basic building blocks such as clock synchronization, synchronous atomic broadcast, time-bounded membership protocols, real-time scheduling theory, and state recovery methods. Practical implementation issues such as special operating system data structures and algorithms, open system design, and security concerns. Prerequisites: Graduate standing, and an undergraduate course in operating systems or consent of instructor.

## CS 386W *Wireless Networking*

Prof. Lili Qiu, M 1-4 pm. Fundamental concepts and principles of wireless network technologies and protocol design, ranging from physical layer to application layer, and in-depth studies of current wireless research. Prerequisites: Graduate standing.

## CS 388G *Algorithms: Techniques and Theory*

Prof. Vijaya Ramachandran, TTh 3:30-5 pm. Sorting and searching algorithms, graph algorithms, algorithm design techniques, lower bound theory, fast Fourier transforms, NP-completeness. Three lecture hours a week for one semester. Prerequisite: Graduate standing, and Computer Science 357 or the equivalent or consent of instructor.

## CS 391L *Machine Learning*

Prof. Dana Ballard, MW 10:30-12 pm. Computing systems that automatically improve their performance with experience, including various approaches to inductive classification such as version space, decision tree, rule-based, neural network, Bayesian, and instance-based methods; as well as computational learning theory, explanation-based learning, and knowledge refinement. Prerequisites: Graduate standing, and Computer Science 381K or equivalent knowledge of artificial intelligence and LISP.

## CS 391R *Robot Learning*

Prof. Yuke Zhu, TTh 2-3:30 pm. Survey a wide range of modern techniques in robotics that learn from data, largely focusing on robot perception and decision making. Explore 3D vision, representation learning, active perception, reinforcement learning, imitation learning, and applications in robot manipulation. Prerequisites: Graduate standing, and experience in machine learning and computer vision.

## CS 393R *Autonomous Robots*

Prof. Joydeep Biswas, MW 9-10:30 am. Explore an advanced overview of autonomous mobile robotics, including control, perception, and planning. Examine algorithms and data structures related to these, cover widely adopted and state of the art techniques. Implement and extend such algorithms on real robots. Prerequisites: Graduate standing.

## CS 394N *Neural Networks*

Prof. Risto Miikkulainen, W 9-12 pm. Biological information processing; architectures and algorithms for supervised learning, self-organization, reinforcement learning, and neuro-evolution; theoretical analysis; hardware implementations and simulators; applications in engineering, artificial intelligence, and cognitive science. Prerequisites: Graduate standing.

## CS 395T *Advanced Quantum Complexity Theory*

Prof. John Wright, TTh 12:30-2 pm. This course will cover recent advancements in quantum complexity theory. Topics to be covered will likely include: Nonlocal games, Self-testing, Interactive proofs (QIP, MIP*), Unentangled proofs (QMA(2)), Classical verification of quantum computation. Prerequisites: A class in quantum computing (e.g., CS 378). Taking Quantum Complexity Theory (CS395T) is strongly encouraged. This course will likely be of interest to students in computer science, mathematics, and physics.

## CS 395T *Approximability*

Prof. Dana Moshkovitz, MW 2-3:30 pm. This class is about approximation algorithms and their limitations. It covers: combinatorial approximation algorithms; approximation algorithms based on linear and semidefinite programming; hierarchies of linear and semidefinite programming; limitations of the aforementioned techniques with connections to communication complexity and proof complexity; hardness of approximation and connections to multi-prover games and probabilistic checking of proofs; the proof of the PCP theorem, including combinatorial and algebraic techniques; sum-check; linearity testing; low degree testing; locally testable and decodable codes; composition; parallel repetition; long code, Fourier analysis and optimal inapproximability results; the Unique Games Conjecture; dictator tests and integrality gaps.

## CS 395T *Data Centers*

Prof. Simon Peter, MW 10-11:30 am. This course covers advanced topics in data centers. The focus is on principles, architectures, and protocols used in modern data centers. We will cover hardware and networking architectures, operating systems, storage, and applications. The goal of the course is to build on basic computer architecture, networking and operating systems course material to provide an understanding of large, complex networked systems, and provide concrete experience of the challenges through a set of labs. Prerequisites: This course builds on the computer systems course (CS 439 or equivalent), the contents of which will be assumed knowledge. Proficiency in C programming is assumed.

## CS 395T *Expanders and Extractors*

Prof. David Zuckerman, TTh 2-3:30 pm. Expander graphs and randomness extractors are fundamental objects in the study of pseudorandomness. An expander is a graph where any subset of nodes has many neighbors. A randomness extractor is an efficient algorithm to purify randomness. These are related in non-obvious ways and have many applications to a wide variety of areas, including pseudorandomness, coding theory, cryptography, randomized algorithms, network constructions, inapproximability, and data structures. In this course, we will explore these objects and their applications, including recent developments such as two-source extractors and high-dimensional expanders. Prerequisites: Graduate standing.

## CS 395T *Sublinear Algorithms*

Prof. Eric Price, TTh 2-3:30 pm. This graduate course will study algorithms that can process very large data sets. In particular, we will consider algorithms for: Data streams, where you don't have enough space to store all the data being generated; Property testing, where you don't have enough time to look at all the data; Compressed sensing, where you don't have enough measurement capacity to observe all the data. Prerequisites: Mathematical maturity and comfort with undergraduate algorithms and basic probability. Ideally also familiarity with linear algebra.

## CS 395T *Topics in Natural Language Processing*

Prof. Eunsol Choi, TTh 9:30-11 am. In this course, we discuss traditional and newly proposed topics in NLP (e.g., generation, question answering, grounding, dialogue, etc.), and machine learning methods introduced to address such tasks. Each topic discussion will span multiple classes: we will first study how the research problems have been framed, and discuss the advances and limitations of machine learning methods designed to address the problem. The class will include, in addition to paper reviews and discussions, a final group project. This course focuses on identifying research problems in NLP and understanding existing methods to address such research problems. It does not require a prior background in NLP, but a background in programming and machine learning.

## CS 395T *Foundations of Predictive Machine Learning*

Prof. Chandrajit Bajaj, MW 3:30-5 pm. This course is on foundational aspects of data sciences, machine (deep) learning and statistical inference analysis. The topics span frequentist and Bayesian learning from data, to permit prediction, classification, detection, ranking and decision making. It utilizes state of the art convex and non-convex geometric, manifold optimization, while weaving together discrete and continuous mathematics, computer science and statistics. Students shall delve with breadth-and-depth into dimensionality reduction, sparsity, resolution, resolvability, recovery, equivariance, stability, prediction with uncertainty quantification, for a variety of imaging and simulate data (sequence, steam, graph-based, time-series, images, video, hyper-spectral), emanating from multiple sensors (big and small, slow and fast), and snapshots of scientific simulations possibly satisfying various conservation laws. Issues of measurement and computation errors, noise and outliers shall be central to bounding the precision and accuracy of the data analysis. Such data driven applications abound in every area of science, engineering, and medicine. Prerequisites: Graduate standing.

#### spring 2021 courses

## CS 380D *Distributed Computing I*

Prof. Vijay Chidambaram, TTh 3:30-5 pm. Models of distributed systems; language issues, proving properties of distributed systems; time, clocks, partial ordering of events; deadlock and termination detection; diffusing computations; computing in hostile environments; distributed resource management. Prerequisites: Graduate standing.

## CS 380S *Theory and Practice of Secure Systems*

Prof. Hovav Shacham, TTh 9:30-11 am. Survey of modern security, designed to introduce the basic techniques used in the design and analysis of secure systems. Prerequisites: Graduate standing, and Computer Science 353 or consent of instructor.

## CS 386D *Database Systems*

Prof. Dan Miranker, M 6-9 pm. Introduction to the principles of database systems, including fundamental ideas and algorithms used in the construction of centralized database management systems, distributed database management systems, and database machines and their roles in Internet infrastructure. Topics include data storage and indexing algorithms, query processing and optimization, concurrency control, recovery, XML and object-oriented databases, database evaluation and tuning, and recent directions in database research. Three lecture hours a week for one semester. Prerequisite: Graduate standing and Computer Science 347 and 375.

## CS 3386L *Programming Languages*

Prof. William Cook, TTh 12:30-2 pm. Topics include formal syntax representations, program correctness, typing, and data abstraction. Features and problems in languages that allow parallelism. Exploration of different programming styles, such as imperative, functional, logic, data flow, and object-oriented programming. Three lecture hours a week for one semester. Prerequisite: Graduate standing, and Computer Science 345 or consent of instructor.

## CS 388C *Combinatorics & Graph Theory*

Prof. Anna Gal, TTh 12:30-2 pm. ng, matching theory, extremal set theory, Ramsey theory, probabilistic method, linear algebra method, coding theory. Applications to computer science, including randomized algorithms. Three lecture hours a week for one semester. Prerequisite: Graduate standing, and Computer Science 336 or the equivalent or consent of instructor. An understanding of elementary proof and counting techniques is assumed.

## CS 388 *Natural Language Processing*

Prof. Greg Durrett, TTh 9:30-11 am. Computational methods for syntactic and semantic analysis of structures representing meanings of natural language; study of current natural language processing systems; methods for computing outlines and discourse structures of descriptive text. Three lecture hours a week for one semester. Prerequisite: Graduate standing, and a course in artificial intelligence or consent of instructor.

## CS 388G *Algorithms: Techniques and Theory*

Prof. Greg Plaxton, MW 2-3:30 pm. Sorting and searching algorithms, graph algorithms, algorithm design techniques, lower bound theory, fast Fourier transforms, NP-completeness. Three lecture hours a week for one semester. Prerequisite: Graduate standing, and Computer Science 357 or the equivalent or consent of instructor.

## CS 389L *Automated Logical Reasoning*

Prof. Isil Dillig, TTh 2-3:30 pm. Subjects include automated reasoning techniques for propositional logic, first-order logic, linear arithmetic over reals and integers, theory of uninterpreted functions, and combinations of these theories. Examines automated logical reasoning both from a theoretical and practical perspective, giving a hands-on experience building useful tools, such as SAT and SMT solvers. Three lecture hours a week for one semester. Computer Science 389L and 395T (Topic: Automated Logical Reasoning) may not both be counted. Prerequisite: Graduate standing.

## CS 394P *Automatic Programming*

Prof. Swarat Chaudhuri, TTh 3:30-5 pm. Automatic generation of computer programs from high-level specifications. Program analysis, optimization, and transformation; partial evaluation; object-oriented programming; transformation of formal specifications; specialization of generic procedures; views. Prerequisites: Graduate standing. Computer Science 375 and 381K are recommended.

## CS 395T *Grounded Natural Language Processing*

Prof. Ray Mooney, MW 2-3:30 pm. This course will be a graduate research seminar in grounded natural language processing (GNLP), a subarea of AI that studies the connection between natural language and perception and action in the world. It makes connections between natural language processing (NLP) and computer vision, robotics, and computer graphics. Almost all work in the area uses machine learning to learn the connection between language and perception and/or action from some form of multi-modal training data. Prerequisites: This class is intended for graduate students actively working in NLP, computer vision, robotics, machine learning, and/or computer graphics. Students should have had a graduate class in at least one of these areas, ideally more than one. A graduate NLP class such as CS 388 will be particularly valuable.

## CS 395T *Neural Computation*

Prof. Alex Huth, MW 3:30-5 pm. Inferring what algorithms are used by existing computational systems. Using black box system identification to understand the function of real neural/brain systems. Using gradient propagation and other methods to understand the function of artificial neural networks. Prerequisites: Students should have some previous programming experience (preferably in python). Discuss your situation with the instructor if you think you might not fulfill these prerequisites.

## CS 395T *Numerical Optimization: Graphics/AI*

Prof. Qixing Huang, MW 3:30-5 pm. This course will cover a wide range of topics in numerical optimization. The major goal is to learn a set of tools that will be useful for research in Artificial Intelligence and Computer Graphics. The course is a graduate-level course that combines instruction of basic material, written homeworks, and a final project. The course material integrates the theory of optimization and concrete real applications. Prerequisites: The course assumes a good knowledge of linear algebra and probability.

## CS 395T *Physical Simulation*

Prof. Etienne Vouga, TTh 2-3:30 pm. This project-oriented course will introduce you to the key concepts and algorithms for simulating physical systems: starting from the ground up with particle systems and mass-spring networks, we will move on to cover topics such as rigid and elastic bodies, collisions, cloth, and fluids.

## CS 395T *Quantum Complexity Theory*

Prof. Scott Aaronson, TTh 3:30-5 pm. This is an advanced graduate course about quantum complexity theory and its relationship to classical complexity theory. What that means is: we'll develop the theory of quantum computation, in a way that's accessible to computer scientists who might not even have seen quantum mechanics before. But we'll focus on a slightly unusual set of topics: ones where progress seems to depend as much on advances in classical complexity theory as it does on quantum advances, or where the whole difficulty is to rule out a classical solution to something that's known to be solvable quantumly, or where one wants to know whether one can solve a quantum problem (such as a circuit lower bound) without having to solve a corresponding classical problem. Prerequisites. The main prerequisite for the course is a previous course on computational complexity theory, or equivalent knowledge. There are no physics prerequisites: previous exposure to quantum computation is of course helpful, but won’t be assumed. If in doubt, students should talk to Prof. Aaronson.

## CS 395T *Systems Verification and Synthesis*

Prof. James Bornholt, TTh 12:30-2 pm. Recent advances in formal methods have demonstrated that it is practical to verify realistic, large scale systems, and even to automatically synthesize their implementations. This course will examine research papers on applying formal verification and program synthesis techniques to build reliable systems software, including compilers, operating systems, and distributed services. In parallel, we will conduct a hands-on survey of the landscape of verification and synthesis tools and languages. Prerequisite: Graduate standing.