Tutorial on quasi-poly hardness results assuming ETH-hypothesis


More information here

How Exactly Hard are “Intermediately-Hard” Problems? Proving Quasi-Polynomial Hardness via Birthday Repetition In this talk we give a broad introduction to Birthday Repetition, a technique introduced in [AIM ‘14] to prove quasi-polynomial hardness of “Free” game assuming the Exponential Time Hypothesis. The main observation of the technique is Birthday Paradox, in particular that aggregating the variables in 2CSPs to a tuple of size Õ(√n) then choosing two tuples at random will have a challenge from original 2CSP with high probability.

Using the technique, we show the following specific applications:

  1. ε-approximate Nash Equilibrium with good social welfare [BKW ‘15, KY ‘16];
  2. Densest-k-subgraph with perfect completeness (or additive approximation guarantees) [BKRW ‘15];
  3. Signaling for Bayesian Games [Rub ‘16, KY ‘16];
  4. Approximation guarantee for dense-CSPs [MR ‘16].

Download PPT here