dblp.uni-trier.de www.uni-trier.de

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

Home | Conferences | Journals | Series | FAQ — Search: Faceted | Complete | Author
Copyright © Sat May 16 23:57:48 2009 by Michael Ley (ley@uni-trier.de)