<script type="text/javascript">
<!--
document.write('<div id="oa_widget"></div>');
document.write('<script type="text/javascript" src="https://www.openaire.eu/index.php?option=com_openaire&view=widget&format=raw&projectId=undefined&type=result"></script>');
-->
</script>

COPY SCRIPT

For further information contact us at helpdesk@openaire.eu

Claim

Separating NOF communication complexity classes RP and NP

descriptionPublicationkeyboard_double_arrow_right Preprint , Article 01 Jan 2008Embargo end date: 01 Jan 2008arXiv NSERC

Authors: David, Matei; Pitassi, Toniann;

doi: 10.48550/arxiv.0802.3860

Separating NOF communication complexity classes RP and NP

- Summary
- Subjects
- References
  (16)
- Metrics

Abstract

We provide a non-explicit separation of the number-on-forehead communication complexity classes RP and NP when the number of players is up to \delta log(n) for any \delta<1. Recent lower bounds on Set-Disjointness [LS08,CA08] provide an explicit separation between these classes when the number of players is only up to o(loglog(n)).

Related Organizations

View all View all

Subjects by Vocabulary

arXiv: Computer Science::Computer Science and Game Theory Computer Science::Computational Complexity

Keywords

FOS: Computer and information sciences, Computer Science - Computational Complexity, Computational Complexity (cs.CC), F.1.3

16 references, page 1 of 2

[1] La´szlo´ Babai, P. Frankl, and Janos Simon. Complexity classes in communication complexity theory. In 27th Annual Symposium on Foundations of Computer Science, pages 337-347, Toronto, Ontario, October 1986. IEEE.

[2] La´szlo´ Babai, Noam Nisan, and Ma´rio´ Szegedy. Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs. Journal of Computer and System Sciences, 45(2):204-232, October 1992. [OpenAIRE]

[3] P. Beame, M. David, T. Pitassi, and P. Woelfel. Separating deterministic from nondeterministic nof multiparty communication complexity. In ICALP, pages 134-145, 2007.

[4] P. Beame, P. Pitassi, and N. Segerlind. Lower bounds for lovasz-schrijver systems and beyond follow from multiparty communication complexity. In Proceedings from Thirty-second ICALP. IEEE, 2005. [OpenAIRE]

[5] Ashok K. Chandra, Merrick L. Furst, and Richard J. Lipton. Multi-party protocols. In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, pages 94-99, Boston, MA, April 1983. [OpenAIRE]

[6] A. Chattopadhyay. Discrepancy and the power of bottom fan-in in depth-three circuits. In IEEE FOCS, 2007.

[7] A. Chattopadhyay and A. Ada. Multiparty communication complexity of disjointness. In Electronic Colloquium on Computational Complexity TR08-002, 2008.

[8] F. Chung and P. Tetali. Communication complexity and quasi-randomness. SIAM J. Discrete Math., 6(1):110-123, 1993.

[9] Johan Ha˚stad and M. Goldmann. On the power of small-depth threshold circuits. In Proceedings 31st Annual Symposium on Foundations of Computer Science, pages 610-618, St. Louis, MO, October 1990. IEEE.

[10] T. Lee and A. Shraibman. Disjointness is hard in the multiparty number-on-forehead model. In Electronic Colloquium on Computational Complexity TR08-003, 2008.

chevron_left
1
2
chevron_right

Impact byBIP!

	citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	0
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average

	citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	0
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average

BIP!

Found an issue? Give us feedback

Average

Funded by

NSERC