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 >>>

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 >>>

We show that hard sets S for NP must have exponential density, i.e. |S_=n| ≥ 2^nε 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^1-ε queries. In addition we study the instance ... more >>>

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 increasing ... more >>>

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 >>>

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 >>>

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 >>>

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, we consider the ... more >>>

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 >>>