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.