License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.606
URN: urn:nbn:de:0030-drops-53266
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5326/
Go to the corresponding LIPIcs Volume Portal

Brody, Joshua ; Sanchez, Mario

Dependent Random Graphs and Multi-Party Pointer Jumping

pdf-format:
36.pdf (0.6 MB)

Abstract

We initiate a study of a relaxed version of the standard Erdos-Renyi random graph model, where each edge may depend on a few other edges. We call such graphs "dependent random graphs". Our main result in this direction is a thorough understanding of the clique number of dependent random graphs. We also obtain bounds for the chromatic number. Surprisingly, many of the standard properties of random graphs also hold in this relaxed setting. We show that with high probability, a dependent random graph will contain a clique of size ((1-o(1))log(n))/log(1/p), and the chromatic number will be at most (nlog(1/(1-p)))/log(n). We expect these results to be of independent interest. As an application and second main result, we give a new communication protocol for the k-player Multi-Party Pointer Jumping problem (MPJk) in the number-on-the-forehead (NOF) model. Multi-Party Pointer Jumping is one of the canonical NOF communication problems, yet even for three players, its communication complexity is not well understood. Our protocol for MPJ3 costs O((n * log(log(n)))/log(n)) communication, improving on a bound from [BrodyChakrabarti08]. We extend our protocol to the non-Boolean pointer jumping problem, achieving an upper bound which is o(n) for any k >= 4 players. This is the first o(n) protocol and improves on a bound of Damm, Jukna, and Sgall, which has stood for almost twenty years.

BibTeX - Entry

@InProceedings{brody_et_al:LIPIcs:2015:5326,
  author =	{Joshua Brody and Mario Sanchez},
  title =	{{Dependent Random Graphs and Multi-Party Pointer Jumping}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{606--624},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Naveen Garg and Klaus Jansen and Anup Rao and Jos{\'e} D. P. Rolim},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5326},
  URN =		{urn:nbn:de:0030-drops-53266},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.606},
  annote =	{Keywords: random graphs, communication complexity, number-on-the-forehead model, pointer jumping}
}

Keywords: random graphs, communication complexity, number-on-the-forehead model, pointer jumping
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)
Issue Date: 2015
Date of publication: 13.08.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI