Hardness Self-Amplification: Simplified, Optimized, and Unified

In this paper, we extend the proof framework of direct product theorem based on samplers by [Impagliazzo, Jaiswal, Kabanets, Wigderson, SICOMP2010] to amplify the hardness of a wide variety of natural problems including planted clique, matrix multiplication, online matrix-vector multiplication, and triangle counting. This improves and significantly simplifies previous techniques of hardness self-amplification of [Asadi, Golovnev, Gur, Shinker, STOC22][Hirahara, Shimizu, FOCS22].

Transcript

1. Hardness Self-Amplification: Simplified, Optimized, and Unified Nobutaka Shimizu Tokyo Institute of Technology STOC2023 Shuichi Hirahara National Institute of Informatics
2. •How many hard instances? •Algo computes with success probability if ‣ is chosen from some input distribution (of fixed size) A f γ Pr x [A(x) = f(x)] ≥ γ x Average-Case Complexity 2 I can get -fraction of score of this exam γ f
3. • is worst-case hard efficient algo , , • is weakly-hard efficient algo has success prob • is strongly-hard efficient algo has success prob f def ⟺ ∀ A ∃x A(x) ≠ f(x) f def ⟺ ∀ ≤ 0.99 f def ⟺ ∀ ≤ 0.01 Average-Case Complexity 3 Perfect score is difficult
4. • is worst-case hard efficient algo , , • is weakly-hard efficient algo has success prob • is strongly-hard efficient algo has success prob f def ⟺ ∀ A ∃x A(x) ≠ f(x) f def ⟺ ∀ ≤ 0.99 f def ⟺ ∀ ≤ 0.01 Average-Case Complexity 4 99% score is difficult
5. • is worst-case hard efficient algo , , • is weakly-hard efficient algo has success prob • is strongly-hard efficient algo has success prob f def ⟺ ∀ A ∃x A(x) ≠ f(x) f def ⟺ ∀ ≤ 0.99 f def ⟺ ∀ ≤ 0.01 Average-Case Complexity 5
6. • is worst-case hard efficient algo , , • is weakly-hard efficient algo has success prob • is strongly-hard efficient algo has success prob f def ⟺ ∀ A ∃x A(x) ≠ f(x) f def ⟺ ∀ ≤ 0.99 f def ⟺ ∀ ≤ 0.01 Average-Case Complexity 6 is strongly-hard f is weakly-hard f is worst-case hard f trivial trivial
7. • is worst-case hard efficient algo , , • is weakly-hard efficient algo has success prob • is strongly-hard efficient algo has success prob f def ⟺ ∀ A ∃x A(x) ≠ f(x) f def ⟺ ∀ ≤ 0.99 f def ⟺ ∀ ≤ 0.01 Average-Case Complexity 7 is strongly-hard f is weakly-hard f is worst-case hard f random self-reduction hardness self-amplification
8. •This paper: hardness self-amplification for popular problems ‣ matrix multiplication ‣ online matrix-vector problem ‣ triangle counting (for nonuniform algo) ‣ planted clique •Our Ingredient ‣ A framework of hardness amplification using expanders (samplers) ‣ The same framework was previously used to obtain Direct Product Theorem Our Results 8 [Impagliazzo, Jaiswal, Kabanets, Wigderson (2010)]
9. Planted Clique
10. Random Graph with Planted Clique 10 •Input: random -clique + (Erdős–Rényi graph) ‣ Sample ‣ Randomly choose a set of vertices ‣ Make a -clique by adding edges ‣ let be the resulting graph •Maximum clique of ‣ We assume ‣ Then, is the unique -clique (whp) k Gn,1/2 Gn,1/2 C ⊆ V k C k Gn,1/2,k Gn,1/2 ≈ 2 log2 n k ≫ log n C k many -cliques O(log n) unique -clique k
11. Search Planted Clique 11 Input : Output : any -clique (not necessarily be the planted one) Gn,1/2,k k Def (Search Planted Clique Problem) •If , poly-time algo with success prob ‣ the larger , the easier it it is to solve •open problem: poly-time algo for k = Ω( n) ∃ 1 − 2−n0.1 k log n ≪ k ≪ n [Jerrum, 92][Kučera, 95] [Alon, Krivelevich, Sudakov, 98] [Dekel, Gurel-Gurevich, Peres, 2014]
12. Decision Planted Clique 12 Input : (with prob 1/2) or (with prob 1/2) Output : “Yes” if the input contains a -clique. “No” otherwise. Gn,1/2,k Gn,1/2 k Def (Decision Planted Clique Problem) • has advantage if ‣ Random guess: ‣ Goal: •Algo for Search Planted Clique Algo for Decision Planted Clique •Does converse hold? 𝒜 γ Pr G [ 𝒜 (G) is correct] ≥ 1 + γ 2 γ = 0 γ ≈ 1 ⇒
13. Decision Planted Clique 13 Input : (with prob 1/2) or (with prob 1/2) Output : “Yes” if the input contains a -clique. “No” otherwise. Gn,1/2,k Gn,1/2 k Def (Decision Planted Clique Problem) • has advantage if ‣ Random guess: ‣ Goal: •Algo for Search Planted Clique Algo for Decision Planted Clique •Does converse hold? 𝒜 γ Pr G [ 𝒜 (G) is correct] ≥ 1 + γ 2 γ = 0 γ ≈ 1 ⇒ Search-to-Decision Reduction?
14. Previous Work 14 Theorem (Alon, Andoni, Kaufman, Matulef, Rubinfeld, Xie, 2007). If we can decide or with advantage , then, we can find a -clique in with success prob . Gn,1/2,k Gn,1/2 1 − 1/n2 k Gn,1/2,k 1 − 1/n •for low-error regime 😔 ‣ reduction has queries + union bound n vs
15. Our Result 15 Theorem. If we can decide or with advantage , then, we can find a -clique in with success prob , where . GN,1/2,k GN,1/2 ϵ(N) ≥ N−1/2+c k Gn,1/2,k 1 − 1/n N = nO(1/c) vs •high-error regime! •Blow-up in instance size 😔
16. Proof Outline 16 decision algo with adv ϵ decision algo with adv 1 − 1/n2 search algo with success prob 1 − 1/n vs vs hardness amplification polynomial blow-up in n Search-to-Decision by [Alon, Andoni, Kaufman, Matulef, Rubinfeld, Xie, 07]
17. Proof Outline 17 decision algo with adv ϵ decision algo with adv 1 − 1/n2 search algo with success prob 1 − 1/n vs vs hardness amplification polynomial blow-up in n Search-to-Decision by [Alon, Andoni, Kaufman, Matulef, Rubinfeld, Xie, 07]
18. Our Reduction 18 •For simplicity we focus on Search Planted Clique • : algo with success prob • : input (chosen from ) 𝒜 ϵ G Gn,1/2,k G ?
19. Our Reduction 19 •For , randomly embed into . Let be the resulting graph. ‣ Let be the randomized reduction that outputs •Repeat until outputs a -clique in • contains a unique -clique since N = poly(n) G GN,1/2 G ℛ 𝒜 (G) 𝒜 (G) ℛ 𝒜 (G) 𝒜 (G) k G G k k ≫ log N G ? ? G
20. Analysis 20 Def (Query Graph) X Y P(G, H) G H The query graph is the edge-weighted bipartite graph defined by set of all -vertex graph having a -clique set of all -vertex graph having a -clique produces query Q = (X, Y, P) X = n k Y = N k P(G, H) = Pr[ℛ 𝒜 (G) H]
21. Analysis 21 Def (Query Graph) The query graph is the edge-weighted bipartite graph defined by set of all -vertex graph having a -clique set of all -vertex graph having a -clique produces query Q = (X, Y, P) X = n k Y = N k P(G, H) = Pr[ℛ 𝒜 (G) H] X Y G G is a random neighbor of G G
22. Analysis 22 Def (Query Graph) The query graph is the edge-weighted bipartite graph defined by set of all -vertex graph having a -clique set of all -vertex graph having a -clique produces query Q = (X, Y, P) X = n k Y = N k P(G, H) = Pr[ℛ 𝒜 (G) H] Theorem (informal) The query graph has an expansion property for some Q N = poly(n,1/δ,1/ϵ)
23. Sampler and Expander 23 •Let be ‣ upward random walk •Let be ‣ = downward random walk P = [0,1]X×Y P(x, y) = 1 |N(x)| P(x, ⋅ ) = P† ∈ [0,1]Y×X P†(y, x) = 1 |N(y)| P†(y, ⋅ ) If , then has the expansion property. λ2 (PP†) ≤ λ Q Lemma x P y P†
24. Query Graph 24 S = {r ∈ R: ℳ(r) succeeds} S
25. Query Graph 25 S has density inside S ϵ R
26. Query Graph 26 By the expansion property, for of , -fraction of neighbors are in 99 % (X, Y) ϵ/2 S (X, Y) S ϵ/2 99%
27. Query Graph 27 If we sample random neighbors, one of them is in O(1/ϵ) S (X, Y) S ϵ/2 99%
28. Up-Down Walk 28 P P† To bound , we need rapid mixing of RW according to λ2 (PP†) PP†
29. Up-Down Walk 29 P P† This can be done by coupling technique of Markov chain
30. •Expansion property of query graph hardness amplification ‣ direct product theorem - Matrix Multiplication - Online Matrix-Vector Multiplication - Triangle Counting ‣ random embedding reduction - Planted Clique - (possibly) other “planted” problems (e.g., planted k-SUM) •Open Problem ‣ improve the blow-up of (ultimately, we want ) ⇒ N = poly(n) N = O(n) Conclusion 30