We study the existence of time hierarchies for heuristic (average-case) algorithms. We prove that a time hierarchy exists for heuristics algorithms in such syntactic classes as NP and co-NP, and also in semantic classes AM and MA. Earlier, Fortnow and Santhanam (FOCS'04) proved the existence of a time hierarchy for ... more >>>

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

more >>>

Motivated by a recent study of Zimand (22nd CCC, 2007),
we consider the average-case complexity of property testing
(focusing, for clarity, on testing properties of Boolean strings).
We make two observations:

1) In the context of average-case analysis with respect to
the uniform distribution (on all strings of ... more >>>

We describe a public-key cryptosystem with worst-case/average case
equivalence. The cryptosystem has an amortized plaintext to
ciphertext expansion of $O(n)$, relies on the hardness of the
$\tilde O(n^2)$-unique shortest vector problem for lattices, and
requires a public key of size at most $O(n^4)$ bits. The new
cryptosystem generalizes a conceptually ... more >>>

We study the question of whether the value of mathematical programs such as
linear and semidefinite programming hierarchies on a graph $G$, is preserved
when taking a small random subgraph $G'$ of $G$. We show that the value of the
Goemans-Williamson (1995) semidefinite program (SDP) for \maxcut of $G'$ is
more >>>

We give an explicit function $h:\{0,1\}^n\to\{0,1\}$ such that any deMorgan formula of size $O(n^{2.499})$ agrees with $h$ on at most $\frac{1}{2} + \epsilon$ fraction of the inputs, where $\epsilon$ is exponentially small (i.e. $\epsilon = 2^{-n^{\Omega(1)}}$). Previous lower bounds for formula size were obtained for exact computation.

The same ... more >>>

We give a function $h:\{0,1\}^n\to\{0,1\}$ such that every deMorgan formula of size $n^{3-o(1)}/r^2$ agrees with $h$ on at most a fraction of $\frac{1}{2}+2^{-\Omega(r)}$ of the inputs. This improves the previous average-case lower bound of Komargodski and Raz (STOC, 2013).

Our technical contributions include a theorem that shows that the ``expected ... more >>>