Range Avoidance
Delve into the realm of circuit lower bounds with Range Avoidance Part II. Uncover the complexities of Boolean functions, rigid matrices, and algorithmic methods for attaining stronger lower bounds in circuit theory. Explore intriguing connections between deterministic algorithms, non-trivial circuit classes, and the quest for rigid matrix construction.
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.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
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.
E N D
Presentation Transcript
Range Avoidance Part II: Beyond Circuit Lower Bounds! Hanlin Ren Oxford November 1, 2022 Based on joint works with Yeyuan Chen, Yizhi Huang, Jiatu Li, Rahul Santhanam, and Zhikun Wang. ? 0 / 14
Recap: Range Avoidance Input: a (multi-output) circuit ?: 0,1? 0,1 ( > ?) Output: any string ? Range ? I.e. for every ? 0,1?, ? ? ? A non-output of ?. ? 0,1 Range avoidance captures explicit construction problems (Korten 21) Seek for deterministic algorithms ? ? 0,1? 1 / 14
Example: Rigid Matrices An ? ? matrix is rigid, if we need to change 0.1?2entries to make its rank below 0.1?. Equivalently: it is 0.1?2-far from every matrix of rank 0.1? Most matrices are rigid! Proof: Every non-rigid matrix can be compressed into 0.4?2bits. Can we explicitly find one? Reduction to range avoidance! Let s say rank is over ?2 A non-rigid matrix ?2 bits Decompressor for non-rigid matrices 0.4?2 bits = # of bits is 0.1?2+ 0.1 ? + ? 0.1? < 0.4?2 2 / 14
Example: Circuit Lower Bounds Find a Boolean function ?: 0,1? 0,1 without size- 2?/2circuits? Most Boolean functions require > 2?/2size! Proof: otherwise, compress the truth table in 2?/2poly ? bits Can we explicitly find one? Reduction to range avoidance! A circuit computing ?1 ?2 from [Arora-Barak] Truth table of ? 01100010011 001010 2? bits ?? 2?/2poly ? bits Description of a size-2?/2 circuit ? ??stands for truth table . 3 / 14
Circuit Lower Bounds via Algorithmic Method ????: a frontier circuit class that we don t know how to prove lower bounds otherwise [Williams 11]: ???? ????. Two steps in the proof: CAPP for ???0admits a non-trivial algorithm Such algorithms imply circuit lower bounds! Nontrivial: Running in 2?/?? 1 time The connection between algorithm and lower bounds is very general, applicable to other classes besides ???0 ?-CAPP (Circuit Acceptance Probability Problem): Given a circuit ?, estimate Pr ?? ? = 1 . 4 / 14
Algorithmic Method for Rigid Matrices Since [Williams 11], we prove stronger and stronger lower bounds via the Algorithmic Method . What else could we do? [Alman-Chen 19]: ????construction of rigid matrices! with parameters much better than previously known Idea: treat low-rank matrices as a special circuit class ! Rigid matrices = (average-case) circuit lower bounds against Turns out there are good CAPP algorithms for 5 / 14
A Range Avoidance Interpretation? Rigid Matrices ???? Circuit Lower Bounds Truth table of ? A non-rigid matrix 01100010011 001010 2? bits ?2 bits ?rigidity ?????0 poly ? bits 0.4?2 bits , , Description of an ???0circuit ? The range avoidance problem, for the specific circuit ?????0, has an unconditional ???? algorithm. The range avoidance problem, for the specific circuit ?rigidity, has an unconditional ???? algorithm. (for different parameters) 6 / 14
Is it just circuit lower bounds & rigid matrices, or ? Is there a general Algorithmic Method for range avoidance? What analogue of CAPP algorithms imply ???? algorithms for ?-Avoid? 7 / 14
RSW22: Algorithmic Method for Range Avoidance Non-trivial Hamming Weight Estimation data structures imply ????algorithms for range avoidance Hamming Weight Estimation Preprocessing: Given a circuit ?: 0,1? 0,1 , compute a data structure DS in ??? Query: Given ? 0,1?, estimate the Hamming weight of ? ? in deterministic /log? 1 time, with oracle access to DS output ? input Remark: CAPP = Hamming Weight Est. for ?? (the truth table generator)! See you tomorrow at my FOCS talk This result generalises Williams s Algorithmic Method! 8 / 14
Ongoing Work: Range Avoidance from Satisfying-Pairs Hamming Weight Est is hard and RSW didn t have good unconditional results, but Non-trivial algorithms for Satisfying-Pairs imply ????algorithms for range avoidance Satisfying-Pairs ?1 ?2 ?3 ?4 Input: ? circuits ?1,?2, ,??: 0,1? 0,1 and ? inputs ?1,?2, ,?? 0,1? Estimate: the number of ?,? such that ???? = 1. 1 0 1 0 ?1 0 0 1 0 ?2 Nontrivial: Running in ??/log? 1?? time 1 1 1 0 ?3 Remark: CAPP = Satisfying-Pairs for 1 circuit and 2? inputs! 1 1 0 0 ?4 9 / 14
The Landscape of ????? (w.r.t. ???? reductions) ?????-complete Inside ???? ???? 20.01?-Hard ??????? 20.01?-Hard ????2?? 1 -Hard Optimal linear codes ???0-Avoid (quasipoly stretch) ??1-Avoid (? + 1 stretch) ???? 2?/3? -Hard Ramsey Graphs (Razborov-)Rigid matrices (Valiant-)Rigid matrices ??0-Avoid (?2 stretch) ??0-Avoid (? + 1 stretch) Avoid easy hard 10 / 14
Invitation ????-explicit constructions are interesting! We don t know Whether Avoid ????is one of the most notorious open problem in complexity theory! it s equivalent to circuit lower bounds for ??? Many explicit construction problems are widely open, even for ????- explicitness! We will know! This talk: the Algorithmic Method as a tool for ????-explicit constructions! and this is not the only technique to use the ?? oracle! E.g., Korten s paper contains different and clever usage of the ?? oracle 11 / 14
Open Problem 1: Ramsey Graphs An ?-vertex graph is Ramsey if it contains neither cliques nor independent sets of size 10log?. Compression of non-Ramsey graphs: ? (a subset of size 10log?) ? (whether ? is clique or IS) Other edges Bit complexity = 10log2? + 1 + ? 2 2 A non-Ramsey graph bits Decompressor for non-Ramsey graphs 10log bits ?,?,other edges WARNING: the stretch is small! A test ground for small-stretch avoidance? 10 log ? ? 2 20log? < 12 / 14
Open Problem 2: ???-Avoid 0-Avoid with ? = ?1.01stretch is in ???? Conjecture: ??3 output input It suffices to solve the problem in deterministic ??/log? 1?? time: Each edge contains exactly 7 vertices Input: a 7-uniform hypergraph consisting of ? vertices, ? = ?1.01 hyperedges; and ? = ?100 cuts Output: The number of ?,? such that the ?-th cut goes through the ?-th hyperedge The cut goes through the blue and orange edges, but not the green and purple ones. 13 / 14
The Landscape of ????? (w.r.t. ???? reductions) ?????-complete Inside ???? with your cool ideas and ?? oracle ???? 20.01?-Hard ??????? 20.01?-Hard ????2?? 1 -Hard Optimal linear codes ???0-Avoid (quasipoly stretch) ??1-Avoid (? + 1 stretch) ???? 2?/3? -Hard Ramsey Graphs (Razborov-)Rigid matrices (Valiant-)Rigid matrices ??0-Avoid (?2 stretch) ??0-Avoid (? + 1 stretch) Avoid easy hard Thank you! Questions are welcome! 14 / 14
