Recent Applications of Quasi-Poly Time Hardness in Densest k-Subgraph
Recent applications of the Birthday Repetition technique have demonstrated the quasi-polynomial time hardness in various computational problems, including AM with k provers, Dense CSPs, Free games, and Nash equilibria. These applications also explore the potential implications in signaling theory and Densest k-Subgraph related challenges.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
ETH-hardness of Densest-k-Subgraph with Perfect Completeness Aviad Rubinstein (UC Berkeley) Mark Braverman, Young Kun Ko, and Omri Weinstein
A confession this talk isn t really about low-polynomial time rest of workshop this talk ?2 vs ?3 ??(1) vs ?log(?) SETH: SAT requires 2?(1 ?(1) ETH: SAT requires 2 (?) Reduction size: 2?/3 Reduction size: 2 ? (and this isn t really Grandma)
Densest k-Subgraph with perfect completeness
k-CLIQUE (NP-hard [Karp72]) G |S|=k does G contain a k-clique?
relax k? |S| k |S| < k/n1- G vs G NP-hard [FGLSS96 Zuckerman07]
relax clique? den(S)=1 |S|=k G den(S)<1- vs |S|=k G Quasi-poly algorithms [FS97, Barman15]
relax both? den(S) = 1 |S| k G |S| < k/n /loglogn den(S) < 1- vs G Our main result: ETH-hard
0<s(n)<c(n)1 related works on sparse vs very sparse den(S) c(n) den(S)<s(n) vs G G [Feige02, AAMMW11] random k-CNF [BCVGZ12] SDP relaxations [RS10] Unique Games with expansion
Recent applications of B-day Rep Quasi-poly time hardness for [AIM14]: AM with k provers ( something quantum ) Dense CSP s Free games [BKW15]: -best -Nash [BPR16]: -Nash [R15] / [BCKS]: Signaling [this talk]: Densest k-Subgraph [ you! ]: ???
Recent applications of B-day Rep Quasi-poly time hardness for [AIM14]: AM with k provers ( something quantum ) Dense CSP s Free games [BKW15]: -best -Nash [BPR16]: -Nash [R15] / [BCKS]: Signaling [this talk]: Densest k-Subgraph [ you! ]: graph isomorphism??
Recent applications of B-day Rep Quasi-poly time hardness for [AIM14]: AM with k provers ( something quantum ) Dense CSP s Free games [BKW15]: -best -Nash [BPR16]: -Nash [R15] / [BCKS]: Signaling Tight by [FS97], [LMM03], [Barman15], [MM15], [CCDEHT15], etc. [this talk]: Densest k-Subgraph
Reduction in 1 slide variables xi constraints
Analysis (soundness) in 1 slide Birthday Paradox: every pair (u,v) should test a constraint If every assignment to 2CSP violates ?-fraction of the constrains, the corresponding k-subgraph should be missing (?)-fraction of edges. QED? what about k-subgraphs that don t correspond to any assignment?
Not so simple Typically birthday repetition is easy Queries to Alice and Bob are independent. More subtle for Densest k-Subgraph Very simple problem hard to enforce structure we only know that the subgraph is large + dense like proving a parallel repetition theorem, when Alice and Bob choose which queries to answer If it were easy, we would get hardness for den(S)=1 vs den(S)=
So what can we do? Typically birthday repetition is easy Queries to Alice and Bob are independent. More subtle for Densest k-Subgraph Very simple problem hard to enforce structure we only know that the subgraph is large + dense like proving a parallel repetition theorem, when Alice and Bob choose which queries to answer If it were easy, we would get hardness for den(S)=1 vs den(S)=
Analysis in 1 slide: counting entropy |S|=k G choice of variables choice of assignments many CSP violations! many consistency violations! low density, QED!
Open problems Warmup : same result for Densest k-Bi-Subgraph Den(S)=1 vs den(S)= Stronger (NP?) hardness for sparse vs very sparse Fixed parameter (k) tractability?
