default search action
Electronic Colloquium on Computational Complexity, 2004
Volume TR04, 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 E. 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-NC1 != Multilinear-NC2. - 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 Dvorák, 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 S. 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 NC1. - 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 HAMna. - Vikraman Arvind, Piyush P. Kurur, T. C. Vijayaraghavan:
Bounded Color Multiplicity Graph Isomorphism is in the #L Hierarchy.
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.
last updated on 2024-12-26 00:54 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: