- Dimitris Fotakis, Paul G. Spirakis:
Graph Properties that Facilitate Travelling. Electron. Colloquium Comput. Complex. TR98 (1998) - Mihir Bellare, Oded Goldreich, Erez Petrank:
Uniform Generation of NP-witnesses using an NP-oracle. Electron. Colloquium Comput. Complex. TR98 (1998) - Claus-Peter Schnorr:
Security of Allmost ALL Discrete Log Bits. Electron. Colloquium Comput. Complex. TR98 (1998) - Venkatesan Guruswami, Daniel Lewin, Madhu Sudan, Luca Trevisan:
A tight characterization of NP with 3 query PCPs. Electron. Colloquium Comput. Complex. TR98 (1998) - Maria Luisa Bonet, Juan Luis Esteban, Nicola Galesi, Jan Johannsen:
Exponential Separations between Restricted Resolution and Cutting Planes Proof Systems. Electron. Colloquium Comput. Complex. TR98 (1998) - Vince Grolmusz, Gábor Tardos:
Lower Bounds for (MOD p -- MOD m) Circuits. Electron. Colloquium Comput. Complex. TR98 (1998) - Johannes Köbler, Rainer Schuler:
Average-Case Intractability vs. Worst-Case Intractability. Electron. Colloquium Comput. Complex. TR98 (1998) - Marek Karpinski:
On the Computational Power of Randomized Branching Programs. Electron. Colloquium Comput. Complex. TR98 (1998) - Christoph Meinel, Thorsten Theobald:
Ordered Binary Decision Diagrams and Their Significance in Computer-Aided Design of VLSI Circuits - a Survey. Electron. Colloquium Comput. Complex. TR98 (1998) - Madhu Sudan, Luca Trevisan:
Probabilistically checkable proofs with low amortized query complexity. Electron. Colloquium Comput. Complex. TR98 (1998) - Stasys Jukna:
Combinatorics of Monotone Computations. Electron. Colloquium Comput. Complex. TR98 (1998) - Pavel Pudlák:
A Note On the Use of Determinant for Proving Lower Bounds on the Size of Linear Circuits. Electron. Colloquium Comput. Complex. TR98 (1998) - Venkatesan Guruswami, Madhu Sudan:
Improved decoding of Reed-Solomon and algebraic-geometric codes. Electron. Colloquium Comput. Complex. TR98 (1998) - Jirí Sgall:
Bounds on Pairs of Families with Restricted Intersections. Electron. Colloquium Comput. Complex. TR98 (1998) - Detlef Sieling:
A Separation of Syntactic and Nonsyntactic (1,+k)-Branching Programs. Electron. Colloquium Comput. Complex. TR98 (1998) - Lars Engebretsen:
An Explicit Lower Bound for TSP with Distances One and Two. Electron. Colloquium Comput. Complex. TR98 (1998) - Salil P. Vadhan:
Extracting All the Randomness from a Weakly Random Source. Electron. Colloquium Comput. Complex. TR98 (1998) - Irit Dinur, Guy Kindler, Shmuel Safra
:
Approximating CVP to Within Almost Polynomial Factor is NP-Hard. Electron. Colloquium Comput. Complex. TR98 (1998) - Dimitris Fotakis, Paul G. Spirakis:
Random Walks, Conditional Hitting Sets and Partial Derandomization. Electron. Colloquium Comput. Complex. TR98 (1998) - Farid M. Ablayev, Svetlana Ablayeva:
A Discrete Approximation and Communication Complexity Approach to the Superposition Problem. Electron. Colloquium Comput. Complex. TR98 (1998) - Petr Savický:
A probabilistic nonequivalence test for syntactic (1,+k)-branching programs. Electron. Colloquium Comput. Complex. TR98 (1998) - Boris Hemkemeier, Frank Vallentin:
On the decomposition of lattices. Electron. Colloquium Comput. Complex. TR98 (1998) - Paul Beame, Michael E. Saks, Jayram S. Thathachar:
Time-Space Tradeoffs for Branching Programs. Electron. Colloquium Comput. Complex. TR98 (1998) - Igor E. Shparlinski:
On Polynomial Representations of Boolean Functions Related to Some Number Theoretic Problems. Electron. Colloquium Comput. Complex. TR98 (1998) - Luca Trevisan:
Constructions of Near-Optimal Extractors Using Pseudo-Random Generators. Electron. Colloquium Comput. Complex. TR98 (1998) - Anna Bernasconi, Igor E. Shparlinski:
Circuit Complexity of Testing Square-Free Numbers. Electron. Colloquium Comput. Complex. TR98 (1998) - Manindra Agrawal, Eric Allender, Samir Datta, Heribert Vollmer, Klaus W. Wagner:
Characterizing Small Depth and Small Space Classes by Operators of Higher Types. Electron. Colloquium Comput. Complex. TR98 (1998) - 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. Electron. Colloquium Comput. Complex. TR98 (1998) - Clemens Lautemann, Pierre McKenzie, Thomas Schwentick, Heribert Vollmer:
The Descriptive Complexity Approach to LOGCFL. Electron. Colloquium Comput. Complex. TR98 (1998) - Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan:
Learning Polynomials with Queries - The Highly Noisy Case. Electron. Colloquium Comput. Complex. TR98 (1998)
