The cost of the missing bit

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 cost of the missing bit: communication complexity with help

Full text

Pdf (1.26 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: 673 - 682

Year of Publication: 1998

ISBN:0-89791-962-9

Authors

László Babai	Department of Computer Science, University of Chicago, 1100 East, 58th, Street, IL
Thomas P. Hayes	Department of Mathemntics, University of Chicago, 5734 S. University Avenue, Chicaco, IL
Peter G. Kimmel	Department of Computer Science, University of Chicago

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): 22, 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.276883 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.

	B	L. Babai. The Fourier Transform and Equations Over Finite Abelian Groups, Lecture Notes, version 1.2, December 1989.
	BKL	L. Babai, P. Kimmel, and S. V. Lokam. Simtdtaneotts Messages vs. Communication. 12th Syrup. on Theoretical Aspects of Comp. Sci., 1995, Springer Lecture Notes in Comp. Sei., 900, pp. 361-372. Updated version: L. Babai, A. G~, P. Kimmel, and S. V. Lokam. Simttltancotts Messages vs. Communication. Manuscript, 1995.
	BNS	László Babai , Noam Nisan , Márió Szegedy, Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs, Journal of Computer and System Sciences, v.45 n.2, p.204-232, Oct. 1992 [doi>10.1016/0022-0000(92)90047-M]
	BT	Richard Beigel , Jun Tarui, On ACC, Proceedings of the 32nd annual symposium on Foundations of computer science, p.783-792, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185449]
	CFL	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]
	CT	Fan R. K. Chung , Prasad Tetali, Communication complexity and quasi randomness, SIAM Journal on Discrete Mathematics, v.6 n.1, p.110-125, Feb. 1993 [doi>10.1137/0406009]
	CW	L. Carter and M. Wegman, Universal Hash Fttnctions, J. Computer and Sys. Sei., 18 (1979) 143-154.
	GT	Hans Dietmar Gröger , György Turán, On linear decision trees computing Boolean functions, Proceedings of the 18th international colloquium on Automata, languages and programming, p.707-718, June 1991, Madrid, Spain
	HM+	A. Hajnal, W. Maass, P. Pudl'&, M. Szegedy, G. Tur/in. Threshold circuits of bounded depth. 28th FOCS, 1987, pp. 99-110.
	HG	J. H~tad and M. Goldmann. On the Power of SmalbDepth ThreshoM Circuits. Computational Complexity, 1 (1991) 113--129.
	KN	E. Kushilevitz and N. Nisan. Contmunication Comple.~io: Cambridge University Press, 1997.
	LVW	M. Luby, B. Veli~:kovi6, and A. Wigderson. Deterministic Approximate Counting of Depth-2 Cilvttits. Proe. Second Israel Syrup. on Theory and Computing Systems, 1993, pp, 18-24.
	MNT	Yishay Mansour , Noam Nisan , Prasoon Tiwari, The computational complexity of universal hashing, Theoretical Computer Science, v.107 n.1, p.121-133, Jan. 4, 1993 [doi>10.1016/0304-3975(93)90257-T]
	Ni	N. Nisan. The communication complexiO, of threshold gates. In: Combinatorics, Paul Erd6s is Eighty (D. Mikl6s, T. Sz6nyi, V.T. S6s, eds.), Vol. 1. Bolyai Society Mathematical Studies 1, Budapest 1993 {distributed by the A.M.S.), pp. 301-315.
	NW	Noam Nisan , Avi Wigderson, Rounds in communication complexity revisited, SIAM Journal on Computing, v.22 n.1, p.211-219, Feb. 1993 [doi>10.1137/0222016]
	PRS	Pavel Pudlák , Vojtech Rödl , Jirí Sgall, Boolean Circuits, Tensor Ranks, and Communication Complexity, SIAM Journal on Computing, v.26 n.3, p.605-633, June 1997 [doi>10.1137/S0097539794264809]
	Sch	W.M. Sehmidt: Equations over Finite Fields: Art Elentcn. tary Approach. Leer. Notes in Math. 536, Springer 1976,
	Wi	A. Wigderson. Personal communication. April 20, 1997.
	Y	A. C-C. Yao. On ACC and ThreshoM Circuits. 31st IEEE FOCS, 1990, pp. 619-627.

CITED BY 3

	Beate Bolling , Martin Sauerhoff , Ingo Wegener, On the nonapproximability of boolean Function by OBDDs and read-k-times Branching Programs, Information and Computation, v.178 n.1, p.263-278, October 10, 2002
	Martin Sauerhoff, Approximation of boolean functions by combinatorial rectangles, Theoretical Computer Science, v.301 n.1-3, p.45-78, 14 May 2003
	Benjamin Doerr , Anand Srivastav, Multicolour Discrepancies, Combinatorics, Probability and Computing, v.12 n.4, p.365-399, July 2003