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
