Depth-Three Boolean Circuits and Arithmetic Circuits: A Study on Circuit Complexity

Slide Note

Explore the intricacies of depth-three Boolean circuits and arithmetic circuits with general gates, focusing on the size, structure, and complexity measures. The research delves into the relationship between circuit depth, gate types, and multi-linear functions, offering insights into circuit models, lower bounds, and explicit function constructions to showcase the theoretical foundations of computational complexity theory.

ntron Follow

Uploaded on Oct 09, 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

Boolean Circuits of Depth-Three and Arithmetic Circuits with General Gates Oded Goldreich Weizmann Institute of Science Based on Joint work with Avi Wigderson Original title: On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions , ECCC TR13-043.

Constant Depth Boolean Circuits Paritynrequires depth d circuits of size exp( (n1/(d-1))). Famous frontier: Stronger circuit models. Another frontier: Stronger lower bounds (i.e., exp( (n))). Multi-linear functions : x=(x(1), ,x(t)), x(i) 0,1 n F(x(1), ,x(t)) = (i_1, ,i_t) Txi_1(1) xi_t(t) associated with tensor T [n]t Think of t=2, log n Conj (sanity check): For every t>1, there exists a t-linear function that requires depth-three circuits of size exp( (tnt/(t+1))). [holds for t=1 ]

t-linear functions x=(x(1),,x(t)), |x(i)|=n F(x(1), ,x(t)) = (i_1, ,i_t) Txi_1(1) xi_t(t) The Program* Conj (1stsanity check): For every t>1, there exists a t-linear function that requires depth-three circuits of size exp( (tnt/(t+1))). [holds for t=1] Goal: For every t>1, present an explicit t-linear function that requires depth-three circuits of size exp( (tnt/(t+1))). [holds for t=1] A 2ndsanity check: Consider a restricted model of (depth-three) circuits, and prove the L.B. in it. *) Taking advantage of Avi s absence.

Arithmetic Circuits with General Gates Motivation: Depth-three Boolean Circuits for Paritynare obtained by implementing a sqrt(n)-way sum of sqrt(n)- way sums. In general, depth-three BC are obtained via depth-two AC with general ML-gates. We get depth-three BC for F of size exponential in C2(F) Model: Depth-two (set-)multi-linear circuits with arbitrary (set-)multi-linear gates. Complexity measure (C2) = the (max.) arity of a gate. Recall: We use a fix partition of the variables, and multi-linear means being linear in each variable-block. Depth-three BC obtained this way are restricted in (1) their structure arising from direct composition, and (2) ML gates.

Arithmetic Circuits with General Gates (cont.) Model: Unbounded-depth (set-)multi-linear circuits with arbitrary (set-)multi-linear gates. Complexity measure (C) = max(arity, #gates). PROP: Every ML function F has a depth-three BC of size exp(O(C(F)). PF: guess & verify. THM: There exist bilinear functions F such that C(F)=sqrt(n) but C2(F)= (n2/3). OBS: For every t-linear F, Ct+1(F) 2C(F).

Arith. Circuits with General Gates: Results Model: Unbounded-depth (set-)multi-linear circuits with arbitrary (set-)multi-linear gates. Complexity measure (C) = max(arity, #gates); C2for depth-two. THM 1: There exist bilinear functions F such that C(F)=sqrt(n) but C2(F)= (n2/3). THM 2: For every t-linear function F it holds that C(F) C2(F) = O(tnt/(t+1)). THM 3: Almost all t-linear functions F satisfy C2(F) C(F) = (tnt/(t+1)). Open: An explicit function as in Thm 3; for starters (tn0.51).

Arith. Circuits with General Gates: Results (cont.) Model: Unbounded-depth (set-)multi-linear circuits with arbitrary (set-)multi-linear gates. Complexity measure (C) = max(arity, #gates); C2for depth-two. Open: An explicit function as in Thm 3; for starters (tn0.51). An approach (a candidate): The 3-linear function assoc. with tensor T= (i,j,k): |i-(n/2)|+|j-(n/2)|+|k-(n/2)| n/2 . PROP: The complexity of the above 3-linear function is lower bounded by the maximum complexity of all bilinear functions associated w. Toeplitz matrices. THM: If matrix M has rigidity m3for rank m, then the corresponding bilinear function has complexity (m). Note: A restricted notion of ( structured ) rigidity suffices. Open: Show that Toeplitz matrix w. rigidity n1.51for rank n0.51.

Comments on the proofs Model: Multi-linear circuits with arbitrary multi-linear gates. Complexity measure (C) = max(arity, #gates); C2for depth-two. THM 1: There exist bilinear functions F such that C(F)=sqrt(n) but C2(F)= (n2/3). PF idea: s=sqrt(n), f(x,y)=g(x,L1(y), ,Ls(y)). THM 2: For every t-linear function F it holds that C(F) C2(F) = O(tnt/(t+1)). PF: Covering by m cubes of side m. THM 3: Almost all t-linear functions F satisfy C2(F) C(F) = (tnt/(t+1)). PF: A counting argument. THM 4: If matrix M has rigidity m3for rank m, then the corresponding bilinear function has complexity (m). PF idea: The m linear function yield a rank m matrix, whereas the m quadratic forms (in variables) cover m3entries.

Addl comments on the proof of THM 1 Model: Multi-linear circuits with arbitrary multi-linear gates. Complexity measure (C) = max(arity, #gates); C2for depth-two. THM 1: There exist bilinear functions F such that C(F)=sqrt(n) but C2(F)= (n2/3). PF: For s=sqrt(n), let f(x,y)=g(x,L1(y), ,Ls(y)), where g is generic (over n+s bits), each Licomputes the sum of s variables in y. A generic depth-two ML circuit of complexity m computes f as B(F1(x), ,Fm(x),G1(y), ,Gm(y)) + i [m]Bi(x,y) where the Bi s are quadratic and each function has arity m. Hitting y with a random restriction that leaves one variable alive in each block, we get B(F1(x), ,Fm(x),G 1(y ), ,G m(y )) + i [m]B i(x,y ) where each B I(and G I) depends on O(m/s) variables. Hence, the description length is O(m3/s) ; cf. to ns=n2/s.

Structured Rigidity DEF: Matrix M has (m1,m2,m3)-structured rigidity for rank r if matrix R of rank r the non-zeros of M-R cannot be covered by m1(gen.) m2-by-m3rectangles. Rigidity m1m2m3 implies (m1,m2,m3) structured rigidity for the same rank, but not vice versa. THM 5: There exist matrices of (m,m,m)-structured rigidity for rank m that do not have rigidity 3mn for rank 0 (let alone for rank m). For every m [n0.51,n0.66]. PF: Consider a random matrix with 3mn one-entries. THM 4 : If matrix M has (m,m,m)-structured rigidity for rank m, then the corresponding bilinear function has complexity (m). PF idea: The proof of Thm 4 goes through w.o. any change.

t-linear functions x=(x(1),,x(t)), |x(i)|=n F(x(1), ,x(t)) = (i_1, ,i_t) Txi_1(1) xi_t(t) Summary Long-term/dream goal: For every t>1, present an explicit t-linear function that requires depth-three circuits of size exp( (tnt/(t+1))). [holds for t=1] Conj (1stsanity check): For every t>1, there exists a t-linear function that requires depth-three circuits of size exp( (tnt/(t+1))). [holds for t=1] 2ndsanity check: Prove L.B. for a restricted model of (depth- three) circuits; specifically, Arithm.Ckts with general gates: Current goal: Show that explicit t-linear functions F satisfy C2(F) C(F) = (tnt/(t+1)) or so (i.e. super-sqrt).