More Web Proxy on the site http://driver.im/

research-article

Free access

Black-box identity testing of depth-4 multilinear circuits

Authors:

Shubhangi Saraf,

Ilya VolkovichAuthors Info & Claims

STOC '11: Proceedings of the forty-third annual ACM symposium on Theory of computing

Pages 421 - 430

https://doi.org/10.1145/1993636.1993693

Published: 06 June 2011 Publication History

Abstract

We study the problem of identity testing for multilinear ΣΠΣΠ(k) circuits, i.e. multilinear depth-4 circuits with fan-in k at the top + gate. We give the first polynomial-time deterministic identity testing algorithm for such circuits. Our results also hold in the black-box setting.

The running time of our algorithm is (ns)^O(k³), where n is the number of variables, s is the size of the circuit and k is the fan-in of the top gate. The importance of this model arises from [3], where it was shown that derandomizing black-box polynomial identity testing for general depth-4 circuits implies a derandomization of polynomial identity testing (PIT) for general arithmetic circuits. Prior to our work, the best PIT algorithm for multilinear ΣΠΣΠ(k) circuits [13] ran in quasi-polynomial-time, with the running time being n^{O(k⁶ log(k) log² s )}.

We obtain our results by showing a strong structural result for multilinear ΣΠΣΠ(k) circuits that compute the zero polynomial. We show that under some mild technical conditions, any gate of such a circuit must compute a sparse polynomial. We then show how to combine the structure theorem with a result by Klivans and Spielman [17], on the identity testing for sparse polynomials, to yield the full result.

Supplementary Material

JPG File (stoc_7b_3.jpg)

Download
16.58 KB

MP4 File (stoc_7b_3.mp4)

Download
103.93 MB

References

[1]

M. Agrawal, N. Kayal, and N. Saxena. Primes is in P. Annals of Mathematics, 160(2):781--793, 2004.

[2]

M. Agrawal and V. Vinay. Arithmetic circuits: A chasm at depth four. In Proceedings of the 49th Annual FOCS, pages 67--75, 2008.

Digital Library

[3]

N. Alon. Combinatorial nullstellensatz. Combinatorics, Probability and Computing, 8:7--29, 1999.

Digital Library

[4]

M. Anderson, D. van Melkebeek, and I. Volkovich. Derandomizing polynomial identity testing for multilinear constant-read formulae. In Proceedings of the 26rd Annual IEEE Conference on Computational Complexity, CCC, 2011.

Digital Library

[5]

V. Arvind and P. Mukhopadhyay. The monomial ideal membership problem and polynomial identity testing. Information and Computation, 208(4):351--363, 2010.

Digital Library

[6]

M. Ben-Or and P. Tiwari. A deterministic algorithm for sparse multivariate polynominal interpolation. In Proceedings of the 20th Annual STOC, pages 301--309, 1988.

Digital Library

[7]

F R Chung, R L Graham, P Frankl, and J B Shearer. Some intersection theorems for ordered sets and graphs. J. Comb. Theory Ser. A, 43(1):23--37, 1986.

Digital Library

[8]

Z. Dvir and A. Shpilka. Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits. SIAM J. on Computing, 36(5):1404--1434, 2006.

Digital Library

[9]

Z. Dvir, A. Shpilka, and A. Yehudayoff. Hardness-randomness tradeoffs for bounded depth arithmetic circuits. SIAM J. on Computing, 39(4):1279--1293, 2009.

Digital Library

[10]

J. Heintz and C. P. Schnorr. Testing polynomials which are easy to compute (extended abstract). In Proceedings of the 12th annual STOC, pages 262--272, 1980.

Digital Library

[11]

V. Kabanets and R. Impagliazzo. Derandomizing polynomial identity tests means proving circuit lower bounds. Computational Complexity, 13(1--2):1--46, 2004.

Digital Library

[12]

Z. S. Karnin, P. Mukhopadhyay, A. Shpilka, and I. Volkovich. Deterministic identity testing of depth 4 multilinear circuits with bounded top fan-in. In Proceedings of the 42nd Annual STOC, pages 649--658, 2010.

Digital Library

[13]

Z. S. Karnin and A. Shpilka. Deterministic black box polynomial identity testing of depth-3 arithmetic circuits with bounded top fan-in. In Proceedings of the 23rd Annual CCC, pages 280--291, 2008.

Digital Library

[14]

N. Kayal and S. Saraf. Blackbox polynomial identity testing for depth 3 circuits. In Proceedings of the 50th Annual FOCS, pages 198--207, 2009.

Digital Library

[15]

N. Kayal and N. Saxena. Polynomial identity testing for depth 3 circuits. Computational Complexity, 16(2):115--138, 2007.

Digital Library

[16]

A. Klivans and D. Spielman. Randomness efficient identity testing of multivariate polynomials. In Proceedings of the 33rd Annual STOC, pages 216--223, 2001.

Digital Library

[17]

R. J. Lipton and N. K. Vishnoi. Deterministic identity testing for multivariate polynomials. In Proceedings of the 14th annual SODA, pages 756--760, 2003.

Digital Library

[18]

L. Lovasz. On determinants, matchings, and random algorithms. In L. Budach, editor, Fundamentals of Computing Theory. Akademia-Verlag, 1979.

[19]

C. Lund, L. Fortnow, H. Karloff, and N. Nisan. Algebraic methods for interactive proof systems. JACM, 39(4):859--868, 1992.

Digital Library

[20]

K. Mulmuley, U. Vazirani, and V. Vazirani. Matching is as easy as matrix inversion. Combinatorica, 7(1):105--113, 1987.

Digital Library

[21]

R. Raz. Separation of multilinear circuit and formula size. Theory of Computing, 2(1):121--135, 2006.

[22]

R. Raz. Multi-linear formulas for permanent and determinant are of super-polynomial size. J. ACM, 56(2), 2009.

Digital Library

[23]

R. Raz, A. Shpilka, and A. Yehudayoff. A lower bound for the size of syntactically multilinear arithmetic circuits. SIAM J. on Computing, 38(4):1624--1647, 2008.

Digital Library

[24]

R. Raz and A. Yehudayoff. Lower bounds and separations for constant depth multilinear circuits. Computational Complexity, 18(2):171--207, 2009.

[25]

N. Saxena. Diagonal circuit identity testing and lower bounds. In ICALP (1), pages 60--71, 2008.

Digital Library

[26]

N. Saxena and C. Seshadhri. An almost optimal rank bound for depth-3 identities. In Proceedings of the 24th annual CCC, pages 137--148, 2009.

Digital Library

[27]

N. Saxena and C. Seshadhri. Blackbox identity testing for bounded top fanin depth-3 circuits: the field doesn't matter. ECCC, (167), 2010.

[28]

N. Saxena and C. Seshadhri. From sylvester-gallai configurations to rank bounds: Improved black-box identity test for deph-3 circuits. In Proceedings of the 51st Annual FOCS, pages 21--30, 2010.

Digital Library

[29]

J. T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. J. ACM, 27(4):701--717, 1980.

Digital Library

[30]

Adi Shamir. IP=PSPACE. In Proceedings of the Thirty First Annual Symposium on Foundations of Computer Science, pages 11--15, 1990.

Digital Library

[31]

A. Shpilka and I. Volkovich. Improved polynomial identity testing for read-once formulas. In APPROX-RANDOM, pages 700--713, 2009.

Digital Library

[32]

A. Shpilka and I. Volkovich. On the relation between polynomial identity testing and finding variable disjoint factors. In ICALP (1), pages 408--419, 2010.

Digital Library

[33]

A. Shpilka and A. Yehudayoff. Arithmetic circuits: A survey of recent results and open questions. Foundations and Trends® in Theoretical Computer Science, 5(3--4):207--388, 2010.

Digital Library

[34]

R. Zippel. Probabilistic algorithms for sparse polynomials. In Symbolic and algebraic computation, pages 216--226. 1979.

Digital Library

Cited By

Garg AGurvits LOliveira RWigderson A(2019)Operator Scaling: Theory and ApplicationsFoundations of Computational Mathematics10.1007/s10208-019-09417-z20:2(223-290)Online publication date: 6-May-2019
https://doi.org/10.1007/s10208-019-09417-z
Allen-Zhu ZGarg ALi YOliveira RWigderson ADiakonikolas IKempe DHenzinger M(2018)Operator scaling via geodesically convex optimization, invariant theory and polynomial identity testingProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3188745.3188942(172-181)Online publication date: 20-Jun-2018
https://dl.acm.org/doi/10.1145/3188745.3188942
Anderson MForbes MSaptharishi RShpilka AVolk B(2018)Identity Testing and Lower Bounds for Read-k Oblivious Algebraic Branching ProgramsACM Transactions on Computation Theory10.1145/317070910:1(1-30)Online publication date: 10-Jan-2018
https://dl.acm.org/doi/10.1145/3170709
Show More Cited By

Index Terms

Black-box identity testing of depth-4 multilinear circuits
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Deterministic identity testing of depth-4 multilinear circuits with bounded top fan-in
STOC '10: Proceedings of the forty-second ACM symposium on Theory of computing

We give the first sub-exponential time deterministic polynomial identity testing algorithm for depth-4 multilinear circuits with a small top fan-in. More accurately, our algorithm works for depth-4 circuits with a plus gate at the top (also known as ...
Deterministic Identity Testing of Depth-4 Multilinear Circuits with Bounded Top Fan-in
^† Special Section on the Fiftieth Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009)

We give the first subexponential time deterministic polynomial identity testing algorithm for depth-4 multilinear circuits with a small top fan-in. More accurately, our algorithm works for depth-4 multilinear circuits with a plus gate at the top (also known ...
Black-Box Identity Testing of Depth-4 Multilinear Circuits

We study the problem of identity testing for multilinear Σ?Σ?(k) circuits, i.e., multilinear depth-4 circuits with fan-in k at the top + gate. We give the first polynomial-time deterministic identity testing algorithm for such circuits when k=O(1). Our ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '11: Proceedings of the forty-third annual ACM symposium on Theory of computing

June 2011

840 pages

ISBN:9781450306911

DOI:10.1145/1993636

General Chair:
Lance Fortnow
Northwestern University
,
Program Chair:
Salil Vadhan
Harvard University

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 June 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC'11

Sponsor:

SIGACT

STOC'11: Symposium on Theory of Computing

June 6 - 8, 2011

California, San Jose, USA

Acceptance Rates

STOC '11 Paper Acceptance Rate 84 of 304 submissions, 28%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

25
Total Citations
View Citations
387
Total Downloads

Downloads (Last 12 months)68
Downloads (Last 6 weeks)13

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Garg AGurvits LOliveira RWigderson A(2019)Operator Scaling: Theory and ApplicationsFoundations of Computational Mathematics10.1007/s10208-019-09417-z20:2(223-290)Online publication date: 6-May-2019
https://doi.org/10.1007/s10208-019-09417-z
Allen-Zhu ZGarg ALi YOliveira RWigderson ADiakonikolas IKempe DHenzinger M(2018)Operator scaling via geodesically convex optimization, invariant theory and polynomial identity testingProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3188745.3188942(172-181)Online publication date: 20-Jun-2018
https://dl.acm.org/doi/10.1145/3188745.3188942
Anderson MForbes MSaptharishi RShpilka AVolk B(2018)Identity Testing and Lower Bounds for Read-k Oblivious Algebraic Branching ProgramsACM Transactions on Computation Theory10.1145/317070910:1(1-30)Online publication date: 10-Jan-2018
https://dl.acm.org/doi/10.1145/3170709
Kumar MSaraf S(2016)Sums of products of polynomials in few variablesProceedings of the 31st Conference on Computational Complexity10.5555/2982445.2982480(1-29)Online publication date: 29-May-2016
https://dl.acm.org/doi/10.5555/2982445.2982480
Kumar MSaraf S(2016)Arithmetic circuits with locally low algebraic rankProceedings of the 31st Conference on Computational Complexity10.5555/2982445.2982479(1-27)Online publication date: 29-May-2016
https://dl.acm.org/doi/10.5555/2982445.2982479
Anderson MForbes MSaptharishi RShpilka AVolk B(2016)Identity testing and lower bounds for read-k oblivious algebraic branching programsProceedings of the 31st Conference on Computational Complexity10.5555/2982445.2982475(1-25)Online publication date: 29-May-2016
https://dl.acm.org/doi/10.5555/2982445.2982475
Garg AGurvits LOliveira RWigderson A(2016)A Deterministic Polynomial Time Algorithm for Non-commutative Rational Identity Testing2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS.2016.95(109-117)Online publication date: Oct-2016
https://doi.org/10.1109/FOCS.2016.95
Oliveira RShpilka AVolk B(2016)Subexponential Size Hitting Sets for Bounded Depth Multilinear FormulasComputational Complexity10.1007/s00037-016-0131-125:2(455-505)Online publication date: 1-Jun-2016
https://dl.acm.org/doi/10.1007/s00037-016-0131-1
Mukhopadhyay P(2016)Depth-4 Identity Testing and Noether's Normalization LemmaProceedings of the 11th International Computer Science Symposium on Computer Science --- Theory and Applications - Volume 969110.1007/978-3-319-34171-2_22(309-323)Online publication date: 9-Jun-2016
https://dl.acm.org/doi/10.1007/978-3-319-34171-2_22
Oliveira RShpilka AVolk BZuckerman D(2015)Subexponential size hitting sets for bounded depth multilinear formulasProceedings of the 30th Conference on Computational Complexity10.5555/2833227.2833242(304-322)Online publication date: 17-Jun-2015
https://dl.acm.org/doi/10.5555/2833227.2833242
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents