Technique for Hardness Amplification Against AC0 Circuits
Explore the study on hardness amplification against AC0 circuits, analyzing depth hierarchies, average-case complexity, and correlation bounds in parallel computation models. Discover insights from Sipser, Yao, and Håstad, as well as the correlation bound for depth reduction proposed in William M. Hoza's work.
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
A Technique for Hardness Amplification Against AC0 @ CCC July 23, 2024 William M. Hoza1 The University of Chicago 1Part of this work was done while the author was visiting the Simons Institute for the Theory of Computing.
AC0 circuits AC0 circuit: Literals (variables and their negations) ?1 ?3 ?2 ?1 ?4 feeding into a network of AND and OR gates Fan-in is unbounded
AC0 circuits Size = number of AND/OR gates ?1 ?3 ?2 ?1 ?4 Depth = length of longest path from input to output 0circuit means an AC0 circuit of depth ? AC? We are especially interested in the case ? = ? 1 A model of constant-time parallel computation
Depth hierarchies To what extent are deeper circuits more powerful than shallower circuits? What is the marginal utility of time for parallel computation? Theorem[Sipser 1983] [Yao 1985] [H stad 1989]: Sip: 0,1? 0,1 such that 0 Sip can be computed by an AC?+1 circuit of size ? ? 0 circuit computing Sip has size 2? 1/?. Every AC? What about average-case complexity? ?1 ?2 ??
The average-case depth hierarchy theorem log ? log log ? Let ?,? with ? = ? Theorem [H stad, Rossman, Servedio, Tan 2017]: Sip:{0,1}? {0,1} such that 0 Sip can be computed by an AC?+1 circuit of size ? ? 0 circuit ?, either ? has size 2? 1/?, or else we have AC? ? {0,1}?[? ? = Sip ? ] 1 2+ ? 1/? Pr
The correlation bound The HRST correlation bound ? 1/? might be a little disappointing Can we improve it to ? ? 1? 0 No. The discriminator lemma implies that for every AC?+1 circuit of 0 circuit ? of size ?(?) such that size ?(?), there exists an AC? 1 Pr ?? ? = ? 2+ 1/? 0 circuits to AC?+? 0 However, what happens if we compare AC? circuits?
Our correlation bound for depth reduction log ? log log ? Let ?,?,? with ? 3 and ?? = ? Theorem (this work): :{0,1}? {0,1} such that 0 can be computed by an AC?+? circuit of size ? ? 0 circuit ?, either ? has size 2? 1/?, or else we have AC? ? {0,1}?[? ? = ? ] 1 2+ 2 log ?? 1 (1/?) Pr
Our hard function Sip Sip Sip Sip Our hard function is given by = Sip ? where ? log? 2? ? Sip ??1, ,?? Sip ?? ?=1 0 circuit, Sip ? is almost Basic intuition: From the perspective of an AC? like a biased coin XORing independent coin tosses would rapidly shrink the bias
Inspiration: Yaos XOR Lemma Let ? be any circuit class and let :{0,1}? {0,1} be any function Yao s XOR Lemma (informal): If is moderately hard for Maj ? circuits, then ?is very hard for ? circuits Yao s XOR Lemma is not applicable in our setting, because Maj AC0 is much more powerful than AC0
XOR-of-Majority function Maj Maj Maj Maj We also analyze the correlation between Maj ? and AC0 circuits Motivation: We would like to understand AC0 circuits, i.e., AC0 circuits augmented with parity gates
Majority is moderately hard for AC0 0 circuit of size ? ? Let ?:{0,1}? {0,1} be any AC? Theorem [Razborov 1987, Smolensky 1987, ]: 2+? log?? 1 1 ? {0,1}?? ? = Maj?? Pr ? 0 circuits Major open problem: Prove that some NP is very hard for AC? Maj ? is a good candidate hard function
? Our correlation bound for Maj? 0 circuit of size ? Let ?:{0,1}?? {0,1} be any AC? Theorem (this work): ? ? log?? 1 1 ?? ? {0,1}??? ? = Maj? Pr 2+ ? The XOR-of-Majority function is very hard for AC0 circuits
Our technique In summary, we prove new correlation bounds for Sip ? and Maj ? against AC0 circuits The proofs are similar. Let s focus on the case Maj ? Proof Step 1: Re-prove that Maj is moderately hard for AC0 circuits
? ? Maj is moderately hard for AC0 ? ? Maj Maj ? Let ? be an AC0 circuit Let ? be a random balanced restriction Switching lemmas W.h.p., ? ? is a shallow decision tree Meanwhile, Maj ? is simply the majority function on fewer bits Maj is moderately hard for shallow decision trees (w.r.t. suitable input distribution) It follows that Maj is moderately hard for AC0
Analyzing Maj? via random restrictions ? Maj Maj Maj Maj Maj Maj Maj Maj Proof Step 2: Apply an XOR lemma for decision trees This will show that Maj ? is very hard for shallow decision trees and AC0
Druckers XOR lemma for decision trees Let :{0,1}? {0,1} 1 Assume that depth-? decision tree ?, we have Pr ?? ? = ? 2+ ? Lemma [Drucker 2012]: For every constant ? > 0, there exists ? = ?? such that for every depth-? decision tree ?, we have 1 ?? ? = ?? 1 ? ? Pr 2+ ? ?
Stronger XOR lemmas for decision trees? Drucker s XOR lemma is not quite good enough for us We need a correlation bound of ? ?? instead of ? ? 1 ? ? OBSTACLE [Shaltiel 2003]: There are counterexamples! The issue is that even though is hard for depth-? trees, might nevertheless be easy for depth- ? + 1 trees. In this case, a tree of depth ??? can solve ? copies of SOLUTION: Let s strengthen the assumption
Our new XOR lemma for decision trees Let :{0,1}? {0,1} Assume that for every ? and every depth-? decision tree ?, we have ?[? ? = ? ] 1 Pr 2+ ? ? , where ?: 0, 0, is log-concave ?? 2 decision tree ?, we have Lemma (this work): ?,? and depth- 1 ?? ? = ?? 2+ ? ?(?)? Pr
Fair decision trees The proof of our new XOR lemma is based on a concept of a fair decision tree, generalizing a definition in [Shaltiel 2003] Let ?:{0,1}?? {0,1} be a decision tree and let ? ? Definition: We say that ?is ?-fair if for every ?1, ,?? {0,1}??, there exists ?1, ,?? ? such that for every ?, the computation ? ?1, ,?? involves at most ?? queries to ??
XOR lemma for ?-fair decision trees ? Let 1, , ?:{0,1}? {0,1} and let ?1, ,?? ??? = ?=1 Let ?:{0,1}?? {0,1} be a ?-fair decision tree Lemma (this work): ? Corr ,? Corr ?, depth ?? decision trees ?=1 ?1, ,?? ? Proof is a straightforward induction on depth
Proof of our main XOR lemma for decision trees Let ?:{0,1}?? {0,1} be a decision tree of depth ??/2 Let ? = {? ?:?1+ + ?? ?? and each ?? is a multiple of ?/2} ? Then ? is ?-fair, so Corr ?, ? ?1, ,?? ? ?=1 Corr ,depth ?? DTs ? ?1, ,?? ? ?=1 ? ? ?? ? ?? (log-concavity) 2? ? ? ??.
Correlation bound for Sip? HRST s proof that Sip is moderately hard has the same structure as our proof that Maj is moderately hard 1. They design a distribution over random projections ? 0 circuit, then w.h.p., ? ? is a shallow decision tree 2. They show that if ? is an AC? 3. They show that w.h.p., Sip ? is moderately hard for decision trees (w.r.t. suitable input distribution) Hence, our technique of using XOR lemmas for decision trees works here too In fact, a weak XOR lemma for decision trees is sufficient in this case
Open problems Problem: Prove a general XOR Lemma for AC0Circuits 0circuits Problem: Prove tight bounds on the correlation between AC? 0 and AC?+? circuits (Near-tight bounds are known when ? = 1 or ? = 1) Thanks for listening! Questions?
