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

Electronic Colloquium on Computational Complexity, Volume 6, 1999

Volume 6, 1999

  1. Detlef Sieling:
    The Complexity of Minimizing FBDDs.
    Electronic Edition (link) BibTeX
  2. Oded Goldreich, Daniele Micciancio, Shmuel Safra, Jean-Pierre Seifert:
    Approximating Shortest Lattice Vectors is Not Harder Than Approximating Closest Lattice Vectors.
    Electronic Edition (link) BibTeX
  3. Stephen A. Fenner, Frederic Green, Steven Homer, Randall Pruim:
    Determining Acceptance Possibility for a Quantum Computation is Hard for the Polynomial Hierarchy.
    Electronic Edition (link) BibTeX
  4. Valentine Kabanets:
    Almost k-Wise Independence and Boolean Functions Hard for Read-Once Branching Programs.
    Electronic Edition (link) BibTeX
  5. Michael Schmitt:
    On the Sample Complexity for Nonoverlapping Neural Networks.
    Electronic Edition (link) BibTeX
  6. Jin-yi Cai:
    Some Recent Progress on the Complexity of Lattice Problems.
    Electronic Edition (link) BibTeX
  7. Juraj Hromkovic, Georg Schnitger:
    On the Power of Las Vegas II: Two-Way Finite Automata.
    Electronic Edition (link) BibTeX
  8. Eric Allender, Vikraman Arvind, Meena Mahajan:
    Arithmetic Complexity, Kleene Closure, and Formal Power Series.
    Electronic Edition (link) BibTeX
  9. Marek Karpinski, Rustam Mubarakzjanov:
    A Note on Las Vegas OBDDs.
    Electronic Edition (link) BibTeX
  10. Eric Allender, Igor Shparlinski, Michael E. Saks:
    A Lower Bound for Primality.
    Electronic Edition (link) BibTeX
  11. Matthias Krause, Petr Savický, Ingo Wegener:
    Approximations by OBDDs and the variable ordering problem.
    Electronic Edition (link) BibTeX
  12. Eric Allender, Andris Ambainis, David A. Mix Barrington, Samir Datta, Huong LeThanh:
    Bounded Depth Arithmetic Circuits: Counting and Closure.
    Electronic Edition (link) BibTeX
  13. Oded Goldreich, Amit Sahai, Salil P. Vadhan:
    Can Statistical Zero Knowledge be made Non-Interactive? or On the Relationship of SZK and NISZK.
    Electronic Edition (link) BibTeX
  14. Alexander A. Razborov, Nikolai K. Vereshchagin:
    One Property of Cross-Intersecting Families.
    Electronic Edition (link) BibTeX
  15. Irit Dinur, Shmuel Safra:
    On the Hardness of Approximating Label Cover.
    Electronic Edition (link) BibTeX
  16. Irit Dinur:
    Approximating SVPinfty to within Almost-Polynomial Factors is NP-hard.
    Electronic Edition (link) BibTeX
  17. Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, Alex Samorodnitsky:
    Improved Testing Algorithms for Monotonicity.
    Electronic Edition (link) BibTeX
  18. Manindra Agrawal, Somenath Biswas:
    Reducing Randomness via Chinese Remaindering.
    Electronic Edition (link) BibTeX
  19. Detlef Sieling:
    Lower Bounds for Linear Transformed OBDDs and FBDDs.
    Electronic Edition (link) BibTeX
  20. Marek Karpinski:
    Randomized Complexity of Linear Arrangements and Polyhedra.
    Electronic Edition (link) BibTeX
  21. Igor Shparlinski:
    On the Uniformity of Distribution of a Certain Pseudo-Random Function.
    Electronic Edition (link) BibTeX
  22. Eli Ben-Sasson, Avi Wigderson:
    Short Proofs are Narrow - Resolution made Simple.
    Electronic Edition (link) BibTeX
  23. Amir Shpilka, Avi Wigderson:
    Depth-3 Arithmetic Formulae over Fields of Characteristic Zero.
    Electronic Edition (link) BibTeX
  24. Oded Goldreich, Shafi Goldwasser, Silvio Micali:
    Interleaved Zero-Knowledge in the Public-Key Model. .
    Electronic Edition (link) BibTeX
  25. Yonatan Aumann, Johan Håstad, Michael O. Rabin, Madhu Sudan:
    Linear Consistency Testing.
    Electronic Edition (link) BibTeX
  26. Miklós Ajtai:
    A Non-linear Time Lower Bound for Boolean Branching Programs.
    Electronic Edition (link) BibTeX
  27. Marek Karpinski, Igor Shparlinski:
    On the Computational Hardness of Testing Square-Freeness of Sparse Polynomials.
    Electronic Edition (link) BibTeX
  28. Stefan Edelkamp, Ingo Wegener:
    On the performance of WEAK-HEAPSORT.
    Electronic Edition (link) BibTeX
  29. Ilya Dumer, Daniele Micciancio, Madhu Sudan:
    Hardness of Approximating the Minimum Distance of a Linear Code.
    Electronic Edition (link) BibTeX
  30. Meena Mahajan, P. R. Subramanya, V. Vinay:
    A Combinatorial Algorithm for Pfaffians.
    Electronic Edition (link) BibTeX
  31. Hans-Joachim Böckenhauer, Juraj Hromkovic, Ralf Klasing, Sebastian Seibert, Walter Unger:
    Towards the Notion of Stability of Approximation for Hard Optimization Tasks and the Traveling Salesman Problem.
    Electronic Edition (link) BibTeX
  32. Cristopher Moore:
    Quantum Circuits: Fanout, Parity, and Counting.
    Electronic Edition (link) BibTeX
  33. Vikraman Arvind, Johannes Köbler:
    Graph Isomorphism is Low for ZPPNP and other Lowness results.
    Electronic Edition (link) BibTeX
  34. Wolfgang Merkle:
    The Global Power of Additional Queries to p-random Oracles.
    Electronic Edition (link) BibTeX
  35. Leonard J. Schulman:
    Clustering for Edge-Cost Minimization.
    Electronic Edition (link) BibTeX
  36. Edward A. Hirsch:
    A New Algorithm for MAX-2-SAT.
    Electronic Edition (link) BibTeX
  37. Johan Håstad, Mats Näslund:
    The Security of all RSA and Discrete Log Bits.
    Electronic Edition (link) BibTeX
  38. Peter Jonsson, Paolo Liberatore:
    On the Complexity of Finding Satisfiable Subinstances in Constraint Satisfaction.
    Electronic Edition (link) BibTeX
  39. Johan Håstad:
    On approximating CSP-B.
    Electronic Edition (link) BibTeX
  40. Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson:
    Space Complexity in Propositional Calculus.
    Electronic Edition (link) BibTeX
  41. Oliver Kullmann:
    Investigating a general hierarchy of polynomially decidable classes of CNF's based on short tree-like resolution proofs.
    Electronic Edition (link) BibTeX
  42. Ran Canetti, Oded Goldreich, Shafi Goldwasser, Silvio Micali:
    Resettable Zero-Knowledge.
    Electronic Edition (link) BibTeX
  43. Venkatesan Guruswami:
    The Approximability of Set Splitting Problems and Satisfiability Problems with no Mixed Clauses.
    Electronic Edition (link) BibTeX
  44. Farid M. Ablayev:
    On Complexity of Regular (1,+k)-Branching Programs.
    Electronic Edition (link) BibTeX
  45. Valentine Kabanets, Jin-yi Cai:
    Circuit Minimization Problem.
    Electronic Edition (link) BibTeX
  46. Ran Raz, Omer Reingold, Salil P. Vadhan:
    Extracting All the Randomness and Reducing the Error in Trevisan's Extractors.
    Electronic Edition (link) BibTeX
  47. Wolfgang Slany:
    Graph Ramsey games.
    Electronic Edition (link) BibTeX
  48. Beate Bollig, Ingo Wegener:
    Asymptotically Optimal Bounds for OBDDs and the Solution of Some Basic OBDD Problems.
    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)