Electronic Colloquium on Computational Complexity, Volume 6, 1999
Volume 6, 1999
Detlef Sieling: The Complexity of Minimizing FBDDs.- Oded Goldreich, Daniele Micciancio, Shmuel Safra, Jean-Pierre Seifert: Approximating Shortest Lattice Vectors is Not Harder Than Approximating Closest Lattice Vectors.
- Stephen A. Fenner, Frederic Green, Steven Homer, Randall Pruim: Determining Acceptance Possibility for a Quantum Computation is Hard for the Polynomial Hierarchy.
- Valentine Kabanets: Almost k-Wise Independence and Boolean Functions Hard for Read-Once Branching Programs.
- Michael Schmitt: On the Sample Complexity for Nonoverlapping Neural Networks.
- Jin-yi Cai: Some Recent Progress on the Complexity of Lattice Problems.
- Eric Allender, Vikraman Arvind, Meena Mahajan: Arithmetic Complexity, Kleene Closure, and Formal Power Series.
- Matthias Krause, Petr Savický, Ingo Wegener: Approximations by OBDDs and the variable ordering problem.
- Eric Allender, Andris Ambainis, David A. Mix Barrington, Samir Datta, Huong LeThanh: Bounded Depth Arithmetic Circuits: Counting and Closure.
- Oded Goldreich, Amit Sahai, Salil P. Vadhan: Can Statistical Zero Knowledge be made Non-Interactive? or On the Relationship of SZK and NISZK.
- Irit Dinur: Approximating SVPinfty to within Almost-Polynomial Factors is NP-hard.
- Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, Alex Samorodnitsky: Improved Testing Algorithms for Monotonicity.
- Detlef Sieling: Lower Bounds for Linear Transformed OBDDs and FBDDs.
- Marek Karpinski: Randomized Complexity of Linear Arrangements and Polyhedra.
- Igor Shparlinski: On the Uniformity of Distribution of a Certain Pseudo-Random Function.
- Oded Goldreich, Shafi Goldwasser, Silvio Micali: Interleaved Zero-Knowledge in the Public-Key Model. .
- Miklós Ajtai: A Non-linear Time Lower Bound for Boolean Branching Programs.
- Marek Karpinski, Igor Shparlinski: On the Computational Hardness of Testing Square-Freeness of Sparse Polynomials.
- Ilya Dumer, Daniele Micciancio, Madhu Sudan: Hardness of Approximating the Minimum Distance of a Linear Code.
- 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.
- Cristopher Moore: Quantum Circuits: Fanout, Parity, and Counting.
- Wolfgang Merkle: The Global Power of Additional Queries to p-random Oracles.
- Leonard J. Schulman: Clustering for Edge-Cost Minimization.
- Edward A. Hirsch: A New Algorithm for MAX-2-SAT.
- Peter Jonsson, Paolo Liberatore: On the Complexity of Finding Satisfiable Subinstances in Constraint Satisfaction.
- Johan Håstad: On approximating CSP-B.
- Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson: Space Complexity in Propositional Calculus.
- Oliver Kullmann: Investigating a general hierarchy of polynomially decidable classes of CNF's based on short tree-like resolution proofs.
- Venkatesan Guruswami: The Approximability of Set Splitting Problems and Satisfiability Problems with no Mixed Clauses.
- Farid M. Ablayev: On Complexity of Regular (1,+k)-Branching Programs.
- Ran Raz, Omer Reingold, Salil P. Vadhan: Extracting All the Randomness and Reducing the Error in Trevisan's Extractors.
- Wolfgang Slany: Graph Ramsey games.
- Beate Bollig, Ingo Wegener: Asymptotically Optimal Bounds for OBDDs and the Solution of Some Basic OBDD Problems.
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-06-18T211851 by the dblp team