- Troy Lee, Andrei E. Romashchenko:
On Polynomially Time Bounded Symmetry of Information. Electron. Colloquium Comput. Complex. TR04 (2004) - Ryan Williams:
A new algorithm for optimal constraint satisfaction and its implications. Electron. Colloquium Comput. Complex. TR04 (2004) - Michael Schmitt:
On the sample complexity of learning for networks of spiking neurons with nonlinear synaptic interactions. Electron. Colloquium Comput. Complex. TR04 (2004) - April Rasala Lehman, Eric Lehman:
Network Coding: Does the Model Need Tuning? Electron. Colloquium Comput. Complex. TR04 (2004) - Scott Contini, Ernie Croot, Igor E. Shparlinski:
Complexity of Inverting the Euler Function. Electron. Colloquium Comput. Complex. TR04 (2004) - Ziv Bar-Yossef, T. S. Jayram, Iordanis Kerenidis:
Exponential Separation of Quantum and Classical One-Way Communication Complexity. Electron. Colloquium Comput. Complex. TR04 (2004) - Elmar Böhler, Christian Glaßer, Bernhard Schwarz, Klaus W. Wagner:
Generation Problems. Electron. Colloquium Comput. Complex. TR04 (2004) - John Case, Sanjay Jain, Rüdiger Reischuk, Frank Stephan, Thomas Zeugmann:
A Polynomial Time Learner for a Subclass of Regular Patterns. Electron. Colloquium Comput. Complex. TR04 (2004) - Andrzej Lingas, Martin Wahlen:
On approximation of the maximum clique minor containment problem and some subgraph homeomorphism problems. Electron. Colloquium Comput. Complex. TR04 (2004) - Venkatesan Guruswami, Alexander Vardy:
Maximum-likelihood decoding of Reed-Solomon codes is NP-hard. Electron. Colloquium Comput. Complex. TR04 (2004) - Michael Alekhnovich, Edward A. Hirsch, Dmitry Itsykson:
Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas. Electron. Colloquium Comput. Complex. TR04 (2004) - Ran Raz:
Multilinear-NC1 != Multilinear-NC2. Electron. Colloquium Comput. Complex. TR04 (2004) - Luca Trevisan:
Some Applications of Coding Theory in Computational Complexity. Electron. Colloquium Comput. Complex. TR04 (2004) - Eric Allender, Harry Buhrman, Michal Koucký:
What Can be Efficiently Reduced to the Kolmogorov-Random Strings? Electron. Colloquium Comput. Complex. TR04 (2004) - Hartmut Klauck, Robert Spalek, Ronald de Wolf:
Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs. Electron. Colloquium Comput. Complex. TR04 (2004) - Eli Ben-Sasson, Madhu Sudan:
Robust Locally Testable Codes and Products of Codes. Electron. Colloquium Comput. Complex. TR04 (2004) - Xiaoyang Gu:
A note on dimensions of polynomial size circuits. Electron. Colloquium Comput. Complex. TR04 (2004) - André Lanka, Andreas Goerdt:
An approximation hardness result for bipartite Clique. Electron. Colloquium Comput. Complex. TR04 (2004) - Piotr Berman, Marek Karpinski, Yakov Nekrich:
Optimal Trade-Off for Merkle Tree Traversal. Electron. Colloquium Comput. Complex. TR04 (2004) - Michelle Effros, Leonard J. Schulman:
Deterministic clustering with data nets. Electron. Colloquium Comput. Complex. TR04 (2004) - Zdenek Dvorák, Daniel Král, Ondrej Pangrác:
Locally consistent constraint satisfaction problems. Electron. Colloquium Comput. Complex. TR04 (2004) - Michael Ben-Or, Don Coppersmith, Michael Luby, Ronitt Rubinfeld:
Non-Abelian Homomorphism Testing, and Distributions Close to their Self-Convolutions. Electron. Colloquium Comput. Complex. TR04 (2004) - Aduri Pavan, N. V. Vinodchandran:
Polylogarithmic Round Arthur-Merlin Games and Random-Self-Reducibility. Electron. Colloquium Comput. Complex. TR04 (2004) - Andrei A. Muchnik, Alexander Shen, Nikolai K. Vereshchagin, Michael V. Vyugin:
Non-reducible descriptions for conditional Kolmogorov complexity. Electron. Colloquium Comput. Complex. TR04 (2004) - Kousha Etessami, Andreas Lochbihler:
The computational complexity of Evolutionarily Stable Strategies. Electron. Colloquium Comput. Complex. TR04 (2004) - N. V. Vinodchandran:
A note on the circuit complexity of PP. Electron. Colloquium Comput. Complex. TR04 (2004) - Mónica del Pilar Canales Chacon, Michael Vielhaber:
Structural and Computational Complexity of Isometries and their Shift Commutators. Electron. Colloquium Comput. Complex. TR04 (2004) - John Case, Sanjay Jain, Eric Martin, Arun Sharma, Frank Stephan:
Identifying Clusters from Positive Data. Electron. Colloquium Comput. Complex. TR04 (2004) - Beatrice List, Markus Maucher, Uwe Schöning, Rainer Schuler:
Randomized Quicksort and the Entropy of the Random Number Generator. Electron. Colloquium Comput. Complex. TR04 (2004) - Eli Ben-Sasson, Madhu Sudan:
Simple PCPs with Poly-log Rate and Query Complexity. Electron. Colloquium Comput. Complex. TR04 (2004)