- 1999
- Detlef Sieling:
The Complexity of Minimizing FBDDs. Electron. Colloquium Comput. Complex. TR99 (1999) - Oded Goldreich, Daniele Micciancio, Shmuel Safra, Jean-Pierre Seifert:
Approximating Shortest Lattice Vectors is Not Harder Than Approximating Closest Lattice Vectors. Electron. Colloquium Comput. Complex. TR99 (1999) - Stephen A. Fenner, Frederic Green, Steven Homer, Randall Pruim:
Determining Acceptance Possibility for a Quantum Computation is Hard for the Polynomial Hierarchy. Electron. Colloquium Comput. Complex. TR99 (1999) - Valentine Kabanets:
Almost k-Wise Independence and Boolean Functions Hard for Read-Once Branching Programs. Electron. Colloquium Comput. Complex. TR99 (1999) - Michael Schmitt:
On the Sample Complexity for Nonoverlapping Neural Networks. Electron. Colloquium Comput. Complex. TR99 (1999) - Jin-yi Cai:
Some Recent Progress on the Complexity of Lattice Problems. Electron. Colloquium Comput. Complex. TR99 (1999) - Juraj Hromkovic, Georg Schnitger:
On the Power of Las Vegas II: Two-Way Finite Automata. Electron. Colloquium Comput. Complex. TR99 (1999) - Eric Allender, Vikraman Arvind, Meena Mahajan:
Arithmetic Complexity, Kleene Closure, and Formal Power Series. Electron. Colloquium Comput. Complex. TR99 (1999) - Marek Karpinski, Rustam Mubarakzjanov:
A Note on Las Vegas OBDDs. Electron. Colloquium Comput. Complex. TR99 (1999) - Eric Allender, Igor E. Shparlinski, Michael E. Saks:
A Lower Bound for Primality. Electron. Colloquium Comput. Complex. TR99 (1999) - Matthias Krause, Petr Savický, Ingo Wegener:
Approximations by OBDDs and the variable ordering problem. Electron. Colloquium Comput. Complex. TR99 (1999) - Eric Allender, Andris Ambainis, David A. Mix Barrington, Samir Datta, Huong LeThanh:
Bounded Depth Arithmetic Circuits: Counting and Closure. Electron. Colloquium Comput. Complex. TR99 (1999) - Oded Goldreich, Amit Sahai, Salil P. Vadhan:
Can Statistical Zero Knowledge be made Non-Interactive? or On the Relationship of SZK and NISZK. Electron. Colloquium Comput. Complex. TR99 (1999) - Alexander A. Razborov, Nikolai K. Vereshchagin:
One Property of Cross-Intersecting Families. Electron. Colloquium Comput. Complex. TR99 (1999) - Irit Dinur, Shmuel Safra:
On the Hardness of Approximating Label Cover. Electron. Colloquium Comput. Complex. TR99 (1999) - Irit Dinur:
Approximating SVPinfty to within Almost-Polynomial Factors is NP-hard. Electron. Colloquium Comput. Complex. TR99 (1999) - Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, Alex Samorodnitsky:
Improved Testing Algorithms for Monotonicity. Electron. Colloquium Comput. Complex. TR99 (1999) - Manindra Agrawal, Somenath Biswas:
Reducing Randomness via Chinese Remaindering. Electron. Colloquium Comput. Complex. TR99 (1999) - Detlef Sieling:
Lower Bounds for Linear Transformed OBDDs and FBDDs. Electron. Colloquium Comput. Complex. TR99 (1999) - Marek Karpinski:
Randomized Complexity of Linear Arrangements and Polyhedra. Electron. Colloquium Comput. Complex. TR99 (1999) - Igor E. Shparlinski:
On the Uniformity of Distribution of a Certain Pseudo-Random Function. Electron. Colloquium Comput. Complex. TR99 (1999) - Eli Ben-Sasson, Avi Wigderson:
Short Proofs are Narrow - Resolution made Simple. Electron. Colloquium Comput. Complex. TR99 (1999) - Amir Shpilka, Avi Wigderson:
Depth-3 Arithmetic Formulae over Fields of Characteristic Zero. Electron. Colloquium Comput. Complex. TR99 (1999) - Oded Goldreich, Shafi Goldwasser, Silvio Micali:
Interleaved Zero-Knowledge in the Public-Key Model. Electron. Colloquium Comput. Complex. TR99 (1999) - Yonatan Aumann, Johan Håstad, Michael O. Rabin, Madhu Sudan:
Linear Consistency Testing. Electron. Colloquium Comput. Complex. TR99 (1999) - Miklós Ajtai:
A Non-linear Time Lower Bound for Boolean Branching Programs. Electron. Colloquium Comput. Complex. TR99 (1999) - Marek Karpinski, Igor E. Shparlinski:
On the Computational Hardness of Testing Square-Freeness of Sparse Polynomials. Electron. Colloquium Comput. Complex. TR99 (1999) - Stefan Edelkamp, Ingo Wegener:
On the performance of WEAK-HEAPSORT. Electron. Colloquium Comput. Complex. TR99 (1999) - Ilya Dumer, Daniele Micciancio, Madhu Sudan:
Hardness of Approximating the Minimum Distance of a Linear Code. Electron. Colloquium Comput. Complex. TR99 (1999) - Meena Mahajan, P. R. Subramanya, V. Vinay:
A Combinatorial Algorithm for Pfaffians. Electron. Colloquium Comput. Complex. TR99 (1999)