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 exhibit a new computational-based definition of awareness, informally that our level of unawareness of an object is the amount of time needed to generate that object within a certain environment. We give several examples to show this notion matches our intuition in scenarios where one organizes, accesses and transfers ... more >>>

We study the notion of "instance compressibility" of NP problems [Harnik-Naor06], closely related to the notion of kernelization in parameterized complexity theory [Downey-Fellows99, Flum-Grohe06, Niedermeier06]. A language $L$ in NP is instance compressible if there is a polynomial-time computable function $f$ and a set $A$ such that for each instance ... more >>>

We survey time hierarchies, with an emphasis on recent attempts to prove hierarchies for semantic classes. more >>>

We explore whether various complexity classes can have linear or more generally $n^k$-sized circuit families for some fixed $k$. We show 1) The following are equivalent, - NP is in SIZE(n^k) (has O(n^k)-size circuit families) for some k - P^NP|| is in SIZE(n^k) for some k - ONP/1 is in ... more >>>

Consider a weather forecaster predicting a probability of rain for the next day. We consider tests that given a finite sequence of forecast predictions and outcomes will either pass or fail the forecaster. Sandroni (2003) shows that any test which passes a forecaster who knows the distribution of nature, can ... more >>>

Antunes, Fortnow, van Melkebeek and Vinodchandran captured the notion of non-random information by computational depth, the difference between the polynomial-time-bounded Kolmogorov complexity and traditional Kolmogorov complexity We show how to find satisfying assignments for formulas that have at least one assignment of logarithmic depth. The converse holds under a standard ... more >>>

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 functions are hard, for example, if TFNP is computable in polynomial-time does this imply the polynomial-time hierarchy collapses? We give a relativized ... more >>>

We show that under a reasonable hardness assumptions, the time-bounded Kolmogorov distribution is a universal samplable distribution. Under the same assumption we exactly characterize the worst-case running time of languages that are in average polynomial-time over all P-samplable distributions. more >>>

We apply recent results on extracting randomness from independent sources to ``extract'' Kolmogorov complexity. For any $\alpha, \epsilon > 0$, given a string $x$ with $K(x) > \alpha|x|$, we show how to use a constant number of advice bits to efficiently compute another string $y$, $|y|=\Omega(|x|)$, with $K(y) > (1-\epsilon)|y|$. ... more >>>

We show that RL is contained in L/O(n), i.e., any language computable in randomized logarithmic space can be computed in deterministic logarithmic space with a linear amount of non-uniform advice. To prove our result we show how to take an ultra-low space walk on the Gabber-Galil expander graph. more >>>

A property tester with high probability accepts inputs satisfying a given property and rejects inputs that are far from satisfying it. A tolerant property tester, as defined by Parnas, Ron and Rubinfeld, must also accept inputs that are close enough to satisfying the property. We construct properties of binary functions ... more >>>

We prove a new equivalence between the non-uniform and uniform complexity of exponential time. We show that EXP in NP/log if and only if EXP = P^NP|| (polynomial time with non-adaptive queries to SAT). Our equivalence makes use of a recent result due to Shaltiel and Umans showing EXP in ... more >>>

We show that for any constant a, ZPP/b(n) strictly contains ZPTIME(n^a)/b(n) for some b(n) = O(log n log log n). Our techniques are very general and give the same hierarchy for all the common promise time classes including RTIME, NTIME \cap coNTIME, UTIME, MATIME, AMTIME and BQTIME. We show a ... 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 introduce the study of Kolmogorov complexity with error. For a metric d, we define C_a(x) to be the length of a shortest program p which prints a string y such that d(x,y) \le a. We also study a conditional version of this measure C_{a,b}(x|y) where the task is, given ... 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 >>>

We study the complexity of solving succinct zero-sum games, i.e., the games whose payoff matrix $M$ is given implicitly by a Boolean circuit $C$ such that $M(i,j)=C(i,j)$. We complement the known $\EXP$-hardness of computing the \emph{exact} value of a succinct zero-sum game by several results on \emph{approximating} the value. (1) ... more >>>

We show that any 1-round 2-server Private Information Retrieval Protocol where the answers are 1-bit long must ask questions that are at least $n-2$ bits long, which is nearly equal to the known $n-1$ upper bound. This improves upon the approximately $0.25n$ lower bound of Kerenidis and de Wolf while ... more >>>

We show new tradeoffs for satisfiability and nondeterministic linear time. Satisfiability cannot be solved on general purpose random-access Turing machines in time $n^{1.618}$ and space $n^{o(1)}$. This improves recent results of Lipton and Viglas and Fortnow. more >>>

We review the past ten years in computational complexity theory by focusing on ten theorems that the author enjoyed the most. We use each of the theorems as a springboard to discuss work done in various areas of complexity theory. more >>>