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

Electronic Colloquium on Computational Complexity, Volume 5, 1998

Volume 5, 1998

  1. Detlef Sieling:
    On the Existence of Polynomial Time Approximation Schemes for OBDD Minimization.
    Electronic Edition (link) BibTeX
  2. Jayram S. Thathachar:
    On Separating the Read-k-Times Branching Program Hierarchy.
    Electronic Edition (link) BibTeX
  3. Ibrahim Cahit, M. Tezer:
    Irregular Assignments of the Forest of Paths.
    Electronic Edition (link) BibTeX
  4. Farid M. Ablayev, Marek Karpinski:
    On the Power of Randomized Ordered Branching Programs.
    Electronic Edition (link) BibTeX
  5. Jin-yi Cai:
    A new transference theorem and applications to Ajtai's connection factor.
    Electronic Edition (link) BibTeX
  6. Alfredo De Santis, Giovanni Di Crescenzo, Oded Goldreich, Giuseppe Persiano:
    The Graph Clustering Problem has a Perfect Zero-Knowledge Proof.
    Electronic Edition (link) BibTeX
  7. Luca Trevisan:
    Recycling Queries in PCPs and in Linearity Tests.
    Electronic Edition (link) BibTeX
  8. Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy:
    Proof verification and the hardness of approximation problems.
    Electronic Edition (link) BibTeX
  9. Bruce E. Litow:
    Parallel complexity of integer coprimality.
    Electronic Edition (link) BibTeX
  10. Phong Q. Nguyen, Jacques Stern:
    A Converse to the Ajtai-Dwork Security Proof and its Cryptographic Implications.
    Electronic Edition (link) BibTeX
  11. Farid M. Ablayev, Marek Karpinski:
    A Lower Bound for Integer Multiplication on Randomized Read-Once Branching Programs .
    Electronic Edition (link) BibTeX
  12. Meena Mahajan, V. Vinay:
    Determinant: Old Algorithms, New Insights.
    Electronic Edition (link) BibTeX
  13. Nader H. Bshouty:
    A New Composition Theorem for Learning Algorithms.
    Electronic Edition (link) BibTeX
  14. Gunter Blache, Marek Karpinski, Juergen Wirtgen:
    On Approximation Intractability of the Bandwidth Problem.
    Electronic Edition (link) BibTeX
  15. Valentin E. Brimkov, Stefan S. Dantchev:
    Lower Bounds, "Pseudopolynomial" and Approximation Algorithms for the Knapsack Problem with Real Coefficients.
    Electronic Edition (link) BibTeX
  16. Daniele Micciancio:
    The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant.
    Electronic Edition (link) BibTeX
  17. Oded Goldreich, Madhu Sudan:
    Computational Indistinguishability: A Sample Hierarchy.
    Electronic Edition (link) BibTeX
  18. Martin Sauerhoff:
    Randomness and Nondeterminism are Incomparable for Read-Once Branching Programs.
    Electronic Edition (link) BibTeX
  19. Eric Allender, Klaus Reinhardt:
    Isolation, Matching, and Counting.
    Electronic Edition (link) BibTeX
  20. Andris Ambainis, David A. Mix Barrington, Huong LeThanh:
    On Counting AC0 Circuits with Negative Constants.
    Electronic Edition (link) BibTeX
  21. Shai Ben-David, Anna Gringauze:
    On the Existence of Propositional Proof Systems and Oracle-relativized Propositional Logic.
    Electronic Edition (link) BibTeX
  22. Steffen Reith, Heribert Vollmer:
    The Complexity of Computing Optimal Assignments of Generalized Propositional Formulae.
    Electronic Edition (link) BibTeX
  23. Eric Allender, Shiyu Zhou:
    Uniform Inclusions in Nondeterministic Logspace.
    Electronic Edition (link) BibTeX
  24. Wenceslas Fernandez de la Vega, Marek Karpinski:
    On Approximation Hardness of Dense TSP and other Path Problems.
    Electronic Edition (link) BibTeX
  25. Joseph Cheriyan, Ramakrishna Thurimella:
    Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching. BibTeX
  26. Richard Beigel:
    Gaps in Bounded Query Hierarchies.
    Electronic Edition (link) BibTeX
  27. Vikraman Arvind, Jacobo Torán:
    Sparse Sets, Approximable Sets, and Parallel Queries to NP.
    Electronic Edition (link) BibTeX
  28. Paul Beame, Faith E. Fich:
    On Searching Sorted Lists: A Near-Optimal Lower Bound.
    Electronic Edition (link) BibTeX
  29. Piotr Berman, Marek Karpinski:
    On Some Tighter Inapproximability Results.
    Electronic Edition (link) BibTeX
  30. Stasys Jukna, Stanislav Zák:
    On Branching Programs With Bounded Uncertainty.
    Electronic Edition (link) BibTeX
  31. Dimitris Fotakis, Paul G. Spirakis:
    Graph Properties that Facilitate Travelling.
    Electronic Edition (link) BibTeX
  32. Mihir Bellare, Oded Goldreich, Erez Petrank:
    Uniform Generation of NP-witnesses using an NP-oracle.
    Electronic Edition (link) BibTeX
  33. Claus-Peter Schnorr:
    Security of Allmost ALL Discrete Log Bits.
    Electronic Edition (link) BibTeX
  34. Venkatesan Guruswami, Daniel Lewin, Madhu Sudan, Luca Trevisan:
    A tight characterization of NP with 3 query PCPs.
    Electronic Edition (link) BibTeX
  35. Maria Luisa Bonet, Juan Luis Esteban, Nicola Galesi, Jan Johannsen:
    Exponential Separations between Restricted Resolution and Cutting Planes Proof Systems.
    Electronic Edition (link) BibTeX
  36. Vince Grolmusz, Gábor Tardos:
    Lower Bounds for (MOD p -- MOD m) Circuits.
    Electronic Edition (link) BibTeX
  37. Johannes Köbler, Rainer Schuler:
    Average-Case Intractability vs. Worst-Case Intractability.
    Electronic Edition (link) BibTeX
  38. Marek Karpinski:
    On the Computational Power of Randomized Branching Programs.
    Electronic Edition (link) BibTeX
  39. Christoph Meinel, Thorsten Theobald:
    Ordered Binary Decision Diagrams and Their Significance in Computer-Aided Design of VLSI Circuits - a Survey.
    Electronic Edition (link) BibTeX
  40. Madhu Sudan, Luca Trevisan:
    Probabilistically checkable proofs with low amortized query complexity.
    Electronic Edition (link) BibTeX
  41. Stasys Jukna:
    Combinatorics of Monotone Computations.
    Electronic Edition (link) BibTeX
  42. Pavel Pudlák:
    A Note On the Use of Determinant for Proving Lower Bounds on the Size of Linear Circuits.
    Electronic Edition (link) BibTeX
  43. Venkatesan Guruswami, Madhu Sudan:
    Improved decoding of Reed-Solomon and algebraic-geometric codes.
    Electronic Edition (link) BibTeX
  44. Jiri Sgall:
    Bounds on Pairs of Families with Restricted Intersections.
    Electronic Edition (link) BibTeX
  45. Detlef Sieling:
    A Separation of Syntactic and Nonsyntactic (1,+k)-Branching Programs.
    Electronic Edition (link) BibTeX
  46. Lars Engebretsen:
    An Explicit Lower Bound for TSP with Distances One and Two.
    Electronic Edition (link) BibTeX
  47. Salil P. Vadhan:
    Extracting All the Randomness from a Weakly Random Source.
    Electronic Edition (link) BibTeX
  48. Irit Dinur, Guy Kindler, Shmuel Safra:
    Approximating CVP to Within Almost Polynomial Factor is NP-Hard.
    Electronic Edition (link) BibTeX
  49. Dimitris Fotakis, Paul G. Spirakis:
    Random Walks, Conditional Hitting Sets and Partial Derandomization.
    Electronic Edition (link) BibTeX
  50. Farid M. Ablayev, Svetlana Ablayeva:
    A Discrete Approximation and Communication Complexity Approach to the Superposition Problem.
    Electronic Edition (link) BibTeX
  51. Petr Savický:
    A probabilistic nonequivalence test for syntactic (1,+k)-branching programs.
    Electronic Edition (link) BibTeX
  52. Boris Hemkemeier, Frank Vallentin:
    On the decomposition of lattices.
    Electronic Edition (link) BibTeX
  53. Paul Beame, Michael E. Saks, Jayram S. Thathachar:
    Time-Space Tradeoffs for Branching Programs.
    Electronic Edition (link) BibTeX
  54. Igor Shparlinski:
    On Polynomial Representations of Boolean Functions Related to Some Number Theoretic Problems.
    Electronic Edition (link) BibTeX
  55. Luca Trevisan:
    Constructions of Near-Optimal Extractors Using Pseudo-Random Generators.
    Electronic Edition (link) BibTeX
  56. Anna Bernasconi, Igor Shparlinski:
    Circuit Complexity of Testing Square-Free Numbers.
    Electronic Edition (link) BibTeX
  57. Manindra Agrawal, Eric Allender, Samir Datta, Heribert Vollmer, Klaus W. Wagner:
    Characterizing Small Depth and Small Space Classes by Operators of Higher Types.
    Electronic Edition (link) BibTeX
  58. Harry Buhrman, Dieter van Melkebeek, Kenneth W. Regan, Martin Strauss, D. Sivakumar:
    A Generalization of Resource-Bounded Measure, With Application to the BPP vs. EXP Problem.
    Electronic Edition (link) BibTeX
  59. Clemens Lautemann, Pierre McKenzie, Thomas Schwentick, Heribert Vollmer:
    The Descriptive Complexity Approach to LOGCFL.
    Electronic Edition (link) BibTeX
  60. Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan:
    Learning Polynomials with Queries - The Highly Noisy Case.
    Electronic Edition (link) BibTeX
  61. Robert H. Sloan, Ken Takata, György Turán:
    On frequent sets of Boolean matrices.
    Electronic Edition (link) BibTeX
  62. Oded Goldreich, Dana Ron, Madhu Sudan:
    Chinese Remaindering with Errors.
    Electronic Edition (link) BibTeX
  63. Oded Goldreich, Salil P. Vadhan:
    Comparing Entropies in Statistical Zero-Knowledge with Applications to the Structure of SZK.
    Electronic Edition (link) BibTeX
  64. Wenceslas Fernandez de la Vega, Marek Karpinski:
    Polynomial Time Approximation of Dense Weighted Instances of MAX-CUT.
    Electronic Edition (link) BibTeX
  65. Piotr Berman, Marek Karpinski:
    On Some Tighter Inapproximability Results, Further Improvements.
    Electronic Edition (link) BibTeX
  66. Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra:
    PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability.
    Electronic Edition (link) BibTeX
  67. Paul Beame, Toniann Pitassi:
    Propositional Proof Complexity: Past, Present and Future.
    Electronic Edition (link) BibTeX
  68. Petr Savický:
    On Random Orderings of Variables for Parity OBDDs.
    Electronic Edition (link) BibTeX
  69. Rüdiger Reischuk, Thomas Zeugmann:
    An Average-Case Optimal One-Variable Pattern Language Learner.
    Electronic Edition (link) BibTeX
  70. Rüdiger Reischuk:
    Can Large Fanin Circuits Perform Reliable Computations in the Presence of Noise?
    Electronic Edition (link) BibTeX
  71. Itsik Pe'er, Ron Shamir:
    The median problems for breakpoints are NP-complete.
    Electronic Edition (link) BibTeX
  72. Ziv Bar-Yossef, Oded Goldreich, Avi Wigderson:
    Deterministic Amplification of Space Bounded Probabilistic Algorithms.
    Electronic Edition (link) BibTeX
  73. Tomoyuki Yamakami, Andrew Chi-Chih Yao:
    NQP = co-C=P.
    Electronic Edition (link) BibTeX
  74. Madhu Sudan, Luca Trevisan, Salil P. Vadhan:
    Pseudorandom generators without the XOR Lemma.
    Electronic Edition (link) BibTeX
  75. Adam Klivans, Dieter van Melkebeek:
    Graph Nonisomorphism has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses.
    Electronic Edition (link) BibTeX
  76. Nader H. Bshouty, Jeffrey C. Jackson, Christino Tamon:
    Attribute Efficient PAC Learning of DNF with Membership Queries under the Uniform Distribution.
    Electronic Edition (link) BibTeX
  77. Miklós Ajtai:
    Determinism versus Non-Determinism for Linear Time RAMs with Memory Restrictions.
    Electronic Edition (link) BibTeX
  78. Vikraman Arvind, K. V. Subrahmanyam, N. V. Vinodchandran:
    The Query Complexity of Program Checking by Constant-Depth Circuits.
    Electronic Edition (link) BibTeX

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