Volume 4, 1997
- Marco Cesati, Luca Trevisan:
On the Efficiency of Polynomial Time Approximation Schemes.

- Richard Beigel, Alexis Maciel:
Upper and Lower Bounds for Some Depth-3 Circuit Classes.

- Sanjeev Arora, Madhu Sudan:
Improved low-degree testing and its applications.

- Marek Karpinski, Alexander Zelikovsky:
Approximating Dense Cases of Covering Problems.

- Moni Naor, Omer Reingold:
On the Construction of Pseudo-Random Permutations: Luby-Rackoff Revisited.

- Marco Cesati, Miriam Di Ianni:
Parameterized Parallel Complexity.

- Stasys Jukna:
Exponential Lower Bounds for Semantic Resolution.

- Noam Nisan, Ziv Bar-Yossef:
Pointer Jumping Requires Concurrent Read.

- Jonathan F. Buss, Gudmund Skovbjerg Frandsen, Jeffrey Shallit:
The Computational Complexity of Some Problems of Linear Algebra.

- Marcos A. Kiwi:
Testing and Weight Distributions of Dual Codes.

- Alexander E. Andreev, Andrea E. F. Clementi, José D. P. Rolim, Luca Trevisan:
Weak Random Sources, Hitting Sets, and BPP Simulations.

- Luca Trevisan:
On Local versus Global Satisfiability.

- Bernd Borchert, Dietrich Kuske, Frank Stephan:
On Existentially First-Order Definable Languages and their Relation to NP.

- Klaus Reinhardt, Eric Allender:
Making Nondeterminism Unambiguous.

- Jan Krajícek:
Interpolation by a Game.

- Manindra Agrawal, Eric Allender, Samir Datta:
On TC0, AC0, and Arithmetic Circuits.

- Marek Karpinski, Juergen Wirtgen, Alexander Zelikovsky:
An Approximation Algorithm for the Bandwidth Problem on Dense Graphs.

- Oded Goldreich, Shafi Goldwasser, Shai Halevi:
Eliminating Decryption Errors in the Ajtai-Dwork Cryptosystem.

- Martin Sauerhoff:
A Lower Bound for Randomized Read-k-Times Branching Programs.

- Oded Goldreich:
A Sample of Samplers - A Computational Perspective on Sampling (survey).

- Farid M. Ablayev:
Randomization and nondeterminsm are incomparable for ordered read-once branching programs.

- Gunnar Andersson, Lars Engebretsen:
Better Approximation Algorithms and Tighter Analysis for Set Splitting and Not-All-Equal Sat.

- Stasys Jukna, Alexander A. Razborov, Petr Savický, Ingo Wegener:
On P versus NP \cap co-NP for Decision Trees and Read-Once Branching Programs.

- Marek Karpinski:
Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems.

- Harald Hempel, Gerd Wechsung:
The Operators min and max on the Polynomial Hierarchy.

- Jochen Meßner, Jacobo Torán:
Optimal proof systems for Propositional Logic and complete sets.

- Johannes Merkle, Ralph Werchner:
On the Security of Server aided RSA protocols.

- Scott E. Decatur, Oded Goldreich, Dana Ron:
Computational Sample Complexity.

- Pavol Duris, Juraj Hromkovic, José D. P. Rolim, Georg Schnitger:
On the Power of Las Vegas for One-way Communication Complexity, Finite Automata, and Polynomial-time Computations.

- Martin Sauerhoff:
On Nondeterminism versus Randomness for Read-Once Branching Programs.

- Oded Goldreich, Shafi Goldwasser:
On the Limits of Non-Approximability of Lattice Problems.

- Jan Johannsen:
Lower Bounds for Monotone Real Circuit Depth and Formula Size and Tree-like Cutting Planes.

- Meena Mahajan, Venkatesh Raman:
Parametrizing Above Guaranteed Values: MaxSat and MaxCut.

- Jui-Lin Lee:
Counting in Uniform TC0.

- Richard Chang:
Bounded Queries, Approximations and the Boolean Hierarchy.

- Meena Mahajan, V. Vinay:
Determinant: Combinatorics, Algorithms, and Complexity.

- Johan Håstad:
Some optimal inapproximability results.

- Johan Håstad:
Clique is hard to approximate within n1-epsilon.

- Pierluigi Crescenzi, Luca Trevisan:
MAX NP-Completeness Made Easy.

- Dorit Dor, Shay Halperin, Uri Zwick:
All Pairs Almost Shortest Paths.

- Marek Karpinski, Juergen Wirtgen:
On Approximation Hardness of the Bandwidth Problem.

- Russell Impagliazzo, Pavel Pudlák, Jiri Sgall:
Lower Bounds for the Polynomial Calculus and the Groebner Basis Algorithm.

- Bruno Codenotti, Pavel Pudlák, Giovanni Resta:
Some structural properties of low rank matrices related to computational complexity.

- David A. Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, Sven Skyum:
Searching constant width mazes captures the AC0 hierarchy.

- Oded Goldreich, David Zuckerman:
Another proof that BPP subseteq PH (and more). .

- Alexander Barg:
Complexity Issues in Coding Theory.

- Miklós Ajtai:
The Shortest Vector Problem in L2 is NP-hard for Randomized Reductions.

- Søren Riis, Meera Sitharam:
Non-constant Degree Lower Bounds imply linear Degree Lower Bounds.

- Wolfgang Maass, Michael Schmitt:
On the Complexity of Learning for Spiking Neurons with Temporal Coding.

- Stanislav Zák:
A subexponential lower bound for branching programs restricted with regard to some semantic aspects.

- Wolfgang Maass, Pekka Orponen:
On the Effect of Analog Noise in Discrete-Time Analog Computations.

- Wolfgang Maass, Eduardo D. Sontag:
Analog Neural Nets with Gaussian or other Common Noise Distributions cannot Recognize Arbitrary Regular Languages.

- Alexander E. Andreev, Juri L. Baskakov, Andrea E. F. Clementi, José D. P. Rolim:
Small Random Sets for Affine Spaces and Better Explicit Lower Bounds for Branching Programs.

- Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolai K. Vereshchagin:
Arthur-Merlin Games in Boolean Decision Trees.

- Bruce E. Litow:
A Decision Method for the Rational Sequence Problem.

- Oded Goldreich:
Combinatorial Property Testing (a survey). .

- Petr Savický:
Complexity and Probability of some Boolean Formulas.

- Oded Goldreich:
Notes on Levin's Theory of Average-Case Complexity.

- Jin-yi Cai, Ajay Nerurkar:
Approximating the SVP to within a factor (1 + 1/dimepsilon) is NP-hard under randomized reductions.

- Manindra Agrawal, Thomas Thierauf:
The Satisfiability Problem for Probabilistic Ordered Branching Programs.

- Eli Biham, Dan Boneh, Omer Reingold:
Generalized Diffie-Hellman Modulo a Composite is not Weaker than Factoring.

Last update Thu May 23 18:42:52 2013
CET by the DBLP Team —
Data released under the ODC-BY 1.0 license — See also our legal information page