Bounded-width polynomial-size branching programs recognize exactly those languages in NC1

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Bounded-width polynomial-size branching programs recognize exactly those languages in NC¹

Full text

Pdf (420 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the eighteenth annual ACM symposium on Theory of computing table of contents

Berkeley, California, United States

Pages: 1 - 5

Year of Publication: 1986

ISBN:0-89791-193-8

Author

D A Barrington

Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 12, Downloads (12 Months): 78, Citation Count: 14

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/12130.12131 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.

	Aj83	M. Ajtai, 'E~ formulae on finite structures', Annals of Pure and Applied Logic 24 (1983), 1-48.
	ABHKST86	M Ajtai , L Babai , P Hajnal , J Komlos , P Pudlak, Two lower bounds for branching programs, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.30-38, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12134]
	Ba85	D. A. Barrington, 'Width-3 permutation branching programs', Technical Memorandum TM-293, M.I.T. Laboratory for Computer Science.
	BCH84	P. W. Beame, S. A. Cook, and H. J. Hoover, 'Logdepth circuits for division and related problems', Proc. 25th IEEE FOCS, 1984, 1-6.
	BDFP83	Allan Borodin , Danny Dolev , Faith E. Fich , Wolfgang Paul, Bounds for width two branching programs, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.87-93, December 1983 [doi>10.1145/800061.808736]
	Be73	C. H. Bennett, 'Logical reversibility of computation', IBM Journal of Research and Development, 17 (1973), 525-532.
	CFL83	Ashok K. Chandra , Merrick L. Furst , Richard J. Lipton, Multi-party protocols, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.94-99, December 1983 [doi>10.1145/800061.808737]
	Co85	Stephen A. Cook, A taxonomy of problems with fast parallel algorithms, Information and Control, v.64 n.1-3, p.2-22, Jan./Feb./March 1985 [doi>10.1016/S0019-9958(85)80041-3]
	FKPS84	R. Fagin, M. M. Klawe, N. J. Pippenger, and L. Stochmeyer, 'Bounded depth, polynomial-size circuits for symmetric functions', IBM Report RJ 4040 (45198) (October 1983), IBM Research Laboratory, San Jose.
	FSSS1	M, Furst, J. B. Saxe, and M. Sipser, 'Parity, circuits, and the polynomial time heirarchy', Proc, 22nd IEEE FOCS, 1981, 260-270.
	GS??	M. Ger~l>-Graus and E. Szemer~di, 'There are no p-complete families of symmetric Boolean functions', preprint.
	Ha86	J. Hastad, 'Improved lower bounds for small depth circuits', these proceedings.
	LF77	R. E. Ladner and M. J. Fischer, 'Parallel prefix computation', Proc. 1977 Intl. Conf. on Parallel Processing, 218-233.
	Le59	C. Y. Lee, 'Representation of switching functions by binary decision programs', Bell System Technical Journal 38 (1959) 985-999.
	Ma76	W. Masek, 'A fast algorithm for the string editing problem and decision graph complexity', M. Sc. Thesis, MIT, May 1976.
	Pu84	Pavel Pudlák, A Lower Bound on Complexity of Branching Programs (Extended Abstract), Proceedings of the Mathematical Foundations of Computer Science 1984, p.480-489, September 03-07, 1984
	Ru81	W. L. Ruzzo, 'On uniform circuit complexity', JCS~ 22, 3 (June 1981), 365-383.
	Sa72	J. E. Savage, Computational Work and Time on Finite Machines, Journal of the ACM (JACM), v.19 n.4, p.660-674, Oct. 1972 [doi>10.1145/321724.321731]
	Sh85	J. B. Shearer, personal communication, 1985.
	SV81	S. Skyum and L. G. Valiant, 'A complexity theor~ based on Boolean algebra', Proc. 22nd IEEE FOCS, 1981, 244~ 253.
	Ya83	A. C. Yao, 'Lower bounds by probabilistic argu merits', Proc. 24th IEEE FOCS, 1983, 420-428.
	Ya85	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
	Za58	H. J. Zassenhaus, Th~ Theory off Groups, 2nd ed (New York, Chelsea Publ. Co., 1958).

CITED BY 14

	D. Barrington , D. Therien, Finite monoids and the fine structure of NC¹, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.101-109, January 1987, New York, New York, United States
	A. C. Yao, Circuits and local computation, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.186-196, May 14-17, 1989, Seattle, Washington, United States
	J. Bar-Ilan , D. Beaver, Non-cryptographic fault-tolerant computing in constant number of rounds of interaction, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.201-209, June 1989, Edmonton, Alberta, Canada
	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
	Joe Kilian, Founding crytpography on oblivious transfer, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.20-31, May 02-04, 1988, Chicago, Illinois, United States
	Richard Cleve, Computing algebraic formulas with a constant number of registers, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.254-257, May 02-04, 1988, Chicago, Illinois, United States
	O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.218-229, January 1987, New York, New York, United States
	M. Szegedy, Functions with bounded symmetric communication complexity and circuits with mod m gates, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.278-286, May 13-17, 1990, Baltimore, Maryland, United States
	R. Cleve, Towards optimal simulations of formulas by bounded-width programs, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.271-277, May 13-17, 1990, Baltimore, Maryland, United States
	Michael Ben-Or , Shafi Goldwasser , Joe Kilian , Avi Widgerson, Multi-prover interactive proofs: how to remove intractability assumptions, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.113-131, May 02-04, 1988, Chicago, Illinois, United States
	Vince Grolmusz, A weight-size trade-off for circuits with MOD m gates, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.68-74, May 23-25, 1994, Montreal, Quebec, Canada
	Nicholas Pippenger, The complexity of computations by networks, IBM Journal of Research and Development, v.31 n.2, p.235-243, March 1987
	Alex Brodsky, An impossibility gap between width-4 and width-5 permutation branching programs, Information Processing Letters, v.94 n.4, p.159-164, 31 May 2005
	Craig Gentry, Fully homomorphic encryption using ideal lattices, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA