Does the Polynomial Hierarchy Collapse if Onto Functions are Invertible? (2009)
Harry Buhrman, Lance Fortnow, John D. Rogers, Nikolay Vereshchagin
Abstract. The class TFNP, defined by Megiddo and Papadimitriou, consists of multivalued functions with values that are polynomially verifiable and guaranteed to exist. Do we have evidence that such...
Randomised Individual Communication Complexity (2009)
Harry Buhrman, Nikolai Vereshchagin
In this paper we study the individual communication complexity of the following problem. Alice receives an input string x and Bob an input string y, and Alice has to output y. For deterministic...
Van Der Gulik, Peter, Massar, Serge, Gilis, Dimitri, Buhrman, Harry, Rooman, Marianne
The issues we attempt to tackle here are what the first peptides did look like when they emerged on the primitive earth, and what simple catalytic activities they fulfilled. We conjecture that the...
Some mathematical refinements concerning error minimization in the genetic code (2009)
Buhrman, Harry, Kelk, Steven M., Koolen, Wouter M., Stougie, Leen
The genetic code is known to have a high level of error robustness and has been shown to be very error robust compared to randomly selected codes, but to be significantly less error robust than a...
NP-Hard Sets are Exponentially Dense Unless coNP ⊆ NP/poly (2009)
Harry Buhrman, John M. Hitchcock
We show that hard sets S for NP must have exponential density, i.e. |S=n | ≥ 2nɛ some ɛ> 0 and infinitely many n, unless coNP ⊆ NP/poly and the polynomial-time hierarchy collapses. This...
A Post's Program For Complexity Theory (2009)
Jacobo Torán, Harry Buhrman, Leen Torenvliet
Some of the most important and chalenging problems in complexity theory deal with the separation of complexity classes. Apart from the results derived from the hierarchy theorems and some lower...
Non-locality and Communication Complexity (2009)
Buhrman, Harry, Cleve, Richard, Massar, Serge, De Wolf, Ronald
Quantum information processing is the emerging field that defines and realizes computing devices that make use of quantum mechanical principles, like the superposition principle, entanglement, and...
Arbitrarily little knowledge can give a quantum advantage for nonlocal tasks (2009)
Allcock, Jonathan, Buhrman, Harry, Linden, Noah
It has previously been shown that quantum nonlocality offers no benefit over classical correlations for performing a distributed task known as nonlocal computation. This is where separated parties...
Harry Buhrman, Troy Lee, Dieter Van Melkebeek
The language compression problem asks for succinct descriptions of the strings in a language A such that the strings can be efficiently recovered from their description when given a membership oracle...
A generalized Grothendieck inequality and entanglement in XOR games (2009)
Briët, Jop, Buhrman, Harry, Toner, Ben
Suppose Alice and Bob make local two-outcome measurements on a shared entangled state. For any d, we show that there are correlations that can only be reproduced if the local dimension is at least d....
Andris Ambainis, Harry Buhrman, William Gasarch, Bala Kalyanasundaram, Leen Torenvliet
Let k, n ∈ N and f: {0, 1} n × {0, 1} n → {0, 1}. Assume Alice has x1,..., xk ∈ {0, 1} n, Bob has y1,..., yk ∈ {0, 1} n, and they want to compute f k (x1x2 · · · xk, y1y2 · · · yk) =...
NP-Hard Sets are Exponentially Dense Unless coNP ⊆ NP/poly (2008)
Harry Buhrman, John M. Hitchcock
We show that hard sets S for NP must have exponential density, for some ɛ> 0 and infinitely many n, unless coNP ⊆ i.e. |S=n | ≥ 2nɛ NP/poly and the polynomial-time hierarchy collapses. This...
NP-Hard Sets are Exponentially Dense Unless (2008)
Harry Buhrman, John M. Hitchcock
Abstract We show that hard sets S for NP must have exponential density, i.e. |S=n |> = 2n ffl for some ffl> 0 and infinitely many n, unless coNP ` NP/poly and the polynomial-time hierarchy...
Possibility, impossibility, and cheat sensitivity of quantum-bit string commitment (2008)
Buhrman, Harry, Christandl, Matthias, Hayden, Patrick, Lo, Hoi-Kwong, Wehner, Stephanie
High Entropy Random Selection Protocols [Extended Abstract] (2008)
Harry Buhrman, Matthias Christ, Zvi Lotker, Nikolai Vereshchagin
Abstract. We study the two party problem of randomly selecting a string among all the strings of length n. We want the protocol to have the property that the output distribution has high entropy,...
Sparse Selfreducible Sets and Polynomial Size Circuit (2008)
Lower Bounds, Harry Buhrman, Leen Torenvliet
Abstract. It is well-known that the class of sets that can be computed by polynomial size circuits is equal to the class of sets that are polynomial time reducible to a sparse set. It is widely...
First Of All, I Prof, Harry Buhrman
the Centrum voor Wiskunde en Informatica (CWI) in Amsterdam for all the help and his time he spent with me. I also thank him for his useful remarks regarding the thesis and many discussions about...
Inverting Onto Functions and Polynomial Hierarchy (2008)
Harry Buhrman, Lance Fortnow, John D. Rogers, Nikolay Vereshchagin
Abstract. The class TFNP, defined by Megiddo and Papadimitriou, consists of multivalued functions with values that are polynomially verifiable and guaranteed to exist. Do we have evidence that such...
Individual Communication Complexity ⋆ Extended Abstract (2008)
Harry Buhrman, Hartmut Klauck, Nikolai Vereshchagin, Paul Vitányi
Abstract. 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 correct...
Enumerations of the Kolmogorov Function (2008)
Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, ...
A recursive enumerator for a function h is an algorithm f which enumerates for an input x finitely many elements including h(x). f is an k(n)-enumerator if for every input x of length n, h(x) is...
Inverting Onto Functions and Polynomial Hierarchy (2008)
Harry Buhrman, Lance Fortnow, John D. Rogers, Nikolay Vereshchagin
Abstract. The class TFNP, defined by Megiddo and Papadimitriou, consists of multivalued functions with values that are polynomially verifiable and guaranteed to exist. Do we have evidence that such...
Some results on derandomization (2008)
Harry Buhrman, Lance Fortnow, A. Pavan
We show several results about derandomization including
Enumerations of the Kolmogorov Function (2008)
Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, ...
A recursive enumerator for a function h is an algorithm f which enumerates
Enumerations of the Kolmogorov Function (2008)
Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, ...
A recursive enumerator for a function h is an algorithm f which enumerates
Inverting Onto Functions and Polynomial Hierarchy (2008)
Harry Buhrman, Lance Fortnow, John D. Rogers, Nikolay Vereshchagin
Abstract. The class TFNP, defined by Megiddo and Papadimitriou, consists of multivalued functions with values that are polynomially verifiable and guaranteed to exist. Do we have evidence that such...
Some results on derandomization (2008)
Harry Buhrman, Lance Fortnow, A. Pavan
We show several results about derandomization including
‘Computational Complexity of Quantum Hamiltonian Systems ’ in Leiden. (2008)
Supervisors Prof, Dr. Harry Buhrman, Committee Members, Prof Dr, Harry Buhrman, Christian Schaffner, ...
A survey of classical simulation methods
07411 Executive Summary -- Algebraic Methods in Computational Complexity (2008)
Agrawal, Manindra, Buhrman, Harry, Fortnow, Lance, Thierauf, Thomas
The seminar brought together almost 50 researchers covering a wide spectrum of complexity theory. The focus on algebraic methods showed once again the great importance of algebraic techniques for...
07411 Abstracts Collection -- Algebraic Methods in Computational Complexity (2008)
Agrawal, Manindra, Buhrman, Harry, Fortnow, Lance, Thierauf, Thomas
From 07.10. to 12.10., the Dagstuhl Seminar 07411 ``Algebraic Methods in Computational Complexity'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the...
High Entropy Random Selection Protocols (2008)
Vereshchagin, Nikolai K., Buhrman, Harry, Cristandl, Matthias, Koucky, Michal, Lotker, Zvi, Patt-Shamir, Boaz
We study the two party problem of randomly selecting a string among all the strings of length n. We want the protocol to have the property that the output distribution has high entropy, even when one...
Harry Buhrman, Tao Jiang, Ming Li
The incompressibility method is an elementary yet powerful proof technique based on Kolmogorov complexity. It has been used successfully in many areas [8]. To further demonstrate its power and...
Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, Ronald De Wolf
quant-ph/9802049 v3
Harry Buhrman, Mark Heiligman, Miklos Santha, Ronald De Wolf
We present several applications of quantum amplitude amplication to nding claws and collisions in ordered or unordered functions. Our algorithms generalize those of Brassard, Hyer, and Tapp, and...
The Communication Complexity of Enumeration, Elimination, and Selection (2007)
Andris Ambainis Univ, Andris Ambainis, Harry Buhrman, William Gasarch, Bala Kalyanasundaram, Leen Torenvliet, ...
Let f : {0, 1} n {0, 1} n # {0, 1}. Assume Alice has x 1 , . . . , x k # {0, 1} n , Bob has y 1 , . . . , y k # {0, 1} n , and they want to compute f(x 1 , y 1 ) f(x k , y k ) communicating as few...
Optimal Resiliency against Mobile Faults (2007)
Exte Nd Ed, Harry Buhrman, Juan A. Garay, Jaap-henk Hoepman
) Harry Buhrman Juan A. Garay y Jaap-Henk Hoepman CWI IBM T.J. Watson Research Center CWI P.O. Box 94070 P.O. Box 704 P.O. Box 94070 1090 GB Amsterdam Yorktown Heights, NY 10598 1090 GB Amsterdam The...
Complete Sets under Non-Adaptive Reductions are Scarce (2007)
Harry Buhrman, Dieter Van Melkebeek
We investigate the frequency of complete sets for various complexity classes within EXP under non-adaptive reductions in the sense of resource bounded measure. We show that these sets are rare: ffl...
A Generalization of Resource-Bounded Measure, With Application to the BPP vs. EXP Problem (2007)
Harry Buhrman Cwi, Harry Buhrman, Dieter Van Melkebeek, Kenneth W. Regan, D. Sivakumar, Martin Strauss
We introduce resource-bounded betting games, and propose a generalization of Lutz's resourcebounded measure in which the choice of next string to bet on is fully adaptive. Lutz's...
Complete Sets under Non-Adaptive Reductions are Scarce (2007)
Harry Buhrman, Dieter Van Melkebeek
We investigate the frequency of complete sets for various complexity classes within EXP under non-adaptive reductions in the sense of resource bounded measure. We show that these sets are rare: ffl...
Characterizing the Learnability of Kolmogorov Easy Circuit Expressions (2007)
Jos'e Balc'azar, Harry Buhrman
We show that Kolmogorov easy circuit expressions can be learned with membership queries in polynomial time if and only if every NE-predicate is E-solvable. Moreover we show that the previously known...
A Generalization of Resource-Bounded Measure, With Application to the BPP vs. EXP Problem (2007)
Harry Buhrman, Dieter Van Melkebeek, Kenneth W., Kenneth W. Regan, D. Sivakumar, Martin Strauss
We introduce resource-bounded betting games, and propose a generalization of Lutz's resourcebounded measure in which the choice of next string to bet on is fully adaptive. Lutz's...
Harry Buhrman, Steven Homer, Leen Torenvliet
We demonstrate differences between reducibilities and corresponding completeness notions for nondeterministic time and space classes. For time classes the studied completeness notions under...
Richard Beigel, Harry Buhrman, Lance Fortnow, U. Chicago
We construct an oracle A such that P
Harry Buhrman, Richard Chang, Lance Fortnow
The results in this paper show that coNP is contained in NP with 1 bit of advice (denoted NP=1) if and only if the Polynomial Hierarchy (PH) collapses to D P, the second level of the Boolean...
Optimal Resiliency against Mobile Faults (Extended Abstract) (2007)
Harry Buhrman, Juan A. Garay, Jaap-henk Hoepman
In this paper we consider a model where malicious agents can corrupt hosts and move around in a network of processors. We consider a family of mobile-fault models MF ( t n−1, ρ). In MF ( t n−1,...
Harry Buhrman, Richard Cleve, John Watrous, Ronald De Wolf
Classical ngerprinting associates with each string a shorter string (its ngerprint), such that, with high probability, any two distinct strings can be distinguished by comparing their ngerprints...
Andris Ambainis, Harry Buhrman, William Gasarch, Bala Kalyanasundaram, Leen Torenvliet
N and f: {0,
Harry Buhrman, Thomas Thierauf
Abstract. We consider the following questions: 1. Can one compute satisfying assignments for satisfiable Boolean formulas in polynomial time with parallel queries to NP? 2. Is the unique optimal...
Harry Buhrman, Cwi Amsterdam, Jim Kadin, Thomas Thierauf
k, the class of functions that can be computed in polynomial time with nonadaptive queries to an NP oracle. This is motivated by the question of whether it is possible to compute witnesses for NP...
Some results on derandomization (2007)
We show several results about derandomization including 1. If NP is easy on average then ecient pseudorandom generators exist and P = BPP. 2. If NP is easy on average then given an NP machine M we...
Harry Buhrman, Alessandro Panconesi, Riccardo Silvestri, Paul Vitanyi
We show that Naming-- the existence of distinct IDs known to all-- is a hidden, but necessary, assumption of Herlihy's universality result for Consensus. We then show in a very precise sense...
Harry Buhrman, Richard Cleve, John Watrous, Ronald De Wolf
Classical ngerprinting associates with each string a shorter string (its ngerprint), such that, with high probability, any two distinct strings can be distinguished by comparing their ngerprints...
We prove a general upper bound on the tradeoff between time and space that suffices for the reversible simulation of irreversible computation. Previously, only simulations using exponential time or...
Richard Beigel, Harry Buhrman, Lance Fortnow, Leen Torenvliet
We consider the hardness of enumerating k possible values for the Kolmogorov complexity function C(x) so that one of them is correct. We show several results including Any computable enumerator for...
Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, Ronald De Wolf, Name Robert Beals, ...
A preliminary version of this paper was presented at FOCS'98 [Beals et al. 1998]. HB and RdW are partially supported by EU fth framework program QAIP, IST-1999-11234. RC and MM gratefully...
Twenty Questions to a P-selector (2007)
Harry Buhrman, Leen Torenvliet, Peter Emde Boas
We show in this note, that any set that is positive Turing reducible to a p-selective set is in fact many-one reducible to this set. Therefore, such a set is itself p-selective. 1
Abstract. The results in this paper show that coNP is contained in NP with 1 bit of advice (denoted NP=1) if and only if the Polynomial Hierarchy (PH) collapses to D P, the second level of the...
Enumerations of the Kolmogorov Function (2007)
Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpre, ...
Torenvliet i A recursive enumerator for a function h is an algorithm f which enumerates for an input x finitely many elements including h(x). f is an k(n)-enumerator if for every input x of length n,...
Some results on derandomization (2007)
Harry Buhrman, Lance Fortnow, A. Pavan
We show several results about derandomization including 1. If NP is easy on average then e#cient pseudorandom generators exist and P = BPP. 2. If NP is easy on average then given an NP machine M we...
Two Oracles that Force a Big Crunch (2007)
Harry Buhrman, Stephen Fenner, Lance Fortnow, Leen Torenvliet
We construct an oracle A such that NEXP . The construction of this oracle answers a long standing open question rst posed by Heller, and unsuccessfully attacked many times since. For the rst...
On computation and communication with small bias (2007)
We present two results for computational models that allow error probabilities close to 1/2. First, most computational complexity classes have an analogous class in communication complexity. The...
Harry Buhrman, Benjamin Hescott, Steven Homer, Leen Torenvliet
Reductions and completeness notions form the heart of computational complexity theory. Recently non-uniform reductions have been naturally introduced in a variety of settings concerning completeness...
High Entropy Random Selection Protocols (2007)
Harry Buhrman, Boaz Patt-shamir, Matthias Christandl, Zvi Lotker, Nikolai Vereshchagin
We study the two party problem of randomly selecting a string among all the strings of length n. We want the protocol to have the property that the output distribution has high entropy, even when one...
Security of quantum bit string commitment depends on the information measure (2006)
Buhrman, Harry, Christandl, Matthias, Hayden, Patrick, Lo, Hoi-Kwong, Wehner, Stephanie
Unconditionally secure non-relativistic bit commitment is known to be impossible in both the classical and the quantum world. However, when committing to a string of n bits at once, how far can we...
Enumerations of the Kolmogorov function (2006)
Beigel, Richard, Buhrman, Harry, Fejer, Peter, Fortnow, Lance, Grabowski, Piotr, Longpré, Luc, ...
A recursive enumerator for a function h is an algorithm f which enumerates for an input x finitely many elements including h(x). f is a k(n)-enumerator if for every input x of length n, h(x) is among...
New Limits on Fault-Tolerant Quantum Computation (2006)
Buhrman, Harry, Cleve, Richard, Laurent, Monique, Linden, Noah, Schrijver, Alexander, Unger, Falk
We show that quantum circuits cannot be made fault-tolerant against a depolarizing noise level of approximately 45%, thereby improving on a previous bound of 50% (due to Razborov). Our precise...
Quantum Information, Computation and Complexity * Programme at the Institut Henri Poincaré, January 4th April 7th, 2006 * Organizers: Ph.Grangier, M.Santha and D.L.Shepelyansky * Lectures have...
Quantum Information, Computation and Complexity * Programme at the Institut Henri Poincaré, January 4th April 7th, 2006 * Organizers: Ph.Grangier, M.Santha and D.L.Shepelyansky * Lectures have...
Individual communication complexity (2006)
Harry Buhrman, Hartmut Klauck, Nikolai Vereshchagin
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 correct protocols,...
New limits on fault-tolerant quantum computation (2006)
Harry Buhrman, Monique Laurent, Noah Linden, Alexander Schrijver
A limit on nonlocality in any world in which communication complexity is not trivial (2005)
Brassard, Gilles, Buhrman, Harry, Linden, Noah, Methot, Andre A., Tapp, Alain, Unger, Falk
Bell proved that quantum entanglement enables two space-like separated parties to exhibit classically impossible correlations. Even though these correlations are stronger than anything classically...
Implications of Superstrong Nonlocality for Cryptography (2005)
Buhrman, Harry, Christandl, Matthias, Unger, Falk, Wehner, Stephanie, Winter, Andreas
Non-local boxes are hypothetical ``machines'' that give rise to superstrong non-local correlations, leading to a stronger violation of Bell/CHSH inequalities than is possible within the framework of...
Possibility, Impossibility and Cheat-Sensitivity of Quantum Bit String Commitment (2005)
Buhrman, Harry, Christandl, Matthias, Hayden, Patrick, Lo, Hoi-Kwong, Wehner, Stephanie
Unconditionally secure non-relativistic bit commitment is known to be impossible in both the classical and the quantum worlds. But when committing to a string of n bits at once, how far can we...
Harry Buhrman, Ro Panconesi, Riccardo Silvestri, Paul Vitanyi
Abstract. We show that Naming – the existence of distinct IDs known to all – is a hidden, but necessary, assumption of Herlihy’s universality result for Consensus. We then show in a very...
Robust polynomials and quantum algorithms (2005)
Harry Buhrman, Ilan Newman, Hein Röhrig, Ronald De Wolf
We define and study the complexity of robust polynomials for Boolean functions and the related fault-tolerant quantum decision trees, where input bits are perturbed by noise. We show that, in...
Robust polynomials and quantum algorithms (2005)
Harry Buhrman, Ilan Newman, Hein Röhrig, Ronald De Wolf
Abstract. We define and study the complexity of robust polynomials for Boolean functions and the related fault-tolerant quantum decision trees, where input bits are perturbed by noise. We show that,...
Robust polynomials and quantum algorithms (2005)
Harry Buhrman, Ilan Newman, Hein Röhrig, Ronald De Wolf
We define and study the complexity of robust polynomials for Boolean functions and the related fault-tolerant quantum decision trees, where input bits are perturbed by noise. We compare several...
04421 Abstracts Collection -- Algebraic Methods in Computational Complexity (2005)
Buhrman, Harry, Fortnow, Lance, Thierauf, Thomas
From 10.10.04 to 15.10.04, the Dagstuhl Seminar 04421 ``Algebraic Methods in Computational Complexity'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During...
Quantum Verification of Matrix Products (2004)
Buhrman, Harry, Spalek, Robert
We present a quantum algorithm that verifies a product of two n*n matrices over any field with bounded error in worst-case time n^{5/3} and expected time n^{5/3} / min(w,sqrt(n))^{1/3}, where w is...
Separating complexity classes using structural properties (2004)
Harry Buhrman, Leen Torenvliet
We study the robustness of complete sets for various complexity classes. A complete set A is robust if for any f(n)-dense set S ∈ P, A − S is still complete, where f(n) ranges from log(n),...
What Can be Efficiently Reduced to the Kolmogorov-Random Strings? (2004)
Eric Allender, Harry Buhrman, Michal Koucký
We investigate the question of whether one can characterize complexity classes (such as PSPACE or NEXP) in terms of efficient reducibility to the set of Kolmogorov-random strings R_C. We show that...
Robust Polynomials and Quantum Algorithms (2003)
Buhrman, Harry, Newman, Ilan, Roehrig, Hein, De Wolf, Ronald
We define and study the complexity of robust polynomials for Boolean functions and the related fault-tolerant quantum decision trees, where input bits are perturbed by noise. We compare several...
Multiparty Quantum Coin Flipping (2003)
Ambainis, Andris, Buhrman, Harry, Dodis, Yevgeniy, Roehrig, Hein
We investigate coin-flipping protocols for multiple parties in a quantum broadcast setting: (1) We propose and motivate a definition for quantum broadcast. Our model of quantum broadcast channel is...
Individual Communication Complexity (2003)
Buhrman, Harry, Klauck, Hartmut, Vereshchagin, Nikolai, Vitanyi, Paul
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 correct protocols,...
Quantum property testing (2003)
Harry Buhrman, Lance Fortnow, Ilan Newman
Hein R"ohrig \Lambda \Lambda
Quantum property testing (2003)
Harry Buhrman, Lance Fortnow, Ilan Newman
A language L has a property tester if there exists a probabilistic algorithm that given an input x only asks a small number of bits of x and distinguishes the cases as to whether x is in L and x has...
Quantum property testing (2003)
Harry Buhrman, Lance Fortnow, Ilan Newman, Hein Röhrig
A language L has a property tester if there exists a probabilistic algorithm that given an input x only asks a small number of bits of x and distinguishes the cases as to whether x is in L and x has...
Harry Buhrman, Richard Chang, Lance Fortnow
Abstract. The results in this paper show that coNP is contained in NP with 1 bit of advice (denoted NP/1) if and only if the Polynomial Hierarchy (PH) collapses to D P, the second level of the...
Quantum property testing (2003)
Harry Buhrman, Lance Fortnow, Ilan Newman, Hein Röhrig
A language L has a property tester if there exists a probabilistic algorithm that given an input x only asks a small number of bits of x and distinguishes the cases as to whether x is in L and x has...
Quantum Zero-Error Algorithms Cannot be Composed (2002)
Buhrman, Harry, De Wolf, Ronald
We exhibit two black-box problems, both of which have an efficient quantum algorithm with zero-error, yet whose composition does not have an efficient quantum algorithm with zero-error. This shows...
Combinatorics and Quantum Nonlocality (2002)
Buhrman, Harry, Hoyer, Peter, Massar, Serge, Roehrig, Hein
We use techniques for lower bounds on communication to derive necessary conditions (in terms of detector efficiency or amount of super-luminal communication) for being able to reproduce the quantum...
On the Importance of Having an Identity or, is Consensus really Universal? (2002)
Buhrman, Harry, Panconesi, Alessandro, Silvestri, Riccardo, Vitanyi, Paul
We show that Naming-- the existence of distinct IDs known to all-- is a hidden but necessary assumption of Herlihy's universality result for Consensus. We then show in a very precise sense that...
Power from random strings (2002)
Eric Allender, Harry Buhrman, Dieter Melkebeek, Detlef Ronneburger
We show that sets consisting of strings of high Kolmogorov complexity provide examples of sets that are complete for several complexity classes under probabilistic and non-uniform reductions. These...
Harry Buhrman, Richard Chang, Lance Fortnow
The results in this paper show that coNP is contained in NP with 1 bit of advice (denoted NP/1) if and only if the Polynomial Hierarchy (PH) collapses to DP,thesecond level of the Boolean Hierarchy...
Power from random strings (2002)
Eric Allender, Harry Buhrman, Dieter Melkebeek, Detlef Ronneburger
We consider sets of strings with high Kolmogorov complexity, mainly in resource-bounded settings but also in the traditional recursion-theoretic sense. We present efficient reductions, showing that...
Power from Random Strings (2002)
Eric Allender, Harry Buhrman, Michal Koucky, Dieter Van Melkebeek, Detlef Ronneburger
We show that sets consisting of strings of high Kolmogorov complexity provide examples of sets that are complete for several complexity classes under probabilistic and non-uniform reductions. These...
Kolmogorov Random Graphs and the Incompressibility Method (2001)
Buhrman, Harry, Li, Ming, Tromp, John, Vitanyi, Paul
We investigate topological, combinatorial, statistical, and enumeration properties of finite graphs with high Kolmogorov complexity (almost all graphs) using the novel incompressibility method....
Buhrman, Harry, Cleve, Richard, Watrous, John, De Wolf, Ronald
Classical fingerprinting associates with each string a shorter string (its fingerprint), such that, with high probability, any two distinct strings can be distinguished by comparing their...
Time and Space Bounds for Reversible Simulation (2001)
Buhrman, Harry, Tromp, J., Vitanyi, Paul
We prove a general upper bound on the tradeoff between time and space that suffices for the reversible simulation of irreversible computation. Previously, only simulations using exponential time or...
Quantum Algorithms for Element Distinctness (2001)
Harry Buhrman, Christoph Dürr, Mark Heiligman, Peter Høyer, Frédéric Magniez, Miklos Santha, ...
We present several applications of quantum amplitude amplification to finding claws and collisions in ordered or unordered functions. Our algorithms generalize those of Brassard, Høyer, and Tapp,...
Quantum Entanglement and Communication Complexity (2001)
Harry Buhrman, Richard Cleve, Van Dam
Abstract. We consider a variation of the communication complexity scenario, where the parties are supplied with an extra resource: particles in an entangled quantum state. We note that...
Harry Buhrman, Richard Cleve, John Watrous, Ronald De Wolf
Classical fingerprinting associates with each string a shorter string (its fingerprint), such that, with high probability, any two distinct strings can be distinguished by comparing their...
Quantum Entanglement and Communication Complexity (2001)
Harry Buhrman, Harry Buhrman, Richard Cleve, Richard Cleve
See back inner page for a list of recent BRICS Report Series publications. Copies may be obtained by contacting: BRICS
Quantum Algorithms for Element Distinctness (2001)
Harry Buhrman, Christoph Dürrþ, Mark Heiligmanü, Peter Høyerß, Frédéric Magniez, Miklos Santha, ...
anÇÆ��ÐÓ�Æ We present several applications of quantum amplitude amplification to finding claws and collisions in ordered or unordered functions. Our algorithms generalize those of...
Quantum Algorithms for Element Distinctness (2001)
Harry Buhrman, Christoph D Ürr, Mark Heiligman, Peter Høyer, Fr Édéric Magniez, Miklos Santha, ...
Abstract. We present several applications of quantum amplitude amplification to finding claws and collisions in ordered or unordered functions. Our algorithms generalize those of Brassard, Høyer,...
Quantum Entanglement and Communication Complexity (2001)
Harry Buhrman, Richard Cleve, Van Dam
Abstract. We consider a variation of the communication complexity scenario, where the parties are supplied with an extra resource: particles in an entangled quantum state. We note that “quantum...
Quantum Algorithms for Element Distinctness (2001)
Harry Buhrman, Christoph Dürr, Mark Heiligman, Peter Høyer, Frédéric Magniez, Miklos Santha, ...
We present several applications of quantum amplitude amplification to finding claws and collisions in ordered or unordered functions. Our algorithms generalize those of Brassard, Høyer, and Tapp,...
Quantum Algorithms for Element Distinctness (2001)
Harry Buhrman, Christoph D Ürr, Mark Heiligman, Peter Høyer, Fr Édéric Magniez, Miklos Santha, ...
Abstract. We present several applications of quantum amplitude amplification for deciding whether all elements in the image of a given function are distinct, for finding an intersection of two sorted...
Quantum Algorithms for Element Distinctness (2000)
Buhrman, Harry, Durr, Christoph, Heiligman, Mark, Hoyer, Peter, Magniez, Frederic, Santha, Miklos, ...
We present several applications of quantum amplitude amplification to finding claws and collisions in ordered or unordered functions. Our algorithms generalize those of Brassard, Hoyer, and Tapp, and...
A generalization of resource-bounded measure, with application to the BPP vs. EXP problem (2000)
Harry Buhrman, Dieter Melkebeek, Kenneth W. Regan, D. Sivakumar, Martin Strauss
We introduce resource-bounded betting games, and propose a generalization of Lutz’s resource-bounded measure in which the choice of next string to bet on is fully adaptive. Lutz’s martingales are...
A generalization of resource-bounded measure, with application to the BPP vs. EXP problem (2000)
Harry Buhrman, Dieter Van Melkebeek, Kenneth W. Regan, D. Sivakumar, Martin Strauss
1
Quantum computing and communication complexity (2000)
Quantum computing combines the framework of quantum mechanics with that of computer science. In this paper we give a short introduction to quantum computing and survey the results in the area of...
Are Bitvectors Optimal? (2000)
Harry Buhrman, Peter Bro Miltersen, Jaikumar Radhakrishnan, Srinivasan Venkatesh, H. Buhrman, P. B. Miltersen, ...
We study the static membership problem: Given a set S of at most n keys drawn from a universe of size m, store it so that queries of the form "Is x in S?" can be answered quickly. We study...
Harry Buhrman, Leen Torenvliet
We study the set of incompressible strings for various resource bounded versions of Kolmogorov complexity. The resource bounded versions of Kolmogorov complexity we study are: polynomial time CD...
The Communication Complexity of Enumeration, Elimination, and Selection (2000)
Andris Ambainis, Harry Buhrman, William Gasarch, Bala Kalyanasundaram, Leen Torenvliet
Let k, n # N and f : {0, 1} n {0, 1} n # {0, 1}. Assume Alice has x 1 , . . . , x k # {0, 1} n , Bob has y 1 , . . . , y k # {0, 1} n , and they want to compute f(x 1 , y 1 ) f(x k , y k )...
Quantum Algorithms for Element Distinctness (2000)
Harry Buhrman, Christoph Dürr, Mark Heiligman, Peter Høyer, Frédéric Magniez, Miklos Santha, ...
We present several applications of quantum amplitude amplification to finding claws and collisions in ordered or unordered functions. Our algorithms generalize those of Brassard, Hyer, and Tapp, and...
Harry Buhrman, Alessandro Panconesi, Riccardo Silvestri, Paul Vitany
) Harry Buhrman 1 , Alessandro Panconesi 2 , Riccardo Silvestri 3 , and Paul Vitanyi1 1 CWI, Amsterdam 2 Informatica, Universita di Bologna, 3 Informatica, Universita de L'Aquila Abstract. We...
Optimal Proof Systems and Sparse Sets (2000)
Harry Buhrman, Steve Fenner, Lance Fortnow, Dieter Van Melkebeek
. We exhibit a relativized world where NP \ SPARSE has no complete sets. This gives the rst relativized world where no optimal proof systems exist. We also examine under what reductions NP \ SPARSE...
Optimal Proof Systems and Sparse Sets (2000)
Harry Buhrman, Steve Fenner, Lance Fortnow, Dieter Van Melkebeek
. We exhibit a relativized world where NP # SPARSE has no complete sets. This gives the first relativized world where no optimal proof systems exist. We also examine under what reductions NP # SPARSE...
Optimal Proof Systems and Sparse Sets (2000)
By Harry Buhrman, Harry Buhrman, Steve Fenner, Lance Fortnow, Dieter Van Melkebeek
We exhibit a relativized world where NP # SPARSE has no complete sets. This gives the first relativized world where no optimal proof systems exist. We also examine under what reductions NP # SPARSE...
Communication Complexity Lower Bounds by Polynomials (1999)
Buhrman, Harry, De Wolf, Ronald
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 bound techniques are...
Space-Efficient Routing Tables for Almost All Networks and the Incompressibility Method (1999)
Buhrman, Harry, Hoepman, Jaap-Henk, Vitanyi, Paul
We use the incompressibility method based on Kolmogorov complexity to determine the total number of bits of routing information for almost all network topologies. In most models for routing, for...
Quantum Bounded Query Complexity (1999)
We combine the classical notions and techniques for bounded query classes with those developed in quantum computing. We give strong evidence that quantum queries to an oracle in the class NP does...
Buhrman, Harry, Franklin, Matthew, Garay, Juan A., Hoepman, Jaap-Henk, Tromp, John, Vitanyi, Paul
We introduce a search problem called ``mutual search'' where $k$ \agents, arbitrarily distributed over $n$ sites, are required to locate one another by posing queries of the form ``Anybody at site...
Space-efficient routing tables for almost all networks and the incompressibility method (1999)
Harry Buhrman, Jaap-henk Hoepman, Vit Ányi
Abstract. We use the incompressibility method based on Kolmogorov complexity to determine the total number of bits of routing information for almost all network topologies. In most models for...
Harry Buhrman, Matthew Franklin, Juan A. Garay, John Tromp, Paul Vitányi
Permission to make digital / hard copy of part or all of this work for personal or classroom use is granted without fee provided that the copies are not made or distributed for profit or commercial...
Optimal Proof Systems and Sparse Sets (1999)
Harry Buhrman, Steve Fenner, Lance Fortnow, Dieter Van Melkebeek
We exhibit a relativized world where NP # SPARSE has no complete sets. This gives the first relativized world where no optimal proof systems exist. We also examine under what reductions NP # SPARSE...
Complexity Measures and Decision Tree Complexity: A Survey (1999)
We discuss several complexity measures for Boolean functions: certificate complexity, sensitivity, block sensitivity, and the degree of a representing or approximating polynomial. We survey the...
Two Oracles that Force a Big Crunch (1999)
Harry Buhrman, Stephen Fenner, Lance Fortnow, Leen Torenvliet
The central theme of this paper is the construction of an oracle A such that NEXP A = P NP A . The construction of this oracle answers a long standing open question rst posed by Heller, and...
One-sided Versus Two-sided Error in Probabilistic Computation (1999)
We demonstrate how to use Lautemann's proof that BPP is in \Sigma p 2 to exhibit that BPP is in RP PromiseRP . Immediate consequences show that if PromiseRP is easy or if there exist quick...
Communication Complexity Lower Bounds by Polynomials (1999)
The quantum version of communication complexity allows Alice and Bob to communicate qubits and/or to make use of prior entanglement (shared EPR-pairs). Some lower bound techniques are available for...
Bounds for Small-Error and Zero-Error Quantum Algorithms (1999)
Harry Buhrman, Richard Cleve, Ronald De Wolf, Christof Zalka
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-offs between the...
A Lower Bound for Quantum Search of an Ordered List (1999)
It is known that a quantum computer can search an unordered list of N items using O( p N) look-ups, which is quadratically faster than any classical algorithm. We examine the case where the list is...
Circuit Expressions of Low Kolmogorov Complexity (1999)
José Balcázar, Harry Buhrman, Montserrat Hermo
We study circuit expressions of logarithmic and poly-logarithmic polynomial-time Kolmogorov complexity, focusing on their complexity-theoretic characterizations and learnability properties. They...
Harry Buhrman, Matthew Franklin, Juan A. Garay, Jaap-henk Hoepman, John Tromp, Paul Vitányi
We introduce a search problem called "mutual search" where k agents , arbitrarily distributed over n sites, are required to locate one another by posing queries of the form "Anybody at...
Space-Efficient Routing Tables For Almost All Networks And The Incompressibility Method (1999)
Harry Buhrman, Jaap-Henk Hoepman, Paul Vitányi, Vit Anyi
. We use the incompressibility method based on Kolmogorov complexity to determine the total number of bits of routing information for almost all network topologies. In most models for routing, for...
Bounds for small-error and zero-error quantum algorithms (1999)
Harry Buhrman, Richard Cleve, Ronald De Wolf, Christof Zalka
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-offs between the...
Lower Bounds for Quantum Search and Derandomization (1998)
Buhrman, Harry, De Wolf, Ronald
We prove lower bounds on the error probability of a quantum algorithm for searching through an unordered list of N items, as a function of the number T of queries it makes. In particular, if...
New Applications of the Incompressibility Method: Part II (1998)
Buhrman, Harry, Jiang, Tao, Li, Ming, Vitanyi, Paul
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 new simple proofs...
Separating complexity classes using autoreducibility (1998)
Buhrman, Harry, Fortnow, Lance, Torenvliet, Leen, Van Melkebeek, Dieter
A set is autoreducible if it can be reduced to itself by a Turing machine that does not ask its own input to the oracle. We use autoreducibility to separate the polynomial-time hierarchy from...
Quantum Lower Bounds by Polynomials (1998)
Beals, Robert, Buhrman, Harry, Cleve, Richard, Mosca, Michele, De Wolf, Ronald
We examine the number T of queries that a quantum network requires to compute several Boolean functions on {0,1}^N in the black-box model. We show that, in the black-box model, the exponential...
Quantum vs. Classical Communication and Computation (1998)
Buhrman, Harry, Cleve, Richard, Wigderson, Avi
We present a simple and general simulation technique that transforms any black-box quantum algorithm (a la Grover's database search algorithm) to a quantum communication protocol for a related...
Quantum Entanglement and Communication Complexity (1998)
Harry Buhrman Cwi, Harry Buhrman, Richard Cleve
We consider a variation of the multi-party communication complexity scenario where the parties are supplied with an extra resource: particles in an entangled quantum state. We show that, although a...
Quantum vs. Classical Communication and Computation (1998)
Harry Buhrman, Richard Cleve, Avi Wigderson
We present a simple and general simulation technique that transforms any black-box quantum algorithm (a la Grover's database search algorithm) to a quantum communication protocol for a related...
Separating Complexity Classes using Autoreducibility (1998)
Harry Buhrman, Lance Fortnow, Dieter Van Melkebeek, Leen Torenvliet
A set is autoreducible if it can be reduced to itself by a Turing machine that does not ask its own input to the oracle. We use autoreducibility to separate the polynomial-time hierarchy from...
A Generalization of Resource-Bounded Measure, With an Application (Extended Abstract) (1998)
Harry Buhrman, Dieter Van Melkebeek, Kenneth W. Regan, D. Sivakumar, Martin Strauss
) Harry Buhrman 1 , Dieter van Melkebeek 2 , Kenneth W. Regan 3 , D. Sivakumar 4 , and Martin Strauss 5 1 CWI, Kruislaan 413, 1098SJ Amsterdam, The Netherlands. E-mail: buhrman@cwi.nl. Partly...
Separating Complexity Classes using Autoreducibility (1998)
Harry Buhrman Cwi, Harry Buhrman, Lance Fortnow, Dieter Van Melkebeek, Leen Torenvliet
A set is autoreducible if it can be reduced to itself by a Turing machine that does not ask its own input to the oracle. We use autoreducibility to separate the polynomial-time hierarchy from...
Hard Sets Are Hard to Find (1998)
Harry Buhrman, Dieter Van Melkebeek
We investigate the frequency of complete sets for various complexity classes within EXP under several polynomial-time reductions in the sense of resource-bounded measure. We show that these sets are...
NP Might Not Be As Easy As Detecting Unique Solutions (1998)
Richard Beigel, Harry Buhrman, Lance Fortnow
We construct an oracle A such that P A = \PhiP A and NP A = EXP A : This relativized world has several amazing properties: ffl The oracle A gives the first relativized world where one can solve...
Separating Complexity Classes using Autoreducibility (1998)
Harry Buhrman Cwi, Harry Buhrman, Lance Fortnow, Dieter Van Melkebeek, Leen Torenvliet
A set is autoreducible if it can be reduced to itself by a Turing machine that does not ask its own input to the oracle. We use autoreducibility to separate the polynomial-time hierarchy from...
Nonrelativizing Separations (1998)
Harry Buhrman, Lance Fortnow, Thomas Thierauf
We show that MA EXP , the exponential time version of the Merlin-Arthur class, does not have polynomial size circuits. This significantly improves the previous known result due to Kannan since we...
Quantum vs. Classical Communication and Computation (1998)
Harry Buhrman, Richard Cleve, Avi Wigderson
We present a simple and general simulation technique that transforms any black-box quantum algorithm (a la Grover's database search algorithm) to a quantum communication protocol for a related...
Quantum Entanglement and Communication Complexity (1998)
Harry Buhrman, Richard Cleve, Wim Van Dam
We consider a variation of the multi-party communication complexity scenario where the parties are supplied with an extra resource: particles in an entangled quantum state. We show that, although a...
Separating Complexity Classes using Autoreducibility (1998)
Harry Buhrman, Lance Fortnow, Dieter Van Melkebeek, Leen Torenvliet
A set is autoreducible if it can be reduced to itself by a Turing machine that does not ask its own input to the oracle. We use autoreducibility to separate the polynomial-time hierarchy from...
Hard Sets Are Hard to Find (1998)
Harry Buhrman, Dieter Van Melkebeek
We investigate the frequency of complete sets for various complexity classes within EXP under several polynomial-time reductions in the sense of resource bounded measure. We show that these sets are...
Separating Complexity Classes using Autoreducibility (1998)
Harry Buhrman, Lance Fortnow, Dieter Van Melkebeek, Leen Torenvliet
A set is autoreducible if it can be reduced to itself by a Turing machine that does not ask its own input to the oracle. We use autoreducibility to separate the polynomial-time hierarchy from...
We consider the question whether two queries to SAT are as powerful as one query. We show that if P NP[1] = P NP[2] then ffl Locally either NP = coNP or NP has polynomial-size circuits. ffl P NP = P...
One-sided Versus Two-sided Randomness (1998)
We demonstrate how to use Lautemann's proof that BPP is in \Sigma p 2 to exhibit that BPP is in RP PromiseRP . Immediate consequences show that if PromiseRP is easy or if there exist quick...
Quantum Lower Bounds by Polynomials (1998)
Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, Ronald De Wolf
We examine the number T of queries that a quantum network requires to compute several Boolean functions on f0; 1g N in the black-box model. We show that, in the blackbox model, the exponential...
Hard Sets Are Hard to Find (1998)
Harry Buhrman, Dieter Van Melkebeek
We investigate the frequency of complete sets for various complexity classes within EXP under several polynomial-time reductions in the sense of resource-bounded measure. We show that these sets are...
A Generalization of Resource-Bounded Measure, With Application to the BPP vs. EXP Problem (1998)
Harry Buhrman, Dieter Van Melkebeek, Kenneth W. Regan, D. Sivakumar, Martin Strauss
We introduce resource-bounded betting games, and propose a generalization of Lutz's resourcebounded measure in which the choice of next string to bet on is fully adaptive. Lutz's...
Separating Complexity Classes using Autoreducibility (1998)
Harry Buhrman, Lance Fortnow, Dieter Van Melkebeek, Leen Torenvliet
A set is autoreducible if it can be reduced to itself by a Turing machine that does not ask its own input to the oracle. We use autoreducibility to separate the polynomial-time hierarchy from...
Separating Complexity Classes using Autoreducibility (1998)
Harry Buhrman, Lance Fortnow, Dieter Van Melkebeek, Leen Torenvliet
A set is autoreducible if it can be reduced to itself by a Turing machine that does not ask its own input to the oracle. We use autoreducibility to separate the polynomial-time hierarchy from...
Lower Bounds for Quantum Search and Derandomization (1998)
We prove lower bounds on the error probability of a quantum algorithm for searching through an unordered list of N items, as a function of the number T of queries it makes. In particular, if T 2 O( p...
Quantum lower bounds by polynomials (1998)
Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca
We examine the numberTof queries that a quantum network requires to compute several Boolean functions on f0;1gNin the black-box model. We show that, in the blackbox model, the exponential quantum...
Complicated Complementations (1998)
Harry Buhrman, Leen Torenvliet
Kolmogorov complexity has proven to be a very useful tool in simplifying and improving proofs that use complicated combinatorial arguments. In this paper we use Kolmogorov complexity for oracle...
Harry Buhrman, Leen Torenvliet
We study the set of incompressible strings for various resource bounded versions of Kolmogorov complexity. The resource bounded versions of Kolmogorov complexity we study are: polynomial time CD...
Complete Sets and Structure in Subrecursive Classes (1998)
Harry Buhrman, Leen Torenvliet
In this expository paper, we investigate the structure of complexity classes and the structure of complete sets therein. We give an overview of recent results on both set structure and class...
Multiparty Quantum Communication Complexity (1997)
Buhrman, Harry, Van Dam, Wim, Hoyer, Peter, Tapp, Alain
Quantum entanglement cannot be used to achieve direct communication between remote parties, but it can reduce the communication needed for some problems. Let each of k parties hold some partial input...
Quantum Entanglement and Communication Complexity (1997)
Buhrman, Harry, Cleve, Richard, Van Dam, Wim
We consider a variation of the multi-party communication complexity scenario where the parties are supplied with an extra resource: particles in an entangled quantum state. We show that, although a...
Substituting Quantum Entanglement for Communication (1997)
Cleve, Richard, Buhrman, Harry
We show that quantum entanglement can be used as a substitute for communication when the goal is to compute a function whose input data is distributed among remote parties. Specifically, we show...
Resource-bounded Kolmogorov complexity revisited (1997)
Harry Buhrman, Lance Fortnow, Sophie Laplante
We take a fresh look at CD complexity, where CD t (x) is the size of the smallest program that distinguishes x from all other strings in time t(jxj). We also look at CND complexity, a new...
Resource-bounded Kolmogorov complexity revisited (1997)
Harry Buhrman, Lance Fortnow, Sophie Laplante
We take a fresh look at CD complexity, where CD t (x) is the size of the smallest program that distinguishes x from all other strings in time t(jxj). We also look at CND complexity, a new...
Complete Sets under Non-Adaptive Reductions are Scarce (1997)
Harry Buhrman, Dieter Van Melkebeek
We investigate the frequency of complete sets for various complexity classes within EXP under non-adaptive reductions in the sense of resource bounded measure. We show that these sets are rare: ffl...
Resource-Bounded Kolmogorov Complexity Revisited (1997)
We take a fresh look at CD complexity, where CD t (x) is the smallest program that distinguishes x from all other strings in time t(jxj). We also look at a CND complexity, a new nondeterministic...
Six Hypotheses in Search of a Theorem (1997)
Harry Buhrman, Lance Fortnow, Leen Torenvliet
We consider the following six hypotheses: ffl P = NP. ffl SAT is truth-table reducible to a P-selective set. ffl SAT is truth-table reducible to a k- approximable set for some k. ffl FP NP jj = FP...
Results on Resource-Bounded Measure (1997)
Harry Buhrman, Stephen Fenner, Lance Fortnow
. We construct an oracle relative to which NP has p-measure 0 but D p has measure 1 in EXP. This gives a strong relativized negative answer to a question posed by Lutz [Lut96]. Secondly, we give...
Kolmogorov Random Graphs (1997)
Harry Buhrman, Ming Li, Paul Vitanyi
We investigate topological, combinatorial, statistical, and enumeration properties of finite graphs with high Kolmogorov complexity (almost all graphs) using the novel incompressibility method....
Nonrelativizing Separations (1997)
Harry Buhrman, Lance Fortnow, Thomas Thierauf, Abt Theoretische Informatik
We show that MA EXP , the exponential time version of the Merlin-Arthur class, does not have polynomial size circuits. This significantly improves the previous known result due to Kannan since we...
Kolmogorov Random Graphs And The Incompressibility Method (1997)
Harry Buhrman, Ming Li, John Tromp, Paul Vitanyi
. We investigate topological, combinatorial, statistical, and enumeration properties of finite graphs with high Kolmogorov complexity (almost all graphs) using the novel incompressibility method....
Kolmogorov random graphs and the incompressibility method (1997)
Harry Buhrman, Ming Li, John Tromp, Vit Ányi
Abstract. We investigate topological, combinatorial, statistical, and enumeration properties of finite graphs with high Kolmogorov complexity (almost all graphs) using the novel incompressibility...
Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai Vereshchagin
classification: Kolmogorov complexity, computational complexity
Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai Vereshchagin
classification: Kolmogorov complexity, computational complexity
Harry Buhrman, Jaap-henk Hoepman, Paul Vitányi
The optimal space used to represent routing schemes in communication networks is established, both for worst-case static networks and on the average for all static networks. Several factors may...
Random Strings Make Hard Instances (1996)
We establish the truth of the "instance complexity conjecture" in the case of DEXT-complete sets w.r.t. polynomial time computations, and r.e. complete sets w.r.t. recursive computations....
We consider the question whether two queries to SAT are as powerful as one query. We show that if P NP[1] = P NP[2] then Locally either NP = coNP or NP has polynomial-size circuits. P NP = P NP[1] ....
P-selective Self-reducible sets: A New Characterization of P (1996)
Harry Buhrman, Leen Torenvliet
We show that any p-selective and self-reducible set is in P . As the converse is also true, we obtain a new characterization of the class P . A generalization and several consequences of this theorem...
Structure and Complexity (1996)
Uwe Schöning, Klaus W. Wagner, Farid Ablayev, Eric Allender, ...
S On the Power of Randomized Branching Programs Farid Ablayev Kazan University (joint work with Marek Karpinski, Universitat Bonn) We define a notion of randomized branching programs in a natural way...
P-selective Self-reducible sets: A New Characterization of (1996)
Harry Buhrman, Leen Torenvliet
We show that any p-selective and self-reducible set is in P . As the converse is also true, we obtain a new characterization of the class P . A generalization and several consequences of this theorem...
Introduction Hemaspaandra, Hemaspaandra and Hempel [HHH96] showed that for k ? 2, if P \Sigma p k [2] tt = P \Sigma p k [1] then \Sigma p k = \Pi p k . We extend their techniques to show that if P...
Two Results on Resource-Bounded Measure (1996)
Harry Buhrman, Stephen Fenner, Lance Fortnow
We construct an oracle relative to which NP has p-measure 0 but D p has measure 1 in EXP. This gives a strong relativized negative answer to a question posed by Lutz [Lut96]. Secondly, we give strong...
An Excursion to the Kolmogorov Random Strings (1995)
Harry Buhrman, Elvira Mayordomo
We study the set of resource bounded Kolmogorov random strings: R t = fx j K t (x) jxjg for t a time constructible function such that t(n) 2 n 2 and t(n) 2 2 n O(1) . We show that the class of sets...
Using Autoreducibility to Separate Complexity Classes (1995)
Harry Buhrman, Lance Fortnow, Leen Torenvliet
A language is autoreducible if it can be reduced to itself by a Turing machine that does not ask its own input to the oracle. We use autoreducibility to separate exponential space from doubly...
An Excursion to the Kolmogorov Random Strings (1995)
Harry Buhrman, Elvira Mayordomo
We study the set of resource bounded Kolmogorov random strings: R t = fx j K t (x) jxjg for t a time constructible function such that t(n) 2 n 2 and t(n) 2 2 n O(1) . We show that the class of sets...
On the Sparse Set Conjecture for Sets with Low Density (1995)
Harry Buhrman, Montserrat Hermo
. We study the sparse set conjecture for sets with low density. The sparse set conjecture states that P = NP if and only if there exists a sparse Turing hard set for NP . In this paper we study a...
Learnability of Kolmogorov-Easy Circuit Expressions Via Queries (1995)
José L. Balcázar, Harry Buhrman, Montserrat Hermo
. Circuit expressions were introduced to provide a natural link between Computational Learning and certain aspects of Structural Complexity. Upper and lower bounds on the learnability of circuit...
Using Autoreducibility to Separate Complexity Classes (1995)
Harry Buhrman, Lance Fortnow, Leen Torenvliet
A language is autoreducible if it can be reduced to itself by a Turing machine that does not ask its own input to the oracle. We use autoreducibility to separate exponential space from doubly...
Distinguishing Complexity and Symmetry of Information (1995)
We describe how to use polynomial-time Kolmogorov distinguishing complexity to give an approximate measure of the size of sets. For any set S, we show that relative to S the polynomial time...
Long-Lived Renaming Made Fast (1995)
Harry Buhrman, Juan A. Garay, Jaap-henk Hoepman, Mark Moir
In the long-lived renaming problem --- a generalization of the classical one-time renaming problem --- n processors with unique names ranging over a source name space f0; : : : ; S \Gamma 1g...
On Functions Computable with Nonadaptive Queries to NP (1994)
Harry Buhrman, Jim Kadin, Thomas Thierauf
We study FP NP k , the class of functions that can be computed with nonadaptive queries to an NP oracle. We show that optimization problems stemming from the known NP complete sets, where the optimum...
On the Cutting Edge of Relativization: The Resource Bounded Injury Method (1994)
Harry Buhrman, Leen Torenvliet
In this report we present a new method of diagonalization that is a refinement of the well-known finite injury priority method discovered independently by Friedberg and Muchnik in 1957. In the...
On the Structure of Complete Sets (1994)
Harry Buhrman Leen, Harry Buhrman, Leen Torenvliet
The many types of resource bounded reductions that are both object of study and research tool in structural complexity theory have given rise to a large variety of completeness notions. A complete...
Random Strings Make Hard Instances (1994)
We establish the truth of the "instance complexity conjecture" in the case of DEXT-complete sets over polynomial time computations, and r.e. complete sets over recursive computations....
On the Structure of Complete Sets (1994)
Harry Buhrman, Leen Torenvliet
The many types of resource bounded reductions that are both object of study and research tool in structural complexity theory have given rise to a large variety of completeness notions. A complete...
On the Cutting Edge of Relativization: The Resource Bounded Injury Method (1994)
Harry Buhrman, Pau Gargallo, Leen Torenvliet
In this paper we construct an oracle A such that NEXP A ` P NP A . For the construction of this oracle we present a new variation on the finite injury priority method that we call the resource...
Twenty Questions to a P-selector (1994)
Harry Buhrman, Leen Torenvliet
We show in this note, that any set that is positive Turing reducible to a p-selective set is in fact many-one reducible to this set. Therefore, such a set is itself p-selective. 1 Introduction...
Splittings, Robustness and Structure of Complete Sets (1993)
Harry Buhrman, Albrecht Hoene, Leen Torenvliet
We investigate the structure of EXP and NEXP complete and hard sets under various kinds of reductions. In particular, we are interested in the way in which information that makes the set complete is...
SPARSE reduces conjunctively to TALLY (1993)
Harry Buhrman, Edith Hemaspaandra, Luc Longpré
Polynomials over finite fields are used to show that any sparse set can conjunctively reduce to a tally set. This leads to new results and to simple proofs of known results about various classes that...
Splittings, Robustness and Structure of Complete Sets (1993)
Harry Buhrman, Albrecht Hoene, Leen Torenvliet
We investigate the structure of EXP and NEXP complete and hard sets under various kinds of reductions. In particular, we are interested in the way in which information that makes the set complete is...
Harry Buhrman, Edith Spaan, Leen Torenvliet
We study properties of resource-- and otherwise bounded reductions and corresponding completeness notions on nondeterministic time classes which contain exponential time. As it turns out, most of...
Superpolynomial Circuits, Almost Sparse Oracles and the Exponential Hierarchy (1992)
Several problems concerning superpolynomial size circuits and superpolynomialtime advice classes are investigated. First we consider the implications of NP (and other fun- damental complexity...
On `hot spot' contention (1985)
This thesis owes a lot to David Mix Barrington, as it was a conversation with him that brought the problems discussed here to my attention. It was also series of lectures given by him the year before...
The Relative Power Of Logspace And Polynomial Time Reductions
Harry Buhrman, Edith Spaan, Leen Torenvliet
. There exist many different formalisms to model the notion of resource bounded `truth-table' reduction. Most papers in which truthtable reductions appear refer to the seminal paper of Ladner,...
Quantum Lower Bounds by Polynomials
Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, Ronald De Wolf
We examine the number T of queries that a quantum network requires to compute several Boolean functions on f0; 1g N in the black-box model. We show that, in the blackbox model, the exponential...
Quantum Lower Bounds by Polynomials
Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, Ronald De Wolf
We examine the number of queries to input variables that a quantum algorithm requires to compute Boolean functions on in the black-box model. We show that the exponential quantum speed-up obtained...
The Relative Power Of Logspace And Polynomial Time Reductions
Harry Buhrman, Edith Spaan, Leen Torenvliet
. There exist many different formalisms to model the notion of resource bounded `truth-table' reduction. Most papers in which truthtable reductions appear refer to the seminal paper of Ladner,...