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

Nearly Optimal Average-Case Complexity of Count...

Nearly Optimal Average-Case Complexity of Counting Bicliques Under SETH

Slide of my talk at SODA2021.

Nobutaka Shimizu

July 05, 2022
Tweet

More Decks by Nobutaka Shimizu

Other Decks in Research

Transcript

  1. /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
  2. /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]
  3. /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
  4. /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
  5. /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]
  6. /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]
  7. /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]
  8. /27 )BSEOFTT"NQMJ DBUJPO w #BTFEPOBNJMEMZIBSEQSPCMFN DPOTUSVDUBTUSPOHMZIBSE QSPCMFN (Π, 𝒟 )

    (Π′  , 𝒟 ′  ) 9 (Π, 𝒟 ) (Π′  , 𝒟 ′  ) [Yao, 1982] w "QQMJDBUJPOJODSZQUPHSBQIZBOEEFSBOEPNJ[BUJPO w 8FMMTUVEJFEJODPBSTFHSBJOFEDPNQMFYJUZ
  9. /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 ) (Π, 𝒟 )
  10. 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]
  11. /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)
  12. /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)
  13. /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]
  14. /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]
  15. /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
  16. /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
  17. /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)
  18. /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
  19. /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
  20. /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
  21. /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 )
  22. /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
  23. /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]