Constant depth circuits, Fourier transform, and learnability

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Constant depth circuits, Fourier transform, and learnability

Full text

Pdf (824 KB)

Source

Journal of the ACM (JACM) archive
Volume 40 , Issue 3 (July 1993) table of contents

Pages: 607 - 620

Year of Publication: 1993

ISSN:0004-5411

Authors

Nathan Linial	Hebrew University, Jerusalem,Israel
Yishay Mansour	Tel-Aviv University, Tel-Aviv, Israel
Noam Nisan	Hebrew University, Jerusalem, Israel

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 166, Citation Count: 56

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/174130.174138 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	~ AJTAI, M. E~l-formulae on finite structure. Ann. Pure Appl. Logic 24 (1983), 1-48.
	2	~AJTAI, M., AND WIGDERSON, A. Deterministic simulation of probabilistic constant depth ~circuits. In Aduances in computing research, Vol. 5. S. Micali, ed. JAI Press, Greenwich, Ct., ~1989, pp. 199-222.
	3	Y. Brandman , A. Orlitsky , J. Hennessy, A Spectral Lower Bound Technique for the Size of Decision Trees and Two-Level AND/OR Circuits, IEEE Transactions on Computers, v.39 n.2, p.282-287, February 1990 [doi>10.1109/12.45216]
	4	~DYM, H., AND MCKEAN, H.P. Fourier Series and httegrals. Academic Press, Orlando, Fla., ~1972.
	5	~FURST, M., SAXE, J., AND SIPSER, M. Parity, circuits, and the polynomial-time hierarchy. ~Math. Syst. Theory 17 (1984), 13-27.
	6	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]
	7	Torben Hagerup , C. Rüb, A guided tour of Chernoff bounds, Information Processing Letters, v.33 n.6, p.305-308, February 1990 [doi>10.1016/0020-0190(90)90214-I]
	8	Johan Håstad, Computational limitations of small-depth circuits, MIT Press, Cambridge, MA, 1987
	9	~KAHN, J., KALAI, G., AND LINIAL, N. The influence of variables on Boolean functions. In ~Proceedings of the 29th Annual Symposium on Foundations of Computer Science (White Plains, ~N.Y., Oct.). IEEE, New York, 1988, pp. 68-80.
	10	M. Kearns , L. G. Valiant, Crytographic limitations on learning Boolean formulae and finite automata, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.433-444, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73049]
	11	N. Linial , N. Nisan, Approximate inclusion-exclusion, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.260-270, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100250]
	12	Y. Mansour , N. Nisan , P. Tiwari, The computational complexity of universal hashing, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.235-243, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100246]
	13	~NISAN, N., AND WIGDERSON, m. Hardness vs. randomness. In Proceedings of the 29th Annual ~Symposium on Foundations of Computer Science (White Plains, N.Y., Oct.) IEEE, New York, ~1988, pp. 2-12.
	14	~RAZBOROV, A. A. Lower bounds for the size of circuits of bounded depth with basis ~AND, XOR. Math. Zametskz 41 (1987), 598-607 (in Russian). English translation in Math ~Notes 41 (1987), 333-338.
	15	Ronald L. Rivest, Learning Decision Lists, Machine Learning, v.2 n.3, p.229-246, November 1987 [doi>10.1023/A:1022607331053]
	16	Miklos Santha , Christopher Wilson, Polynomial size constant depth circuits with a limited number of negations, Proceedings of the 8th annual symposium on Theoretical aspects of computer science, p.228-237, February 1991, Hamburg, Germany
	17	R. Smolensky, Algebraic methods in the theory of lower bounds for Boolean circuit complexity, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.77-82, January 1987, New York, New York, United States [doi>10.1145/28395.28404]
	18	L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]
	19	~YAO, A.C. Theory and applications of trapdoor functions. In Proceedings of the 23rd A~mual ~Symposium on Foundatzons of Computer Science. IEEE, New York, 1982, pp. 80-91.
	20	Andrew C-C. Yao, Separating the polynomial-time hierarchy by oracles, Proc. 26th annual symposium on Foundations of computer science, p.1-10, October 1985, Portland, Oregon, United States

CITED BY 56

	Nader H. Bshouty , Christino Tamon, On the Fourier spectrum of monotone functions, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.219-228, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Anna Bernasconi , Carsten Damm , Igor Shparlinski, Circuit and decision tree complexity of some number theoretic problems, Information and Computation, v.168 n.2, p.113-124, Aug. 1, 2001
	Ryan O'Donnell, Hardness amplification within NP, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Jeffrey C. Jackson , Adam R. Klivans , Rocco A. Servedio, Learnability beyond AC⁰, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Nader H. Bshouty , Jeffrey C. Jackson , Christino Tamon, Uniform-distribution attribute noise learnability, Proceedings of the twelfth annual conference on Computational learning theory, p.75-80, July 07-09, 1999, Santa Cruz, California, United States
	Anna Gál , Adi Rosén, A theorem on sensitivity and applications in private computation, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.348-357, May 01-04, 1999, Atlanta, Georgia, United States
	Elchanan Mossel , Ryan O'Donnell , Rocco P. Servedio, Learning juntas, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Hillol Kargupta , Byung-Hoon Park , Sweta Pittie , Lei Liu , Deepali Kushraj , Kakali Sarkar, MobiMine: monitoring the stock market from a PDA, ACM SIGKDD Explorations Newsletter, v.3 n.2, January 2002
	William Evans , Nicholas Pippenger, Lower bounds for noisy Boolean decision trees, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.620-628, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Nader H. Bshouty , Christino Tamon, On the Fourier spectrum of monotone functions, Journal of the ACM (JACM), v.43 n.4, p.747-770, July 1996
	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
	Ryan O'Donnell , Rocco A. Servedio, New degree bounds for polynomial threshold functions, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Hillol Kargupta , Byung-Hoon Park, A Fourier Spectrum-Based Approach to Represent Decision Trees for Mining Data Streams in Mobile Environments, IEEE Transactions on Knowledge and Data Engineering, v.16 n.2, p.216-229, February 2004
	Nader H. Bshouty , Jeffrey C. Jackson , Christino Tamon, Uniform-distribution attribute noise learnability, Information and Computation, v.187 n.2, p.277-290, 15 December 2003
	Valentine Kabanets , Russell Impagliazzo, Derandomizing polynomial identity tests means proving circuit lower bounds, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Anna Bernasconi , Bruno Codenotti, Spectral Analysis of Boolean Functions as a Graph Eigenvalue Problem, IEEE Transactions on Computers, v.48 n.3, p.345-351, March 1999
	Tanja Lange , Arne Winterhof, Interpolation of the discrete logarithm in Fq by Boolean functions and by polynomials in several variables modulo a divisor of q - 1, Discrete Applied Mathematics, v.128 n.1, p.193-206, 15 May 2003
	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
	Katarzyna Radecka , Zeljko Zilic, Design Verification by Test Vectors and Arithmetic Transform Universal Test Set, IEEE Transactions on Computers, v.53 n.5, p.628-640, May 2004
	Lane A. Hemaspaandra, SIGACT News complexity theory column 32, ACM SIGACT News, v.32 n.2, June 2001
	Elchanan Mossel , Ryan O'Donnell , Rocco A. Servedio, Learning functions of k relevant variables, Journal of Computer and System Sciences, v.69 n.3, p.421-434, November 2004
	Eric Allender , Anna Bernasconi , Carsten Damm , Joachim von Zur Gathen , Michael Saks , Igor Shparlinski, Complexity of some arithmetic problems for binary polynomials, Computational Complexity, v.12 n.1/2, p.23-25, July 2004
	Ryan O'Donnell, Hardness amplification within NP, Journal of Computer and System Sciences, v.69 n.1, p.68-94, August 2004
	Rocco A. Servedio, On learning monotone DNF under product distributions, Information and Computation, v.193 n.1, p.57-74, 25 August 2004
	Adam R. Klivans , Ryan O'Donnell , Rocco A. Servedio, Learning intersections and thresholds of halfspaces, Journal of Computer and System Sciences, v.68 n.4, p.808-840, June 2004
	Elchanan Mossel , Ryan O'Donnell, On the noise sensitivity of monotone functions, Random Structures & Algorithms, v.23 n.3, p.333-350, October 2003
	Lisa Hellerstein , Vijay Raghavan, Exact learning of DNF formulas using DNF hypotheses, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Hoeteck Wee, On obfuscating point functions, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Ronitt Rubinfeld , Rocco A. Servedio, Testing monotone high-dimensional distributions, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Nader H. Bshouty , Elchanan Mossel , Ryan O'Donnell , Rocco A. Servedio, Learning DNF from random walks, Journal of Computer and System Sciences, v.71 n.3, p.250-265, October 2005
	Lisa Hellerstein , Vijay Raghavan, Exact learning of DNF formulas using DNF hypotheses, Journal of Computer and System Sciences, v.70 n.4, p.435-470, June 2005
	Valentine Kabanets , Russell Impagliazzo, Derandomizing polynomial identity tests means proving circuit lower bounds, Computational Complexity, v.13 n.1/2, p.1-46, January 2004
	Adam Drake , Dan Ventura, A practical generalization of Fourier-based learning, Proceedings of the 22nd international conference on Machine learning, p.185-192, August 07-11, 2005, Bonn, Germany
	Nader H. Bshouty , Jeffrey C. Jackson , Christino Tamon, Exploring learnability between exact and PAC, Journal of Computer and System Sciences, v.70 n.4, p.471-484, June 2005
	Matthias Krause, On the computational power of Boolean decision lists, Computational Complexity, v.14 n.4, p.362-375, March 2006
	Bella Dubrov , Yuval Ishai, On the randomness complexity of efficient sampling, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	A. C. Gilbert , S. Guha , P. Indyk , S. Muthukrishnan , M. Strauss, Near-optimal sparse fourier representations via sampling, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Dana Angluin , James Aspnes , Jiang Chen , Yinghua Wu, Learning a circuit by injecting values, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Parikshit Gopalan , Adam Tauman Kalai , Adam R. Klivans, Agnostically learning decision trees, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Avrim Blum , Merrick Furst , Jeffrey Jackson , Michael Kearns , Yishay Mansour , Steven Rudich, Weakly learning DNF and characterizing statistical query learning using Fourier analysis, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.253-262, May 23-25, 1994, Montreal, Quebec, Canada
	Igor E. Shparlinski, Bounds on the Fourier coefficients of the weighted sum function, Information Processing Letters, v.103 n.3, p.83-87, July, 2007
	Ariel Elbaz , Homin K. Lee , Rocco A. Servedio , Andrew Wan, Separating Models of Learning from Correlated and Uncorrelated Data, The Journal of Machine Learning Research, 8, p.277-290, 5/1/2007
	Andreas Birkendorf , Eli Dichterman , Jeffrey Jackson , Norbert Klasner , Hans Ulrich Simon, On Restricted-Focus-of-Attention Learnability of Boolean Functions, Machine Learning, v.30 n.1, p.89-123, Jan. 1998
	Yishay Mansour , Sigal Sahar, Implementation Issues in the Fourier Transform Algorithm, Machine Learning, v.40 n.1, p.5-33, July 2000
	Jeffrey Jackson, On the Efficiency of Noise-Tolerant PAC Algorithms Derived from Statistical Queries, Annals of Mathematics and Artificial Intelligence, v.39 n.3, p.291-313, November 2003
	Mahya Ghandehari , Hamed Hatami, Fourier analysis and large independent sets in powers of complete graphs, Journal of Combinatorial Theory Series B, v.98 n.1, p.164-172, January, 2008
	Hillol Kargupta , Byung-Hoon Park , Haimonti Dutta, Orthogonal Decision Trees, IEEE Transactions on Knowledge and Data Engineering, v.18 n.8, p.1028-1042, August 2006
	Dana Angluin , James Aspnes , Jiang Chen , Lev Reyzin, Learning large-alphabet and analog circuits with value injection queries, Machine Learning, v.72 n.1-2, p.113-138, August 2008
	Shafi Goldwasser , Yael Tauman Kalai , Guy N. Rothblum, Delegating computation: interactive proofs for muggles, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Christopher Ré , Dan Suciu, Approximate lineage for probabilistic databases, Proceedings of the VLDB Endowment, v.1 n.1, August 2008
	Dana Angluin , James Aspnes , Jiang Chen , Yinghua Wu, Learning a circuit by injecting values, Journal of Computer and System Sciences, v.75 n.1, p.60-77, January, 2009
	Lance Fortnow , Adam R. Klivans, Efficient learning algorithms yield circuit lower bounds, Journal of Computer and System Sciences, v.75 n.1, p.27-36, January, 2009
	Alexander Razborov, A Simple Proof of Bazzi’s Theorem, ACM Transactions on Computation Theory (TOCT), v.1 n.1, p.1-5, February 2009
	Hamed Hatami, Decision trees and influences of variables over product probability spaces, Combinatorics, Probability and Computing, v.18 n.3, p.357-369, May 2009
	Hiroshi Tsukimoto, Extracting propositions from trained neural networks, Proceedings of the Fifteenth international joint conference on Artifical intelligence, p.1098-1105, August 23-29, 1997, Nagoya, Japan
	Vitaly Feldman, On The Power of Membership Queries in Agnostic Learning, The Journal of Machine Learning Research, 10, p.163-182, June 2009