Electronic Colloquium on Computational Complexity, Volume 9, 2002

Volume 9, 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 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.
  

Last update Sat May 18 20:22:59 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page