22 citations · 26 across the 2 of their papers we have counts for
3 papers
Minimum Circuit Size, Graph Isomorphism, and Related Problems
Eric Allender, Joshua A. Grochow, Dieter van Melkebeek +2
We study the computational power of deciding whether a given truth-table can be described by a circuit of a given size (the Minimum Circuit Size Problem, or MCSP for short), and of…
A Quantum Time-Space Lower Bound for the Counting Hierarchy
Dieter van Melkebeek, Thomas Watson
We obtain the first nontrivial time-space lower bound for quantum algorithms solving problems related to satisfiability. Our bound applies to MajSAT and MajMajSAT, which are comple…
On the Quantum Black-Box Complexity of Majority
Thomas Hayes, Samuel Kutin, Dieter van Melkebeek
We describe a quantum black-box network computing the majority of N bits with zero-sided error eps using only 2N/3 + O(sqrt{N (log log N + log 1/eps)}) queries: the algorithm retur…