Article

Interpolation of depth-3 arithmetic circuits with two multiplication gates

Author:

Amir ShpilkaAuthors Info & Claims

STOC '07: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing

Pages 284 - 293

https://doi.org/10.1145/1250790.1250833

Published: 11 June 2007 Publication History

Get Access

References

[1]

{1} A. Beimel, F. Bergadano, N. H. Bshouty, E. Kushilevitz, and S. Varricchio. Learning functions represented as multiplicity automata. J. ACM, 47(3):506-530, 2000.

Digital Library

Google Scholar

[2]

{2} M. Ben-Or and P. Tiwari. A deterministic algorithm for sparse multivariate polynominal interpolation (extended abstract). In 20th STOC, pages 301-309, 1988.

Digital Library

Google Scholar

[3]

{3} F. Bergadano, N. H. Bshouty, C. Tamon, and S. Varricchio. On learning branching programs and small depth circuits. In 3rd EuroCOLT, volume 1208 of LNCS, pages 150-161, 1997.

Digital Library

Google Scholar

[4]

{4} F. Bergadano, N. H. Bshouty, and S. Varricchio. Learning multivariate polynomials from substitution and equivalence queries. ECCC, 3(8), 1996.

Google Scholar

[5]

{5} D. Bshouty and N. H. Bshouty. On interpolating arithmetic read-once formulas with exponentiation. JCSS, 56(1):112-124, 1998.

Digital Library

Google Scholar

[6]

{6} N. H. Bshouty and R. Cleve. Interpolating arithmetic read-once formulas in parallel. SICOMP, 27(2):401-413, 1998.

Digital Library

Google Scholar

[7]

{7} N. H. Bshouty, T. R. Hancock, and L. Hellerstein. Learning arithmetic read-once formulas. SICOMP, 24(4):706-735, 1995.

Digital Library

Google Scholar

[8]

{8} Z. Dvir and A. Shpilka. Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits. In 37th STOC, pages 592-601, 2005.

Digital Library

Google Scholar

[9]

{9} O. Goldreich, S. Goldwasser, and S. Micali. How to construct random functions. J. ACM, 33(4):792-807, 1986.

Digital Library

Google Scholar

[10]

{10} O. Goldreich, H. J. Karloff, L. J. Schulman, and L. Trevisan. Lower bounds for linear locally decodable codes and private information retrieval. In 17th CCC, pages 175-183, 2002.

Digital Library

Google Scholar

[11]

{11} D. Grigoriev, M. Karpinski, and M. F. Singer. Computational complexity of sparse rational interpolation. SICOMP, 23(1):1-11, 1994.

Digital Library

Google Scholar

[12]

{12} T. R. Hancock and L. Hellerstein. Learning read-once formulas over fields and extended bases. In 4th COLT, pages 326-336, 1991.

Digital Library

Google Scholar

[13]

{13} E. Kaltofen. Polynomial-time reductions from multivariate to bi- and univariate integral polynomial factorization. SICOMP, 14(2):469-489, 1985.

Crossref

Google Scholar

[14]

{14} E. Kaltofen. Effective Noether irreducibility forms and applications. JCSS, 50(2):274-295, 1995.

Digital Library

Google Scholar

[15]

{15} E. Kaltofen and B. M. Trager. Computing with polynomials given by black boxes for their evaluations: Greatest common divisors, factorization, separation of numerators and denominators. J. of Symbolic Comp., 9(3):300-320, 1990.

Digital Library

Google Scholar

[16]

{16} M. Karpinski and I. Shparlinski. On some approximation problems concerning sparse polynomials over finite fields. TCS, 157(2):259-266, 1996.

Digital Library

Google Scholar

[17]

{17} J. Katz and L. Trevisan. On the efficiency of local decoding procedures for error-correcting codes. In 32nd STOC, pages 80-86, 2000.

Digital Library

Google Scholar

[18]

{18} M. J. Kearns and L. G. Valiant. Cryptographic limitations on learning boolean formulae and finite automata. J. ACM, 41(1):67-95, 1994.

Digital Library

Google Scholar

[19]

{19} M. Kharitonov. Cryptographic lower bounds for learnability of boolean functions on the uniform distribution. JCSS, 50(3):600-610, 1995.

Digital Library

Google Scholar

[20]

{20} A. Klivans and A. Shpilka. Learning restricted models of arithmetic circuits. Theory of Computing, 2(10):185-206, 2006.

Crossref

Google Scholar

[21]

{21} A. R. Klivans and D. Spielman. Randomness efficient identity testing of multivariate polynomials. In 33rd STOC, pages 216-223. ACM Press, 2001.

Digital Library

Google Scholar

[22]

{22} M. Krause and S. Lucks. Pseudorandom functions in TC0 and cryptographic limitations to proving lower bounds. Computational Complexity, 10(4):297-313, 2001.

Digital Library

Google Scholar

[23]

{23} Y. Mansour. Randomized interpolation and approximation of sparse polynomials. SICOMP, 24(2):357-368, 1995.

Digital Library

Google Scholar

[24]

{24} M. Naor and O. Reingold. Number-theoretic constructions of efficient pseudo-random functions. J. ACM, 51(2):231-262, 2004.

Digital Library

Google Scholar

[25]

{25} A. A. Razborov and S. Rudich. Natural proofs. JCSS., 55(1):24-35, 1997.

Digital Library

Google Scholar

[26]

{26} R. E. Schapire and L. M. Sellie. Learning sparse multivariate polynomials over a field with queries and counterexamples. JCSS, 52(2):201-213, 1996.

Digital Library

Google Scholar

[27]

{27} A. Shpilka and A. Wigderson. Depth-3 arithmetic circuits over fields of characteristic zero. Computational Complexity, 10(1):1-27, 2001.

Digital Library

Google Scholar

Cited By

View all

Zeron EDe Loera J(2024)Computing the Degree of Black-Box Polynomials, with ApplicationsHandbook of Visual, Experimental and Computational Mathematics10.1007/978-3-030-93954-0_54-1(1-16)Online publication date: 1-Jun-2024
https://doi.org/10.1007/978-3-030-93954-0_54-1
Garg AKayal NSaha C(2020)Learning sums of powers of low-degree polynomials in the non-degenerate case2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS46700.2020.00087(889-899)Online publication date: Nov-2020
https://doi.org/10.1109/FOCS46700.2020.00087
Kayal NSaha CCharikar MCohen E(2019)Reconstruction of non-degenerate homogeneous depth three circuitsProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing10.1145/3313276.3316360(413-424)Online publication date: 23-Jun-2019
https://dl.acm.org/doi/10.1145/3313276.3316360
Show More Cited By

Interpolation of depth-3 arithmetic circuits with two multiplication gates
1. Theory of computation

Recommendations

Interpolation of Depth-3 Arithmetic Circuits with Two Multiplication Gates

In this paper we consider the problem of constructing a small arithmetic circuit for a polynomial for which we have oracle access. Our focus is on $n$-variate polynomials, over a finite field $\mathbb{F}$, that have depth-3 arithmetic circuits (with an ...
Reconstruction of Generalized Depth-3 Arithmetic Circuits with Bounded Top Fan-in
CCC '09: Proceedings of the 2009 24th Annual IEEE Conference on Computational Complexity

In this paper we give reconstruction algorithms for depth-3 arithmetic circuits with $k$ multiplication gates (also known as $\Sigma\Pi\Sigma(k)$ circuits), where $k=O(1)$. Namely, we give an algorithm that when given a black box holding a $\Sigma\Pi\...
Design of Arithmetic Circuits Using Reversible Logic Gates and Power Dissipation Calculation
ISED '10: Proceedings of the 2010 International Symposium on Electronic System Design

In the recent years, reversible logic has emerged as a promising technology having its applications in low power CMOS, quantum computing, nano technology and optical computing. Reversible logic circuits provide less power dissipation as well as distinct ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '07: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing

June 2007

734 pages

ISBN:9781595936318

DOI:10.1145/1250790

General Chair:
David Johnson
AT&T Labs - Research
,
Program Chair:
Uriel Feige
Microsoft Research and Weizmann Institute

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 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

STOC07

Sponsor:

STOC07: Symposium on Theory of Computing

June 11 - 13, 2007

California, San Diego, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
217
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Zeron EDe Loera J(2024)Computing the Degree of Black-Box Polynomials, with ApplicationsHandbook of Visual, Experimental and Computational Mathematics10.1007/978-3-030-93954-0_54-1(1-16)Online publication date: 1-Jun-2024
https://doi.org/10.1007/978-3-030-93954-0_54-1
Garg AKayal NSaha C(2020)Learning sums of powers of low-degree polynomials in the non-degenerate case2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS46700.2020.00087(889-899)Online publication date: Nov-2020
https://doi.org/10.1109/FOCS46700.2020.00087
Kayal NSaha CCharikar MCohen E(2019)Reconstruction of non-degenerate homogeneous depth three circuitsProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing10.1145/3313276.3316360(413-424)Online publication date: 23-Jun-2019
https://dl.acm.org/doi/10.1145/3313276.3316360
Kayal NNair VSaha CTavenas S(2018)Reconstruction of Full Rank Algebraic Branching ProgramsACM Transactions on Computation Theory10.1145/328242711:1(1-56)Online publication date: 21-Nov-2018
https://dl.acm.org/doi/10.1145/3282427
Kayal NNair VSaha CTavenas S(2017)Reconstruction of full rank algebraic branching programsProceedings of the 32nd Computational Complexity Conference10.5555/3135595.3135616(1-61)Online publication date: 9-Jul-2017
https://dl.acm.org/doi/10.5555/3135595.3135616
Sinha G(2016)Reconstruction of real depth-3 circuits with top fan-in 2Proceedings of the 31st Conference on Computational Complexity10.5555/2982445.2982476(1-53)Online publication date: 29-May-2016
https://dl.acm.org/doi/10.5555/2982445.2982476
Gupta AKayal NQiao Y(2013)Random Arithmetic Formulas Can Be Reconstructed Efficiently2013 IEEE Conference on Computational Complexity10.1109/CCC.2013.10(1-9)Online publication date: Jun-2013
https://doi.org/10.1109/CCC.2013.10
Kayal NKarloff HPitassi T(2012)Affine projections of polynomialsProceedings of the forty-fourth annual ACM symposium on Theory of computing10.1145/2213977.2214036(643-662)Online publication date: 19-May-2012
https://dl.acm.org/doi/10.1145/2213977.2214036
Kayal NSaraf S(2009)Blackbox Polynomial Identity Testing for Depth 3 CircuitsProceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer Science10.1109/FOCS.2009.67(198-207)Online publication date: 25-Oct-2009
https://dl.acm.org/doi/10.1109/FOCS.2009.67
Bläser MHardt MLipton RVishnoi N(2009)Deterministically testing sparse polynomial identities of unbounded degreeInformation Processing Letters10.1016/j.ipl.2008.09.029109:3(187-192)Online publication date: 1-Jan-2009
https://dl.acm.org/doi/10.1016/j.ipl.2008.09.029
Show More Cited By

View Options

Login options

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

Cited By

Recommendations

Interpolation of Depth-3 Arithmetic Circuits with Two Multiplication Gates

Reconstruction of Generalized Depth-3 Arithmetic Circuits with Bounded Top Fan-in

Design of Arithmetic Circuits Using Reversible Logic Gates and Power Dissipation Calculation