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

Copyright © Mon Nov 2 21:34:17 2009 by Michael Ley (ley@uni-trier.de)