18.405J / 6.841J Advanced Complexity Theory, Fall 2001

18.405J / 6.841J Advanced Complexity Theory, Fall 2001

The topics for this course cover various aspects of complexity theory, such as  the basic time and space classes, the polynomial-time hierarchy and the randomized classes . This is a pure theory class, so no applications were involved.

Bibliographic Details
Main Author: Spielman, Daniel
Other Authors: Massachusetts Institute of Technology. Department of Mathematics
Format: Learning Object
Language:en-US
Published: 2001
Subjects:
Basic time and space classes
polynomial-time hierarchy
Randomized classes: RP, BPP, RL, and their relation to PH
Counting classes: #P
Non-uniform classes
Oracles, relativization
Interactive proof systems
Pseudo-random generators
randomness
Some circuit lower bounds > monotone and AC0.
oracles
relativization
randomized classes
RP
BPP
RL
PH
circuit lower bonds
monotone
AC0
basic time classes
basic space classes
18.405J
6.841J
18.405
6.841
Online Access:http://hdl.handle.net/1721.1/106671

Internet

http://hdl.handle.net/1721.1/106671

Similar Items