Electronic Colloquium on Computational Complexity, Volume 9, 2002

Volume 9, 2002

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