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