211 - 220 of 366 results for: CS

Automated logical reasoning has enabled substantial progress in many fields, including hardware and software verification, theorem-proving, and artificial in- telligence. Different application scenarios may require different automated rea- soning techniques and sometimes their combination. In this course, we will study widely-used logical theories as well as algorithms for answering whether formu- las in those theories are satisfiable. We will consider state-of-the-art automated reasoning techniques for propositional logic, first-order logic, and various first- order theories, such as linear arithmetic over reals and integers, uninterpreted functions, bit-vectors, and arrays. We will also consider ways to reason about combinations of those theories. Topics include: logical foundations, SAT-solving, techniques for first-order theorem proving, decision procedures for different first- order theories, theory combination, the DPLL(T) framework, and applications of automated reasoning in program analysis and hardware verification. Prerequisites: CS154 Introduction to the Theory of Computation, or CS106b Programming Abstractions and CS103 Mathematical Foundations of Computing, or consent of instructor

This course will give an overview of how the development of quantum computers will fundamentally change the landscape of modern cryptography. This course will cover both the threats and opportunities of quantum computers for cryptography, and will include the following topics: A study of quantum algorithms for attacking classical cryptography; Cryptographic tools that resist such attacks; Quantum protocols such as quantum money that achieve never-before-possible capabilities. The course is intended for advanced undergraduates and masters students.

This course introduces the basics of quantum computing. Topics include: qubits, entanglement, and non-local correlations; quantum gates, circuits, and compilation algorithms; basic quantum algorithms such as Simon's algorithm and Grover's algorithm; Shor's factoring algorithm and the hidden subgroup problem; Hamiltonian simulation; stabilizer circuits, the Gottesman-Knill theorem, and the basics of quantum error correction. Prerequisites: Knowledge of linear algebra & discrete probability, and knowledge of algorithms OR quantum mechanics (or both)

Algorithms, algorithmic paradigms, and algorithmic tools for provably solving combinatorial optimization problems. Emphasis on graph optimization and discussion of approaches based on linear programming and continuous optimization. Potential optimization problems include both polynomial time solve-able problems, e.g., maximum flow, minimum cost flow, matching, assignment, minimum cut, matroid optimization, submodular function minimization, and NP-hard problems, e.g., Steiner trees, traveling salesperson, maximum cut. Potential paradigms and tools include: linear programming, multiplicative weight update method, algebraic methods, and spectral methods. Prerequisite: 161 or equivalent.

This course will cover various algorithm design techniques for two intimately connected class of problems: sampling from complex probability distributions and counting combinatorial structures. A large part of the course will cover Markov Chain Monte Carlo techniques: coupling, stationary times, canonical paths, Poincare and log-Sobolev inequalities. Other topics include correlation decay in spin systems, variational techniques, holographic algorithms, and polynomial interpolation-based counting. Prerequisites: CS161 or equivalent, STAT116 or equivalent.

This course is motivated by problems for which the traditional worst-case analysis of algorithms fails to differentiate meaningfully between different solutions, or recommends an intuitively "wrong" solution over the "right" one. This course studies systematically alternatives to traditional worst-case analysis that nevertheless enable rigorous and robust guarantees on the performance of an algorithm. Topics include: instance optimality; smoothed analysis; parameterized analysis and condition numbers; models of data (pseudorandomness, locality, diffuse adversaries, etc.); average-case analysis; robust distributional analysis; resource augmentation; planted and semi-random graph models. Motivating problems will be drawn from online algorithms, online learning, constraint satisfaction problems, graph partitioning, scheduling, linear programming, hashing, machine learning, and auction theory. Prerequisites: CS161 (required). CS261 is recommended but not required.

Randomness pervades the natural processes around us, from the formation of networks, to genetic recombination, to quantum physics. Randomness is also a powerful tool that can be leveraged to create algorithms and data structures which, in many cases, are more efficient and simpler than their deterministic counterparts. This course covers the key tools of probabilistic analysis, and application of these tools to understand the behaviors of random processes and algorithms. Emphasis is on theoretical foundations, though we will apply this theory broadly, discussing applications in machine learning and data analysis, networking, and systems. Topics include tail bounds, the probabilistic method, Markov chains, and martingales, with applications to analyzing random graphs, metric embeddings, random walks, and a host of powerful and elegant randomized algorithms. Prerequisites: CS 161 and STAT 116, or equivalents and instructor consent.

Algorithms for optimization and decision-making face many sources of uncertainty: inputs that change over time, are too large to read or store, or are held by strategic agents. We will cover different models of uncertainty, as well as techniques for coping with it. In particular, we will focus on robust algorithms that provide meaningful guarantees such as competitive ratio and regret analysis even when the uncertainty cannot be resolved by learning a reliable model. Sample topics include online algorithms and learning, streaming algorithms, and sublinear-time algorithms. Prerequisite: CS161.

Many 21st-century computer science applications require the design of software or systems that interact with multiple self-interested participants. This course will provide students with the vocabulary and modeling tools to reason about such design problems. Emphasis will be on understanding basic economic and game theoretic concepts that are relevant across many application domains, and on case studies that demonstrate how to apply these concepts to real-world design problems. Topics include auction and contest design, equilibrium analysis, cryptocurrencies, design of networks and network protocols, reputation systems, social choice, and social network analysis. Case studies include BGP routing, Bitcoin, eBay's reputation system, Facebook's advertising mechanism, Mechanical Turk, and dynamic pricing in Uber/Lyft. Prerequisites: CS106B/X and CS161, or permission from the instructor.