Cited By
View all- Harsha PKumar MSaptharishi RSudan M(2024)An Improved Line-Point Low-Degree Test*2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00113(1883-1892)Online publication date: 27-Oct-2024
Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring
Article No.: 18, Pages 1 - 39
Abstract
Newton iteration is an almost 350-year-old recursive formula that approximates a simple root of a polynomial quite rapidly. We generalize it to a matrix recurrence (allRootsNI) that approximates all roots simultaneously. In this form, the process yields better circuit complexity in the case when the number of roots r is small but the multiplicities are exponentially large. Our method sets up a linear system in r unknowns and iteratively builds the roots as formal power series. For an algebraic circuit \(f(x_1,\ldots ,x_n)\) of size s, we prove that each factor has size at most a polynomial ins and the degree of the squarefree part of f. Consequently, if \(f_1\) is a \(2^{\Omega (n)}\)-hard polynomial, then any nonzero multiple \(\prod _{i} f_i^{e_i}\) is equally hard for arbitrary positive \(e_i\)’s, assuming that \(\sum _i\deg (f_i)\) is at most \(2^{O(n)}\).
It is an old open question whether the class of poly(n) size formulas (respectively, algebraic branching programs) is closed under factoring. We show that given a polynomial f of degree \(n^{O(1)}\) and formula (respectively, algebraic branching program) size \(n^{O(\log n)}\), we can find a similar-size formula (respectively, algebraic branching program) factor in randomized poly(\(n^{\log n}\)) time. Consequently, if the determinant requires an \(n^{\Omega (\log n)}\) size formula, then the same can be said about any of its nonzero multiples.
In all of our proofs, we exploit the following property of multivariate polynomial factorization. Under a random linear transformation \(\tau\), the polynomial \(f(\tau \overline{x})\) completely factors via power series roots. Moreover, the factorization adapts well to circuit complexity analysis. Therefore, with the help of the strong mathematical characterizations and the ‘allRootsNI’ technique, we make significant progress towards the old open problems; supplementing the vast body of classical results and concepts in algebraic circuit factorization (e.g., [17, 51, 54, 111]).
References
[1]
Oliver Aberth. 1973. Iteration methods for finding all zeros of a polynomial simultaneously. Mathematics of Computation 27, 122 (1973), 339–344.
[2]
Manindra Agrawal, Sumanta Ghosh, and Nitin Saxena. 2019. Bootstrapping variables in algebraic circuits. Proceedings of the National Academy of Sciences 116, 17 (2019), 8107–8118.
[3]
Manindra Agrawal and V. Vinay. 2008. Arithmetic circuits: A chasm at depth four. In Proceedings of the 2008 IEEE 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS’08). IEEE, Los Alamitos, CA, 67–75.
[4]
Mohammadali Asadi, Alexander Brandt, Mahsa Kazemi, Marc Moreno Maza, and Erik Postma. 2021. Multivariate power series in Maple. arXiv preprint arXiv:2106.15519 (2021).
[5]
Daniel Augot and Lancelot Pecquet. 2000. A Hensel lifting to replace factorization in list-decoding of algebraic-geometric and Reed-Solomon codes. IEEE Transactions on Information Theory 46, 7 (2000), 2605–2614.
[6]
Michael Ben-Or and Richard Cleve. 1992. Computing algebraic formulas using a constant number of registers. SIAM Journal on Computing 21, 1 (1992), 54–58.
[7]
Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, and Shubhangi Saraf. 2020. Proximity gaps for Reed-Solomon codes. In Proceedings of the Electronic Colloquium on Computational Complexity (ECCC’20). https://eccc.weizmann.ac.il/report/2020/083/.
[8]
Elwyn R. Berlekamp. 1970. Factoring polynomials over large finite fields. Mathematics of Computation 24, 111 (1970), 713–735.
[9]
Vishwas Bhargava, Shubhangi Saraf, and Ilya Volkovich. 2020. Deterministic factorization of sparse polynomials with bounded individual degree. Journal of the ACM 67, 2, (May 2020), Article 8, 28 pages.
[10]
Markus Bläser and Gorav Jindal. 2018. On the complexity of symmetric polynomials. In Proceedings of the 10th Innovations in Theoretical Computer Science Conference (ITCS’19).
[11]
Lenore Blum, Felipe Cucker, Michael Shub, and Steve Smale. 1998. Complexity and Real Computation. Springer Science & Business Media.
[12]
Lenore Blum, Mike Shub, and Steve Smale. 1989. On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bulletin (New Series) of the American Mathematical Society 21, 1 (1989), 1–46.
[13]
Nicolas Bourbaki. 2013. Algebra II: Chapters 4-7. Elements of Mathematics. Springer Science & Business Media.
[14]
Richard P. Brent and Hsiang T. Kung. 1978. Fast algorithms for manipulating formal power series. Journal of the ACM 25, 4 (1978), 581–595.
[15]
Karl Bringmann, Christian Ikenmeyer, and Jeroen Zuiddam. 2018. On algebraic branching programs of small width. Journal of the ACM 65, 5, (2018), Article 32, 29 pages.
[16]
Peter Bürgisser. 2001. On implications between P-NP-hypotheses: Decision versus computation in algebraic complexity. In Proceedings of the 26th International Symposium on Mathematical Foundations of Computer Science (MFCS’01). 3–17.
[17]
Peter Bürgisser. 2004. The complexity of factors of multivariate polynomials. Foundations of Computational Mathematics 4, 4 (2004), 369–396.
[18]
Peter Bürgisser. 2013. Completeness and Reduction in Algebraic Complexity Theory, Vol. 7. Springer Science & Business Media.
[19]
Peter Bürgisser, Michael Clausen, and Amin Shokrollahi. 2013. Algebraic Complexity Theory, Vol. 315. Springer Science & Business Media.
[20]
David G. Cantor and Daniel M. Gordon. 2000. Factoring polynomials over \(\rho\)-Adic fields. In Proceedings of the International Algorithmic Number Theory Symposium. 185–208.
[21]
David G. Cantor and Hans Zassenhaus. 1981. A new algorithm for factoring polynomials over finite fields. Mathematics of Computation 36, 154 (1981), 587–592.
[22]
Alexander L. Chistov. 1994. Algorithm of polynomial complexity for factoring polynomials over local fields. Journal of Mathematical Sciences 70, 4 (1994), 1912–1933.
[23]
Chi-Ning Chou, Mrinal Kumar, and Noam Solomon. 2019. Closure of VP under taking factors: A short and simple proof. arXiv preprint arXiv:1903.02366 (2019).
[24]
Chi-Ning Chou, Mrinal Kumar, and Noam Solomon. 2019. Closure results for polynomial factorization. Theory of Computing 15, 13 (2019), 1–34.
[25]
Richard Courant, Herbert Robbins, and Ian Stewart. 1996. What Is Mathematics? An Elementary Approach to Ideas and Methods. Oxford University Press.
[26]
Germund Dahlquist and Åke Björck. 2008. Numerical Methods in Scientific Computing, Vol. I. Society for Industrial and Applied Mathematics.
[27]
Richard A. Demillo and Richard J. Lipton. 1978. A probabilistic remark on algebraic program testing. Information Processing Letters 7, 4 (1978), 193–195.
[28]
Émile Durand. 1960. Solutions numériques des équations algébriques. Tome I, Équations du type F(x)= 0. In Racines d’une Polynôme. Masson, 279–281.
[29]
Pranjal Dutta. 2021. Real \(\tau\)-conjecture for sum-of-squares: A unified approach to lower bound and derandomization. In Proceedings of the International Computer Science Symposium in Russia. 78–101.
[30]
Pranjal Dutta, Prateek Dwivedi, and Nitin Saxena. 2021. Demystifying the border of depth-3 algebraic circuits. In Proceedings of the 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS’21).
[31]
Pranjal Dutta, Prateek Dwivedi, and Nitin Saxena. 2021. Deterministic identity testing paradigms for bounded top-fanin depth-4 circuits. In 36th Computational Complexity Conference, CCC 2021, July 20-23, 2021, Toronto, Ontario, Canada (Virtual Conference) (LIPIcs), Valentine Kabanets (Ed.), Vol. 200. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Article 11, 27 pages.
[32]
Pranjal Dutta, Gorav Jindal, Anurag Pandey, and Amit Sinhababu. 2021. Arithmetic circuit complexity of division and truncation. In Proceedings of the 36th Computational Complexity Conference (CCC’21).
[33]
Pranjal Dutta, Nitin Saxena, and Thomas Thierauf. 2021. A largish sum-of-squares implies circuit hardness and derandomization. In Proceedings of the 12th Innovations in Theoretical Computer Science Conference (ITCS’21).
[34]
Zeev Dvir, Amir Shpilka, and Amir Yehudayoff. 2009. Hardness-randomness tradeoffs for bounded depth arithmetic circuits. SIAM Journal on Computing 39, 4 (2009), 1279–1293.
[35]
Ashish Dwivedi, Rajat Mittal, and Nitin Saxena. 2019. Efficiently factoring polynomials modulo \(p^4\). arxiv preprint arXiv:1901.06628 (2019).
[36]
Louis W. Ehrlich. 1967. A modified Newton method for polynomials. Communications of the ACM 10, 2 (1967), 107–108.
[37]
Michael A. Forbes and Amir Shpilka. 2015. Complexity theory column 88: Challenges in polynomial factorization. ACM SIGACT News 46, 4 (2015), 32–49.
[38]
Michael A. Forbes, Amir Shpilka, Iddo Tzameret, and Avi Wigderson. 2016. Proof complexity lower bounds from algebraic circuit complexity. In Proceedings of the 31st Conference on Computational Complexity (CCC’16). 32.
[39]
Shuhong Gao. 2003. Factoring multivariate polynomials via partial differential equations. Mathematics of Computation 72, 242 (2003), 801–822.
[40]
Patrizia Gianni, Barry Trager, and Gail Zacharias. 1988. Gröbner bases and primary decomposition of polynomial ideals. Journal of Symbolic Computation 6, 2 (1988), 149–167.
[41]
M. Giusti, J. Heintz, J. E. Morais, J. Morgenstem, and L. M. Pardo. 1998. Straight-line programs in geometric elimination theory. Journal of Pure and Applied Algebra 124, 1–3 (1998), 101–146.
[42]
Bruno Grenet. 2016. Bounded-degree factors of lacunary multivariate polynomials. Journal of Symbolic Computation 75 (2016), 171–192.
[43]
Joshua A. Grochow. 2015. Unifying known lower bounds via geometric complexity theory. Computational Complexity 24, 2 (2015), 393–475.
[44]
Joshua A. Grochow. 2020. Complexity in ideals of polynomials: Questions on algebraic complexity of circuits and proofs. Bulletin of EATCS 1, 130 (2020), 24 pages.
[45]
Joshua A. Grochow, Ketan D. Mulmuley, and Youming Qiao. 2016. Boundaries of VP and VNP. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP’6), Vol. 55. Article 34, 14 pages.
[46]
Venkatesan Guruswami and Madhu Sudan. 1998. Improved decoding of Reed-Solomon and algebraic-geometric codes. In Proceedings of the 1998 IEEE 39th Annual Symposium on Foundations of Computer Science (FOCS’98). IEEE, Los Alamitos, CA, 28–37.
[47]
Gábor Ivanyos, Marek Karpinski, Lajos Rónyai, and Nitin Saxena. 2012. Trading GRH for algebra: Algorithms for factoring polynomials and related structures. Mathematics of Computation 81, 277 (2012), 493–531.
[48]
Maurice J. Jansen. 2011. Extracting roots of arithmetic circuits by adapting numerical methods. In Proceedings of the 2nd Symposium on Innovations in Computer Science (ICS’11). 87–100. http://homepages.inf.ed.ac.uk/mjansen1/Jansen10.pdf.
[49]
Valentine Kabanets and Russell Impagliazzo. 2003. Derandomizing polynomial identity tests means proving circuit lower bounds. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing. ACM, New York, NY, 355–364.
[50]
Erich Kaltofen. 1985. Computing with polynomials given by straight-line programs I: Greatest common divisors. In Proceedings of the 17th Annual ACM Symposium on Theory of Computing. ACM, New York, NY, 131–142.
[51]
Erich Kaltofen. 1985. Polynomial-time reductions from multivariate to bi-and univariate integral polynomial factorization. SIAM Journal on Computing 14, 2 (1985), 469–489.
[52]
Erich Kaltofen. 1986. Uniform closure properties of p-computable functions. In Proceedings of the 18th Annual ACM Symposium on Theory of Computing. ACM, New York, NY, 330–337.
[53]
Erich Kaltofen. 1987. Single-factor Hensel lifting and its application to the straight-line complexity of certain polynomials. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing. ACM, New York, NY, 443–452.
[54]
Erich Kaltofen. 1989. Factorization of polynomials given by straight-line programs. Randomness and Computation 5 (1989), 375–412.
[55]
Erich Kaltofen. 1990. Polynomial factorization 1982–1986. In Computers in Mathematics. CRC Press, Boca Raton, FL, 86–111.
[56]
Erich Kaltofen. 1992. Polynomial factorization 1987–1991. In Proceedings of the 1st Latin American Symposium on Theoretical Informatics (LATIN’92).294–313.
[57]
Erich Kaltofen and Pascal Koiran. 2008. Expressing a fraction of two determinants as a determinant. In Proceedings of the 21st International Symposium on Symbolic and Algebraic Computation. ACM, New York, NY, 141–146.
[58]
Zohar S. Karnin and Amir Shpilka. 2009. Reconstruction of generalized depth-3 arithmetic circuits with bounded top fan-in. In Proceedings of the 24th Annual IEEE Conference on Computational Complexity (CCC’09). IEEE, Los Alamitos, CA, 274–285.
[59]
Neeraj Kayal. 2011. Efficient algorithms for some special cases of the polynomial equivalence problem. In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms. 1409–1421.
[60]
Neeraj Kayal and Nitin Saxena. 2006. Complexity of ring morphism problems. Computational Complexity 15, 4 (2006), 342–390.
[61]
Gregor Kemper. 2010. A Course in Commutative Algebra, Vol. 256. Springer Science & Business Media.
[62]
Immo O. Kerner. 1966. Ein gesamtschrittverfahren zur berechnung der nullstellen von polynomen. Numerische Mathematik 8, 3 (1966), 290–294.
[63]
Swastik Kopparty, Shubhangi Saraf, and Amir Shpilka. 2015. Equivalence of polynomial identity testing and polynomial factorization. Computational Complexity 24, 2 (2015), 295–331.
[64]
Steven G. Krantz and Harold R. Parks. 2012. The Implicit Function Theorem: History, Theory, and Applications. Springer Science & Business Media.
[65]
Teresa Krick. 2002. Straight-line programs in polynomial equation solving. Foundations of Computational Mathematics: Minneapolis 312 (2002), 96–136.
[66]
Mrinal Kumar, Ramprasad Saptharishi, and Anamay Tengse. 2019. Near-optimal bootstrapping of hitting sets for algebraic circuits. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms. 639–646.
[67]
Mrinal Kumar and Shubhangi Saraf. 2016. Arithmetic circuits with locally low algebraic rank. In Proceedings of the 31st Conference on Computational Complexity (CCC’16). Article 34, 27 pages.
[68]
H. T. Kung and Joseph Frederick Traub. 1978. All algebraic functions can be computed fast. Journal of the ACM 25, 2 (1978), 245–260.
[69]
Susan Landau. 1985. Factoring polynomials over algebraic number fields. SIAM Journal on Computing 14, 1 (1985), 184–195.
[70]
Grégoire Lecerf. 2002. Quadratic Newton iteration for systems with multiplicity. Foundations of Computational Mathematics 2, 3 (2002), 247–293.
[71]
Arjen K. Lenstra. 1983. Factoring polynomials over algebraic number fields. In Proceedings of the European Conference on Computer Algebra. 245–254.
[72]
Arjen Klaas Lenstra, Hendrik Willem Lenstra, and László Lovász. 1982. Factoring polynomials with rational coefficients. Mathematische Annalen 261, 4 (1982), 515–534.
[73]
Arjen K. Lenstra, Hendrik W. Lenstra, Mark S. Manasse, and John M. Pollard. 1990. The number field sieve. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing. ACM, New York, NY, 564–572.
[74]
Rudolph Lidl and Harald Niederreiter. 1997. Finite Fields. Cambridge University Press, Cambridge, UK.
[75]
Nutan Limaye, Srikanth Srinivasan, and Sébastien Tavenas. 2021. Superpolynomial lower bounds against low-depth algebraic circuits. Electronic Colloquium on Computational Complexity 28 (2021), 81. https://eccc.weizmann.ac.il/report/2021/081.
[76]
Richard J. Lipton and Larry J. Stockmeyer. 1978. Evaluation of polynomials with super-preconditioning. Journal of Computer and System Sciences 16, 2 (1978), 124–139.
[77]
Anand Louis and Santosh Srinivas Vempala. 2016. Accelerated Newton iteration for roots of black box polynomials. In Proceedings of the 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS’16). 732–740.
[78]
Meena Mahajan. 2014. Algebraic complexity classes. In Perspectives in Computational Complexity. Springer, 51–75.
[79]
Meena Mahajan and V. Vinay. 1997. A combinatorial algorithm for the determinant. In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’97). 730–738.
[80]
Ketan Mulmuley. 2017. Geometric complexity theory V: Efficient algorithms for Noether normalization. Journal of the American Mathematical Society 30, 1 (2017), 225–309.
[81]
Ketan D. Mulmuley. 2012. The GCT program toward the P vs. NP problem. Communications of the ACM 55, 6 (June 2012), 98–107.
[82]
Ketan D. Mulmuley. 2012. Geometric complexity theory V: Equivalence between blackbox derandomization of polynomial identity testing and derandomization of Noether’s normalization lemma. In Proceedings of the 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS’12). 629–638.
[83]
Vincent Neiger, Johan Rosenkilde, and Éric Schost. 2017. Fast computation of the roots of polynomials over the ring of power series. In Proceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation. 349–356.
[84]
Isaac Newton. 1669. De Analysi per aequationes numero terminorum infinitas [On analysis by infinite series] (in Latin). Published in 1711 by William Jones.
[85]
Rafael Oliveira. 2016. Factors of low individual degree polynomials. Computational Complexity 2, 25 (2016), 507–561.
[86]
Oystein Ore. 1922. Über höhere kongruenzen. Norsk Matematisk Forenings Skrifter 1, 7 (1922), 15.
[87]
Anurag Pandey, Nitin Saxena, and Amit Sinhababu. 2016. Algebraic independence over positive characteristic: New criterion and applications to locally low algebraic rank circuits. In Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS’16). Article 74, 15 pages.
[88]
Sebastian Pauli. 2001. Factoring polynomials over local fields. Journal of Symbolic Computation 32, 5 (2001), 533–547.
[89]
David Alan Plaisted. 1977. Sparse complex polynomials and polynomial reducibility. Journal of Computer and System Sciences 14, 2 (1977), 210–221.
[90]
Ramprasad Saptharishi. 2019. A Survey of Lower Bounds in Arithmetic Circuit Complexity. Retrieved March 2, 2022 from https://github.com/dasarpmar/lowerbounds-survey/releases.
[91]
Tateaki Sasaki and Mutsuko Sasaki. 1993. A unified method for multivariate polynomial factorizations. Japan Journal of Industrial and Applied Mathematics 10, 1 (1993), 21–39.
[92]
Claus-Peter Schnorr. 1977. Improved lower bounds on the number of multiplications/divisions which are necessary to evaluate polynomials. In Proceedings of the International Symposium on Mathematical Foundations of Computer Science (MFCS’77). 135–147.
[93]
Arnold Schönhage. 1982. The fundamental theorem of algebra in terms of computational complexity. Manuscript. University of Tübingen, Germany.
[94]
J. T. Schwartz. 1980. Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM 27, 4 (Oct. 1980), 701–717.
[95]
Amir Shpilka and Amir Yehudayoff. 2010. Arithmetic circuits: A survey of recent results and open questions. Foundations and Trends® in Theoretical Computer Science 5, 3–4 (2010), 207–388.
[96]
Gaurav Sinha. 2016. Reconstruction of real depth-3 circuits with top fan-in 2. In Proceedings of the 31st Conference on Computational Complexity (CCC’16).
[97]
Amit Sinhababu and Thomas Thierauf. 2020. Factorization of polynomials given by arithmetic branching programs. In Proceedings of the 35th Conference on Computational Complexity (CCC’20). https://eccc.weizmann.ac.il/report/2020/077/.
[98]
Volker Strassen. 1973. Vermeidung von divisionen. Journal für Die Reine Und Angewandte Mathematik 264 (1973), 184–202.
[99]
Madhu Sudan. 1997. Decoding of Reed Solomon codes beyond the error-correction bound. Journal of Complexity 13, 1 (1997), 180–193.
[100]
Brook Taylor. 1715. Methodus incrementorum directa et inversa [Direct and reverse methods of incrementation] (in Latin). Translated into English in Struik, D. J. 1969. A Source Book in Mathematics 1200–1800. Harvard University Press, Cambridge, MA, 329–332.
[101]
Leslie G. Valiant. 1979. Completeness classes in algebra. In Proceedings of the 11th Annual ACM Symposium on Theory of Computing (STOC’79). 249–261.
[102]
Leslie G. Valiant, Sven Skyum, Stuart Berkowitz, and Charles Rackoff. 1983. Fast parallel computation of polynomials using few processors. SIAM Journal on Computing 12, 4 (1983), 641–644.
[103]
Ming Li and Paul M. B. Vitanyi. 1997. An Introduction to Kolmogorov Complexity and Its Applications. Texts in Computer Science. Springer.
[104]
Joachim von zur Gathen. 1984. Hensel and Newton methods in valuation rings. Mathematics and Computation 42, 166 (1984), 637–661.
[105]
Joachim von zur Gathen and Jürgen Gerhard. 2013. Modern Computer Algebra. Cambridge University Press.
[106]
Joachim von zur Gathen and Silke Hartlieb. 1996. Factorization of Polynomials Modulo Small Prime Powers. Univ.-Gesamthochsch.-Paderborn, Fachbereich Mathematik-Informatik.
[107]
Joachim von zur Gathen and Erich Kaltofen. 1985. Factoring sparse multivariate polynomials. Journal of Computer and System Sciences 31, 2 (1985), 265–287.
[108]
Wikipedia. n.d. Cauchy Matrix. Retrieved March 2, 2022 from https://en.wikipedia.org/wiki/Cauchy_matrix.
[109]
Oscar Zariski and Pierre Samuel. 1975. Commutative Algebra: Volume II. Graduate Texts in Mathematics, Vol. 29. Springer.
[110]
Richard Zippel. 1979. Probabilistic algorithms for sparse polynomials. In Proceedings of the International Symposium on Symbolic and Algebraic Computation (EUROSAM’79). 216–226.
[111]
Hans Zassenhaus. 1969. On Hensel factorization, I. Journal of Number Theory. Elsevier, 1, 3 (1969), 291–311.
Index Terms
- Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring
Recommendations
Discovering the roots: uniform closure results for algebraic classes under factoring
STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of ComputingNewton iteration (NI) is an almost 350 years old recursive formula that approximates a simple root of a polynomial quite rapidly. We generalize it to a matrix recurrence (allRootsNI) that approximates all the roots simultaneously. In this form, the ...
Bootstrapping variables in algebraic circuits
STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of ComputingWe 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 only need to consider size-s degree-s circuits that depend on the first log∘ c s variables (...
Arithmetic Circuits: A Chasm at Depth Three
FOCS '13: Proceedings of the 2013 IEEE 54th Annual Symposium on Foundations of Computer ScienceWe show that, over Q, if an n-variate polynomial of degree d = nO(1) is computable by an arithmetic circuit of size s (respectively by an arithmetic branching program of size s) then it can also be computed by a depth three circuit (i.e. a Sigma Pi ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 2022
199 pages
ISSN:0004-5411
EISSN:1557-735X
DOI:10.1145/3543540
- Editor:
- Venkatesan Guruswami
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].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 11 June 2022
Online AM: 23 February 2022
Accepted: 01 December 2021
Revised: 01 July 2021
Received: 01 April 2019
Published in JACM Volume 69, Issue 3
Check for updates
Author Tags
Qualifiers
- Research-article
- Refereed
Funding Sources
- Google India Research Program Team
- Microsoft Research Lab India, IARCS, and ACM India
- MHRD (Government of India)
- DFG
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 490Total Downloads
- Downloads (Last 12 months)74
- Downloads (Last 6 weeks)10
Reflects downloads up to 10 Dec 2024
Other Metrics
Citations
Cited By
View all- Harsha PKumar MSaptharishi RSudan M(2024)An Improved Line-Point Low-Degree Test*2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00113(1883-1892)Online publication date: 27-Oct-2024
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign inFull Access
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderFull Text
View this article in Full Text.
Full TextHTML Format
View this article in HTML Format.
HTML Format