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

Copyright © Mon Nov 2 21:34:16 2009 by Michael Ley (ley@uni-trier.de)