Electronic Colloquium on Computational Complexity, Volume 3, 1996

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 2^t-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((log²n)/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 log₂n + 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(n²) 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.
  

Last update Tue May 21 13:13:28 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page