## New Research In

### Physical Sciences

### Social Sciences

#### Featured Portals

#### Articles by Topic

### Biological Sciences

#### Featured Portals

#### Articles by Topic

- Agricultural Sciences
- Anthropology
- Applied Biological Sciences
- Biochemistry
- Biophysics and Computational Biology
- Cell Biology
- Developmental Biology
- Ecology
- Environmental Sciences
- Evolution
- Genetics
- Immunology and Inflammation
- Medical Sciences
- Microbiology
- Neuroscience
- Pharmacology
- Physiology
- Plant Biology
- Population Biology
- Psychological and Cognitive Sciences
- Sustainability Science
- Systems Biology

# Bootstrapping variables in algebraic circuits

Contributed by Manindra Agrawal, March 12, 2019 (sent for review January 31, 2019; reviewed by Mrinal Kumar and Srikanth Srinivasan)

This article requires a subscription to view the full text. If you have a subscription you may use the login form below to view the article. Access to this article can also be purchased.

## Significance

Zero testing [or polynomial identity testing (PIT)] for circuits is a computational algebra problem with numerous practical applications and a beautiful theory (e.g., primality testing and graph matching are solved using PIT). It strongly relates to showing that there are explicit/natural polynomials that require exponentially large circuits. The latter is also called the algebraic version of the P≠NP question (or VP≠?VNP) and lies in the intersection of mathematics and computing. This work provides a plausible route to it if we can design a polynomial-time computable, but small enough, hitting set for trivariate depth-4 circuits [merely

## Abstract

We show that for the blackbox polynomial identity testing (PIT) problem it suffices to study circuits that depend only on the first extremely few variables. One needs only to consider size-s degree-s circuits that depend on the first *i*) a quadratic-time blackbox PIT for 6,913-variate degree-s size-s polynomials will lead to a “near”-complete derandomization of PIT and (*ii*) a blackbox PIT for n-variate degree-s size-s circuits in *Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing STOC ’03*].

## Footnotes

- ↵
^{1}To whom correspondence may be addressed. Email: manindra{at}cse.iitk.ac.in, sumghosh{at}cse.iitk.ac.in, or nitin{at}cse.iitk.ac.in.

This contribution is part of the special series of Inaugural Articles by members of the National Academy of Sciences elected in 2015.

Author contributions: M.A., S.G., and N.S. designed research, performed research, contributed new reagents/analytic tools, and wrote the paper.

Reviewers: M.K., University of Toronto; and S.S., Indian Institute of Technology Bombay.

The authors declare no conflict of interest.

Published under the PNAS license.

## References

- ↵
- Demillo RA,
- Lipton RJ

- ↵
- Ng EW

- Zippel R

- ↵
- Schwartz JT

- ↵
- Mulmuley K

- ↵
- Grochow JA,
- Mulmuley KD,
- Qiao Y

*43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)*, Leibniz International Proceedings in Informatics (LIPIcs), eds Chatzigiannakis I, Mitzenmacher M, Rabani Y, Sangiorgi D (Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany), Vol 55, pp 34.1–34.14. - ↵
- Grochow JA

- ↵
- Mulmuley KD

- ↵
- Kulikov AS,
- Woeginge GJ

- Mukhopadhyay P

- ↵
- Fischer MJ,
- DeMillo RA,
- Lynch NA,
- Burkhard WA,
- Aho AV

- Valiant LG

- ↵
- Miller RE,
- Ginsburg S,
- Burkhard WA,
- Lipton RJ

- Heintz J,
- Schnorr C-P

- ↵
- Larmore LL,
- Goemans MX

- Kabanets V,
- Impagliazzo R

- ↵
- Ramanujam R,
- Sen S

- Agrawal M

- ↵
- Aho AA

- Mulmuley K,
- Vazirani UV,
- Vazirani VV

- ↵
- ↵
- Kopparty S,
- Saraf S,
- Shpilka A

- ↵
- Dvir Z,
- de Oliveira RM,
- Shpilka A

*Proceedings of the 41st International Colloquium on Automata, Languages, and Programming, Part I*, Lecture Notes in Computer Science, eds Esparza J, Fraigniaud P, Husfeldt T, Koutsoupias E (Springer, New York), Vol 8572, pp 417–428. - ↵
- Saxena N

- ↵
- Saxena N

- ↵
- Shpilka A,
- Yehudayoff A

- ↵
- Wigderson A

- ↵
- Mulmuley KD

- ↵
- ↵
- Kayal N,
- Saxena N

- ↵
- Saxena N

*ICALP*, Lecture Notes in Computer Science, eds Aceto L, Damgård I, Goldberg LA, Halldórsson MM, Ingólfsdóttir A, Walukiewicz I (Springer, Berlin), Vol 5125, pp 60–71. - ↵
- Saxena N,
- Seshadhri C

- ↵
- Agrawal M,
- Saha C,
- Saptharishi R,
- Saxena N

- ↵
- Beecken M,
- Mittmann J,
- Saxena N

- ↵
- Saha C,
- Saptharishi R,
- Saxena N

- ↵
- Guruswami V

- Forbes MA

- ↵
- Raz R

- Kumar M,
- Saraf S

- ↵
- Raz R

- Kumar M,
- Saraf S

- ↵
- Pandey A,
- Saxena N,
- Amit S

- ↵
- Karloff HJ,
- Pitassi T

- Forbes MA,
- Shpilka A

- ↵
- Boneh D,
- Roughgarden T,
- Feigenbaum J

- Agrawal M,
- Saha C,
- Saxena N

- ↵
- Shmoys DB

- Forbes MA,
- Saptharishi R,
- Shpilka A

- ↵
- Agrawal M,
- Gurjar R,
- Korwar A,
- Saxena N

- ↵
- Gurjar R,
- Korwar A,
- Saxena N,
- Thierauf T

- ↵
- Gurjar R,
- Korwar A,
- Saxena N

- ↵
- O’Donnell R

- Minahan D,
- Volkovich I

- ↵
- Wichs D,
- Mansour Y

- Fenner SA,
- Gurjar R,
- Thierauf T

- ↵
- Hatami H,
- McKenzie P,
- King V

- Gurjar R,
- Thierauf T

- ↵
- Umans C

- Svensson O,
- Tarnawski J

- ↵
- Chatzigiannakis I,
- Kaklamanis C,
- Marx D,
- Sannella D

- Gurjar R,
- Thierauf T,
- Vishnoi NK

- ↵
- Lagarde G,
- Malod G,
- Perifel S

- ↵
- Dinur I

- Garg A,
- Gurvits L,
- Oliveira R,
- Wigderson A

- ↵
- Larsen KG,
- Bodlaender HL,
- Raskin J-F

- Lagarde G,
- Limaye N,
- Srinivasan S

- ↵
- Saptharishi R

- ↵
- Hatami H,
- McKenzie P,
- King V

- Forbes MA,
- Shpilka A,
- Lee Volk B

- ↵
- Bürgisser P

- ↵
- Kaltofen E

- ↵
- Diakonikolas I,
- Kempe D,
- Henzinge M

- Dutta P,
- Saxena N,
- Amit S

- ↵
- Dwivedi A,
- Mittal R,
- Saxena N

- ↵
- Servedio RA

- Guo Z,
- Saxena N,
- Amit S

- ↵
- Servedio RA

- Forbes MA,
- Shpilka A

- ↵
- Yao AC

- ↵
- Arora S,
- Barak B

- ↵
- Bürgisser P

- ↵
- Kabanets V,
- Russell I

- ↵
- Clausen M,
- Dress A,
- Grabmeier J,
- Karpinski M

- ↵
- Gupta A,
- Kamath P,
- Kayal N,
- Saptharishi R

- ↵
- Agrawal M,
- Vinay V

- ↵
- Martin F

- ↵
- Nabeshima K,
- Nagasaka K,
- Winkler F,
- Szanto A

- Le Gall F

- ↵
- Fischer I

- ↵
- Diakonikolas I,
- Kempe D,
- Henzinger M

- Agrawal M,
- Ghosh S,
- Saxena N

- ↵
- Chan TM

- Kumar M,
- Saptharishi R,
- Tengse A

- ↵
- Kannan R,
- Kumar KN

- Saha C,
- Saptharishi R,
- Saxena N

- ↵
- Chatzigiannakis I,
- Kaklamanis C,
- Marx D,
- Sannella D

- Forbes MA,
- Ghosh S,
- Saxena N

### Log in using your username and password

### Purchase access

Subscribers, for more details, please visit our Subscriptions FAQ.

Please click here to log into the PNAS submission website.

## Citation Manager Formats

## Sign up for Article Alerts

## Article Classifications

- Physical Sciences
- Mathematics