Nearly Optimal Average-Case Complexity of Counting Bicliques Under SETH

/FBSMZ0QUJNBM"WFSBHF$BTF $PNQMFYJUZPG$PVOUJOH#JDMJRVFT 6OEFS4&5) 4IVJDIJ)JSBIBSBBOE/PCVUBLB4IJNJ[V National Institute of Informatics The University
of Tokyo

/27 "WFSBHF$BTF$PNQMFYJUZ w %JTUSJCVUJOPBM1SPCMFN (Π, 𝒟 ) 2 w
JTBQSPCMFN BOTXFSGPSJOQVU Π Π(x) x w JTBTFRVFODFPGEJTUSJCVUJPOT 𝒟 = ( 𝒟 n )n∈ℕ A (deterministic) algorithm solves with success probability if A (Π, 𝒟 ) δ [Levin, 1986] ∀n ∈ ℕ, Pr x∼ 𝒟 n [A(x) = Π(x)] ≥ δ w )BSEOFTTGPSBSBOEPNJOQVU

/27 3 - Hamilton cycle : in time ( with
- chromatic number : 2-approx. in time [Grimmett, McDiarmid, 1975] - max clique : 2-approx. in time [Karp, 1976] - max matching: in time [Motwani, 1994] O(n(log n)2) G(n, p) p ≈ C log n/n O(n3) O(n2) O(m log n) &BTZ1SPCMFNTPO3BOEPN(SBQI [Angluin and Valiant, 1979]

/27 )BSE1SPCMFNTPO3BOEPN(SBQIT w .BYJNVNDMJRVFBENJUTBQQSPYQPMZUJNFBMHPSJUIN ˠ$POKFDUVSFUIBU BQQSPYJTIBSEJOQPMZUJNF[Karp, 1976] (2 − ϵ)
4 ɾSubgraph counting problems [Dalirrooyfard, Lincoln, Williams, 2020] w $MJRVFDPVOUJOH[Goldreich, Rothblum, 2018] [Boix-Adserà, Brennan, Bresler, 2019] k w 1MBOUFEDMJRVF

/27 )BSE1SPCMFNTPO3BOEPN(SBQIT w .BYJNVNDMJRVFBENJUTBQQSPYQPMZUJNFBMHPSJUIN ˠ$POKFDUVSFUIBU BQQSPYJTIBSEJOQPMZUJNF[Karp, 1976] (2 − ϵ)
5 ɾSubgraph counting problems [Dalirrooyfard, Lincoln, Williams, 2020] w $MJRVFDPVOUJOH[Goldreich, Rothblum, 2018] [Boix-Adserà, Brennan, Bresler, 2019] k w 1MBOUFEDMJRVF based on worst-case hardness

/27 8PSTU$BTFUP"WFSBHF$BTF 6 ɾ such that is reducible to [Goldreich,
Rothblum, 2018] ɾ is reducible to with overhead [Boix-Adserà, Brennan, Bresler, 2019] ∃ 𝒟 #Ka (#Ka , 𝒟 ) #Ka (#Ka , G(n, p)) O(p−1) Worst-case to average-case reduction for graph problems: Theorem Under (randomized) ETH, any -time algorithm for has success prob. for any constant . no(a) (#Ka , G(n, p)) ≤ 1 − 1/polylog(n) p [Boix-Adserà, Brennan, Bresler, 2019] ɾFor general subgraph , is reducible to H #H (#H, G(n, p)) [Dalirrooyfard, Lincoln, Williams, 2020]

/27 *TTVF4VDDFTT1SPCBCJMJUZ 7 Theorem Under (randomized) ETH, any -time algorithm
for has success prob. for any constant . no(a) (#Ka , G(n, p)) ≤ 1 − 1/polylog(n) p [Boix-Adserà, Brennan, Bresler, 2019]

/27 *TTVF4VDDFTT1SPCBCJMJUZ w 5IFSFTVMUBCPWFMPPLTBUTNBMMGSBDUJPOPGSBOEPNHSBQIT 8 1/polylog(n) We want hardness of
“almost all” random graphs w 0WFSDPNFUIJTJTTVFCZIBSEOFTTBNQMJ DBUJPO Theorem Under (randomized) ETH, any -time algorithm for has success prob. for any constant . no(a) (#Ka , G(n, p)) ≤ 1 − 1/polylog(n) p [Boix-Adserà, Brennan, Bresler, 2019]

/27 )BSEOFTT"NQMJ DBUJPO w #BTFEPOBNJMEMZIBSEQSPCMFN DPOTUSVDUBTUSPOHMZIBSE QSPCMFN (Π, 𝒟 )
(Π′ , 𝒟 ′ ) 9 (Π, 𝒟 ) (Π′ , 𝒟 ′ ) [Yao, 1982] w "QQMJDBUJPOJODSZQUPHSBQIZBOEEFSBOEPNJ[BUJPO w 8FMMTUVEJFEJODPBSTFHSBJOFEDPNQMFYJUZ

/27 %JSFDU1SPEVDU w %JSFDU1SPEVDUCBTJDUFDIOJRVFPGIBSEOFTTBNQMJ DBUJPO 10 For and , let
a s ɾ , ɾ is a sequence of distributions, where each is the distribution of i.i.d. samples from . (Π, 𝒟 ) k ∈ ℕ (Π, 𝒟 )k := (Πk, 𝒟 k) Πk(x1 , …, xk ) = (Π(x1 ), …, Π(xk )) 𝒟 k = ( 𝒟 k n )n∈ℕ 𝒟 k n k 𝒟 n [Yao, 1982] ˠ*G JTIBSE UIFO JTIBSE*OEFFE UIFDPOWFSTFIPMET (Π, 𝒟 )k (Π, 𝒟 ) (Direct Product Theorem) [Yao, 1982] w *G DBOCFTPMWFEXJUITVDDFTTQSPC UIFO DBOCFTPMWFE XJUITVDDFTTQSPC XJUIBPWFSIFBEPGGBDUPS (Π, 𝒟 ) δ (Πk, 𝒟 k) δk k De fi nition (Direct Product of ) (Π, 𝒟 )

0VS3FTVMU

Input: graph . Output: # of -subgraphs in #Ka,b G
Ka,b G a b • -Detection Ka,b • NP-complete (a and b are given as input ) • W[1]-hard (parameteriszed by ) • -Detection requires time under ET H • time algo a = b Ka,a nΩ( a) O*(1.6914n) [Garey, Johnson 1979] [Lin, 2015] [Binkele-Raible, Fernau, Gaspers, Liedloff, 2010] • #Ka,b • tim e • on bipartite grap h • time O*(1.6107) O*(1.4423n) O(1.2491n) [Kutzkov, 2012] [Gaspers, Kratsch, Liedloff 2012] [Couturier, Kratsch 2012] • enumerate Ka,b pattern mining [Agrawal, Srikant, 1994] bioinformatics [Driskell, Ané, Burleigh, McMahon, Sanderson, 2004] • small : time, or time if a O(na+1) O(nω) a = 2 12 /27 [Lin, 2015]

/27 Theorem Theorem 3FTVMU 13 Under (randomized) SETH, for any
and , there exists such tha any time algorithm for has a success prob. . a ≥ 3 ϵ > 0 b O(na−ϵ) (#Ka,b , 𝒦 a,b,n ) ≤ 1 − 1/polylog(n) For any and , can be solved in time . a ≥ 8 b ∈ ℕ #Ka,b bna+o(1)

/27 Theorem Theorem Under (randomized) SETH, for any and ,
there exists such tha any time algorithm for has a success prob. . a ≥ 3 ϵ > 0 b O(na−ϵ) (#Ka,b , 𝒦 a,b,n ) ≤ 1 − 1/polylog(n) For any and , can be solved in time . a ≥ 8 b ∈ ℕ #Ka,b bna+o(1) 3FTVMU 14 WFSU 𝒦 a,b,n vertices α vertices β : distribution of a random bipartite graph w.p. 1/2 Let α ∼ Unif(1,…, a), β ∼ Unif(1,…, b)

/27 Theorem (Fine-Grained Hardness Ampli cation) 3FTVMU Under SETH, for
any and , there are and such tha any time algorithm for has success prob. . a ≥ 3 ϵ > 0 b ∈ ℕ k = polylog(n) O(na−ϵ) (#Ka,b , 𝒦 a,b,n )k ≤ n−O(ϵ) ɾ#ZDPNCJOJOH(PMESFJDI-FWJOUFDIOJRVF 15 1/polylog(n) 1 − n−ϵ Result 1 Result 2 [Goldreich, Levin, 1989] we amplify the hardness of computing parity , which corresponds to #Ka,b Yao’s XOR lemma [Yao, 1982], [Levin, 1987]

/27 3FMBUFE8PSL ɾ , requires under ET - is the
distribution of “arti fi cial” random graphs ɾ requires time under ET - Issue in success probability: ɾWorst-case to average-case reduction for (H is a general graph - Issue in success probability: ∃ 𝒟 (#Ka , 𝒟 ) nΩ(a) 𝒟 (#Ka , G(n, p)) nΩ(k) 1 − 1/polylog(n) #H 1 − 1/polylog(n) 16 [Goldreich Rothblum, 2018] [Boix-Adserà, Brennan, Bresler, 2019] [Dalirrooyfard, Lincoln, Williams, 2020]

5FDIOJRVFT

/27 Theorem (Reminder) )BSEOFTT"NQMJ DBUJPO Under SETH, for any and
, there are and such tha any time algorithm for has success prob. . a ≥ 3 ϵ > 0 b ∈ ℕ k = polylog(n) O(na−ϵ) (#Ka,b , 𝒦 a,b,n )k ≤ n−O(ϵ) ɾ8FDPNCJOFUIFEJSFDUQSPEVDUUIFPSFNPG 18 1/polylog(n) 1 − n−ϵ Result 1 Result 2 [Impagliazzo, Jaiswal, Kabanets, Wigderson, 2010] XJUIPVSOFXJOUFSBDUJWFQSPPGTZTUFNXJUIMPXRVFSZDPNQMFYJUZ

/27 Theorem (Informal; Impagliazzo et al. 2010) %JSFDU1SPEVDU5IFPSFN Let be
a -time algorithm that solves with success probability Then, there is a list of algorithms such tha ɾFor some , solves with success probability ɾEach runs in time . A T(n) (Π, 𝒟 )k ≈ δk (M1 , …, Mm ) i ∈ [m] MA i (Π, 𝒟 ) ≈ δ MA j ≈ T(n) w 8FBQQMZ%15PG[Impagliazzo, Jaiswal, Kabanets, Wigderson, 2010] Here, , and the list can be computed in time . m = O((1/δ)k) T(n) (each algorithm is represented as an oracle circuit) 19

/27 0VS4FUUJOH#Ka,b w MJTUPGPSBDMFBMHPSJUINTTVDIUIBU ∃M1 , …, Mm 8IJDI TPMWFT
Mi (#Ka,b , 𝒦 a,b,n ) ɾFor some , solves with success prob ɾEach runs in time ɾ i MA i (#Ka,b , 𝒦 a,b,n ) ≥ 1 − n−ϵ Mj ≈ na−ϵ m = poly log n w 5PJEFOUJGZ XFDPOTUSVDUBOJOUFSBDUJWFQSPPGTZTUFN Mi 20 w BMHPSJUINGPS XJUITVDDFTTQSPC A (#Ka,b , 𝒦 a,b,n )polylogn n−ϵ BOETJNVMBUFJUVTJOHFBDI BTBQSPWFS Mj We want to solve in time . #Ka,b na−ϵ+o(1)

/27 Theorem (IP for ) #Ka,b *1XJUIMPXRVFSZDPNQMFYJUZ There is an
-round IP for such that 1. Veri fi er runs in time . 2. Veri fi er makes at most queries 3. Each query is of the form “ 4. If Prover solves correctly, Veri fi er accepts w.p. 1 5. Otherwise, Veri fi er rejects w.p. . O(log n) #Ka,b n2poly log n poly log n #Ka,b (G) = ? #Ka,b ≥ 2/3 21 w (PMESFJDIBOE3PUICMVNDPOTUSVDUFEBO*1GPS XJUIRVFSZDPNQMFYJUZ #Ka Θ(n) [Goldreich and Rothblum, 2018] w #BTFEPOTVNDIFDLQSPUPDPMGPSQFSNBOFOUPG [Lund, Fortnow, Karloff, Nisan, 1990] w 8FDPOTUSVDU*1GPS$PMPSFE H

/27 *EFOUJ fi DBUJPOVTJOH*1 w MJTUPGBMHPSJUINTTVDIUIBU ∃M1 , …, Mm
w 8IJDI TPMWFT Mi (#Ka,b , 𝒦 a,b,n ) ɾFor some , solves with success prob ɾEach runs in time ɾ i Mi (#Ka,b , 𝒦 a,b,n ) ≥ 1 − n−ϵ Mj ≈ na−ϵ m = poly log n w *EFB3VO*1VTJOHFBDI BT1SPWFS Mj 22

/27 *EFOUJ fi DBUJPOVTJOH*1 w -FU CFUIFJOQVUPG G #Ka,b
w 3VO*1VTJOH BT1SPWFS Mj Prover Veri fi er ? #Ka,b (Gj ) = G1 #Ka,b (G1 ) /PUFUIBU JTSFEVDJCMFUP 5IFSFGPSF XFDBOJNQMFNFOU1SPWFSVTJOH #Ka,b (#Ka,b , 𝒦 a,b,n ) Mj w *G7FSJ fi FSBDDFQUTGPS1SPWFS UIFO JTUIFSJHIUBMHPSJUIN Mi Mi 23

/27 3VOOJOH5JNF w &BDI SVOTJOUJNF Mj O(na−ϵ) w 7FSJ
fi FSNBLFT RVFSJFT poly log n w 3VO*1GPS UJNFT m = polylogn w 5PUBMSVOOJOHUJNFna−ϵpolylogn 24 Prover Veri fi er G1 #Ka,b (G1 )

/27 3VOOJOH5JNF w &BDI SVOTJOUJNF Mj O(na−ϵ) w 3VO*1GPS
UJNFT m = polylogn w 5PUBMSVOOJOHUJNFna−ϵpolylogn 25 Prover Veri fi er ? #Ka,b (Gj ) = G1 #Ka,b (G1 ) w 7FSJ fi FSNBLFT RVFSJFT poly log n *G7FSJ fi FSNBLFT RVFSJFT UIFO UPUBMSVOOJOHUJNF n na+1−ϵpoly log n

/27 $PODMVTJPO 26 w lTIBSQUISFTIPMESFTVMUz w )BSEOFTTBNQMJ fi DBUJPOJO fi
OFHSBJOFEDPNQMFYJUZ -time algo ∃ na+o(1) -time algo ∀ na−ϵ hardness ampli fi cation for -time algorithms na−ϵ ɾContributes to fi ne-grained average-case complexity [Ball, Rosen, Sabin, Vasudevan, 2017]

Nearly Optimal Average-Case Complexity of Count...

Nearly Optimal Average-Case Complexity of Counting Bicliques Under SETH

Nobutaka Shimizu

More Decks by Nobutaka Shimizu

Other Decks in Research

Featured

Transcript

/FBSMZ0QUJNBM"WFSBHF$BTF $PNQMFYJUZPG$PVOUJOH#JDMJRVFT 6OEFS4&5) 4IVJDIJ)JSBIBSBBOE/PCVUBLB4IJNJ[V National Institute of Informatics The University

/27 "WFSBHF$BTF$PNQMFYJUZ w %JTUSJCVUJOPBM1SPCMFN (Π, 𝒟 ) 2 w

/27 3 - Hamilton cycle : in time ( with

/27 )BSE1SPCMFNTPO3BOEPN(SBQIT w .BYJNVNDMJRVFBENJUTBQQSPYQPMZUJNFBMHPSJUIN ˠ$POKFDUVSFUIBU BQQSPYJTIBSEJOQPMZUJNF[Karp, 1976] (2 − ϵ)

/27 )BSE1SPCMFNTPO3BOEPN(SBQIT w .BYJNVNDMJRVFBENJUTBQQSPYQPMZUJNFBMHPSJUIN ˠ$POKFDUVSFUIBU BQQSPYJTIBSEJOQPMZUJNF[Karp, 1976] (2 − ϵ)

/27 8PSTU$BTFUP"WFSBHF$BTF 6 ɾ such that is reducible to [Goldreich,

/27 *TTVF4VDDFTT1SPCBCJMJUZ 7 Theorem Under (randomized) ETH, any -time algorithm

/27 *TTVF4VDDFTT1SPCBCJMJUZ w 5IFSFTVMUBCPWFMPPLTBUTNBMMGSBDUJPOPGSBOEPNHSBQIT 8 1/polylog(n) We want hardness of

/27 )BSEOFTT"NQMJ DBUJPO w #BTFEPOBNJMEMZIBSEQSPCMFN DPOTUSVDUBTUSPOHMZIBSE QSPCMFN (Π, 𝒟 )

/27 %JSFDU1SPEVDU w %JSFDU1SPEVDUCBTJDUFDIOJRVFPGIBSEOFTTBNQMJ DBUJPO 10 For and , let

0VS3FTVMU

Input: graph . Output: # of -subgraphs in #Ka,b G

/27 Theorem Theorem 3FTVMU 13 Under (randomized) SETH, for any

/27 Theorem Theorem Under (randomized) SETH, for any and ,

/27 Theorem (Fine-Grained Hardness Ampli cation) 3FTVMU Under SETH, for

/27 3FMBUFE8PSL ɾ , requires under ET - is the

5FDIOJRVFT

/27 Theorem (Reminder) )BSEOFTT"NQMJ DBUJPO Under SETH, for any and

/27 Theorem (Informal; Impagliazzo et al. 2010) %JSFDU1SPEVDU5IFPSFN Let be

/27 0VS4FUUJOH#Ka,b w MJTUPGPSBDMFBMHPSJUINTTVDIUIBU ∃M1 , …, Mm 8IJDI TPMWFT

/27 Theorem (IP for ) #Ka,b *1XJUIMPXRVFSZDPNQMFYJUZ There is an

/27 EFOUJ fi DBUJPOVTJOH1 w MJTUPGBMHPSJUINTTVDIUIBU ∃M1 , …, Mm

/27 EFOUJ fi DBUJPOVTJOH1 w -FU CFUIFJOQVUPG G #Ka,b

/27 3VOOJOH5JNF w &BDI SVOTJOUJNF Mj O(na−ϵ) w 7FSJ

/27 3VOOJOH5JNF w &BDI SVOTJOUJNF Mj O(na−ϵ) w 3VO*1GPS

/27 $PODMVTJPO 26 w lTIBSQUISFTIPMESFTVMUz w )BSEOFTTBNQMJ fi DBUJPOJO fi