Las Vegas is better than determinism in VLSI and distributed computing (Extended Abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Las Vegas is better than determinism in VLSI and distributed computing (Extended Abstract)

Full text

Pdf (428 KB)

Source

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

San Francisco, California, United States

Pages: 330 - 337

Year of Publication: 1982

ISBN:0-89791-070-2

Authors

Kurt Mehlhorn
Erik M. Schmidt

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 23, Citation Count: 36

Additional Information:

abstract references cited by 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/800070.802208 What is a DOI?

ABSTRACT

In this paper we describe a new method for proving lower bounds on the complexity of VLSI - computations and more generally distributed computations. Lipton and Sedgewick observed that the crossing sequence arguments used to prove lower bounds in VLSI (or TM or distributed computing) apply to (accepting) nondeterministic computations as well as to deterministic computations. Hence whenever a boolean function f is such that f and -&-fmarc; (the complement of f, -&-fmarc; -&-equil; 1 -&-minus; f) have efficient nondeterministic chips then the known techniques are of no help for proving lower bounds on the complexity of deterministic chips. In this paper we describe a lower bound technique (Thm 1) which only applies to deterministic computations

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	R. Freivalds; Probabilistic machines can use less running time, Information Processing 1977, IFIP, North Holland, 1977, 839-842.
	2	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]
	3	Franco P. Preparata , Jean Vuillemin, Area-Time Optimal VLSI Networks for Computing Integer Multiplications and Discrete Fourier Transform, Proceedings of the 8th Colloquium on Automata, Languages and Programming, p.29-40, July 13-17, 1981
	4	Erik Meineche Schmidt, Succinctness of descriptions of context-free, regular and finite languages., 1978
	5	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]
	6	Andrew C. Yao, The entropic limitations on VLSI computations(Extended Abstract), Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.308-311, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802483]

CITED BY 37

	Zhi-Quan Luo , John N. Tsitsiklis, On the communication complexity of distributed algebraic computation, Journal of the ACM (JACM), v.40 n.5, p.1019-1047, Nov. 1993
	Satyanarayana V. Lokam, Complexity Lower Bounds using Linear Algebra, Foundations and Trends® in Theoretical Computer Science, v.4 n.1–2, p.1-155, January 2009
	Anne Condon , Lisa Hellerstein , Samuel Pottle , Avi Wigderson, On the power of finite automata with both nondeterministic and probabilistic states (preliminary version), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.676-685, May 23-25, 1994, Montreal, Quebec, Canada
	Bernd Halstenberg , Rudiger Reischuk, On different modes of communication, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.162-172, May 02-04, 1988, Chicago, Illinois, United States
	Eyal Kushilevitz , Nathan Linial , Rafail Ostrovsky, The linear-array conjecture in communication complexity is false, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.1-10, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Paul Beame , Joan Lawry, Randomized versus nondeterministic communication complexity, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.188-199, May 04-06, 1992, Victoria, British Columbia, Canada
	Alfred V. Aho , Jeffrey D. Ullman , Mihalis Yannakakis, On notions of information transfer in VLSI circuits, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.133-139, December 1983
	J. Hromkovic , G. Schnitger, Nondeterministic communication with a limited number of advice bits, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.551-560, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Rajiv Gupta , Scott A. Smolka , Shaji Bhaskar, On randomization in sequential and distributed algorithms, ACM Computing Surveys (CSUR), v.26 n.1, p.7-86, March 1994
	T.-T. Hwang , R. M. Owens , M. J. Irwin, Multi-level logic synthesis using communication complexity, Proceedings of the 26th ACM/IEEE conference on Design automation, p.215-220, June 25-28, 1989, Las Vegas, Nevada, United States
	Peter Bro Miltersen , Noam Nisan , Shmuel Safra , Avi Wigderson, On data structures and asymmetric communication complexity, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.103-111, May 29-June 01, 1995, Las Vegas, Nevada, United States
	András Hajnal , Wolfgang Maass , György Turán, On the communication complexity of graph properties, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.186-191, May 02-04, 1988, Chicago, Illinois, United States
	A Siegel, Aspects of information flow in VLSI circuits, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.448-459, May 28-30, 1986, Berkeley, California, United States
	Anna Gál, A characterization of span program size and improved lower bounds for monotone span programs, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.429-437, May 24-26, 1998, Dallas, Texas, United States
	Mihalis Yannakakis, Expressing combinatorial optimization problems by linear programs, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.223-228, May 02-04, 1988, Chicago, Illinois, United States
	M. Furer, The power of randomness for communication complexity, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.178-181, January 1987, New York, New York, 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
	T. Lam , P. Tiwari , M. Tompa, Tradeoffs between communication and space, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.217-226, May 14-17, 1989, Seattle, Washington, United States
	Prasoon Tiwari, Lower bounds on communication complexity in distributed computer networks, Journal of the ACM (JACM), v.34 n.4, p.921-938, Oct. 1987
	Juraj Karhuäki , Sebastian Seibert , Juhani Karhumaki , Hartmut Klauck , Georg Schnitger, Communication complexity method for measuring nondeterminism in finite automata, Information and Computation, v.172 n.2, p.202-217, January 29, 2002
	Juraj Hromkovič , Georg Schnitger, On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata, Information and Computation, v.169 n.2, p.284-296, September 15, 2001
	Pavol Duris , Zvi Galil , Georg Schnitger, Lower bounds on communication complexity, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.81-91, December 1984
	Ronald de Wolf, Quantum communication and complexity, Theoretical Computer Science, v.287 n.1, p.337-353, 25 September 2002
	Martin Sauerhoff, Approximation of boolean functions by combinatorial rectangles, Theoretical Computer Science, v.301 n.1-3, p.45-78, 14 May 2003
	Anna Gál, A characterization of span program size and improved lower bounds for monotone span programs, Computational Complexity, v.10 n.4, p.277-296, May 2002
	Paul Valiant, The Log-Rank conjecture and low degree polynomials, Information Processing Letters, v.89 n.2, p.99-103, 31 January 2004
	Martin Dietzfelbinger, The linear-array problem in communication complexity resolved, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.373-382, May 04-06, 1997, El Paso, Texas, United States
	Alok Aggarwal , Ashok Chandra , Prabhakar Raghavan, Energy consumption in VLSI circuits, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.205-216, May 02-04, 1988, Chicago, Illinois, United States
	Pavol Ďuriš , Juraj Hromkovič , Katsushi Inoue, On the power of nondeterminism and Las Vegas randomization for two-dimensional finite automata, Journal of Computer and System Sciences, v.68 n.3, p.675-699, May 2004
	Pavol Ďuriš, Multiparty communication complexity and very hard functions, Information and Computation, v.192 n.1, p.1-14, 1 July 2004
	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
	Carsten Damm , Matthias Krause , Christoph Meinel , Stephan Waack, On relations between counting communication complexity classes, Journal of Computer and System Sciences, v.69 n.2, p.259-280, September 2004
	Gueesang Lee , M. J. Irwin , R. M. Owens, Polynomial Time Testability of Circuits Generated by Input Decomposition, IEEE Transactions on Computers, v.43 n.2, p.201-210, February 1994
	Juraj Hromkovič , Georg Schnitger, On the power of randomized multicounter machines, Theoretical Computer Science, v.330 n.1, p.135-144, 31 January 2005
	Noam Nisan , Avi Widgerson, Rounds in communication complexity revisited, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.419-429, May 05-08, 1991, New Orleans, Louisiana, United States
	Nicholas J. A. Harvey, Matroid intersection, pointer chasing, and Young's seminormal representation of S_n, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.542-549, January 20-22, 2008, San Francisco, California
	Eyal Kushilevitz , Enav Weinreb, On the complexity of communication complexity, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA

Collaborative Colleagues:

Kurt Mehlhorn: colleagues

Erik M. Schmidt: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player