Lower Bounds on Sampling Good Codes in Bounded-Depth Circuits
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
•
AC
0
circuits cannot approximate
parity
[…,Håstad’87]
•
But AC
0
circuits can sample (x,
parity
(x)):
•
In fact, AC
0
circuits can (approximately) sample
any
symmetric function
[Viola’10]
Sampling lower bounds for AC
0
•
[Viola’10]
: challenge - explicit
distribution
that
cannot be sampled (or approximated) by AC
0
•
This work: uniform distribution over a
code
–
Applications to
data structure lower bounds
and
pseudorandomness
•
[Viola’11]
:
(x,b(x))
for a Boolean
Talk overview
•
Describe result
•
Applications
•
Proof
Computational model: AC
0
•
Constant depth circuits with AND,OR,NOT gates
•
Multiple outputs: maps
m bits
into
n bits
•
Polynomial size (can handle sub-exponential size)
Codes
•
(n,k,d) code:
–
Subset
–
Size
–
Minimal distance:
•
A code is
good
if
(our results extend also to )
•
Good codes exist
Main result: AC
0
cannot sample codes
•
Good code
•
AC
0
circuit
•
Theorem: the
uniform distribution over
and the
output distribution of
f
have
statistical distance
Application 1: data structures
•
(n,k,d) good code
•
Consider a data structure for messages which
allows
encoding in AC
0
•
Claim: data structure has
redundancy log(n)
(i.e. use at least
bits
)
•
Proof: encode a uniform string
•
Previous results : bounded query model (i.e. NC
0
)
[Gál-Miltersen’07]
Application 2: Nisan PRG against AC
0
•
Nisan (1991) gave the first PRG against AC
0
•
To
fool AC
0
circuits of depth d
, a naïve
implementation
requires AC
0
circuits of depth d+1
•
Is this necessary? Maybe the pseudorandom
distribution can be otherwise sampled
–
k-wise independence, which also fools AC
0
, 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: AC
0
cannot sample codes
•
Good code
•
AC
0
circuit
•
Theorem: the
uniform distribution over
and the
output distribution of
f
have
statistical distance
Core idea: noise sensitivity
•
AC
0
circuits are
noise insensitive
:
flipping few input bits hardly changes output
•
Codes are
sensitive
:
Distinct codewords have large distance
•
Easily shows that AC
0
cannot
compute
codes;
sampling
lower bound requires some more work
AC
0
noise (in)sensitivity
•
Boolean AC
0
circuit:
•
Coupled inputs
:
•
Noise (in)sensitivity
[LMN’93,Boppana’97]
:
•
Multi-output functions:
Warm-up: AC
0
cannot compute codes
•
(n,k,d) code
•
Encoding map
•
Assume
f
can be computed by AC
0
circuits
•
Coupled inputs
:
•
Contradiction whenever
AC
0
cannot (exactly) sample codes
•
(n,k,d) code
•
uniform over
•
Assume
f
can be computed by AC
0
circuits
•
Coupled inputs
:
•
Can
f
be
local
: f(x)=f(x’) w.h.p ?
Local maps: isoperimetric inequality
•
uniform over (n,k,d) code
•
f
induces a
partition
of {0,1}m
with
2
k
equal parts
:
•
Coupled input (x,x’):
edge
in hypercube {0,1}m
•
Edge-isoperimetric inequality
[Harper’64, Hart’76]
:
Each part cannot contain too many edges
•
So, with good probability:
(hence )
Local maps: isoperimetric inequality
•
uniform over (n,k,d) code
•
Edge-isoperimetric inequality:
–
Subset of {0,1}m
of
size 2
m-k
has
edges
Putting it all together
•
uniform over (n,k,d) code
•
AC
0
sensitivity:
•
Isoperimetric inequality:
•
Contradiction when
AC
0
cannot (approximately) sample codes
•
The previous argument actually shows that
the statistical distance between:
–
The uniform distribution over a
code
–
The uniform distribution of
AC
0
circuit
is
at least
•
To get
statistical distance
, use less
coupled inputs (i.e. more noise)
Summary
•
AC
0
circuits
cannot sample
uniform codeword
–
Statistical distance
•
Conjecture: statistical distance
•
Applications:
–
Lower bounds for data structures for codes
–
Limitations of Nisan PRG
Open problems
•
Sampling lower bounds – relatively
unexplored area
•
New lower bounds?
•
New applications?
THANK YOU!
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.
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
Open problems Sampling lower bounds relatively unexplored area New lower bounds? New applications? THANK YOU!
