Transcript Many random walks are faster than one

A new characterization of
ACC0 and probabilistic CC0
Kristoffer Arnsfelt
Hansen
Aarhus University
Denmark
Michal Koucký
Institute of Mathematics
Czech Republic
Bounded depth Boolean circuits





x1
x3
x4
x7
Constant depth, polynomial size circuits
MOD-q (x1, x2, …, xn ) = 0
iff
 i >0 xi  0 mod q
MAJ (x1, x2, …, xn ) = 0
iff
 i >0 xi > n/2
2
Bounded depth Boolean circuits
AC0: unbounded fan-in AND, OR and unary NOT gates.
ACC0: unbounded fan-in AND, OR, MOD-q and unary NOT.
CC0: unbounded fan-in MOD-q gates.
TC0: unbounded fan-in MAJ and unary NOT gates.
NC1: fan-in two AND, OR and unary NOT gates, O(log)-depth.
Constant depth, polynomial size circuits
MOD-q (x1, x2, …, xn ) = 0
iff
 i >0 xi  0 mod q
MAJ (x1, x2, …, xn ) = 0
iff
 i >0 xi > n/2
3
Known relationships



AC0  ACC0  TC0  NC1
CC0  AC0
but
CC0  ACC0
Open questions: NP  CC0 ?
CC0  ACC0 ?

Conjecture (Barrington-Straubing-Thérien):
AND  CC0
4
Our results
Thm: ACC0  rand-CC0.
Thm: ACC0  AND  OR  CC0.
Thm: ACC0 = rand-ACC0 = rand-CC0 = rand( log n )-CC0.
Thm: ACC0 corresponds to planar bounded-with
nondeterministic branching programs of polynomial size.
5
AND vs CC0
Fact:
1) For prime p, CC0[ p ] cannot compute AND.
2) For prime power q, CC0[ q ] cannot compute AND.
Thm (BST): MOD-p  MOD-q circuits require exponential size to
compute AND.
Thm (Thérien): CC0 circuits for AND require Ω( n ) gates in their
first layer.
p,q co-prime integers
6
AND vs CC0
Thm (BST): CC0[ pq ] circuits of exponential size can compute any
Boolean function, in particular AND.

Cor: CC0[ pq ] circuits of size 2n and depth O(1/) can compute
AND.
CC0[
n 1/r
Thm(BBR):
q ] circuits of size 2
and depth 4 can compute
AND if q has r distinct prime factors.
p,q co-prime integers
7
Thm: AND is computable by rand-CC0[ pq ] circuits with error
<1/n log n if p and q are co-prime integers.
Pf: Razborov-Smolensky method
Fixed input x1, x2, …, xn
Take a random set S  {1, …, n }
 with probability at least 1/2 over random choice of S
OR(x1, x2, …, xn ) = MOD-q { xi , i  S }
 take k=log2 n independent random sets S1, S2, …, Sk
 with probability at least 1/n log n over random choices of S’s
OR(x1, x2, …, xn ) = ORj  MOD-q { xi , i  Sj }

Cor: ACC0  rand-CC0.
8
Previous construction requires n log2 n random bits.

One can reduce the number of random bits to O(log n) while
keeping the error below 1/n k by use of:
1.
2.
Valiant-Vazirani isolation technique, and
Randomness efficient sampling using random walks on
expanders.
Similar to [AJMV]
 logspace uniformity
Cor: ACC0  rand(log n)-CC0.
9
Derandomization
Thm (Ajtai, Ben-Or):
1) rand-AC0  AC0.
2) rand-ACC0  ACC0.
Open: rand-CC0  CC0 ?
Claim: rand-CC0 = CC0
iff
AND  CC0.
Thm: ACC0  AND  OR  CC0.
10
Thm: ACC0  AND  OR  CC0.
(non-uniformly)
Pf: Technique of Ajtai and Ben-Or
Cn a rand-CC0 circuit computing fn with error <1/3n.
Take OR of n independent copies of Cn
 if fn ( x ) = 1 then OR  Cn( x ) = 0 with probability < ( 1/3n )n
if fn ( x ) = 0 then OR  Cn( x ) = 1 with probability < 1/3
11
Cn a rand-CC0 circuit computing fn with error <1/3n.
Take OR of n independent copies of Cn
 if fn ( x ) = 1 then OR  Cn( x ) = 0 with probability < ( 1/3n )n
if fn ( x ) = 0 then OR  Cn( x ) = 1 with probability < 1/3
Take AND of n independent copies of OR  Cn
 if fn ( x ) = 1 then AND  OR  Cn( x ) = 0 with p. < n ( 1/3n )n
if fn ( x ) = 0 then AND  OR  Cn( x ) = 1 with p. < ( 1/3 )n
In both cases the probability of error is less than 2n so we can fix a
particular random bits that will give the correct answer for all x.

12
Previous construction requires to fix >n2 random bits so it is nonuniform.

One can get uniform construction using:
1.
Lautemann’s technique, and
2.
Randomness efficient sampling using random walks on
expanders.
Similar to [AH, V]
Thm: ACC0  AND  OR  CC0.
(uniformly)
13
Geometric restrictions of circuits and branching
programs
14
Geometric restrictions of circuits and branching
programs
15
Constant width circuits
Thm (Barrington): NC1 corresponds to constant width circuits.
Thm (Hansen’06): ACC0 corresponds to constant width planar
circuits.
Thm (BLMS’99): AC0 corresponds to constant width upward planar
circuits.
16
Constant width nondeterministic branching programs
Thm (Barrington): NC1 corresponds to constant width
nondeterministic branching programs.
Thm: ACC0 corresponds to constant width planar
nondeterministic branching programs.
Thm (BLMS’98): AC0 corresponds to constant width upward planar
nondeterministic branching programs.
17
Constant width nondeterministic branching programs
Thm (Hansen’08): Quasi-polynomial size ACC0 corresponds to
quasi-polynomial size constant width planar nondeterministic
branching programs.
Thm (HMV): Functions computable by constant width planar
nondeterministic branching programs are in ACC0.
Thm (Hansen’08): Functions from AND  OR  CC0 are
computable by constant width planar nondeterministic
branching programs.
 Thm: ACC0 corresponds to constant width planar
nondeterministic branching programs.
18