The expressive power of voting polynomials

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

The expressive power of voting polynomials

Full text

Pdf (805 KB)

Source

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

New Orleans, Louisiana, United States

Pages: 402 - 409

Year of Publication: 1991

ISBN:0-89791-397-3

Authors

James Aspnes	Carnegie-Mellon Univ., Pittsburgh, PA
Richard Beigel	Yale Univ., New Haven, CT
Merrick Furst	Carnegie-Mellon Univ., Pittsburgh, PA
Steven Rudich	Carnegie-Mellon Univ., Pittsburgh, PA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 34, Citation Count: 10

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/103418.103461 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	Richard Beigel, Relativized counting classes: relations among thresholds, parity, and mods, Journal of Computer and System Sciences, v.42 n.1, p.76-96, Feb. 1991 [doi>10.1016/0022-0000(91)90040-C]
	2	Richard Beigel, Nick Reingold, and Daniel Spielman. The perceptron strikes back. Technical Report YALEU/DCS/TR-813, Yale University, September 1990.
	3	Charles H. Bennett and John Gill. Relative to a random oracle A, pA #: NpA .;/: co_NPA with probability 1. SIAM Journal of Compuging, 10(1):96- 113, February 1981.
	4	Jehoshua Bruck. Harmonic analysis of polynomial threshold functions. SIAM Journal of Discrete Math, 3(2):168-177, May 1990.
	5	Jehoshua Bruck and Roman Smolensky. Polynomial threshold functions, AC~ functions and spectral norms. In Proceedings of the 31,#t Annual Symposium on Foundations of Computer Science, pages 632-641, 1990.
	6	Vagek Chv~tal. Linear Programming. #T.H. Freeman and Company, 1983.
	7	M. Furst, J. Saxe, and M. Sipser. Parity, circuits and the polynomial time hierarchy. Mathematical Systems Theory, 17:13-27, 1984.
	8	Craig Gotsman. On boolean functions, polynomials, and algebraic threshold functions. Unpublished manuscript.
	9	Nathan Linial, Yishay Mansour, and Noa.m Nisan. Constant depth circuits, fourier transform, and learnability. In Proceedings of the 30lh Annual Symposium on Foundations of Computer' Science, pagc# 574-579, 1989.
	10	Marvin L. Minsky and Seymour Papert. Percep- Irons. MIT press, Cambridge, MA, 1085. Expanded Edition. The first edition appeared in 1968.
	11	Ramamohan Paturi and Michael E. Saks. On threshold circuits for parity. In Proceedings of the 31st Annual Symposium on Foundations of Computer Science, pages 397-404, 1990.
	12	A.A. Razborov. Lower bounds for the size of circuits of bounded depth with basis {A,#}. Malh. notes of the Academy of Sciences of the USSR, 41(4):333-338, September 1987.
	13	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]
	14	Erich Stiemke. 0ber positive LSsungen homogener linearer Gleichungen. Mathematische Annalen, 76:340-342, 1915.
	15	Jun Tarui. Randomized polynomials, threshold circuits, and the polynomial hierarchy. Manuscript, August 1990.
	16	L G Valiant , V V Vazirani, NP is as easy as detecting unique solutions, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.458-463, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22196]
	17	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 10

	Adam R. Klivans , Rocco Servedio, Learning DNF in time, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.258-265, July 2001, Hersonissos, Greece
	Noam Nisan , Mario Szegedy, On the degree of Boolean functions as real polynomials, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.462-467, May 04-06, 1992, Victoria, British Columbia, Canada
	Richard Beigel , Nick Reingold , Daniel Spielman, PP is closed under intersection, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.1-9, May 05-08, 1991, New Orleans, Louisiana, United States
	Matthias Krause , Pavel Pudlák, On the computational power of depth 2 circuits with threshold and modulo gates, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.48-57, May 23-25, 1994, Montreal, Quebec, Canada
	Alexander A. Razborov , Steven Rudich, Natural proofs, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.204-213, May 23-25, 1994, Montreal, Quebec, Canada
	Richard Beigel, When do extra majority gates help?, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.450-454, May 04-06, 1992, Victoria, British Columbia, Canada
	Adam R. Klivans , Rocco A. Servedio, Learning DNF in time 2^{õ(n^1/3)}, Journal of Computer and System Sciences, v.68 n.2, p.303-318, March 2004
	Matthias Krause, On the computational power of Boolean decision lists, Computational Complexity, v.14 n.4, p.362-375, March 2006
	Alexander A. Sherstov, Powering requires threshold depth 3, Information Processing Letters, v.102 n.2-3, p.104-107, April, 2007
	Alexander A. Sherstov, Separating AC⁰ from depth-2 majority circuits, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA