Insights on Computational Complexity Threshold Results
Exploring the challenges in proving major lower bounds for computational complexity, focusing on the Hardness Magnification and Minimum Circuit Size Problem (MCSP). Discusses the difficulties in proving weak and strong LBs, highlighting recent theorems and barriers that impact progress in the field.
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
Sharp Threshold Results for Computational Complexity Ryan Williams MIT Lijie Chen MIT Ce Jin Tsinghua U.
How far are we from proving major lower bounds? We can prove weak LBs (e.g. against De Morgan formulas of size ?3). We don t know how to prove strong LBs (such as ?? ???). Can we quantify how far we are from various open lower bounds? Heuristically, we are closer to an ?3.01 formula LB than ?? ??? This intuition can be wrong! Hardness Magnification [OS 18, OPS 19, MMW 19, CJW 19, ] shows that: Some weak LBs are as hard to prove as strong LBs! In this paper, we show more extreme magnification theorems, which we call sharpthresholds for complexity .
Hardness Magnification and Minimum Circuit Size Problem (MCSP) Problem: MCSP[? ? ] Given: ?:{0,1}? {0,1} as a truth table of length ? = 2? Decide: Does ? have a circuit of size at most ?(?)? (Other Hardness Magnification Results) ?1 ?-approximate Clique [Sri 03] Average-case MCSP [OS 18] ?-Vertex-Cover [OS 18] low-depth circuit LBs for ???[AK 10,CT 19] sublinear-depth circuit LBs for ?[LW 13] ??; solvable in ? 2 ? ? ? MCSP ? ? time. We believe MCSP[?10] ?/????! (otherwise, no strong PRGs exist [Razborov-Rudich]) A Hardness Magnification Theorem:If MCSP[?10] doesn t have circuits of ? ??????? ?size and polylog ? depth, then ?? ?/????! [McKay-Murray-Williams 19]
How to view Hardness Magnification? Weak LB Indicates proving weak lower bounds is even harder than previously thought? Suggests new approaches to proving strong lower bounds? Magnification Strong LB It is argued that Hardness Magnification can bypass the Natural Proof Barrier by Razborov-Rudich. [AK 10, OS 18, CHOPRS 20] But [CHOPRS, ITCS 20] recently formulated a new Locality Barrier of Hardness Magnification
Examples of Hardness Magnification theorems If MCSP[?10] (with input length ? = 2?) doesn t have circuits of ? ??????? ?size and polylog ? depth, then ?? ?/????. [McKay-Murray-Williams 19] Compare: A trivial circuit lower bound: ? 1 Best known circuit lower bound for an explicit function: ??(De Morgan circuits) [LR 01, IM 02] (? + ?/??)?(?2-circuits) [FGHK 16] We are relatively far away from proving ? polylog ?circuit lower bounds
Examples of Hardness Magnification theorems If MCSP[?10] (input length ? = 2?) doesn t have ?? ??????? ?-size (De Morgan) formulas, then ?????? ???. [Chen-J-Williams 19] We can prove: MCSP[?10] doesn t have ??.??-size (De Morgan) formulas. [Hirahara-Santhanam 17, Oliveira-Pich-Santhanam 19] Compare: There is an ??+?gap
Our new results Hardness Magnification theorems with sharpthresholds! We can prove a lower bound of ??(much better than the trivial ? 1 lower bound) for ?. An ??+? lower bound for ?, for any? > 0, would imply a breakthrough lower bound! Magnification results for other tasks(also withsharp thresholds) Quantified Derandomization Explicit Obstructions Unlike HM, they are not ruled out by the recent Locality Barrier [CHOPRS 20]. We will mainly work with (De Morgan) Formulas
Hardness Magnification with Sharp Thresholds A probabilistic formula is a distribution over De Morgan formulas. We say computes a function ?, if for all ?, Pr ? [?(?) = ?(?)] 2/3. Theorem: If MCSP[?10] (with input length ? = 2?) doesn t have ?? ??????? ?-size probabilisticformulas, then ?????? ???. Theorem: MCSP[?10] doesn t have ?? ?(?/??? ??? ?)-size probabilistic formulas. Remark: There are cubic size LBs against probabilistic formulas for the dense MCSP ( MCSP[2?/(100?)] )! [Adapting CKLM 19]
Quantified Derandomization The Quantified Derandomization problem [Goldreich-Wigderson 14]: Given an ?-input circuit ? ? that rejects at most ?(?) inputs, deterministically output an ?-bit string that is accepted by ?. Full Derandomization: ? ? = 2?/3. Quantified Derandomization: ? ? = 2?? for ? < 1. Studied by [GW 14, Tell 18, Tell 19, Chen-Tell 19] for ? = AC0,TC0,AC02 , We consider ? = probabilistic formulas
Quantified Derandomization with Sharp Thresholds Theorem: There is a poly(?)-time (black-box) QD algorithm for probabilistic formulas of size ?? ? ?with ? ? = 2??falsifying inputs. (We can achieve ?? ?? ? for generalized* probabilistic formulas.) Theorem: A poly(?)-time QD algorithm for generalized* probabilistic formulas of size ?? ?+?with ? ? = 2??falsifying inputs would imply full derandomization of poly(?)-size formulas in poly(?) time. *may not have bounded probability gap. See paper for precise definition.
Explicit proofs of formula lower bounds An explicit obstruction against ?(?)-size formulas is an algorithm that in deterministic poly(?)-time prints a poly(?)-size list ??,? ?? such that every ?(?)-size formula is inconsistent with the (partially defined) function ?. 0,1? {0,1}, Equivalent to a poly(?)-time printable anti-checker for f [Lipton-Young 94, OPS 19] This is an explicit proof that some poly(?)-time function (extended from ?) does not have ?(?)-size formulas. Inspired by Mulmuley s notion of explicit obstructions (for arithmetic circuits) from his GCT program.
Explicit proofs of formula lower bounds The PARITY function requires formulas of size (??). [Krapchenko 71] Theorem: There is an explicit proof that PARITY requires formulas of size ?? ?(?/??? ??? ?). Best known formula lower bound: nearly cubic[H stad 98, Tal 17]. Can we make the proof explicit? Theorem: An explicit obstruction against ??+?-size formulas would imply: ? = TIME[2? ?] has no 2? ?-size formulas. Explicit obstructions against ??-size formulas, for all ?. In fact, they are equivalent!
Our Techniques Sparse MCSP, MKtP Lower Bounds against prob. formulas Quantified Derandomization of (generalized) prob. formulas Explicit Obstructions against formulas Sharp Adapting Chen-J-Williams FOCS 19 Adapting Efficient linear hashing Magnification theorems Goldreich-Wigderson STOC 14 Slightly sub-quadratic results
Better Explicit Obstructions Imply Breakthrough Lower Bounds: Proof Sketch Let ??,? ?? be an explicit obstruction against ?2+?-size formulas. Assume for contradiction that ? = TIME[2? ?] has 2? ? -size formulas. Deterministically pick a linear hash function (with ?(log?) seed) mapping {??} into distinct?(log?)-bit hash values Output: ? ?? By assumption, ? has ?? 1-size formulas! poly(n)-time algo ? This is an ?2+? 1-size formula which agrees with the obstruction. Input: ?? ?(?2)-size formulas computing PARITY A contradiction! ??
Our Techniques Sparse MCSP, MKtP Lower Bounds against prob. formulas Quantified Derandomization of (generalized) prob. formulas Explicit Obstructions against formulas Sharp Adapting Chen-J-Williams FOCS 19 Adapting Efficient linear hashing Magnification theorems Goldreich-Wigderson STOC 14 Slightly sub-quadratic results Derandomized H stad s Shrinkage Theorem
Restrictions A restriction is a function ?:[?] {0,1, }. Given a function ?: 0,1? {0,1}, define ? ?as the restricted function after fixing the non-star coordinates. Formulas shrink under restrictions: OR ?(? ?) = ? ?(?) = ? Restriction ? ?3 ? ? = ?,? ? = ? ? = AND AND ?3 ?1 ?1 ?2 ? ? = minimum formula size of ?
Shrinkage of Formulas Definition: For 0 < ? < 1, a truly random ?-regular restriction? ?: , w.p. ? 0, w.p. 1 ? /2 1, w.p. 1 ? /2 Shrinkage theorem [H stad 98, Tal 14]: For all functions ?, ?(?) = (independently for all ? [?]) requires ? random bits to sample from ? ? ?2? ? + 1 ?? ?? ? ? That is, a truly random ?-regular restriction shrinks formulas by an ?(?2) factor in expectation. We present a derandomized version of the shrinkage theorem!
Derandomized Shrinkage Lemma We construct a family ?? of pseudorandom restrictions ?: ? 0,1, samplable using ? ???? random bits in poly(?) time, such that (Shrinkage) For all functions ?, ?2? ? + 1 ??(1/ log log ?) ?? ??? ? ? ( Close to ?-regular) ??? ??[ ? 1 ??/2] > 2/3. Optimal?(log?) seed length. Improves the ? log2?seed length by OPS 19. Proof technique: More refined iterated pseudorandom restrictions [IMZ 12,HS 17,OPS 19]
Sparse MCSP, MKtP Lower Bounds Poly-time Quantified Derandomization ?(??? ?)-seed Pseudorandom Restrictions Explicit Obstructions
Explicit proofs from pseudorandom restrictions Goal: an explicit proof that PARITY requires formulas of size ?? ?(?/??? ??? ?) Apply our restriction generator with ? ??/?. ?(log?) seed ????(?)many possible restrictions ?. For each ? that has a star, add two input-output pairs into our list: ? = 1 0 For any formula ? of size ?? ?/ ??? ??? ?, there exists a ? such that: ?(? ?) = 0 (by shrinkage property) ? 1 1 (by close-to-?-regular ) ( ,1) 1 0 0 0 0 ( ,0) 1 1 0 0 0 ?, PARITY(?) So ? should output the same value on these strings. But their parities are different ? is wrong on one of them
Open Problems Can we construct an explicit obstruction against ?2.01-size formulas? Are there any formal barriers? Does our log-seed pseudorandom restriction generator have other applications? Thank you!
