Under the auspices of the
Computational Complexity Foundation (CCF)
2026
2025
2024
2026...1994
Call for Papers
How to use
Scientific Board
Local Office
Copyright Notice
History
ECCC BOOKS, LECTURES AND SURVEYS > SURVEY PAPERS:
TR26-259 | Avi Wigderson :
Michael Rabin's fingerprints across the theory of computation
TR26-249 | Halley Goldberg, Mikito Nanashima, Igor Oliveira :
Learning, Compression, and Meta-Complexity
TR26-197 | Oded Goldreich :
Testing Bipartite in the Bounded-Degree Graph Model, Revisited (A digest of the paper of Fei and Rubinfeld (2026))
TR26-088 | Oded Goldreich :
A digest of the work of Rothblum, Vadhan, and Wigderson (2013)
TR26-045 | Edward Pyne, Roei Tell :
Using Hardness vs Randomness to Design Low-Space Algorithms
TR26-032 | Mrinal Kumar, Noga Ron-Zewi :
Advances in List Decoding of Polynomial Codes
TR25-207 | Madhu Sudan :
Algebra in Algorithmic Coding Theory
TR25-086 | Jiatu Li :
An Introduction to Feasible Mathematics and Bounded Arithmetic for Computer Scientists
TR25-083 | C.S. Bhargav, Prateek Dwivedi, Nitin Saxena :
A primer on the closure of algebraic complexity classes under factoring
TR25-041 | Igor Carboni Oliveira :
Meta-Mathematics of Computational Complexity Theory
TR25-015 | Abhibhav Garg, Prahladh Harsha, Mrinal Kumar, Ramprasad Saptharishi, Ashutosh Shankar :
An exposition of recent list-size bounds of FRS Codes
TR24-159 | Dean Doron :
Binary Codes with Distance Close to Half
TR24-109 | Oded Goldreich :
On the Cook-Mertz Tree Evaluation procedure
TR24-078 | Oded Goldreich :
On the relaxed LDC of BGHSV: A survey that corrects the record
TR24-013 | Oded Goldreich :
On locally-characterized expander graphs (a survey)
TR24-012 | Hamed Hatami, Pooya Hatami :
Structure in Communication Complexity and Constant-Cost Complexity Classes
TR23-200 | Joseph Shunia :
An Efficient Deterministic Primality Test
TR23-179 | Ian Mertz :
Reusing Space: Techniques and Open Problems
TR23-158 | Oded Goldreich :
On coarse and fine approximate counting of $t$-cliques
TR23-094 | Lijie Chen, Roei Tell :
New ways of studying the BPP = P conjecture
TR23-034 | Oded Goldreich :
On teaching the approximation method for circuit lower bounds
TR23-019 | Pooya Hatami, William Hoza :
Theory of Unconditional Pseudorandom Generators
TR22-170 | Huck Bennett :
The Complexity of the Shortest Vector Problem
TR22-142 | Emanuele Viola :
Correlation bounds against polynomials
TR22-126 | Andrei Krokhin, Jakub Opršal :
An Invitation to the Promise Constraint Satisfaction Problem
TR22-121 | William Hoza :
Recent Progress on Derandomizing Space-Bounded Computation
TR22-081 | Zhenjian Lu, Igor Oliveira :
Theory and Applications of Probabilistic Kolmogorov Complexity
TR22-065 | Madhu Sudan :
Streaming and Sketching Complexity of CSPs: A survey
TR22-005 | Anup Rao :
Sunflowers: from soil to oil
TR21-181 | Oded Goldreich :
The KW Games as a Teaser
TR21-175 | Oded Goldreich :
On the Locally Testable Code of Dinur et al. (2021)
TR21-120 | Roei Tell :
How to Find Water in the Ocean: A Survey on Quantified Derandomization
TR21-088 | Oded Goldreich :
Open Problems in Property Testing of Graphs
TR21-065 | Nikhil Mande, Swagato Sanyal :
One-way communication complexity and non-adaptive decision trees
TR21-061 | Noah Fleming, Toniann Pitassi :
Reflections on Proof Complexity and Counting Principles
TR20-115 | Scott Aaronson :
The Busy Beaver Frontier
TR20-086 | Andreas Feldmann, Karthik C. S., Euiwoong Lee, Pasin Manurangsi :
A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
TR20-078 | Eric Allender :
The New Complexity Landscape around Circuit Minimization
TR19-106 | Noah Fleming, Pravesh Kothari, Toniann Pitassi :
Semialgebraic Proofs and Efficient Algorithm Design
TR19-086 | Alex Bredariol Grilo, William Slofstra, Henry Yuen :
Perfect zero knowledge for quantum multiprover interactive proofs
TR18-166 | Tayfun Pay, James Cox :
An overview of some semantic and syntactic complexity classes
TR18-151 | Ankit Garg, Rafael Oliveira :
Recent progress on scaling algorithms and applications
TR18-125 | Zvika Brakerski :
Fundamentals of Fully Homomorphic Encryption – A Survey
TR18-072 | Avi Wigderson :
On the nature of the Theory of Computation (ToC)
TR18-001 | Tim Roughgarden :
Complexity Theory, Game Theory, and Economics
TR17-126 | Swastik Kopparty, Shubhangi Saraf :
Local Testing and Decoding of High-Rate Error-Correcting Codes
TR17-113 | Andrej Bogdanov, Alon Rosen :
Pseudorandom Functions: Three Decades Later
TR17-102 | Oded Goldreich :
Overview of the doubly-efficient interactive proof systems of RRR
TR17-101 | Oded Goldreich :
On the doubly-efficient interactive proof systems of GKR
TR17-084 | Iftach Haitner, Salil Vadhan :
The Many Entropies in One-Way Functions
TR17-067 | Benny Applebaum :
Garbled Circuits as Randomized Encodings of Functions: a Primer
TR17-065 | Boaz Barak :
The Complexity of Public-Key Cryptograph
TR17-004 | Scott Aaronson :
P=?NP
TR17-001 | Stephen Cook, Bruce Kapron :
A Survey of Classes of Primitive Recursive Functions
TR16-109 | Scott Aaronson :
The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes
TR16-101 | Toniann Pitassi, Iddo Tzameret :
Algebraic Proof Complexity: Progress, Frontiers and Challenges
TR16-034 | Mohamed El Halaby :
On the Computational Complexity of MaxSAT
TR15-156 | Tim Roughgarden :
Communication Complexity (for Algorithm Designers)
TR15-153 | Tim Roughgarden :
Computing Equilibria: A Computational Complexity Perspective
TR15-097 | Marek Karpinski :
Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies
TR15-063 | Clement Canonne :
A Survey on Distribution Testing: Your Data is Big. But is it Blue?
TR15-060 | Omri Weinstein :
Information Complexity and the Quest for Interactive Compression
TR15-048 | Kamil Khadiev :
Width Hierarchy for $k$-OBDD of Small Width
TR15-027 | Benny Applebaum :
Cryptographic Hardness of Random Local Functions -- Survey
TR14-143 | Ronald de Haan, Stefan Szeider :
Compendium of Parameterized Problems at Higher Levels of the Polynomial Hierarchy
TR14-106 | Craig Gentry :
Computing on the edge of chaos: Structure and randomness in encrypted computation
TR14-059 | Boaz Barak, David Steurer :
Sum-of-squares proofs and the quest toward optimal algorithms
TR14-041 | Shachar Lovett :
Recent advances on the log-rank conjecture in communication complexity
TR14-008 | N. V. Vinodchandran :
Space Complexity of the Directed Reachability Problem over Surface-Embedded Graphs.
TR13-186 | Nitin Saxena :
Progress on Polynomial Identity Testing - II
TR13-182 | Boaz Barak :
Structure vs Combinatorics in Computational Complexity
TR13-166 | Arnab Bhattacharyya :
On testing affine-invariant properties
TR13-165 | Michael Walfish, Andrew Blumberg :
Verifying computations without reexecuting them: from theoretical possibility to near-practicality
TR13-119 | Emanuele Viola :
Challenges in computational lower bounds
TR13-117 | Igor Oliveira :
Algorithms versus Circuit Lower Bounds
TR13-087 | Hamed Hatami, Shachar Lovett :
Estimating the distance from testable affine-invariant properties
TR13-017 | Pratik Worah :
A Short Excursion into Semi-Algebraic Hierarchies
TR12-120 | Boaz Barak :
Proof vs. Truth in Computational Complexity
TR12-084 | Rahul Santhanam :
Ironic Complicity: Satisfiability Algorithms and Circuit Lower Bounds
TR12-009 | Prabhu Manyem, Julien Ugon :
Computational Complexity, NP Completeness and Optimization Duality: A Survey
TR11-159 | Oded Goldreich, Ron Rothblum :
Enhancements of Trapdoor Permutations
TR11-108 | Scott Aaronson :
Why Philosophers Should Care About Computational Complexity
TR11-093 | Pinyan Lu :
Complexity Dichotomies of Counting Problems
TR11-004 | Oded Goldreich, Salil Vadhan :
On the complexity of computational problems regarding distributions (a survey)
TR10-082 | Oded Goldreich :
Introduction to Testing Graph Properties
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, 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 Glaßer, 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 :
Propositional Proof Complexity: Past, Present and Future
TR98-039 | Christoph Meinel, 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, Avi Wigderson :
On Yao's XOR-Lemma
TR94-008 | Oded Goldreich :
Probabilistic Proof Systems (A Survey)
ISSN 1433-8092 |
Imprint