Interpolation of depth-3 arithmetic circuits with two multiplication gates

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Interpolation of depth-3 arithmetic circuits with two multiplication gates

Full text

Pdf (349 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-ninth annual ACM symposium on Theory of computing table of contents

San Diego, California, USA

SESSION: Session 6B table of contents

Pages: 284 - 293

Year of Publication: 2007

ISBN:978-1-59593-631-8

Author

Amir Shpilka

Technion, Haifa, Israel

Sponsors

ACM: Association for Computing Machinery
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 30, Citation Count: 2

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1250790.1250833 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Amos Beimel , Francesco Bergadano , Nader H. Bshouty , Eyal Kushilevitz , Stefano Varricchio, Learning functions represented as multiplicity automata, Journal of the ACM (JACM), v.47 n.3, p.506-530, May 2000 [doi>10.1145/337244.337257]
	2	Michael Ben-Or, A deterministic algorithm for sparse multivariate polynomial interpolation, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.301-309, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62241]
	3	Francesco Bergadano , Nader H. Bshouty , Christino Tamon , Stefano Varricchio, On Learning Programs and Small Depth Circuits, Proceedings of the Third European Conference on Computational Learning Theory, p.150-161, March 17-19, 1997
	4	[4] F. Bergadano, N. H. Bshouty, and S. Varricchio. Learning multivariate polynomials from substitution and equivalence queries. ECCC, 3(8), 1996.
	5	Daoud Bshouty , Nader H. Bshouty, On interpolating arithmetic read-once formulas with exponentiation, Journal of Computer and System Sciences, v.56 n.1, p.112-124, Feb. 1998 [doi>10.1006/jcss.1997.1550]
	6	Nader H. Bshouty , Richard Cleve, Interpolating Arithmetic Read-Once Formulas in Parallel, SIAM Journal on Computing, v.27 n.2, p.401-413, April 1998 [doi>10.1137/S009753979528812X]
	7	Nader H. Bshouty , Thomas R. Hancock , Lisa Hellerstein, Learning Arithmetic Read-Once Formulas, SIAM Journal on Computing, v.24 n.4, p.706-735, Aug. 1995 [doi>10.1137/S009753979223664X]
	8	Zeev Dvir , Amir Shpilka, Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060678]
	9	Oded Goldreich , Shafi Goldwasser , Silvio Micali, How to construct random functions, Journal of the ACM (JACM), v.33 n.4, p.792-807, Oct. 1986 [doi>10.1145/6490.6503]
	10	Oded Goldreich , Howard Karloff , Leonard J. Schulman , Luca Trevisan, Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval, Proceedings of the 17th IEEE Annual Conference on Computational Complexity, p.175, May 21-24, 2002
	11	Dima Grigoriev , Marek Karpinski , Michael F. Singer, Computational Complexity of Sparse Rational Interpolation, SIAM Journal on Computing, v.23 n.1, p.1-12, Feb. 1994 [doi>10.1137/S0097539791194069]
	12	Thomas Hancock , Lisa Hellerstein, Learning read-once formulas over fields and extended bases, Proceedings of the fourth annual workshop on Computational learning theory, p.326-336, August 05-07, 1991, Santa Cruz, California, United States
	13	[13] E. Kaltofen. Polynomial-time reductions from multivariate to bi- and univariate integral polynomial factorization. SICOMP, 14(2):469-489, 1985.
	14	Erich Kaltofen, Effective Noether irreducibility forms and applications, Journal of Computer and System Sciences, v.50 n.2, p.274-295, April 1995
	15	Erich Kaltofen , Barry M. Trager, Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators, Journal of Symbolic Computation, v.9 n.3, p.301-320, March 1990 [doi>10.1016/S0747-7171(08)80015-6]
	16	Marek Karpinski , Igor Shparlinski, On some approximation problems concerning sparse polynomials over finite fields, Theoretical Computer Science, v.157 n.2, p.259-266, May 5, 1996 [doi>10.1016/0304-3975(95)00162-X]
	17	Jonathan Katz , Luca Trevisan, On the efficiency of local decoding procedures for error-correcting codes, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.80-86, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335315]
	18	Michael Kearns , Leslie Valiant, Cryptographic limitations on learning Boolean formulae and finite automata, Journal of the ACM (JACM), v.41 n.1, p.67-95, Jan. 1994 [doi>10.1145/174644.174647]
	19	Michael Kharitonov, Cryptographic lower bounds for learnability of Boolean functions on the uniform distribution, Journal of Computer and System Sciences, v.50 n.3, p.600-610, June 1995 [doi>10.1006/jcss.1995.1046]
	20	[20] A. Klivans and A. Shpilka. Learning restricted models of arithmetic circuits. Theory of Computing, 2(10):185-206, 2006.
	21	Adam R. Klivans , Daniel Spielman, Randomness efficient identity testing of multivariate polynomials, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.216-223, July 2001, Hersonissos, Greece [doi>10.1145/380752.380801]
	22	Matthias Krause , Stefan Lucks, Pseudorandom functions in TC⁰ and cryptographic limitations to proving lower bounds, Computational Complexity, v.10 n.4, p.297-313, May 2002 [doi>10.1007/s000370100002]
	23	Yishay Mansour, Randomized Interpolation and Approximationof Sparse Polynomials, SIAM Journal on Computing, v.24 n.2, p.357-368, April 1995 [doi>10.1137/S0097539792239291]
	24	Moni Naor , Omer Reingold, Number-theoretic constructions of efficient pseudo-random functions, Journal of the ACM (JACM), v.51 n.2, p.231-262, March 2004 [doi>10.1145/972639.972643]
	25	Alexander A. Razborov , Steven Rudich, Natural proofs, Journal of Computer and System Sciences, v.55 n.1, p.24-35, Aug. 1997 [doi>10.1006/jcss.1997.1494]
	26	Robert E. Schapire , Linda M. Sellie, Learning sparse multivariate polynomials over a field with queries and counterexamples, Journal of Computer and System Sciences, v.52 n.2, p.201-213, April 1996 [doi>10.1006/jcss.1996.0017]
	27	Amir Shpilka , Avi Wigderson, Depth-3 arithmetic circuits over fields of characteristic zero, Computational Complexity, v.10 n.1, p.1-27, 2001 [doi>10.1007/PL00001609]

CITED BY 2

	Amir Shpilka , Ilya Volkovich, Read-once polynomial identity testing, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Markus Bläser , Moritz Hardt , Richard J. Lipton , Nisheeth K. Vishnoi, Deterministically testing sparse polynomial identities of unbounded degree, Information Processing Letters, v.109 n.3, p.187-192, January, 2009

INDEX TERMS

General Terms:
Algorithms

Keywords:
arithmetic circuits, depth-3, exact learning, interpolation

Collaborative Colleagues:

Amir Shpilka: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player