Document Open Access Logo

Dependent Random Graphs and Multi-Party Pointer Jumping

Authors Joshua Brody, Mario Sanchez

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2015.606.pdf
  • Filesize: 0.56 MB
  • 19 pages

Document Identifiers

Author Details

Joshua Brody
Mario Sanchez

Cite As Get BibTex

Joshua Brody and Mario Sanchez. Dependent Random Graphs and Multi-Party Pointer Jumping. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 606-624, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.606

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.

Subject Classification

Keywords
  • random graphs
  • communication complexity
  • number-on-the-forehead model
  • pointer jumping

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Noga Alon and Asaf Nussboim. k-wise independent random graphs. In Proc. 49th Annual IEEE Symposium on Foundations of Computer Science, pages 813-822, 2008. Google Scholar
  2. Noga Alon and Joel H. Spencer. The Probabilistic Method. Wiley-Interscience, New York, NY, 2000. Google Scholar
  3. László Babai, Thomas P. Hayes, and Peter G. Kimmel. The cost of the missing bit: Communication complexity with help. Combinatorica, 21(4):455-488, 2001. Google Scholar
  4. Richard Beigel and Jun Tarui. On ACC. Comput. Complexity, 4:350-366, 1994. Google Scholar
  5. Béla Bollobás. The chromatic number of random graphs. Combinatorica, 8(1):49-55, 1988. Google Scholar
  6. Béla Bollobás. Random graphs. Springer, 1998. Google Scholar
  7. Béla Bollobás and Paul Erdős. Cliques in random graphs. Mathematical Proceedings of the Cambridge Philosophical Society, 80:419-427, 11 1976. Google Scholar
  8. Joshua Brody. The maximum communication complexity of multi-party pointer jumping. In Proc. 24th Annual IEEE Conference on Computational Complexity, pages 379-386, 2009. Google Scholar
  9. Joshua Brody and Amit Chakrabarti. Sublinear communication protocols for multi-party pointer jumping and a related lower bound. In Proc. 25th International Symposium on Theoretical Aspects of Computer Science, pages 145-156, 2008. Google Scholar
  10. Amit Chakrabarti. Lower bounds for multi-player pointer jumping. In Proc. 22nd Annual IEEE Conference on Computational Complexity, pages 33-45, 2007. Google Scholar
  11. Ashok K. Chandra, Merrick L. Furst, and Richard J. Lipton. Multi-party protocols. In Proc. 15th Annual ACM Symposium on the Theory of Computing, pages 94-99, 1983. Google Scholar
  12. Carsten Damm, Stasys Jukna, and Jiří Sgall. Some bounds on multiparty communication complexity of pointer jumping. Comput. Complexity, 7(2):109-127, 1998. Preliminary version in Proc. 13th International Symposium on Theoretical Aspects of Computer Science , pages 643-654, 1996. Google Scholar
  13. Devdatt P. Dubhashi and Alessandro Panconesi. Concentration of measure for the analysis of randomized algorithms. Cambridge University Press, 2009. Google Scholar
  14. Paul Erdős and Alfréd Rényi. On random graphs i. Publ. Math. Debrecen, 6:290-297, 1959. Google Scholar
  15. Andre Gronemeier. Nof-multiparty information complexity bounds for pointer jumping. In Proc. 31st International Symposium on Mathematical Foundations of Computer Science, pages 459-470. Springer, 2006. Google Scholar
  16. Johan Håstad and Mikael Goldmann. On the power of small-depth threshold circuits. Comput. Complexity, 1:113-129, 1991. Google Scholar
  17. Svante Janson. Large deviations for sums of partly dependent random variables. Random Structures & Algorithms, 24(3):234-248, 2004. Google Scholar
  18. Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press, Cambridge, 1997. Google Scholar
  19. Pavel Pudlák, Vojtěch Rödl, and Jiří Sgall. Boolean circuits, tensor ranks and communication complexity. SIAM J. Comput., 26(3):605-633, 1997. Google Scholar
  20. Emanuele Viola and Avi Wigderson. One-way multi-party communication lower bound for pointer jumping with applications. In Proc. 48th Annual IEEE Symposium on Foundations of Computer Science, pages 427-437, 2007. Google Scholar
  21. Ryan Williams. Nonuniform acc circuit lower bounds. J. ACM, 61(1):32, 2014. Google Scholar
  22. Andrew C. Yao. On ACC and threshold circuits. In Proc. 31st Annual IEEE Symposium on Foundations of Computer Science, pages 619-627, 1990. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact