• No products in the cart.

(

ratings

)

1

students

Created by:

Profile Photo

Last updated:

September 23, 2022

Duration:

Unlimited Duration

FREE

This course includes:

Unlimited Duration

Badge on Completion

Certificate of completion

Unlimited Duration

Description

This graduate-level course focuses on current research topics in computational complexity theory.

Topics include: Nondeterministic, alternating, probabilistic, and parallel computation models; Boolean circuits; Complexity classes and complete sets; The polynomial-time hierarchy; Interactive proof systems; Relativization; Definitions of randomness; Pseudo-randomness and derandomizations;Interactive proof systems and probabilistically checkable proofs.

Course Curriculum

  • PH Time-Space Tradeoffs Unlimited
  • Relativization Unlimited
  • Circuits and Karp-Lipton Unlimited
  • Unique-SAT, Parity-SAT, and Approximate Counting Unlimited
  • Toda’s Theorem Unlimited
  • AC0 Lower Bounds and Switching Lemma Unlimited
  • Razborov-Smolensky Unlimited
  • NEXP vs ACC0 (Addendum to Arora-Barak) Unlimited
  • Communication Complexity 1 Unlimited
  • Lower Bounds for Deterministic Communication Unlimited
  • Randomized Communication Unlimited
  • Intro to PCP Unlimited
  • Linearity Testing Unlimited
  • PCP with Polylogarithmic Queries and Sum Check Unlimited
  • Unique Games Conjecture and Hardness for MAX-2LIN Unlimited
  • P vs BPP 1 Unlimited
  • P vs BPP 2 Unlimited
  • Derandomization Implies Circuit Lower Bounds Unlimited

About the instructor

0

Instructor Rating

0

Reviews

1184

Courses

1478

Students

Profile Photo
Massachusetts Institute of Technology
Copyright © 2022 OpenCoursa, All Rights Reserved