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 AC0 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.
Copyright © Sat Nov 28 22:28:29 2009
by Michael Ley (ley@uni-trier.de)