Electronic Colloquium on Computational Complexity, Volume 3, 1996

Volume 3, 1996

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