A characterization of span program size and improved lower bounds for monotone span programs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A characterization of span program size and improved lower bounds for monotone span programs

Full text

Pdf (1.13 MB)

Source

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

Dallas, Texas, United States

Pages: 429 - 437

Year of Publication: 1998

ISBN:0-89791-962-9

Author

Anna Gál

Dept. of Computer Sciences, The University of Texas at Austin, Austin, TX and Dept. of Computer Science and the Fields Institute at the University of Toronto

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 18, Citation Count: 3

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

	A	N. Alon: Personal communication.
	Al	N Alon, Explicit construction of exponential sized families of K-independent sets, Discrete Mathematics, v.58 n.2, p.191-193, Feb. 1986 [doi>10.1016/0012-365X(86)90161-5]
	AB	N. Alon , R. B. Boppana, The monotone circuit complexity of Boolean functions, Combinatorica, v.7 n.1, p.1-22, Jan. 1987 [doi>10.1007/BF02579196]
	ABO	Eric Allender , Robert Beals , Mitsunori Ogihara, The complexity of matrix rank and feasible systems of linear equations (extended abstract), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.161-167, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237856]
	AGHP	N. Alon, O. Goldreich, J. Hfistad, R. Peralta: Simple constructions of almost k-wise independem random variables. Random Structures and Algorithms 3 (1992), 289-304.
	An	A. Andreev: On a method for obtaining lower bounds for the complexity of individual monotone functions, it Soy. Math. Dokl. 31 (1985), pp. 530- 534.
	AMN	Azar, R. Motwani, J. Naor: Approximating probabilit3.' distributions using small sample spaces. Corn. binatorica, to appear.
	B+	László Babai , Anna Gál , János Kollár , Lajos Rónyai , Tibor Szabó , Avi Wigderson, Extremal bipartite graphs and superpolynomial lower bounds for monotone span programs, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.603-611, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.238010]
	BGW	Laszlo Babai , Anna Gal , Avi Wigderson, Superpolynomial Lower Bounds for Monotone Span Programs, Certer for Discrete Mathematics & Theoretical Computer Science, 1996
	BGP	Amos Beimel , Anna Gál , Mike Paterson, Lower bounds for monotone span programs, Computational Complexity, v.6 n.1, p.29-45, 1996/1997 [doi>10.1007/BF01202040]
	Bo	B. Bollob',is: Random graphs. Academic Press, New York, 1985.
	BT	B. Bollob~ and A. Thomason: Graphs which contain all small graphs, European J. Comb.2, 1981, pp. 13-15.
	BDHM	G. Buntrock, C. Damm, H. Hertrampf, and C. Meinel' Structure and importance of the logspace-mod class. Math. Systems Theory 25 (1992), pp. 223-237.
	Cs	L. Csirmaz: The dealer's random bits in perfect secret sharing schemes. Preprint, Mathematical Inst. HungarianAcad. Sei., 1994.
	GH	Mikael Goldmann , Johan Håstad, A simple lower bound for monotone clique using a communication game, Information Processing Letters, v.41 n.4, p.221-226, March 18, 1992 [doi>10.1016/0020-0190(92)90184-W]
	GSi	Michelangelo Grigni , Michael Sipser, Monotone complexity, Poceedings of the London Mathematical Society symposium on Boolean function complexity, p.57-75, December 1992, London, United Kingdom
	GS	R.L. Graham, J. H. Spencer: A constructive solution to a tournament problem. Canad. Math. Bull. 14 (1971),45--48.
	H	J. Hastad: The shrinkage exponent is 2, In Prec. 34th iEEE FOC$, 1993, pp. 114-123.
	Ha	A. Haken, Counting bottlenecks to show monotone P ? NP, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.36, October 23-25, 1995
	KW1	M. Karehmer and A. Wigderson: Monotone Circuits for Connectivity require Super-Logarithmic Depth. In SlAM Journal oit Discrete Mathematics, Vol 3, No. 2, 1990, pp. 255-265.
	KW	M. Karchmer and A. Wigderson: On span programs. In Prec. 8th Ann. Syrup. Structure in Complavity The. or3', IEEE 1993, pp. 102-111.
	K	V.M. Khrapchenko: Methods of determining lower bounds for the complexity of H-schemes. Mat. Za. metkilO (1972) pp. 83-92, (in Russian). English translation in: Math. Notes Acad. Sciences USSR I0 (1972) pp. 474-479.
	KS	D.J. Kleitman and J. Spencer: Families of kindependent sets. Discrete Math.6 (1973), pp. 255. 262.
	KN	Eyal Kushilevitz , Noam Nisan, Communication complexity, Cambridge University Press, New York, NY, 1996
	LS	Richard J. Lipton , Robert Sedgewick, Lower bounds for VLSI, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.300-307, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802482]
	MS	Kurt Mehlhorn , Erik M. Schmidt, Las Vegas is better than determinism in VLSI and distributed computing (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.330-337, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802208]
	NN	Joseph Naor , Moni Naor, Small-bias probability spaces: efficient constructions and applications, SIAM Journal on Computing, v.22 n.4, p.838-856, Aug. 1993 [doi>10.1137/0222053]
	PS	P. Pudlak and J. Sgall: Algebraic models of computation and interpolation for algebraic proof systems. To appear in Feasible Arithmetic and Lengths of Proofs, ed. S. Buss, Lecture Notes in Comput. Sci. Springer-Verlag.
	RW	Ran Raz , Avi Wigderson, Monotone circuits for matching require linear depth, Journal of the ACM (JACM), v.39 n.3, p.736-744, July 1992 [doi>10.1145/146637.146684]
	Ra	A.A. Razborov: Applications of matrix methods to the theory of lower bounds in computational complexity. Combinatorica 10 (1990), pp. 81-93.
	Ra1	A, A. Razborov: Lower bounds for the monotone complexity of some Boolean functions. Soviet Math. Doklady, 31 (1985) 354--357.
	Ra2	A. A, Razborov: A lower bound on the monotone network complexity of the logical permanent. Mat. Zametki 37 (1985), 887-900.
	Ra3	A. A. Razborov, On the method of approximations, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.167-176, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73023]
	Ry	K. L, Ryehkov: A modification of Krapehenko's method and its applications to bounds on the complexity ofiI.schemes and coding funetions. Methody Dlscretnovo Analyza 42 (1985), pp. 91-98 (in Russian).
	SB	G, Seroussi and N. Bshouti: Vector sets for exhaustive testing of logic circuits. IEEE Trans. Inform. Theory, 34 (1988), pp. 513-522.
	SV	S. Skyum , L. G. Valiant, A complexity theory based on Boolean algebra, Journal of the ACM (JACM), v.32 n.2, p.484-502, April 1985 [doi>10.1145/3149.3158]
	T	1~. Tardos: The gap between monotone and nonmonotone circuit complexity is exponential Combinatoriea, 7(4), 1987, pp. 141-142.
	Y	Andrew Chi-Chih Yao, Some complexity questions related to distributive computing(Preliminary Report), Proceedings of the eleventh annual ACM symposium on Theory of computing, p.209-213, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804414]

CITED BY 3

	M V N Ashwin Kumar , Pranava R. Goundan , K Srinathan , C. Pandu Rangan, On perfectly secure communication over arbitrary networks, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California
	Anna Gál , Pavel Pudlák, A note on monotone complexity and the rank of matrices, Information Processing Letters, v.87 n.6, p.321-326, 30 September 2003
	Noga Alon , Venkatesan Guruswami , Tali Kaufman , Madhu Sudan, Guessing secrets efficiently via list decoding, ACM Transactions on Algorithms (TALG), v.3 n.4, p.42-es, November 2007