Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Hardness Self-Amplification: Simplified, Optimi...

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

Nobutaka Shimizu

June 23, 2023
Tweet

More Decks by Nobutaka Shimizu

Other Decks in Science

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. 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
  10. 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]
  11. 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 ⇒
  12. 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?
  13. 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
  14. 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 😔
  15. 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]
  16. 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]
  17. Our Reduction 18 •For simplicity we focus on Search Planted

    Clique • : algo with success prob • : input (chosen from ) 𝒜 ϵ G Gn,1/2,k G ?
  18. 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
  19. 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]
  20. 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
  21. 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/ϵ)
  22. 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†
  23. Query Graph 26 By the expansion property, for of ,

    -fraction of neighbors are in 99 % (X, Y) ϵ/2 S (X, Y) S ϵ/2 99%
  24. Query Graph 27 If we sample random neighbors, one of

    them is in O(1/ϵ) S (X, Y) S ϵ/2 99%
  25. Up-Down Walk 28 P P† To bound , we need

    rapid mixing of RW according to λ2 (PP†) PP†
  26. Up-Down Walk 29 P P† This can be done by

    coupling technique of Markov chain
  27. •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