Bounds for Small-Error and Zero-Error Quantum Algorithms
H. Buhrman, R. Cleve, R. de Wolf et al. · 1999
Abstract onlyNot checked
Computational Theory and Mathematics
Filters3 filters applied
Status
- Not checked
- From publisher notices and Retraction Watch. Not checked means nobody has looked yet.
Year
22 papersQuestions on this topic
The phase transition in random Horn satisfiability and its algorithmic implications
Gabriel Istrate · 1999
Abstract onlyNot checked
Knowledge in Multi-Agent Systems: Initial Configurations and Broadcast
A. R. Lomuscio, R. van der Meyden, M. D. Ryan · 1999
Abstract onlyNot checked
Polynomial-Time Multi-Selectivity
Lane A. Hemaspaandra, Zhigen Jiang, Joerg Rothe et al. · Journal of Universal Computer Science vol. 3, no. 3, pp. 197--229, 1997 · 1999
Abstract onlyNot checked
Robust Reductions
Jin-Yi Cai, Lane A. Hemaspaandra, Gerd Wechsung · 1999
Abstract onlyNot checked
R_{1-tt}^{SN}(NP) Distinguishes Robust Many-One and Turing Completeness
Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel · Theory of Computing Systems, 31, 307-325, 1998 · 1999
Abstract onlyNot checked
A Second Step Towards Complexity-Theoretic Analogs of Rice's Theorem
Lane A. Hemaspaandra, Joerg Rothe · 1999
Abstract onlyNot checked
Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets
Lane A. Hemaspaandra, Joerg Rothe · SIAM Journal on Computing vol. 26, no. 3, pp. 634--653, 1997 · 1999
Abstract onlyNot checked
Translating Equality Downwards
Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel · 1999
Abstract onlyNot checked
Two-way finite automata with quantum and classical states
Andris Ambainis, John Watrous · 1999
Abstract onlyNot checked
PSPACE has 2-round quantum interactive proof systems
John Watrous · 1999
Abstract onlyNot checked
An Introduction to Query Order
Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel · Bulletin of the EATCS, 63, 93-107, 1997 · 1999
Abstract onlyNot checked
Raising NP Lower Bounds to Parallel NP Lower Bounds
Edith Hemaspaandra, Lane A. Hemaspaandra, Joerg Rothe · SIGACT News vol. 28, no. 2, pp. 2--13, 1997 · 1999
Abstract onlyNot checked
Average-Case Complexity of Shellsort
Tao Jiang, Ming Li, Paul Vitanyi · 1999
Abstract onlyNot checked
Reasoning About Common Knowledge with Infinitely Many Agents
Joseph Y. Halpern, Richard A. Shore · 1999
Abstract onlyNot checked
Mutual Search
Harry Buhrman, Matthew Franklin, Juan A. Garay et al. · 1999
Abstract onlyNot checked
Query Order and the Polynomial Hierarchy
Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel · Journal of Universal Computer Science, 4, 574-588, 1998 · 1999
Abstract onlyNot checked
On the Power of Positive Turing Reductions
Edith Hemaspaandra · 1999
Abstract onlyNot checked
Minimum Cuts in Near-Linear Time
David R. Karger · 1998
Abstract onlyNot checked
Tally NP Sets and Easy Census Functions
Judy Goldsmith, Mitsunori Ogihara, Joerg Rothe · 1998
Abstract onlyNot checked