## CS 252: Analysis of Boolean Functions

Boolean functions are among the most basic objects of study in theoretical computer science. This course is about the study of boolean functions from a complexity-theoretic perspective, with an emphasis on analytic methods. We will cover fundamental concepts and techniques in this area, including influence and noise sensitivity, polynomial approximation, hypercontractivity, probabilistic invariance principles, and Gaussian analysis. We will see connections to various areas of theoretical computer science, including circuit complexity, pseudorandomness, classical and quantum query complexity, learning theory, and property testing. Prerequisites:
CS 103 and
CS 109 or equivalents.
CS 154 and
CS 161 recommended.

Last offered: Autumn 2018

## CS 253: Web Security

Principles of web security. The fundamentals and state-of-the-art in web security. Attacks and countermeasures. Topics include: the browser security model, web app vulnerabilities, injection, denial-of-service, TLS attacks, privacy, fingerprinting, same-origin policy, cross site scripting, authentication, JavaScript security, emerging threats, defense-in-depth, and techniques for writing secure code. Course projects include writing security exploits, defending insecure web apps, and implementing emerging web standards. Prerequisite:
CS 142 or equivalent web development experience.

Terms: Spr
| Units: 3

Instructors:
Aboukhadijeh, F. (PI)

## CS 254: Computational Complexity

An introduction to computational complexity theory. Topics include the P versus NP problem and other major challenges of complexity theory; Space complexity: Savitch's theorem and the Immerman-Szelepscényi theorem; P, NP, coNP, and the polynomial hierarchy; The power of randomness in computation; Non-uniform computation and circuit complexity; Interactive proofs. Prerequisites: 154 or equivalent; mathematical maturity.

Terms: Win
| Units: 3

Instructors:
Tan, L. (PI)

## CS 254B: Computational Complexity II

A continuation of
CS254 (Computational Complexity). Topics include Barriers to P versus NP; The relationship between time and space, and time-space tradeoffs for SAT; The hardness versus randomness paradigm; Average-case complexity; Fine-grained complexity; Current and new areas of complexity theory research. Prerequisite:
CS254.

Terms: Spr
| Units: 3

Instructors:
Tan, L. (PI)

## CS 255: Introduction to Cryptography

For advanced undergraduates and graduate students. Theory and practice of cryptographic techniques used in computer security. Topics: encryption (symmetric and public key), digital signatures, data integrity, authentication, key management, PKI, zero-knowledge protocols, and real-world applications. Prerequisite: basic probability theory.

Terms: Win
| Units: 3

Instructors:
Boneh, D. (PI)

## CS 257: Logic and Artificial Intelligence (PHIL 356C)

This is a course at the intersection of philosophical logic and artificial intelligence. After reviewing recent work in AI that has leveraged ideas from logic, we will slow down and study in more detail various components of high-level intelligence and the tools that have been designed to capture those components. Specific areas will include: reasoning about belief and action, causality and counterfactuals, legal and normative reasoning, natural language inference, and Turing-complete logical formalisms including (probabilistic) logic programming and lambda calculus. Our main concern will be understanding the logical tools themselves, including their formal properties and how they relate to other tools such as probability and statistics. At the end, students should expect to have learned a lot more about logic, and also to have a sense for how logic has been and can be used in AI applications. Prerequisites: A background in logic, at least at the level of
Phil 151, will be expected. I
more »

This is a course at the intersection of philosophical logic and artificial intelligence. After reviewing recent work in AI that has leveraged ideas from logic, we will slow down and study in more detail various components of high-level intelligence and the tools that have been designed to capture those components. Specific areas will include: reasoning about belief and action, causality and counterfactuals, legal and normative reasoning, natural language inference, and Turing-complete logical formalisms including (probabilistic) logic programming and lambda calculus. Our main concern will be understanding the logical tools themselves, including their formal properties and how they relate to other tools such as probability and statistics. At the end, students should expect to have learned a lot more about logic, and also to have a sense for how logic has been and can be used in AI applications. Prerequisites: A background in logic, at least at the level of
Phil 151, will be expected. In case a student is willing to put in the extra work to catch up, it may be possible to take the course with background equivalent to
Phil 150 or
CS 157. A background in AI, at the level of
CS 221, would also be very helpful and will at times be expected. 2 unit option only for PhD students past the second year. Course website:
http://web.stanford.edu/class/cs257/

Last offered: Winter 2018

## CS 259Q: Quantum Computing

The course introduces the basics of quantum algorithms, quantum computational complexity, quantum information theory, and quantum cryptography, including the models of quantum circuits and quantum Turing machines, Shor's factoring algorithms, Grover's search algorithm, the adiabatic algorithms, quantum error-correction, impossibility results for quantum algorithms, Bell's inequality, quantum information transmission, and quantum coin flipping. Prerequisites: knowledge of linear algebra, discrete probability and algorithms.

Last offered: Winter 2020

## CS 260: Geometry of Polynomials in Algorithm Design

Over the years, many powerful algorithms have been built via tools such as linear programming relaxations, spectral properties of graphs, and others, that all bridge the discrete and continuous worlds. This course will cover another such tool recently gaining popularity: polynomials, their roots, and their analytic properties, collectively known as geometry of polynomials. The course will cover fundamental properties of polynomials that are useful in designing algorithms, and then will showcase applications in several areas of algorithm design: combinatorial optimization, graph sparsification, high-dimensional expanders, analysis of random walks on combinatorial objects, and counting algorithms. Prerequisites: CS161 or equivalent. Basic knowledge of probability, linear algebra, and calculus.

Last offered: Winter 2020

## CS 261: Optimization and Algorithmic Paradigms

Algorithms for network optimization: max-flow, min-cost flow, matching, assignment, and min-cut problems. Introduction to linear programming. Use of LP duality for design and analysis of algorithms. Approximation algorithms for NP-complete problems such as Steiner Trees, Traveling Salesman, and scheduling problems. Randomized algorithms. Introduction to sub-linear algorithms and decision making under uncertainty. Prerequisite: 161 or equivalent.

Terms: Win
| Units: 3

Instructors:
Goel, A. (PI)

## CS 263: Counting and Sampling

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.

Terms: Aut
| Units: 3

Instructors:
Anari, N. (PI)
;
Vuong, J. (TA)

Filter Results: