NDLI: On the Power of Homogeneous Depth 4 Arithmetic Circuits

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Kumar, Mrinal Saraf, Shubhangi
Copyright Year	2017
Abstract	We prove exponential lower bounds on the size of homogeneous depth 4 arithmetic circuits computing an explicit polynomial in $VP$. Our results hold for the iterated matrix multiplication polynomial---in particular we show that any homogeneous depth 4 circuit computing the (1,1) entry in the product of $n$ generic matrices of dimension $n^{O(1)}$ must have size $n^{\Omega(\sqrt{n})}$. Our results strengthen previous works in two significant ways: (1) Our lower bounds hold for a polynomial in $VP$. Prior to our work, Kayal et al. [Proceedings of FOCS, 2014, pp. 61--70] proved an exponential lower bound for homogeneous depth 4 circuits (over fields of characteristic zero) computing a poly in $VNP$. The best known lower bounds for a depth 4 homogeneous circuit computing a poly in $VP$ was the bound of $n^{\Omega(\log n)}$ by Kayal et al. Our exponential lower bounds also give the first exponential separation between general arithmetic circuits and homogeneous depth 4 arithmetic circuits. In particular they imply that the depth reduction results of Koiran [Theoret. Comput. Sci., 448 (2012), pp. 56--65] and Tavenas [Proceedings of MFCS, 2013] are tight even for reductions to general homogeneous depth 4 circuits (without the restriction of bounded bottom fan-in). (2) Our lower bound holds over all fields. The lower bound of Kayal et al. worked only over fields of characteristic zero. Prior to our work, the best lower bound for homogeneous depth 4 circuits over fields of positive characteristic was $n^{\Omega(\log n)}$ [Kayal et al., Proceedings of FOCS, 2014, pp. 61--70].
Sponsorship	National Science Foundation
Starting Page	336
Ending Page	387
Page Count	52
File Format	PDF
ISSN	00975397
DOI	10.1137/140999335
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	1 (Special Section on the Fifty-Fifth Annual ACM Symposium on Foundations of Computer Science (FOCS 2014))
Volume Number	46
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2017-02-28
Access Restriction	Subscribed
Subject Keyword	Computational difficulty of problems depth 4 circuits shifted partial derivatives depth reduction Computational aspects of field theory and polynomials lower bounds Symbolic computation and algebraic computation
Content Type	Text
Resource Type	Article
Subject	Mathematics Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

The Limits of Depth Reduction for Arithmetic Formulas: It's All About the Top Fan-In

An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas

Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication

Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas

An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas

Evaluating Matrix Circuits

On the Power of Homogeneous Depth 4 Arithmetic Circuits

Algebraic Independence in Positive Characteristic -- A p-Adic Calculus

Lower bounds for depth 4 formulas computing iterated matrix multiplication

On the Power of Homogeneous Depth 4 Arithmetic Circuits

Similar Documents

The Limits of Depth Reduction for Arithmetic Formulas: It's All About the Top Fan-In

An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas

Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication

Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas

An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas

Evaluating Matrix Circuits

On the Power of Homogeneous Depth 4 Arithmetic Circuits

Algebraic Independence in Positive Characteristic -- A p-Adic Calculus

Lower bounds for depth 4 formulas computing iterated matrix multiplication

On the Power of Homogeneous Depth 4 Arithmetic Circuits