dblp.uni-trier.de www.uni-trier.de

Electronic Colloquium on Computational Complexity, Volume 11, 2004

Volume 11, 2004

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

Home | Conferences | Journals | Series | FAQ — Search: Faceted | Complete | Author
Copyright © Sat May 16 23:57:49 2009 by Michael Ley (ley@uni-trier.de)