ECCC - ECCC Books, Lectures and Surveys

ECCC

Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login

Register

Classic Style

ECCC BOOKS, LECTURES AND SURVEYS > SURVEY PAPERS:

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