{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,12,29]],"date-time":"2024-12-29T05:06:51Z","timestamp":1735448811911,"version":"3.32.0"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1995,6,1]],"date-time":"1995-06-01T00:00:00Z","timestamp":801964800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Comput Complexity"],"published-print":{"date-parts":[[1995,6]]},"DOI":"10.1007\/bf01268144","type":"journal-article","created":{"date-parts":[[2005,3,24]],"date-time":"2005-03-24T03:03:06Z","timestamp":1111633386000},"page":"167-189","source":"Crossref","is-referenced-by-count":1,"title":["Evaluating spectral norms for constant depth circuits with symmetric gates"],"prefix":"10.1007","volume":"5","author":[{"given":"Meera","family":"Sitharam","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","unstructured":"E. Allender, A note on the power of threshold circuits. InProc. 30 th Ann. IEEE Symp. Foundations of Computer Science, 1989, 580?584.","DOI":"10.1109\/SFCS.1989.63538"},{"key":"CR2","doi-asserted-by":"crossref","unstructured":"D. A. Barrington, Bounded width, polynomial size branching programs recognize exactly those languages inNC. InProc. 18 th Ann. ACM Symp. Theory of Computing, 1986, 1?5.","DOI":"10.1145\/12130.12131"},{"key":"CR3","doi-asserted-by":"crossref","unstructured":"R. Beigel, ?Why do extra majority gates help?? InProc. 24 th Ann. ACM Symp. Theory of Computing, 1992, 450?454.","DOI":"10.1145\/129712.129755"},{"key":"CR4","doi-asserted-by":"crossref","unstructured":"D. A. Barrington, R. Beigel, and S. Rudich, Representing Boolean functions as polynomials modulo composite numbers. InProc. 24 th Ann. ACM Symp. Theory of Computing, 1992, 455?461.","DOI":"10.1145\/129712.129756"},{"key":"CR5","doi-asserted-by":"crossref","unstructured":"Y. Brandman, A. Orlitsky, and J. Hennessy, A spectral lower bound technique for the size of decision trees and two-level and-or circuits. InIEEE Transaction on Computers 39:2 (1990), 282?287.","DOI":"10.1109\/12.45216"},{"key":"CR6","doi-asserted-by":"crossref","unstructured":"J. Bruck, Harmonic analysis of polynomial threshold functions. InSIAM Journal of Discrete Mathematics 3:2 (1990), 168?177.","DOI":"10.1137\/0403015"},{"key":"CR7","doi-asserted-by":"crossref","unstructured":"M. Bellare, A technique for upper bounding the spectral norm with applications to learning. InProc. 5 th Ann. IEEE Symp. Computational Learning Theory, 1992, 62?70.","DOI":"10.1145\/130385.130392"},{"key":"CR8","doi-asserted-by":"crossref","unstructured":"R. Boppana and M. Sipser,The complexity of finite functions. Technical Report MIT\/LCS\/TM-405, Massachussetts Institute of Technology, Laboratory for Computer Sciences, 1989.","DOI":"10.1016\/B978-0-444-88071-0.50019-9"},{"issue":"1","key":"CR9","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1137\/0221003","volume":"21","author":"J. Bruck","year":"1992","unstructured":"J. Bruck andR. Smolensky, Polynomial Threshold Functions,AC 0 Functions and Spectral Norms.SIAM Journal of Computing 21:1 (1992), 33?42.","journal-title":"SIAM Journal of Computing"},{"key":"CR10","unstructured":"H. Dym and H. P. McKean,Fourier series and integrals. Probability and Methematical Statistics series, Academic Press, 1972."},{"key":"CR11","unstructured":"M. Dowd and M. Sitharam, Shannon bounds for functions over ? n 2 . Technical Report 90-12-1, Kent State University, Department of Mathematics and Computer Science, 1990."},{"key":"CR12","doi-asserted-by":"crossref","unstructured":"M. Furst, J. Jackson, and S. Smith, Improved learning ofAC 0 functions. InProc. 5 th Ann. IEEE Symp. Computational Learning Theory, 1992, 317?325.","DOI":"10.1016\/B978-1-55860-213-7.50032-8"},{"key":"CR13","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1007\/BF01744431","volume":"17","author":"M. Furst","year":"1984","unstructured":"M. Furst, J. Saxe, andM. Sipser, Parity, circuits and the polynomial time hierarchy.Mathematical Systems Theory 17 (1984), 17?27.","journal-title":"Mathematical Systems Theory"},{"key":"CR14","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1007\/BF01200426","volume":"2","author":"M. Goldman","year":"1992","unstructured":"M. Goldman, J. Hastad, andA. A. Razborov, Majority gates vs. general weighted thresgold gates.Computational Complexity 2 (1992), 277?300.","journal-title":"Computational Complexity"},{"key":"CR15","unstructured":"M. Goldman and J. Hastad, On the power of small depth threshold circuits. InProc. 31 st Ann. IEEE Symp. Foundations of Computer Science, 1990, 610?618."},{"key":"CR16","unstructured":"V. Grolmusz,Harmonic analysis, real approximation and communication complexity of Boolean functions. Manuscript, 1994."},{"key":"CR17","unstructured":"J. Hastad,Computational limitations of small depth circuits. Ph. D thesis, Massachussetts Institute of Technology press, 1986."},{"key":"CR18","doi-asserted-by":"crossref","unstructured":"A. Hajnal, W. Maass, P. Pudl\ufffdk, M. Szegedy, and G. Tur\ufffdn, Threshold circuits of bounded depth. InProc. 28 th Ann. IEEE Symp. Foundations of Computer Science, 1987, 99?110.","DOI":"10.1109\/SFCS.1987.59"},{"key":"CR19","doi-asserted-by":"crossref","unstructured":"J. Kahn, J. Kalai, and N. Linial, The influence of variables on Boolean functions. InProc. 29 th Ann. IEEE Symp. Foundations of Computer Science, 1988, 68?80.","DOI":"10.1109\/SFCS.1988.21923"},{"issue":"6","key":"CR20","doi-asserted-by":"crossref","first-page":"1331","DOI":"10.1137\/0222080","volume":"22","author":"E. Kushilevitz","year":"1993","unstructured":"E. Kushilevitz andY. Mansour, Learning decision trees using the Fourier transform.SIAM Journal of Computing 22:6 (1993), 1331?1348.","journal-title":"SIAM Journal of Computing"},{"key":"CR21","doi-asserted-by":"crossref","unstructured":"M. Krause, Geometric arguments yield better bounds for threshold circuits and distributed computing. InProc. 6 th Ann. IEEE Symp. Structure in Complexity Theory, 1991, 314?322.","DOI":"10.1109\/SCT.1991.160275"},{"key":"CR22","doi-asserted-by":"crossref","unstructured":"M. Krause and S. Waack, Variation ranks of communication matrices and lower bounds for depth two circuits having symmetric gates and unbounded fanin. InProc. 32 nd Ann. IEEE Symp. Foundations of Computer Science, 1991, 777?782.","DOI":"10.1109\/SFCS.1991.185448"},{"key":"CR23","doi-asserted-by":"crossref","unstructured":"N. Linial, Y. Mansour, and N. Nisan, Constant depth circuits, Fourier transforms, and learnability. InProc. 30 th Ann. IEEE Symp. Foundations of Computer Science, 1989, 574?579. To appear inJACM.","DOI":"10.1109\/SFCS.1989.63537"},{"issue":"4","key":"CR24","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1007\/BF02128670","volume":"10","author":"N. Linial","year":"1990","unstructured":"N. Linial andN. Nisan, Approximate inclusion-exclusion.Combinatorica 10:4 (1990), 349?365.","journal-title":"Combinatorica"},{"key":"CR25","unstructured":"F. J. MacWiliams and N. J. A. Sloane,The theory of error-correcting codes. North Holland, 1977."},{"key":"CR26","doi-asserted-by":"crossref","unstructured":"N. Nisan and A. W. Widgerson, Hardness vs. randomness. InProc. 29 th Ann. IEEE Symp. Foundations of Computer Science, 1988, 2?11. To appear inJCSS.","DOI":"10.1109\/SFCS.1988.21916"},{"key":"CR27","doi-asserted-by":"crossref","unstructured":"N. Nisan and M. Szegedy, On the degree of Boolean functions as real polynomials. InProc. 24 th Ann. ACM Symp. Theory of Computing, 1992, 468?467.","DOI":"10.1145\/129712.129757"},{"key":"CR28","doi-asserted-by":"crossref","unstructured":"R. Paturi, On the degree of polynomials that approximate symmetric Boolean functions. InProc. 24 th Ann. ACM Symp. Theory of Computing 1992, 468?474.","DOI":"10.1145\/129712.129758"},{"key":"CR29","doi-asserted-by":"crossref","unstructured":"R. Paturi and M. Saks, Threshold circuits for parity. InProc. 31 st Ann. IEEE Symp. Foundations of Computer Science, 1990, 397?404.","DOI":"10.1109\/FSCS.1990.89559"},{"key":"CR30","first-page":"354","volume":"31","author":"A. A. Razborov","year":"1985","unstructured":"A. A. Razborov, Lower bounds on the monotone complexity of some Boolean functions.Soviet Mathematics Doklady 31 (1985), 354?357.","journal-title":"Soviet Mathematics Doklady"},{"key":"CR31","doi-asserted-by":"crossref","unstructured":"A. A. Razborov, Lower bounds on the size of circuits of bounded depth with basis {?,?}. InMath. Notes of the Academy of Sciences of the USSR 41:4 (1987), 333?338.","DOI":"10.1007\/BF01137685"},{"key":"CR32","doi-asserted-by":"crossref","unstructured":"M. Sitharam, Pseudorandom generators and learning algorithms forAC 0. InProc. 26 th Ann. ACM Symp. Theory of Computing, 1994, 478?488. To appear inComputational Complexity.","DOI":"10.1145\/195058.195236"},{"key":"CR33","doi-asserted-by":"crossref","unstructured":"R. Smolensky, Algebraic methods in the theory of lower bounds for boolean circuit complexity. InProc. 19 th Ann. ACM Symp. Theory of Computing, 1987, 77?82.","DOI":"10.1145\/28395.28404"},{"issue":"3","key":"CR34","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1137\/0404038","volume":"4","author":"K. I. Siu","year":"1991","unstructured":"K. I. Siu andJ. Bruck, On the power of threshold circuits with small weights.SIAM Journal of Discrete Mathematics 4:3 (1991), 423?435.","journal-title":"SIAM Journal of Discrete Mathematics"},{"key":"CR35","doi-asserted-by":"crossref","unstructured":"A. C. Yao, Lower bounds by probabilistic arguments. InProc. 24 th Ann. IEEE Symp. Foundations of Computer Science, 1983, 420?428.","DOI":"10.1109\/SFCS.1983.30"},{"key":"CR36","doi-asserted-by":"crossref","unstructured":"A. C. Yao, Separating the polynomial time hierarchy by oracles. InProc. 26 th Ann. IEEE Symp. Foundations of Computer Science, 1985, 1?10.","DOI":"10.1109\/SFCS.1985.49"},{"key":"CR37","doi-asserted-by":"crossref","unstructured":"A. C. Yao, Circuits and local computation. InProc. 21 st Ann. ACM Symp. Theory of Computing, 1989, 186?196.","DOI":"10.1145\/73007.73025"},{"key":"CR38","doi-asserted-by":"crossref","unstructured":"A. C. Yao, OnACC and threshold circuits. InProc. 31 st Ann. IEEE Symp. Foundations of Computer Science, 1990, 619?627.","DOI":"10.1109\/FSCS.1990.89583"}],"container-title":["Computational Complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01268144.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01268144\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01268144","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,28]],"date-time":"2024-12-28T08:22:57Z","timestamp":1735374177000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01268144"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,6]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1995,6]]}},"alternative-id":["BF01268144"],"URL":"https:\/\/doi.org\/10.1007\/bf01268144","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"type":"print","value":"1016-3328"},{"type":"electronic","value":"1420-8954"}],"subject":[],"published":{"date-parts":[[1995,6]]}}}