default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDElectronic Colloquium on Computational Complexity, 1998
Volume TR98, 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, Murat 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. - Jirí 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 E. 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 E. 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 R. 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.
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-12-09 23:40 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
