Introduction to Arithmetic Circuit Complexity Amir Shpilka Technion 1 Arithmetic Circuits March 29, 2014 Goal of talk Survey results in arithmetic circuit complexity! •  Lower Bounds! •  Identity Testing! •  Reconstruction/Interpolation/Learning! Highlight some `next step’ open problems! •  Mostly for restricted models! •  Show why these models/questions are interesting! ! 2 Arithmetic Circuits March 29, 2014 Talk outline •  Definition of the Model! •  Classical Results ! •  Lower Bounds! •  Identity Testing ! •  Reconstruction/Interpolation/Learning! ! 3 Arithmetic Circuits March 29, 2014 Arithmetic Circuits Field: 𝔽! Variables: X ,...,X ! 1 n Gates: +, ×! Every gate in the 
 circuit computes a 
 polynomial in 𝔽 [X ,...,X ]! 1 n Example: (X ⋅ X ) ⋅ (X + 1)! 1 2 2 Size = number of gates! Depth = length of longest input-output path! Degree = max degree of internal gates! ! 4 Arithmetic Circuits March 29, 2014 Arithmetic Formulas Same, except underlying graph is a tree! 5 Arithmetic Circuits March 29, 2014 Motivation •  Most natural model for computing polynomials! •  For many problems (e.g. Matrix Multiplication, Det) best algorithm is by an arithmetic circuit! •  Great algorithmic achievements:! –  Fourier Transform! –  Matrix Multiplication! –  Polynomial Factorization! •  Structured model (compared to Boolean circuits) P vs. NP may be easier! 6 Arithmetic Circuits March 29, 2014 Important Problems Design new algorithms:! –  Õ(n2) for Matrix Multiplication?! –  Polynomial Factorization without depth increase?! Prove lower bounds:! –  Find a polynomial that requires super polynomial size or super logarithmic depth.! Derandomize Polynomial Identity Testing:! –  Given (explicitly or as black-boxed) two arithmetic circuits, decide whether they compute the same polynomial.! Reconstruction of arithmetic circuits:! –  Compute the circuit from its evaluations.! 7 Arithmetic Circuits March 29, 2014 The classics f of degree r computed by size s depth d circuit then:! •  ∂f/∂x ,…,∂f/∂x have size O(s), depth O(d) circuit! 1 n •  Size O(sr2) circuit of depth O(d log(r)) computing all homogeneous components of f! •  Each factor of f has poly(s,r) size circuit! ! If we only have black-box access to f then:! •  Can get BB access to each ∂f/∂x by querying f O(r) k queries for each query to ∂f/∂x ! k •  Same for homogeneous component of f! •  Can get BB access to each factor of f (uses randomness)! 8 Arithmetic Circuits March 29, 2014 The classics: Valiant’s work Valiant defined arithmetic analogs of P and NP : •  VP: All polynomials that have poly size arithmetic circuits of polynomial degree. ! •  VNP: all polys f that for some g in VP 
 f(x ,…,x )=Σ{g(x ,…,x ,e ,…,e ) : e ,…,e ∈ {0,1}}! 1 n 1 n 1 m 1 m Hard problems:! •  For all f in VP there is matrix A, s.t. Det(A) = f, entries of A in {𝔽,X ,...,X }, size of A is nO(log n).! 1 n •  For all f in VNP ∃ matrix A, s.t. Perm(A) = f, 
 entries of A in {𝔽,X ,...,X }, size of A is poly(n). 1 n 9 Arithmetic Circuits March 29, 2014 The classics: Valiant’s work Valiant defined VP, VNP and showed that:! •  For all f in VNP there is matrix A, s.t. Perm(A) = f, 
 entries of A in {𝔽,X ,...,X }, size of A is poly(n). 1 n •  For all f in VP there is matrix A, s.t. Det(A) = f, 
 entries of A in {𝔽,X ,...,X }, size of A is nO(log n).! 1 n To show VP ≠ VNP enough to prove that any such A with det(A) = Perm(X) has size nω(log n)! Best bound [Mignon-Ressayre, Cai-Chen-Li] 
 size(A) = Ω(n2)! Open Problem 1: Prove size(A) ≥ 2n2! 10 Arithmetic Circuits March 29, 2014