default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDElectronic Colloquium on Computational Complexity, 1999
Volume TR99, 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. - Juraj Hromkovic, Georg Schnitger:
On the Power of Las Vegas II: Two-Way Finite Automata. - Eric Allender, Vikraman Arvind, Meena Mahajan:
Arithmetic Complexity, Kleene Closure, and Formal Power Series. - Marek Karpinski, Rustam Mubarakzjanov:
A Note on Las Vegas OBDDs. - Eric Allender, Igor E. Shparlinski, Michael E. Saks:
A Lower Bound for Primality. - 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. - Alexander A. Razborov, Nikolai K. Vereshchagin:
One Property of Cross-Intersecting Families. - Irit Dinur, Shmuel Safra:
On the Hardness of Approximating Label Cover. - 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. - Manindra Agrawal, Somenath Biswas:
Reducing Randomness via Chinese Remaindering. - Detlef Sieling:
Lower Bounds for Linear Transformed OBDDs and FBDDs. - Marek Karpinski:
Randomized Complexity of Linear Arrangements and Polyhedra. - Igor E. Shparlinski:
On the Uniformity of Distribution of a Certain Pseudo-Random Function. - Eli Ben-Sasson, Avi Wigderson:
Short Proofs are Narrow - Resolution made Simple. - Amir Shpilka, Avi Wigderson:
Depth-3 Arithmetic Formulae over Fields of Characteristic Zero. - Oded Goldreich, Shafi Goldwasser, Silvio Micali:
Interleaved Zero-Knowledge in the Public-Key Model. - Yonatan Aumann, Johan Håstad, Michael O. Rabin, Madhu Sudan:
Linear Consistency Testing. - Miklós Ajtai:
A Non-linear Time Lower Bound for Boolean Branching Programs. - Marek Karpinski, Igor E. Shparlinski:
On the Computational Hardness of Testing Square-Freeness of Sparse Polynomials. - Stefan Edelkamp, Ingo Wegener:
On the performance of WEAK-HEAPSORT. - Ilya Dumer, Daniele Micciancio, Madhu Sudan:
Hardness of Approximating the Minimum Distance of a Linear Code. - Meena Mahajan, P. R. Subramanya, V. Vinay:
A Combinatorial Algorithm for Pfaffians. - 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. - Vikraman Arvind, Johannes Köbler:
Graph Isomorphism is Low for ZPPNP and other Lowness results. - 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. - Johan Håstad, Mats Näslund:
The Security of all RSA and Discrete Log Bits. - 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. - Ran Canetti, Oded Goldreich, Shafi Goldwasser, Silvio Micali:
Resettable Zero-Knowledge. - 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. - Valentine Kabanets, Jin-yi Cai:
Circuit Minimization Problem. - 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.
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-10-17 20:32 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
