2016-2017 2017-2018 2018-2019 2019-2020 2020-2021
Browse
by subject...
    Schedule
view...
 
  COVID-19 Scheduling Updates!
Due to recent announcements about Autumn Quarter (see the President's update), please expect ongoing changes to the class schedule.

1 - 2 of 2 results for: CS254

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)
Filter Results:
term offered
updating results...
teaching presence
updating results...
number of units
updating results...
time offered
updating results...
days
updating results...
UG Requirements (GERs)
updating results...
component
updating results...
career
updating results...
© Stanford University | Terms of Use | Copyright Complaints