All reports by Author Harry Buhrman:

__
TR23-015
| 20th February 2023
__

Scott Aaronson, Harry Buhrman, William Kretschmer#### A Qubit, a Coin, and an Advice String Walk Into a Relational Problem

__
TR14-053
| 15th April 2014
__

Harry Buhrman, Richard Cleve, Michal Koucky, Bruno Loff, Florian Speelman#### Computing with a full memory: Catalytic space

Revisions: 1

__
TR12-179
| 13th December 2012
__

Joshua Brody, Harry Buhrman, Michal Koucky, Bruno Loff, Florian Speelman#### Towards a Reverse Newman's Theorem in Interactive Information Complexity

Revisions: 2

__
TR12-054
| 2nd May 2012
__

Eric Allender, Harry Buhrman, Luke Friedman, Bruno Loff#### Reductions to the set of random strings:the resource-bounded case

Revisions: 1

__
TR10-174
| 12th November 2010
__

Scott Aaronson, Baris Aydinlioglu, Harry Buhrman, John Hitchcock, Dieter van Melkebeek#### A note on exponential circuit lower bounds from derandomizing Arthur-Merlin games

__
TR10-163
| 3rd November 2010
__

Harry Buhrman, Leen Torenvliet, Falk Unger, Nikolay Vereshchagin#### Sparse Selfreducible Sets and Nonuniform Lower Bounds

__
TR09-064
| 3rd August 2009
__

Harry Buhrman, Lance Fortnow, Rahul Santhanam#### Unconditional Lower Bounds against Advice

__
TR09-060
| 4th June 2009
__

Harry Buhrman, David García Soriano, Arie Matsliah#### Learning parities in the mistake-bound model.

__
TR08-022
| 9th January 2008
__

Harry Buhrman, John Hitchcock#### NP-Hard Sets are Exponentially Dense Unless NP is contained in coNP/poly

__
TR04-081
| 9th September 2004
__

Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolay Vereshchagin#### Increasing Kolmogorov Complexity

__
TR04-044
| 1st June 2004
__

Eric Allender, Harry Buhrman, Michal Koucky#### What Can be Efficiently Reduced to the Kolmogorov-Random Strings?

__
TR04-015
| 24th February 2004
__

Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrej Muchnik, Frank Stephan, Leen Torenvliet#### Enumerations of the Kolmogorov Function

__
TR04-002
| 8th January 2004
__

Troy Lee, Dieter van Melkebeek, Harry Buhrman#### Language Compression and Pseudorandom Generators

__
TR02-028
| 15th May 2002
__

Eric Allender, Harry Buhrman, Michal Koucky, Detlef Ronneburger, Dieter van Melkebeek#### Power from Random Strings

Revisions: 1

__
TR01-019
| 2nd March 2001
__

Andris Ambainis, Harry Buhrman, William Gasarch, Bala Kalyansundaram, Leen Torenvliet#### The Communication Complexity of Enumeration, Elimination, and Selection

Scott Aaronson, Harry Buhrman, William Kretschmer

Relational problems (those with many possible valid outputs) are different from decision problems, but it is easy to forget just how different. This paper initiates the study of FBQP/qpoly, the class of relational problems solvable in quantum polynomial-time with the help of polynomial-sized quantum advice, along with its analogues for ... more >>>

Harry Buhrman, Richard Cleve, Michal Koucky, Bruno Loff, Florian Speelman

We define the notion of a catalytic-space computation. This is a computation that has a small amount of clean space available and is equipped with additional auxiliary space, with the caveat that the additional space is initially in an arbitrary, possibly incompressible, state and must be returned to this state ... more >>>

Joshua Brody, Harry Buhrman, Michal Koucky, Bruno Loff, Florian Speelman

Newman’s theorem states that we can take any public-coin communication protocol and convert it into one that uses only private randomness with only a little increase in communication complexity. We consider a reversed scenario in the context of information complexity: can we take a protocol that uses private randomness and ... more >>>

Eric Allender, Harry Buhrman, Luke Friedman, Bruno Loff

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 show that an approach laid out by [Allender et al] to settle this conjecture cannot succeed without significant alteration, but that it ... more >>>

Scott Aaronson, Baris Aydinlioglu, Harry Buhrman, John Hitchcock, Dieter van Melkebeek

We present an alternate proof of the recent result by Gutfreund and Kawachi that derandomizing Arthur-Merlin games into $P^{NP}$ implies linear-exponential circuit lower bounds for $E^{NP}$. Our proof is simpler and yields stronger results. In particular, consider the promise-$AM$ problem of distinguishing between the case where a given Boolean circuit ... more >>>

Harry Buhrman, Leen Torenvliet, Falk Unger, Nikolay Vereshchagin

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 believed, but unfortunately up to now unproven, that there are sets in $EXP^{NP}$, or even ... more >>>

Harry Buhrman, Lance Fortnow, Rahul Santhanam

We show several unconditional lower bounds for exponential time classes

against polynomial time classes with advice, including:

\begin{enumerate}

\item For any constant $c$, $\NEXP \not \subseteq \P^{\NP[n^c]}/n^c$

\item For any constant $c$, $\MAEXP \not \subseteq \MA/n^c$

\item $\BPEXP \not \subseteq \BPP/n^{o(1)}$

\end{enumerate}

It was previously unknown even whether $\NEXP \subseteq ... more >>>

Harry Buhrman, David García Soriano, Arie Matsliah

We study the problem of learning parity functions that depend on at most $k$ variables ($k$-parities) attribute-efficiently in the mistake-bound model.

We design simple, deterministic, polynomial-time algorithms for learning $k$-parities with mistake bound $O(n^{1-\frac{c}{k}})$, for any constant $c > 0$. These are the first polynomial-time algorithms that learn $\omega(1)$-parities in ...
more >>>

Harry Buhrman, John Hitchcock

We show that hard sets S for NP must have exponential density, i.e. |S<sub>=n</sub>| ≥ 2<sup>n<sup>ε</sup></sup> for some ε > 0 and infinitely many n, unless coNP ⊆ NP\poly and the polynomial-time hierarchy collapses. This result holds for Turing reductions that make n<sup>1-ε</sup> queries.

In addition we study the instance ... more >>>

Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolay Vereshchagin

How much do we have to change a string to increase its Kolmogorov complexity. We show that we can

increase the complexity of any non-random string of length n by flipping O(sqrt(n)) bits and some strings

require

Omega(sqrt(n)) bit flips. For a given m, we also give bounds for ...
more >>>

Eric Allender, Harry Buhrman, Michal Koucky

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 this question cannot be posed without explicitly dealing

with issues raised by the choice of universal

machine in the ...
more >>>

Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrej Muchnik, Frank Stephan, Leen Torenvliet

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 among the first $k(n)$ elements enumerated by $f$.

If there is a $k(n)$-enumerator for ...
more >>>

Troy Lee, Dieter van Melkebeek, Harry Buhrman

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 for

A. We study randomized and nondeterministic decompression schemes

and investigate how close we can get to the information ...
more >>>

Eric Allender, Harry Buhrman, Michal Koucky, Detlef Ronneburger, Dieter van Melkebeek

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 these sets are hard and complete for various complexity classes.

In particular, in addition to the usual Kolmogorov complexity measure

K, ...
more >>>

Andris Ambainis, Harry Buhrman, William Gasarch, Bala Kalyansundaram, Leen Torenvliet

Normally, communication Complexity deals with how many bits

Alice and Bob need to exchange to compute f(x,y)

(Alice has x, Bob has y). We look at what happens if

Alice has x_1,x_2,...,x_n and Bob has y_1,...,y_n

and they want to compute f(x_1,y_1)... f(x_n,y_n).

THis seems hard. We look at various ...
more >>>