Lower Bounds on Sampling Good Codes in Bounded-Depth Circuits

Slide Note

Bounded-depth circuits are proven unable to sample or approximate good codes effectively. This work delves into lower bounds, showcasing that bounded families of circuits face limitations in computing specific functions or sampling distributions. The example of Parity in AC0 circuits illustrates these constraints. Further exploration includes challenges in sampling lower bounds for AC0, revealing the inability to sample certain explicit distributions. The main result emphasizes that AC0 circuits struggle to sample codes effectively in the context of good codes. Applications to data structure lower bounds and pseudorandomness are discussed.

nysh_101 Follow

Uploaded on Sep 24, 2024 | 0 Views

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

Bounded depth circuits cannot sample good codes Shachar Lovett (IAS) Joint with Emanuele Viola (Northeastern)

Lower bounds Classic lower bounds: functions Bounded families of circuits cannot compute (or approximate) some explicit function This work: distributions Bounded families of circuits cannot sample (or approximate) some explicit distribution

Example: Parity AC0circuits cannot approximate parity [ ,H stad 87] But AC0circuits can sample (x, parity(x)): , , ) ( ( n y y f y + = , , , ) y y y y y + + 1 1 1 2 1 1 1 n n n In fact, AC0circuits can (approximately) sample any symmetric function [Viola 10]

Sampling lower bounds for AC0 [Viola 10]: challenge - explicit distribution that cannot be sampled (or approximated) by AC0 This work: uniform distribution over a code Applications to data structure lower bounds and pseudorandomness n [Viola 11]: (x,b(x)) for a Boolean :{0,1 } {0 1} , b

Talk overview Describe result Applications Proof

Computational model: AC0 Constant depth circuits with AND,OR,NOT gates Multiple outputs: maps m bits into n bits Polynomial size (can handle sub-exponential size) y1 yn AND AND OR AND AND x1x2 xm

Codes (n,k,d) code: Subset Size Minimal distance: {0,1}n | 2k = C C | C : ( , ) x y dist x y d = A code is good if (our results extend also to ) , ( ) n k d kd n Good codes exist

Main result: AC0 cannot sample codes {0,1}n Good code C m n AC0 circuit : {0,1 } {0,1} f Theorem: the uniform distribution over and the output distribution of f have statistical distance C 1 n (1)

Application 1: data structures (n,k,d) good code Consider a data structure for messages which allows encoding in AC0 C Claim: data structure has redundancy log(n) (i.e. use at least bits) Proof: encode a uniform string + (log ) k n Previous results : bounded query model (i.e. NC0) [G l-Miltersen 07]

Application 2: Nisan PRG against AC0 Nisan (1991) gave the first PRG against AC0 To fool AC0 circuits of depth d, a na ve implementation requires AC0 circuits of depth d+1 Is this necessary? Maybe the pseudorandom distribution can be otherwise sampled k-wise independence, which also fools AC0, can be sampled by small depth 2 circuits This work: depth d is necessary for Nisan s PRG (at least for some setting of the underlying designs)

Main result: AC0 cannot sample codes {0,1}n Good code C m n AC0 circuit : {0,1 } {0,1} f Theorem: the uniform distribution over and the output distribution of f have statistical distance C 1 n (1)

Core idea: noise sensitivity AC0 circuits are noise insensitive: flipping few input bits hardly changes output Codes are sensitive: Distinct codewords have large distance Easily shows that AC0 cannot compute codes; sampling lower bound requires some more work

AC0 noise (in)sensitivity : m Boolean AC0 circuit: Coupled inputs: {0,1 {0,1 : } {0,1} dist x x = f m , ' x x } ( , ' ) 1 Noise (in)sensitivity [LMN 93,Boppana 97]: Pr[ ( ) ( )] f x f x 1 m (1) (log )O m m n : {0,1 n m } {0,1} Multi-output functions: [ dist f x E f ( ( ), ( ))] f x

Warm-up: AC0 cannot compute codes C (n,k,d) code Encoding map Assume f can be computed by AC0 circuits k n : {0,1 } {0,1} f dist x x = k , ' x x {0,1 } : ( , ' ) 1 Coupled inputs: 0 [ ( ( ), ( ))] ( ( ), ( ')) dist f x / ( AC sensitivity) distinct codewords) ( dist f x f x f n k E x d Contradiction whenever kd n

AC0 cannot (exactly) sample codes C (n,k,d) code uniform over Assume f can be computed by AC0 circuits m n : {0,1 } {0,1} f = C 100 ( think ) m n dist x x = m , ' x x {0,1 } : ( , ' ) 1 Coupled inputs: 0 [ ( ( ), ( ))] ( ( ), ( ')) f x / ( AC sensitivity) dist f x f x f x n m E ??? dist d Can f be local: f(x)=f(x ) w.h.p ?

Local maps: isoperimetric inequality uniform over (n,k,d) code {0,1 : } {0,1} f m n C f induces a partition of {0,1}m with 2k equal parts: 1( ) { {0,1} : ( ) f c x = = C m }, f x c c Coupled input (x,x ): edge in hypercube {0,1}m Edge-isoperimetric inequality [Harper 64, Hart 76]: Each part cannot contain too many edges x So, with good probability: (hence ) ( ( ), ( ')) dist f x ( ) ( ) f x d f f x

Local maps: isoperimetric inequality m n uniform over (n,k,d) code Edge-isoperimetric inequality: Subset of {0,1}m of size 2m-k has : {0,1 } {0,1} f C m k )2m k ( edges 1 2 k m | | = = 1 Pr[ ( ) f x ( )] f x ( , ') x ( ) c 1 x f m m C c kd m E [ ( ( ), ( ))] dist f x f x

Putting it all together uniform over (n,k,d) code {0,1 : } {0,1} f m n C n m AC0 sensitivity: [ ( ( ), ( ))] dist f x f x E kd m Isoperimetric inequality: E [ ( ( ), ( ))] dist f x f x Contradiction when kd n

AC0 cannot (approximately) sample codes The previous argument actually shows that the statistical distance between: The uniform distribution over a code The uniform distribution of AC0 circuit is at least (1) 1 To get statistical distance , use less coupled inputs (i.e. more noise)

Summary AC0 circuits cannot sample uniform codeword Statistical distance 1 n (1) 1 2 ( ) n Conjecture: statistical distance Applications: Lower bounds for data structures for codes Limitations of Nisan PRG