Direct product results and the GCD problem, in old and new communication models

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Direct product results and the GCD problem, in old and new communication models

Full text

Pdf (1.28 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-ninth annual ACM symposium on Theory of computing table of contents

El Paso, Texas, United States

Pages: 363 - 372

Year of Publication: 1997

ISBN:0-89791-888-6

Authors

Itzhak Parnafes	Weizmann Institute of Science
Ran Raz	Weizmann Institute of Science
Avi Wigderson	The Hebrew University

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): 20, Citation Count: 5

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

	ABG	A. Amir, R. Beigel, W. Gasarch, "Some connections between bounded query classes and nonuniform complexity", 5th Structures in Complexity Theory Conference, 1990.
	Cai	J. Cat, "Lower bounds for constant depth circuits in the presence of help bits", 30th FOUS, pp. 532-537, 1989.
	EIRS	Jeff Edmonds , Russell Impagliazzo , Steven Rudich , Jiří Sgall, Communication complexity towards lower bounds on circuit depth, Proceedings of the 32nd annual symposium on Foundations of computer science, p.249-257, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185375]
	FV	Uriel Feige , Oleg Verbitsky, Error Reduction by Parallel Repetition - A Negative Result, Proceedings of the 11th Annual IEEE Conference on Computational Complexity, p.70, May 24-27, 1996
	FKN	Tomàs Feder , Eyal Kushilevitz , Moni Naor, Amortized communication complexity (Preliminary version), Proceedings of the 32nd annual symposium on Foundations of computer science, p.239-248, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185374]
	GNW	O. Goldreich, N. Nisan, A. Wigderson, "On Yao's XOR lemma", EUCC TR 95-050, 1995.
	HW	J. Hastad, A. Wigderson, "The probabilistic communication complexity of disjointness of k sets is O(k)", Unpublished Manuscript, 1990.
	IRW	R. Impagliazzo, R. Raz. A. Wigderson, "A Direct Product Theorem", Proc. of the 9th Structures in Complexity conference, pp. 88- 96, 1994.
	KKN	M. Karchmer, E. Kushilevitz, N. Nisan, "Fractional Covers and Communication Complexity'', 7th Structures in Complexity Theory Conference, pp. 262-274, 1992.
	KRW	M. Karchmer, R. Raz, A. Wigderson, "On Proving Super-Logarithmic Depth Lower Bounds via the Direct Sum in Communication Complexity", Structures in Complexity Theory '91, pp. 299-304 (1991).
	KS	B. Kalyanasundaram and G. Schnitger "The Probabilistic Communication Complexity of Set Intersection", Proceedings Structure in Complexity Theory pp.41-49, 1987.
	L	L.Lovhsz, "On the ratio of optimal integral and fractional cover", Discrete Mathematics , 13, pp. 383-390, 1975.
	NRS	N. Nisan, S. Rudich M. Saks, "Products and Help Bits in Decision Trees", 35th FOC$, pp. 318-329, 1994.
	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]
	R	A. A. Razborov, On the distributional complexity of disjointness, Proceedings of the seventeenth international colloquium on Automata, languages and programming, p.249-253, July 1990, Warwick University, England
	Ra	Ran Raz, A parallel repetition theorem, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.447-456, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225181]
	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]
	Ya	A.C. Yao, "Theory and Application of Trapdoor Functions", in 23st FOCS, pages 80-91, 1982.

CITED BY 5

	Ronen Shaltiel, Towards proving strong direct product theorems, Computational Complexity, v.12 n.1/2, p.1-22, July 2004
	Anup Rao, Parallel repetition in projection games and a concentration bound, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Thomas Holenstein, Parallel repetition: simplifications and the no-signaling case, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
	Paul Beame , Toniann Pitassi , Nathan Segerlind , Avi Wigderson, A Strong Direct Product Theorem for Corruption and the Multiparty Communication Complexity of Disjointness, Computational Complexity, v.15 n.4, p.391-432, December 2006
	Rahul Jain , Hartmut Klauck , Ashwin Nayak, Direct product theorems for classical communication complexity via subdistribution bounds: extended abstract, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada