User:Tcshasaposse/topics: List of topics

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)