How Exactly Hard are `Intermediately-Hard’ Problems?
Date:
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:
- ε-approximate Nash Equilibrium with good social welfare [BKW ‘15, KY ‘16];
- Densest-k-subgraph with perfect completeness (or additive approximation guarantees) [BKRW ‘15];
- Signaling for Bayesian Games [Rub ‘16, KY ‘16];
- Approximation guarantee for dense-CSPs [MR ‘16].