


default search action
Electronic Colloquium on Computational Complexity, 2002
Volume TR02, 2002
- Cynthia Dwork, Moni Naor:
Zaps and Their Applications. - Howard Barnum, Michael E. Saks:
A lower bound on the quantum query complexity of read-once functions. - Eli Ben-Sasson, Yonatan Bilu:
A Gap in Average Proof Complexity. - Till Tantau:
A Note on the Power of Extra Queries to Membership Comparable Sets. - Aduri Pavan, Alan L. Selman:
Bi-Immunity Separates Strong NP-Completeness Notions. - Philippe Moser:
Random nondeterministic real functions and Arthur Merlin games. - Pavel Pudlák:
Monotone complexity and the rank of matrices. - Valentine Kabanets:
Derandomization: A Brief Overview. - Petr Savický:
On determinism versus unambiquous nondeterminism for decision trees. - Albert Atserias, Maria Luisa Bonet:
On the Automatizability of Resolution and Related Propositional Proof Systems. - Boris Ryabko:
The nonprobabilistic approach to learning the best prediction. - Ran Raz:
On the Complexity of Matrix Product. - Chris Pollett, Farid M. Ablayev, Cristopher Moore:
Quantum and Stochastic Programs of Bounded Width. - Klaus Weihrauch:
Computational Complexity on Computable Metric Spaces. - Philippe Moser:
ZPP is hard unless RP is small. - Alina Beygelzimer, Mitsunori Ogihara:
On the Enumerability of the Determinant and the Rank. - Aggelos Kiayias, Moti Yung:
Cryptographic Hardness based on the Decoding of Reed-Solomon Codes with Applications. - Piotr Berman, Marek Karpinski, Yakov Nekrich
:
Approximating Huffman Codes in Parallel. - Nader H. Bshouty, Lynn Burroughs:
On the proper learning of axis parallel concepts. - Elizaveta A. Okol'nishnikova:
On one lower bound for branching programs. - Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk:
Space Efficient Algorithms for Directed Series-Parallel Graphs. - Wolfgang Maass, Henry Markram:
On the Computational Power of Recurrent Circuits of Spiking Neurons. - Josh Buresh-Oppenheim, Paul Beame, Toniann Pitassi, Ran Raz, Ashish Sabharwal:
Bounded-depth Frege lower bounds for weaker pigeonhole principles. - Piotr Indyk:
List-decoding in Linear Time. - Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon, Yuval Rabani:
Polynomial Time Approximation Schemes for Metric Min-Sum Clustering. - Boaz Barak, Yehuda Lindell:
Strict Polynomial-time in Simulation and Extraction. - Irit Dinur, Venkatesan Guruswami, Subhash Khot:
Vertex Cover on k-Uniform Hypergraphs is Hard to Approximate within Factor (k-3-epsilon). - Eric Allender, Harry Buhrman, Michal Koucký, Detlef Ronneburger, Dieter van Melkebeek:
Power from Random Strings. - Marek Karpinski, Yakov Nekrich
:
Parallel Construction of Minimum Redundancy Length-Limited Codes. - Lars Engebretsen, Jonas Holmerin, Alexander Russell:
Inapproximability Results for Equations over Finite Groups. - Vikraman Arvind, Venkatesh Raman:
Approximate Counting small subgraphs of bounded treewidth and related problems. - Andrei A. Bulatov:
Tractable Constraint Satisfaction Problems on a 3-element set. - Beate Bollig:
A very simple function that requires exponential size nondeterministic graph-driven read-once branching programs. - Andrei A. Bulatov:
Mal'tsev constraints are tractable. - Albert Atserias, Víctor Dalmau:
A Combinatorial Characterization of Resolution Width. - Stephen A. Fenner:
PP-lowness and a simple definition of AWPP. - Vikraman Arvind, Piyush P. Kurur:
Graph Isomorphism is in SPP. - Rahul Santhanam:
Resource Tradeoffs and Derandomization. - Oded Goldreich, Avi Wigderson:
Derandomization that is rarely wrong from short advice that is typically good. - Lars Engebretsen, Jonas Holmerin:
Three-Query PCPs with Perfect Completeness over non-Boolean Domains. - Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon:
A Polynomial Time Approximation Scheme for Metric MIN-BISECTION. - Dima Grigoriev:
Public-key cryptography and invariant theory. - Dalit Naor, Moni Naor, Jeffery Lotspiech:
Revocation and Tracing Schemes for Stateless Receivers. - Wenceslas Fernandez de la Vega, Marek Karpinski:
A Polynomial Time Approximation Scheme for Subdense MAX-CUT. - Daniele Micciancio, Erez Petrank:
Efficient and Concurrent Zero-Knowledge from any public coin HVZK protocol. - Marek Karpinski:
On Approximability of Minimum Bisection Problem. - Oded Goldreich:
The GGM Construction does NOT yield Correlation Intractable Function Ensembles. - Noga Alon, Oded Goldreich, Yishay Mansour:
Almost k-wise independence versus k-wise independence. - Oded Goldreich, Vered Rosen:
On the Security of Modular Exponentiation with Application to the Construction of Pseudorandom Generators. - Oded Goldreich, Madhu Sudan:
Locally Testable Codes and PCPs of Almost-Linear Length. - Chris Pollett:
Nepomnjascij's Theorem and Independence Proofs in Bounded Arithmetic. - Vince Grolmusz:
Computing Elementary Symmetric Polynomials with a Sub-Polynomial Number of Multiplications. - Lars Engebretsen, Venkatesan Guruswami:
Is Constraint Satisfaction Over Two Variables Always Easy? - Detlef Sieling:
Minimization of Decision Trees is Hard to Approximate. - Valentine Kabanets, Russell Impagliazzo:
Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds. - Todd Ebert, Wolfgang Merkle, Heribert Vollmer:
On the Autoreducibility of Random Sequences. - Richard J. Lipton, Anastasios Viglas:
Non-uniform Depth of Polynomial Time and Space Simulations. - Philippe Moser:
A generalization of Lutz's measure to probabilistic classes. - Iordanis Kerenidis, Ronald de Wolf:
Exponential Lower Bound for 2-Query Locally Decodable Codes. - Ke Yang:
New Lower Bounds for Statistical Query Learning. - Miklós Ajtai:
A conjectured 0-1 law about the polynomial time computable properties of random lattices, I. - Andrew Chi-Chih Yao:
Classical Physics and the Church-Turing Thesis. - Oded Goldreich:
Zero-Knowledge twenty years after its invention. - Andrej Bogdanov, Luca Trevisan:
Lower Bounds for Testing Bipartiteness in Dense Graphs. - Olivier Powell:
Measure on P revisited. - Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, V. Vinay:
Circuits on Cylinders. - Marco Cadoli, Francesco M. Donini, Paolo Liberatore, Marco Schaerf:
k-Approximating Circuits. - Tobias Riege, Jörg Rothe:
Complexity of the Exact Domatic Number Problem and of the Exact Conveyor Flow Shop Problem. - Luca Trevisan:
A Note on Deterministic Approximate Counting for k-DNF. - Wenceslas Fernandez de la Vega, Marek Karpinski:
9/8-Approximation Algorithm for Random MAX-3SAT. - Bruno Codenotti, Igor E. Shparlinski:
Non-approximability of the Permanent of Structured Matrices over Finite Fields. - Scott Aaronson:
Quantum Lower Bound for Recursive Fourier Sampling. - Janka Chlebíková, Miroslav Chlebík:
Approximation Hardness for Small Occurrence Instances of NP-Hard Problem. - Andrew Chi-Chih Yao:
On the Power of Quantum Fingerprinting.

manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.