Technique for Hardness Amplification Against AC0 Circuits
Explore the concept of hardness amplification in the realm of theoretical computer science, focusing on converting hard functions to even harder ones. Topics cover Yao's XOR Lemma, quantifying hardness, reasons for amplifying hardness, and limitations of Yao's Lemma against AC0 circuits. Learn about AC0 circuits, their characteristics, and challenges in amplifying hardness against them.
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 @UChicago CS Theory Lunch January 31, 2024 William M. Hoza1 1Part of this work was done while the author was visiting the Simons Institute for the Theory of Computing.
Hardness amplification: Hardness amplification: The art of converting hard functions into harder functions
Example: Yao s XOR Lemma Let :{0,1}? {0,1} be a function ? Define ?:{0,1}?? {0,1} by ??1, ,?? ?? = ?=1 Let ? be any circuit class Yao s XOR Lemma (informal): If is moderately hard for MAJ ? circuits, then ?is very hard for ? circuits
How we are quantifying hardness An average-case lower bound, aka a correlation bound, is a theorem 1 of the form For every ? ?, we have Pr ?? ? = ? 2+ ?. (The input ? is sampled uniformly at random from {0,1}?) If ? = ? 1, we could say that is moderately hard for ? If ? = ? ? 1, we could say that is very hard for ?
Why amplify hardness? Maybe you think of a hardness result as bad news If a problem is very hard, maybe you think of this as very bad news Why would we try to manufacture such a situation? One possible answer: Sometimes, we wish to exploit hardness! Pseudorandom generators Cryptography Reductions
AC0 circuits AC0 circuit: Literals (variables and their negations) feeding into a network of AND and OR gates ?1 ?3 ?2 ?1 ?4 Unbounded fan-in, unbounded fan-out Depth = length of longest path from input to output 0circuit means an AC0 circuit of depth ? AC? Size = number of AND/OR gates
Yaos XOR Lemma doesnt work against AC0 Suppose we prove that is moderately hard for AC0 circuits Can we amplify its hardness? Yao s XOR Lemma (informal): If is moderately hard for MAJ ? circuits, then ?is very hard for ? circuits Issue: MAJ AC0 circuits are much more powerful than AC0 circuits! Lemma is not applicable if we merely know that is hard for AC0 circuits
Does XORing amplify hardness against AC0? Question (informal): If is moderately hard for AC0circuits, does it follow that ? is very hard for AC0 circuits? Yao s XOR Lemma does not resolve this question More generally, black-box hardness amplification schemes cannot resolve this question, because such schemes require MAJ gates [Viola 2006] [Gutfreund, Rothblum 2008] [Shaltiel, Viola 2010] [Grinberg, Shaltiel, Viola 2018] [Shaltiel 2023]
Our contributions We introduce a technique for amplifying hardness against AC0 We are not able to prove a general XOR lemma for AC0 circuits Instead, we use our technique to amplify two specific (and important) moderate hardness results Result 1: Amplifying the average-case depth hierarchy Result 2: Amplifying the hardness of the majority function
The average-case depth hierarchy theorem To what extent are deeper circuits more powerful than shallower circuits? What is the marginal utility of time for parallel computation?
The average-case depth hierarchy theorem log ? log log ? Let ?,? with ? = ? 0 Theorem [H stad, Rossman, Servedio, Tan 2017]: There exists an AC?+1 0 circuit ?, circuit :{0,1}? {0,1} of size ? ? such that for every AC? either ? has size 2? 1/?, or else the following correlation bound holds: ? {0,1}?[? ? = ? ] 1 2+ ? 1/? Pr 0 circuits is moderately hard for AC?
Stronger correlation bounds: Obstacles Can we strengthen the correlation bound to ? ? 1? OBSTACLE 1: The [HRST 2017] hard function is monotone By the KKL theorem, for every monotone :{0,1}? {0,1}, there exists a trivial function ? (a variable or a constant) such that 1 Pr ?? ? = ? 2+ ? 1/? SOLUTION: Let s use a different, non-monotone hard function
Stronger correlation bounds: Obstacles Can we strengthen the correlation bound to ? ? 1? 0 OBSTACLE 2: By the discriminator lemma, for every AC?+1 circuit 0 circuit ? such that of size ? (monotone or not), there exists an AC? 1 Pr ?? ? = ? 2+ 1/? SOLUTION: Let s allow to have depth slightly larger than ? + 1
Our correlation bound for depth reduction log ? log log ? Let ?,?,? with ? 3 and ?? = ? 0 circuit :{0,1}? {0,1} of Theorem (this work): There exists an AC?+? 0 circuit ?, either ? has size 2? 1/?, or size ? ? such that for every AC? else the following correlation bound holds: ? {0,1}?[? ? = ? ] 1 2+ 2 log ?? 1 (1/?) Pr ? where ? log? 2? Our hard function: = HRST
Majority is moderately hard for AC0 circuits 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 ? The majority function is moderately hard for AC0 circuits
? Our correlation bound for MAJ? 0 circuit of size ? Let ?:{0,1}?? {0,1} be any AC? Theorem (this work): ? ? log?? 1 log? 1 ?? ? {0,1}??? ? = MAJ? Pr 2+ ? The XOR-of-majority function is very hard for AC0 circuits
XOR lemmas for decision trees Our technique is based on XOR lemmas for decision trees Let :{0,1}? {0,1}, and assume that for every depth-? decision 1 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+ ? ?
XOR lemmas for decision trees We would like to have ? ?? instead of ? ? 1 ? ? OBSTACLE [Shaltiel 2003]: There are counterexamples Key idea behind the counterexamples: 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 ?: Lemma (this work): For every ?,? and every 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 DT 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 ??
Correlation For convenience, let s switch to { 1} instead of {0,1} Definition: If ?, :{ 1}? { 1}, then Corr ?,? = ??? ? ? =1 2+1 Note: Pr ?? ? = ? 2 Corr ?,? Corr ?,?is like ? from before
XOR lemma for ?-fair decision trees ? Let 1, , ?:{ 1}? { 1} and let ?1, ,?? ??? = ?=1 Let ?:{ 1}?? { 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 DTs Let ?:{ 1}?? { 1} be a DT 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? ? ? ??.
Open problems Problem: Prove that XORing always amplifies hardness against AC0 0circuits Problem: Prove tight bounds on the correlation between AC? 0 and AC?+? circuits (We have near-tight bounds when ? = 1 or ? = 1) Thanks for listening! Questions?
