Konstantin Pervyshev

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

Lance Fortnow, Rahul Santhanam

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

more >>>Oded Goldreich

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

Miklos Ajtai, Cynthia Dwork

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

Boaz Barak, Moritz Hardt, Thomas Holenstein, David Steurer

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

Ilan Komargodski, Ran Raz

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

Ilan Komargodski, Ran Raz, Avishay Tal

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