Electronic Colloquium on Computational Complexity, Volume 11, 2004

Volume 11, 2004

Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans:
On the complexity of succinct zero-sum games.
Troy Lee, Dieter van Melkebeek, Harry Buhrman:
Language Compression and Pseudorandom Generators.
Pascal Koiran:
Valiant's model and the cost of computing integers.
Ramamohan Paturi, Pavel Pudlák:
Circuit lower bounds and linear codes.
Stasys Jukna:
On Graph Complexity.
Günter Hotz:
A remark on nondecidabilities of the initial value problem of ODEs.
Alan L. Selman, Samik Sengupta:
Polylogarithmic-round Interactive Proofs for coNP Collapses the Exponential Hierarchy.
Vikraman Arvind, Jacobo Torán:
Solvable Group Isomorphism is (almost) in NP\cap coNP.
Martin E. Dyer, Alan M. Frieze, Thomas P. Hayes, Eric Vigoda:
Randomly coloring constant degree graphs.
Michal Parnas, Dana Ron, Ronitt Rubinfeld:
Tolerant Property Testing and Distance Approximation.
Christian Glaßer:
Counting with Counterfree Automata.
Paul Beame, Joseph C. Culberson, David G. Mitchell, Cristopher Moore:
The Resolution Complexity of Random Graph k-Colorability.
Oded Goldreich, Dana Ron:
On Estimating the Average Degree of a Graph.
Chris Pollett:
Languages to diagonalize against advice classes.
Richard Beigel, Harry Buhrman, Peter A. Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrei A. Muchnik, Frank Stephan, Leen Torenvliet:
Enumerations of the Kolmogorov Function.
Michael Alekhnovich, Eli Ben-Sasson:
Linear Upper Bounds for Random Walk on Small Density Random 3CNFs.
Evgeny Dantsin, Alexander Wolpert:
Derandomization of Schuler's Algorithm for SAT.
Jan Krajícek:
Diagonalization in proof complexity.
Christian Glaßer, Aduri Pavan, Alan L. Selman, Samik Sengupta:
Properties of NP-Complete Sets.
Emanuele Viola:
The Complexity of Constructing Pseudorandom Generators from Hard Functions.
Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil P. Vadhan:
Robust PCPs of Proximity, Shorter PCPs and Applications to Coding.
Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton:
The Degree of Threshold Mod 6 and Diophantine Equations.
Yaoyun Shi:
Quantum and Classical Tradeoffs.
Thomas Thierauf, Thanh Minh Hoang:
On Closure Properties of GapL.
John M. Hitchcock, Aduri Pavan, Pramodchandran N. Variyam:
Partial Bi-Immunity and NP-Completeness.
Scott Aaronson:
Limitations of Quantum Advice and One-Way Communication.
Henning Fernau:
Parametric Duality: Kernel Sizes and Algorithmics.
Arfst Nickelsen, Till Tantau, Lorenz Weizsäcker:
Aggregates with Component Size One Characterize Polynomial Space.
John M. Hitchcock, María López-Valdés, Elvira Mayordomo:
Scaled dimension and the Kolmogorov complexity of Turing hard sets.
Nikolai K. Vereshchagin:
Kolmogorov complexity of enumerating finite sets.
Troy Lee, Andrei E. Romashchenko:
On Polynomially Time Bounded Symmetry of Information.
Ryan Williams:
A new algorithm for optimal constraint satisfaction and its implications.
Michael Schmitt:
On the sample complexity of learning for networks of spiking neurons with nonlinear synaptic interactions.
April Rasala Lehman, Eric Lehman:
Network Coding: Does the Model Need Tuning?
Scott Contini, Ernie Croot, Igor Shparlinski:
Complexity of Inverting the Euler Function.
Ziv Bar-Yossef, T. S. Jayram, Iordanis Kerenidis:
Exponential Separation of Quantum and Classical One-Way Communication Complexity.
Elmar Böhler, Christian Glaßer, Bernhard Schwarz, Klaus W. Wagner:
Generation Problems.
John Case, Sanjay Jain, Rüdiger Reischuk, Frank Stephan, Thomas Zeugmann:
A Polynomial Time Learner for a Subclass of Regular Patterns.
Andrzej Lingas, Martin Wahlen:
On approximation of the maximum clique minor containment problem and some subgraph homeomorphism problems.
Venkatesan Guruswami, Alexander Vardy:
Maximum-likelihood decoding of Reed-Solomon codes is NP-hard.
Michael Alekhnovich, Edward A. Hirsch, Dmitry Itsykson:
Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas.
Ran Raz:
Multilinear-NC₁ != Multilinear-NC₂.
Luca Trevisan:
Some Applications of Coding Theory in Computational Complexity.
Eric Allender, Harry Buhrman, Michal Koucký:
What Can be Efficiently Reduced to the Kolmogorov-Random Strings?
Hartmut Klauck, Robert Spalek, Ronald de Wolf:
Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs.
Eli Ben-Sasson, Madhu Sudan:
Robust Locally Testable Codes and Products of Codes.
Xiaoyang Gu:
A note on dimensions of polynomial size circuits.
André Lanka, Andreas Goerdt:
An approximation hardness result for bipartite Clique.
Piotr Berman, Marek Karpinski, Yakov Nekrich:
Optimal Trade-Off for Merkle Tree Traversal.
Michelle Effros, Leonard J. Schulman:
Deterministic clustering with data nets.
Zdenek Dvorak, Daniel Král, Ondrej Pangrác:
Locally consistent constraint satisfaction problems.
Michael Ben-Or, Don Coppersmith, Michael Luby, Ronitt Rubinfeld:
Non-Abelian Homomorphism Testing, and Distributions Close to their Self-Convolutions.
Aduri Pavan, N. V. Vinodchandran:
Polylogarithmic Round Arthur-Merlin Games and Random-Self-Reducibility.
Andrei A. Muchnik, Alexander Shen, Nikolai K. Vereshchagin, Michael V. Vyugin:
Non-reducible descriptions for conditional Kolmogorov complexity.
Kousha Etessami, Andreas Lochbihler:
The computational complexity of Evolutionarily Stable Strategies.
N. V. Vinodchandran:
A note on the circuit complexity of PP.
Mónica del Pilar Canales Chacon, Michael Vielhaber:
Structural and Computational Complexity of Isometries and their Shift Commutators.
John Case, Sanjay Jain, Eric Martin, Arun Sharma, Frank Stephan:
Identifying Clusters from Positive Data.
Beatrice List, Markus Maucher, Uwe Schöning, Rainer Schuler:
Randomized Quicksort and the Entropy of the Random Number Generator.
Eli Ben-Sasson, Madhu Sudan:
Simple PCPs with Poly-log Rate and Query Complexity.
Scott Aaronson:
The Complexity of Agreement.
Stasys Jukna:
A note on the P versus NP intersected with co-NP question in communication complexity.
Yehuda Lindell, Benny Pinkas:
A Proof of Yao's Protocol for Secure Two-Party Computation.
Piotr Faliszewski:
Exponential time reductions and sparse languages in NEXP.
Luca Trevisan:
Inapproximability of Combinatorial Optimization Problems.
Tomoyuki Yamakami, Toshio Suzuki:
Resource Bounded Immunity and Simplicity.
Hadi Salmasian, Ravindran Kannan, Santosh Vempala:
The Spectral Method for Mixture Models.
Nir Ailon, Bernard Chazelle:
Information Theory in Property Testing and Monotonicity Testing in Higher Dimension.
Eran Rom, Amnon Ta-Shma:
Improveing the alphabet size in high noise, almost optimal rate list decodable codes.
Leonid Gurvits:
Combinatorial and algorithmic aspects of hyperbolic polynomials.
Marcus Schaefer, Stephen A. Fenner:
Simplicity and Strong Reductions.
John M. Hitchcock:
Hausdorff Dimension and Oracle Constructions.
Henning Fernau:
A Top-Down Approach to Search-Trees: Improved Algorithmics for 3-Hitting Set.
Emanuele Viola:
On Parallel Pseudorandom Generators.
Michael Schmitt:
Some dichotomy theorems for neural learning problems.
Oliver Giel, Ingo Wegener:
Searching Randomly for Maximum Matchings.
Alina Beygelzimer, Varsha Dani, Thomas P. Hayes, John Langford:
Reductions Between Classification Tasks.
Henning Fernau:
Two-Layer Planarization: Improving on Parameterized Algorithmics.
John M. Hitchcock, Jack H. Lutz, Sebastiaan Terwijn:
The Arithmetical Complexity of Dimension and Randomness.
Lance Fortnow, Troy Lee, Nikolai K. Vereshchagin:
Kolmogorov Complexity with Error.
Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin:
Increasing Kolmogorov Complexity.
Olaf Beyersdorff:
Representable Disjoint NP-Pairs.
Boaz Barak, Yehuda Lindell, Salil P. Vadhan:
Lower Bounds for Non-Black-Box Zero Knowledge.
George Karakostas:
A better approximation ratio for the Vertex Cover problem.
Erez Petrank, Guy N. Rothblum:
Selection from Structured Data Sets.
Ronen Shaltiel, Christopher Umans:
Pseudorandomness for Approximate Counting and Sampling.
Alexander Healy, Salil P. Vadhan, Emanuele Viola:
Using Nondeterminism to Amplify Hardness.
Emanuele Viola, Dan Gutfreund:
Fooling Parity Tests with Parity Gates.
Ingo Wegener:
Simulated Annealing Beats Metropolis in Combinatorial Optimization.
Kazuyuki Amano, Akira Maruoka:
Better Simulation of Exponential Threshold Weights by Polynomial Weights.
Ondrej Klíma, Pascal Tesson, Denis Thérien:
Dichotomies in the Complexity of Solving Systems of Equations over Finite Semigroups.
Oded Lachish, Ilan Newman:
Testing Periodicity.
Oded Goldreich, Madhu Sudan, Luca Trevisan:
From logarithmic advice to single-bit advice.
Omer Reingold:
Undirected ST-Connectivity in Log-Space.
Daniele Micciancio:
Generalized compact knapsacks, cyclic lattices, and efficient one-way functions from worst-case complexity assumptions.
Eldar Fischer, Frédéric Magniez, Michel de Rougemont:
Property and Equivalence Testing on Strings.
Víctor Dalmau:
Malt'sev Constraints made Simple.
Lance Fortnow, Rahul Santhanam, Luca Trevisan:
Promise Hierarchies.
Ran Raz:
Extractors with Weak Random Seeds.
Eric Allender, Michael Bauland, Neil Immerman, Henning Schnoor, Heribert Vollmer:
The Complexity of Satisfiability Problems: Refining Schaefer's Theorem.
Miroslav Chlebík, Janka Chlebíková:
Crown reductions for the Minimum Weighted Vertex Cover problem.
Thomas Holenstein:
Key Agreement from Weak Bit Agreement.
Lance Fortnow, Adam R. Klivans:
NP with Small Advice.
María López-Valdés, Elvira Mayordomo:
Dimension is compression.
Eldar Fischer, Lance Fortnow:
Tolerant Versus Intolerant Testing for Boolean Properties.
Christian Glaßer, Alan L. Selman, Liyu Zhang:
Canonical Disjoint NP-Pairs of Propositional Proof Systems.
Ingo Wegener, Philipp Woelfel:
New Results on the Complexity of the Middle Bit of Multiplication.
Eric Allender, Samir Datta, Sambuddha Roy:
Topology inside NC¹.
Neeraj Kayal, Nitin Saxena:
On the Ring Isomorphism & Automorphism Problems.
Tomoyuki Yamakami, Harumichi Nishimura:
An Application of Quantum Finite Automata to Interactive Proof Systems.
Piotr Berman, Marek Karpinski, Alexander D. Scott:
Computational Complexity of Some Restricted Instances of 3SAT.
Nicola Galesi, Neil Thapen:
Resolution and pebbling games.
Mårten Trolin:
Lattices with Many Cycles Are Dense.
Vladimir Trifonov:
An O(log n log log n) Space Algorithm for Undirected s,t-Connectivity.
Iftach Haitner, Ronen Shaltiel:
Statistical Zero-Knowledge Arguments for NP Using Approximable-Preimage-Size One-Way Functions.
Ludovic Perret:
On the computational complexity of some equivalence problems of polynomial systems of equations over finite fields.
Mikhail Alecknovich, Sanjeev Arora, Iannis Tourlakis:
Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy.
Marek Karpinski, Yakov Nekrich:
A Note on Traversing Skew Merkle Trees.
Uriel Feige, Daniel Reichman:
On The Hardness of Approximating Max-Satisfy.
Andris Ambainis, William I. Gasarch, Aravind Srinivasan, Andrey Utis:
Lower bounds on the Deterministic and Quantum Communication Complexity of HAM_n^a.
Vikraman Arvind, Piyush P. Kurur, T. C. Vijayaraghavan:
Bounded Color Multiplicity Graph Isomorphism is in the #L Hierarchy.