Volume 3, 1996
- Manindra Agrawal, Richard Beigel, Thomas Thierauf:
Modulo Information from Nonadaptive Queries to NP.
- Manindra Agrawal, Eric Allender:
An Isomorphism Theorem for Circuit Complexity.
- Alexei Kitaev:
Quantum measurements and the Abelian Stabilizer Problem.
- Shiva Chaudhuri, Jaikumar Radhakrishnan:
Deterministic Restrictions in Circuit Complexity.
- Hans-Jörg Burtschick, Heribert Vollmer:
Lindstroem Quantifiers and Leaf Language Definability.
- Bernd Borchert, Antoni Lozano:
Succinct Circuit Representations and Leaf Language Classes are Basically the same Concept.
- Miklós Ajtai:
Generating Hard Instances of Lattice Problems.
- Francesco Bergadano, Nader H. Bshouty, Stefano Varricchio:
Learning Multivariate Polynomials from Substitution and Equivalence Queries.
- Francesco Bergadano, Nader H. Bshouty, Christino Tamon, Stefano Varricchio:
On Learning Branching Programs and Small Depth Circuits.
- Christoph Meinel, Anna Slobodová:
An Adequate Reducibility Concept for Problems Defined in Terms of Ordered Binary Decision Diagrams.
- Stephen A. Bloch, Jonathan F. Buss, Judy Goldsmith:
Sharply Bounded Alternation within P.
- Giuseppe Ateniese, Carlo Blundo, Alfredo De Santis, Douglas R. Stinson:
Visual Cryptography for General Access Structures.
- Mitsunori Ogihara:
The PL Hierarchy Collapses.
- Mitsunori Ogihara:
Sparse Hard Sets for P Yields Space-Efficient Algorithms.
- Edoardo Amaldi, Viggo Kann:
On the approximability of some NP-hard minimization problems for linear systems.
- Andrea E. F. Clementi, Luca Trevisan:
Improved Non-approximability Results for Minimum Vertex Cover with Density Constraints.
- Christoph Meinel, Stephan Waack:
The ``Log Rank'' Conjecture for Modular Communication Complexity.
- Oded Goldreich, Johan Håstad:
On the Message Complexity of Interactive Proof Systems.
- Claus-Peter Schnorr:
Security of 2t-Root Identification and Signatures.
- Carsten Rössner, Claus-Peter Schnorr:
An Optimal, Stable Continued Fraction Algorithm for Arbitrary Dimension.
- Yongge Wang:
NP-hard Sets Are Superterse unless NP Is Small .
- Martin Sauerhoff, Ingo Wegener, Ralph Werchner:
Optimal Ordered Binary Decision Diagrams for Tree-like Circuits.
- Eric Allender:
A Note on Uniform Circuit Lower Bounds for the Counting Hierarchy.
- Eric Allender, Robert Beals, Mitsunori Ogihara:
The complexity of matrix rank and feasible systems of linear equations.
- Wolfgang Maass, Berthold Ruf:
The Computational Power of Spiking Neurons Depends on the Shape of the Postsynaptic Potentials.
- Stasys Jukna:
Finite Limits and Monotone Computations.
- Lane A. Hemaspaandra, Ashish V. Naik, Mitsunori Ogihara, Alan L. Selman:
Computing Solutions Uniquely Collapses the Polynomial Hierarchy.
- Sanjeev Khanna, Madhu Sudan:
The Optimization Complexity of Constraint Satisfaction Problems.
- Alexander E. Andreev, Andrea E. F. Clementi, José D. P. Rolim:
Towards efficient constructions of hitting sets that derandomize BPP.
- Meera Sitharam:
Approximation from linear spaces and applications to complexity.
- Wolfgang Maass:
Networks of Spiking Neurons: The Third Generation of Neural Network Models.
- Manindra Agrawal, Thomas Thierauf:
The Boolean Isomorphism Problem.
- Bernd Borchert, Desh Ranjan, Frank Stephan:
On the Computational Complexity of some Classical Equivalence Relations on Boolean Functions.
- Vasken Bohossian, Jehoshua Bruck:
On Neural Networks with Minimal Weights.
- Ronald V. Book, Heribert Vollmer, Klaus W. Wagner:
Probabilistic Type-2 Operators and ``Almost''-Classes.
- Petr Savický, Stanislav Zák:
A large lower bound for 1-branching programs.
- Stasys Jukna, Alexander A. Razborov:
Neither Reading Few Bits Twice nor Reading Illegally Helps Much.
- Michael A. Gibson, Jehoshua Bruck:
Efficient Digital to Analog Encoding.
- Carme Àlvarez, Raymond Greenlaw:
A Compendium of Problems Complete for Symmetric Logarithmic Space.
- Thomas Thierauf:
The Isomorphismproblem for One-Time-Only Branching Programs.
- Oded Goldreich, Avi Wigderson:
On the Circuit Complexity of Perfect Hashing.
- Oded Goldreich, Shafi Goldwasser, Shai Halevi:
Collision-Free Hashing from Lattice Problems.
- Edmund Ihler:
On polynomial time approximation schemes and approximation preserving reductions.
- Yosi Ben-Asher, Ilan Newman:
Optimal Search in Trees.
- Bernd Borchert, Lane A. Hemaspaandra, Jörg Rothe:
Powers-of-Two Acceptance Suffices for Equivalence and Bounded Ambiguity Problems.
- Luca Trevisan:
On the Approximability of the Multi-dimensional Euclidean TSP.
- Oded Goldreich, Shmuel Safra:
A Combinatorial Consistency Lemma with application to the PCP Theorem.
- Eric Allender, Klaus-Jörn Lange:
StUSPACE(log n) is Contained in DSPACE((log2n)/loglog n).
- Per Enflo, Meera Sitharam:
Stable basis families and complexity lower bounds.
- Petr Savický, Stanislav Zák:
A hierarchy for (1,+k)-branching programs with respect to k.
- Richard Beigel, William I. Gasarch, Ming Li, Louxin Zhang:
Addition in log2n + O(1) Steps on Average: A Simple Analysis.
- Martin Dietzfelbinger:
Gossiping and Broadcasting versus Computing Functions in Networks.
- Yosi Ben-Asher, Ilan Newman:
Geometric Approach for Optimal Routing on Mesh with Buses.
- Oded Goldreich:
The Graph Clustering Problem has a Perfect Zero-Knowledge Proof .
- Alexander E. Andreev, Andrea E. F. Clementi, José D. P. Rolim:
Hitting Properties of Hard Boolean Operators and their Consequences on BPP.
- Oded Goldreich, Shafi Goldwasser, Shai Halevi:
Public-Key Cryptosystems from Lattice Reduction Problems.
- Oded Goldreich, Shafi Goldwasser, Dana Ron:
Property Testing and its connection to Learning and Approximation.
- Dima Grigoriev, Marek Karpinski:
Randomized Omega(n2) Lower Bound for Knapsack.
- Shai Ben-David, Nader H. Bshouty, Eyal Kushilevitz:
A Composition Theorem for Learning Algorithms with Applications to Geometric Concept Classes.
- Bernd Borchert, Frank Stephan:
Looking for an Analogue of Rice's Theorem in Complexity Theory.
- Ryuhei Uehara, Kensei Tsuchida, Ingo Wegener:
Optimal attribute-efficient learning of disjunction, parity, and threshold functions.
- Sanjeev Khanna, Madhu Sudan, David P. Williamson:
A Complete Characterization of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction.
- Martin Dietzfelbinger:
The Linear-Array Problem in Communication Complexity Resolved.
- Sanjeev Khanna, Madhu Sudan, Luca Trevisan:
Constraint satisfaction: The approximability of minimization problems.
- Miklós Ajtai, Cynthia Dwork:
A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence.
- Pierluigi Crescenzi, Viggo Kann, Riccardo Silvestri, Luca Trevisan:
Structure in Approximation Classes.
- Oded Goldreich, Bernd Meyer:
Computational Indistinguishability - Algorithms vs. Circuits.
Copyright © Wed Nov 25 19:07:58 2009
by Michael Ley (ley@uni-trier.de)