| article
|
contributor
|
discussion
|
| property testing |
Andrej Bogdanov |
rewrote (3/2/09)
|
| quantum computation
|
| algorithmic game theory
|
| derandomization |
|
something in article on randomized algorithms
|
| sketching algorithm
|
| propositional proof complexity |
|
include sth in proof complexity?
|
| arithmetic circuit complexity |
Amir Yehudayoff |
rewrote (4/2/09)
|
| discrete harmonic analysis
|
| streaming algorithms
|
| exact learning
|
| algorithmic mechanism design |
|
link from mechanism design
|
| circuit complexity
|
| online algorithm
|
| PAC learning
|
| pseudorandomness |
Andrej Bogdanov |
rewrote section on pseudorandomness in complexity theory” (3/2/09)
|
| sparsest cut |
Lorenzo Orecchia |
|
| metric embedding |
|
create link from embedding
|
| price of anarchy
|
| combinatorial auction
|
| glauber dynamics
|
| locally testable code |
Andrej Bogdanov |
needs to be expanded (3/3/09)
|
| locally decodable code
|
| average case complexity
|
| worst case complexity |
Chin Ho Lee |
rewrote(26/5/09)
|
| polynomial identity testing
|
| unique games conjecture |
Andrej Bogdanov |
rewrote article (3/3/09)
|
| primal-dual algorithm
|
| smoothed analysis
|
| complexity class
|
| RP (complexity)
|
| computational problem |
Andrej Bogdanov |
rewrote (3/2/09)
|
| conductance (probability) |
Allan Sly |
|
| probabilistically checkable proof |
Andrej Bogdanov |
rewrote (3/3/09)
|
| PCP theorem |
Andrej Bogdanov |
rewrote (3/2/09)
|
| polynomial time hierarchy
|
| algorithms for matrix multiplication
|
| max-flow min-cut |
Chin Ho Lee |
rewrote (14/6/09)
|
| zero knowledge proof
|
| model of computation
|
| list-decoding
|
| dynamic programming
|
| randomness extractor
|
| one way permutation |
|
incorporate in one way function?
|
| selection/median finding |
|
poorly written
|
| pseudorandom generator |
Andrej Bogdanov |
rewrote (3/4/09)
|
| parallel repetition
|
| hardness amplification
|
| long code (mathematics) |
Andrej Bogdanov |
stub (4/10/09)
|
| tower function |
|
this is math, but not there...
|
| sublinear time algorithm
|
| hardness of approximation
|
| pseudorandom generator theorem |
|
someone remove this, please!
|
| epsilon-biased sample spaces |
|
merge with pseudorandom generator?
|
| pseudorandom generators for polynomials |
|
remove or merge with pseudorandom generator?
|
| linear and semidefinite programming hierarchies
|
| hypercontractivity
|
| coin flipping |
|
"coin flipping in telecommunications" part misleading
|
| Cut (graph theory) |
Chin Ho Lee |
rewrote intro and definition (1/6/09)
|
| Maximum flow problem |
Chin Ho Lee |
added definition and application (10/7/09)
|
| Dinic's algorithm |
Chin Ho Lee |
added (17/7/09)
|
| Gomory–Hu tree |
Chin Ho Lee |
added (24/8/09)
|
