Electronic Colloquium on Computational Complexity, Volume 5, 1998

Volume 5, 1998

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

Last update Tue May 21 18:49:37 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page