hard (for ) if • is -hard if ‣ is drawn from some distribution (in this talk, uniform distribution) 𝒞 f 𝒞 ∀A ∈ 𝒞 , ∃x, A(x) ≠ f(x) f δ ∀A ∈ 𝒞 , Pr x [A(x) ≠ f(x)] ≥ δ x Average-Case Complexity 2
hard (for ) if • is -hard if ‣ is drawn from some distribution (in this talk, uniform distribution) 𝒞 f 𝒞 ∀A ∈ 𝒞 , ∃x, A(x) ≠ f(x) f δ ∀A ∈ 𝒞 , Pr x [A(x) ≠ f(x)] ≥ δ x Average-Case Complexity 3 perfect score is difficult
hard (for ) if • is -hard if ‣ is drawn from some distribution (in this talk, uniform distribution) 𝒞 f 𝒞 ∀A ∈ 𝒞 , ∃x, A(x) ≠ f(x) f δ ∀A ∈ 𝒞 , Pr x [A(x) ≠ f(x)] ≥ δ x Average-Case Complexity 4 perfect score is difficult even 50% is difficult
‣ #NSETH •cryptography, derandomization, etc δ f δ ≈ 1 𝖯 ≠ 𝖭 𝖯 Two Directions 5 ᶃ Explicit Construction ᶄ Practical Hardness of Problems •Target: specific over specific input distribution ‣ Find a maximum clique in ‣ Random SAT • efficient algo that succeeds on many inputs? •Avoid the pessimism of worst-case analysis f G(n, p) ∃ Are techniques in ᶃ useful for ᶄ ?
-hard ‣ is strongly hard if is -hard f f f ϵ f f (1/2 − δ) Weak and Strong Hardness 6 Constant algo ( or ) succeeds on 1/2-fraction of inputs. A(x) = 1 A(x) = 0
-hard ‣ is strongly hard if is -hard •Goal of Direction ᶃ : explicit construction of strongly hard f f f ϵ f f (1/2 − δ) f Weak and Strong Hardness 7 strongly hard worst-case hard
lemma ‣ , where are independent •Derandomized XOR lemma ‣ , where have some correlation •Typically, is artificial ‣ They might be not suitable for Direction ᶄ without any modification f g g(x1 , …, xk ) = f(x1 ) ⊕ … ⊕ f(xk ) x1 , …, xk ∼ {0,1}n g(x1 , …, xk ) = f(x1 ) ⊕ … ⊕ f(xk ) x1 , …, xk g Hardness Amplification 9 [Yao 82][Levin 87] [Impagliazzo, Wigderson, 97]
Hardness amplification for Natural Problems ‣ Triangle counting mod 2 ‣ Online Vector-Matrix-Vector Multiplication over •Ingredient: New derandomized XOR lemma based on ‣ Feasible hard-core set : Generalization of hard-core set ‣ Computational design : Generalization of combinatorial design g = f 𝔽 2 Our Contribution 12 [Impagliazzo, 1995] [Nisan, Wigderson, 1994]
Hardness amplification for Natural Problems ‣ Triangle counting mod 2 ‣ Online Vector-Matrix-Vector Multiplication over •Ingredient: New derandomized XOR lemma based on ‣ Feasible hard-core set : Generalization of hard-core set ‣ Computational design : Generalization of combinatorial design g = f 𝔽 2 Our Contribution 13 [Impagliazzo, 1995] [Nisan, Wigderson, 1994]
Triangle Counting is worst-case hard for -time algo, then it is -hard (over Erdős–Rényi graph) • If Triangle Counting Mod 2 is worst-case hard for -time algo, then it is -hard for nω−ϵ 1/polylog(n) nω−ϵ δ δ = 2−9 ≈ 0.000004 Subgraph Counting on Random Graphs 15 [Goldreich and Rothblum, 2018] [Boix-Adserà, Brennan, Bresler, 2019] [Dalirrooyfard, Lincoln, Williams, 2020] [Boix-Adserà, Brennan, Bresler, 2019] [Goldreich, 2020] [Hirahara, Shimizu, 2021] Previous : weak hardness from wrs-hardness [Boix-Adserà, Brennan, Bresler, 2019] [Boix-Adserà, Brennan, Bresler, 2019] [Goldreich, 2020]
be any constants. If is -hard for small circuits, then is -hard for small circuits. In particular, is -hard if it is worst-case hard. δ, ϵ > 0 𝖳 𝗋 𝗂 𝖯 𝖺 𝗋 𝗂 𝗍 𝗒 δ 𝖳 𝗋 𝗂 𝖯 𝖺 𝗋 𝗂 𝗍 𝗒 (1/2 − ϵ) 𝖳 𝗋 𝗂 𝖯 𝖺 𝗋 𝗂 𝗍 𝗒 (1/2 − ϵ) • … #triangles mod 2 in a tripartite graph 𝖳 𝗋 𝗂 𝖯 𝖺 𝗋 𝗂 𝗍 𝗒 : {0,1}3n2 → {0,1} vertices n vertices n vertices n Each possible edge appears with prob 1/2 Tripartite ER Graph
block ( ) •Define by f: {0,1}n → {0,1} x ∈ {0,1}kn xi i |xi | = n g: {0,1}nk → {0,1} XOR Lemma 18 g(x) = f(x1 ) ⊕ ⋯ ⊕ f(xk ) x1 x2 x3 x4 x5 x = If is -hard, then is -hard for some . f δ g (1/2 − ϵ) k = O(log(1/ϵ)/δ) Theorem (informal) [Yao 84][Levin 87]
, ) •For , let •Define by f: {0,1}n → {0,1} 𝒮 = {S1 , …, Sk } Si ⊆ [ℓ] |Si | = n x ∈ {0,1}ℓ xi = x| Si g: {0,1}ℓ → {0,1} Derandomized XOR Lemma of NW 19 x1 x = g(x) = f(x1 ) ⊕ ⋯ ⊕ f(xk ) x2 x3 x4 Suppose is a combinatorial design. If is -hard, then is -hard for some . 𝒮 = (Si ) f δ g (1/2 − ϵ) k = k(δ, ϵ) Theorem (informal) [Impagliazzo, Wigderson, 1997]
, ) •For , let •Define by f: {0,1}n → {0,1} 𝒮 = {S1 , …, Sk } Si ⊆ [ℓ] |Si | = n x ∈ {0,1}ℓ xi = x| Si g: {0,1}ℓ → {0,1} Derandomized XOR Lemma of NW 20 x1 x = g(x) = f(x1 ) ⊕ ⋯ ⊕ f(xk ) x2 x3 x4 Suppose is a combinatorial design. If is -hard, then is -hard for some . 𝒮 = (Si ) f δ g (1/2 − ϵ) k = k(δ, ϵ) [Impagliazzo, Wigderson, 1997] Theorem (informal) is a -combinatorial design if for 𝒮 d |Si ∩ Sj | ≤ d ∀i ≠ j
, ) •For , let •Define by f: {0,1}n → {0,1} 𝒮 = {S1 , …, Sk } Si ⊆ [ℓ] |Si | = n x ∈ {0,1}ℓ xi = x| Si g: {0,1}ℓ → {0,1} New Derandomized XOR Lemma 21 x1 x = g(x) = f(x1 ) ⊕ ⋯ ⊕ f(xk ) x2 x3 x4 Suppose is a computational design. If is -hard, then is -hard for some . 𝒮 = (Si ) f δ g (1/2 − ϵ) k = k(δ, ϵ) Theorem (informal, this work)
, ) •For , let •Define by f: {0,1}n → {0,1} 𝒮 = {S1 , …, Sk } Si ⊆ [ℓ] |Si | = n x ∈ {0,1}ℓ xi = x| Si g: {0,1}ℓ → {0,1} New Derandomized XOR Lemma 22 x1 x = g(x) = f(x1 ) ⊕ ⋯ ⊕ f(xk ) x2 x3 x4 Suppose is a computational design. If is -hard, then is -hard for some . 𝒮 = (Si ) f δ g (1/2 − ϵ) k = k(δ, ϵ) Theorem (informal, this work) Roughly speaking, is a computational design if has a small “computational cost” 𝒮 Si ∩ Sj
, ) •For , let •Define by f: {0,1}n → {0,1} 𝒮 = {S1 , …, Sk } Si ⊆ [ℓ] |Si | = n x ∈ {0,1}ℓ xi = x| Si g: {0,1}ℓ → {0,1} New Derandomized XOR Lemma 23 x1 x = g(x) = f(x1 ) ⊕ ⋯ ⊕ f(xk ) x2 x3 x4 Suppose is a computational design. If is -hard, then is -hard for some . 𝒮 = (Si ) f δ g (1/2 − ϵ) k = k(δ, ϵ) Theorem (informal, this work) is a computational design for if can be computed by a small circuit given in advance. 𝒮 f f(xi ) x| Si ∖Sj
If is -hard for size , then there is a set of such that is -hard over for size . f δ S H ⊆ {0,1}n |H| ≥ δ ⋅ 2n f (1/2 − ϵ) H O(ϵ2δ2S) • Such is called hard-core set • On a hard-core set, is strongly hard • We can derive DXOR of NW from hard-core lemma H f [Hearly, Vadhan, Viola, 2006]
… ⊕ f(xk ) (1/2 − ϵ) xi = x| Si we can distinguish and (f(x1 ), …, f(xk )) (fH (x1 ), …, fH (xk )) we can distinguish and (f(x1 ), …, f(xi−1 ), fH (xi ), fH (xi+1 ), …, fH (xk )) , fH (xi+1 ), …, fH (xk )) f(xi ) (f(x1 ), …, f(xi−1 ), hybrid argument combinatorial design we can distinguish and f(x) fH (x) next-bit predictor is not -hard over f(x) (1/2 − ϵ) H contradict to hard-core lemma! for some i
) ⊕ … ⊕ f(xk ) (1/2 − ϵ) xi = x| Si we can distinguish and (f(x1 ), …, f(xk )) (fH (x1 ), …, fH (xk )) we can distinguish and (f(x1 ), …, f(xi−1 ), fH (xi ), fH (xi+1 ), …, fH (xk )) , fH (xi+1 ), …, fH (xk )) f(xi ) (f(x1 ), …, f(xi−1 ), hybrid argument computational design next-bit predictor is not -hard over f(x) (1/2 − ϵ) H we can distinguish and f(x) fH (x) for some i
) ⊕ … ⊕ f(xk ) (1/2 − ϵ) xi = x| Si we can distinguish and (f(x1 ), …, f(xk )) (fH (x1 ), …, fH (xk )) we can distinguish and (f(x1 ), …, f(xi−1 ), fH (xi ), fH (xi+1 ), …, fH (xk )) , fH (xi+1 ), …, fH (xk )) f(xi ) (f(x1 ), …, f(xi−1 ), hybrid argument computational design is not -hard over f(x) (1/2 − ϵ) H we can distinguish and using -oracle f(x) fH (x) H next-bit predictor for some i
) ⊕ … ⊕ f(xk ) (1/2 − ϵ) xi = x| Si we can distinguish and (f(x1 ), …, f(xk )) (fH (x1 ), …, fH (xk )) we can distinguish and (f(x1 ), …, f(xi−1 ), fH (xi ), fH (xi+1 ), …, fH (xk )) , fH (xi+1 ), …, fH (xk )) f(xi ) (f(x1 ), …, f(xi−1 ), hybrid argument computational design is not -hard over for -oracle circuits f(x) (1/2 − ϵ) H H we can distinguish and using -oracle f(x) fH (x) H next-bit predictor for some i
) ⊕ … ⊕ f(xk ) (1/2 − ϵ) xi = x| Si we can distinguish and (f(x1 ), …, f(xk )) (fH (x1 ), …, fH (xk )) we can distinguish and (f(x1 ), …, f(xi−1 ), fH (xi ), fH (xi+1 ), …, fH (xk )) , fH (xi+1 ), …, fH (xk )) f(xi ) (f(x1 ), …, f(xi−1 ), hybrid argument computational design is not -hard over for -oracle circuits f(x) (1/2 − ϵ) H H we can distinguish and using -oracle f(x) fH (x) H we need to modify hard-core lemma next-bit predictor for some i
If is -hard for size , then there is a set of such that is -hard over for size trapdoor -oracle circuits. f δ S H ⊆ {0,1}n |H| ≥ δ ⋅ 2n f (1/2 − ϵ) H 2−poly(1/ϵ,1/δ)S H • We call such feasible hard-core set • trapdoor oracle circuit for “ can query whenever computes ” • Proof : Boosting algo of [Barak, Hardt, Kale, 09] H CH f C H(q) C f(q) serves as a “key” for the “trapdoor” f(q) H(q)
nobushimi
ks91
__ymgc__
signer
trycycle
sip3ristex
lcolladotor
ikuma_w
aronwalsh
florets1
.jpg){kind=avatar}
mfonobong
.jpg){kind=avatar}
ktatsuya
bkeepers
notwaldorf
ufuk
hannesfritz
jnunemaker
smashingmag
morganepeng
samanthasiow
gr2m
brettharned
moore
brad_frost
