1.2k citations · 3.7k across the 62 of their papers we have counts for
10 papers · 1 filter
Noisy decoding by shallow circuits with parities: classical and quantum
Jop Briët, Harry Buhrman, Davi Castro-Silva +1
We consider the problem of decoding corrupted error correcting codes with NC circuits in the classical and quantum settings. We show that any such classical circuit can…
Matching Triangles and Triangle Collection: Hardness based on a Weak Quantum Conjecture
Andris Ambainis, Harry Buhrman, Koen Leijnse +2
Classically, for many computational problems one can conclude time lower bounds conditioned on the hardness of one or more of key problems: k-SAT, 3SUM and APSP. More recently, sim…
Reductions to the set of random strings: The resource-bounded case
Eric Allender, Harry Buhrman, Luke Friedman +1
This paper is motivated by a conjecture that BPP can be characterized in terms of polynomial-time nonadaptive reductions to the set of Kolmogorov-random strings. In this paper we s…
The non-adaptive query complexity of testing k-parities
Harry Buhrman, David Garcia-Soriano, Arie Matsliah +1
We prove tight bounds of Theta(k log k) queries for non-adaptively testing whether a function f:{0,1}^n -> {0,1} is a k-parity or far from any k-parity. The lower bound combines a…
Derandomizing from Random Strings
Harry Buhrman, Lance Fortnow, Michal Koucký +1
In this paper we show that BPP is truth-table reducible to the set of Kolmogorov random strings R_K. It was previously known that PSPACE, and hence BPP is Turing-reducible to R_K.…
Individual Communication Complexity
Harry Buhrman, Hartmut Klauck, Nikolai Vereshchagin +1
We initiate the theory of communication complexity of individual inputs held by the agents, rather than worst-case or average-case. We consider total, partial, and partially correc…
Communication Complexity Lower Bounds by Polynomials
Harry Buhrman, Ronald de Wolf
The quantum version of communication complexity allows the two communicating parties to exchange qubits and/or to make use of prior entanglement (shared EPR-pairs). Some lower boun…
Bounds for Small-Error and Zero-Error Quantum Algorithms
H. Buhrman, R. Cleve, R. de Wolf +1
We present a number of results related to quantum algorithms with small error probability and quantum algorithms that are zero-error. First, we give a tight analysis of the trade-o…
New Applications of the Incompressibility Method: Part I
Tao Jiang, Ming Li, Paul Vitanyi
The incompressibility method is an elementary yet powerful proof technique. It has been used successfully in many areas. To further demonstrate its power and elegance we exhibit ne…
New Applications of the Incompressibility Method: Part II
Harry Buhrman, Tao Jiang, Ming Li +1
The incompressibility method is an elementary yet powerful proof technique. It has been used successfully in many areas. To further demonstrate its power and elegance we exhibit ne…