Electronic Colloquium on Computational Complexity, Volume 6, 1999

Volume 6, 1999

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