ECCC BOOKS, LECTURES AND SURVEYS > SURVEY PAPERS:
- TR07-099 | Dieter van Melkebeek:
A Survey of Lower Bounds for Satisfiability and Related Problems
- TR07-091 | Martin Grohe:
Logic, Graphs, and Algorithms
- TR07-004 | Lance Fortnow, Rahul Santhanam:
Time Hierarchies: A Survey
- TR06-145 | Jin-Yi Cai, Pinyan Lu:
Holographic Algorithms: From Art to Science
- TR06-123 | Venkatesan Guruswami:
Iterative Decoding of Low-Density Parity Check Codes (A Survey)
- TR05-146 | Gábor Erdèlyi, Tobias Riege, Jörg Rothe:
Quantum Cryptography: A Survey
- TR05-098 | Oded Goldreich:
Bravely, Moderately: A Common Theme in Four Recent Results
- TR05-072 | Christian Glasser, Alan L. Selman, Liyu Zhang:
Survey of Disjoint NP-Pairs and Relations to Propositional Proof Systems
- TR05-026 | Scott Aaronson:
NP-complete Problems and Physical Reality
- TR05-018 | Oded Goldreich:
On Promise Problems (a survey in memory of Shimon Even [1935-2004])
- TR05-014 | Oded Goldreich:
Short Locally Testable Codes and Proofs (Survey)
- TR02-063 | Oded Goldreich:
Zero-Knowledge twenty years after its invention
- TR02-046 | Marek Karpinski:
On Approximability of Minimum Bisection Problem
- TR01-042 | Marek Karpinski:
Approximating Bounded Degree Instances of NP-Hard Problems
- TR01-014 | Marcos Kiwi, Frederic Magniez, Miklos Santha:
Exact and Approximate Testing/Correcting of Algebraic Functions: A Survey
- TR99-020 | Marek Karpinski:
Randomized Complexity of Linear Arrangements and Polyhedra
- TR99-006 | Jin-Yi Cai:
Some Recent Progress on the Complexity of Lattice Problems
- TR98-067 | Paul Beame and Toniann Pitassi:
Propositional Proof Complexity: Past, Present and Future
- TR98-039 | Christoph Meinel and Thorsten Theobald:
Ordered Binary Decision Diagrams and Their Significance in Computer-Aided Design of VLSI Circuits - a Survey
- TR98-038 | Marek Karpinski:
On the Computational Power of Randomized Branching Programs
- TR97-058 | Oded Goldreich:
Notes on Levin's Theory of Average-Case Complexity
- TR97-056 | Oded Goldreich:
Combinatorial Property Testing (a survey)
- TR97-024 | Marek Karpinski:
Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems
- TR97-020 | Oded Goldreich:
A Sample of Samplers -- A Computational Perspective on Sampling (survey)
- TR95-056 | Oded Goldreich:
Three XOR-Lemmas -- An Exposition
- TR95-050 | Oded Goldreich, Noam Nisan and Avi Wigderson:
On Yao's XOR-Lemma
- TR94-008 | Oded Goldreich:
Probabilistic Proof Systems (A Survey)