Finding Pseudorandom Colorings of Pseudorandom Graphs

Authors Akash Kumar, Anand Louis, Madhur Tulsiani



PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2017.37.pdf
  • Filesize: 481 kB
  • 12 pages

Document Identifiers

Author Details

Akash Kumar
Anand Louis
Madhur Tulsiani

Cite AsGet BibTex

Akash Kumar, Anand Louis, and Madhur Tulsiani. Finding Pseudorandom Colorings of Pseudorandom Graphs. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 37:1-37:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.FSTTCS.2017.37

Abstract

We consider the problem of recovering a planted pseudorandom 3-coloring in expanding and low threshold-rank graphs. Alon and Kahale [SICOMP 1997] gave a spectral algorithm to recover the coloring for a random graph with a planted random 3-coloring. We show that their analysis can be adapted to work when coloring is pseudorandom i.e., all color classes are of equal size and the size of the intersection of the neighborhood of a random vertex with each color class has small variance. We also extend our results to partial colorings and low threshold-rank graphs to show the following: * For graphs on n vertices with threshold-rank r, for which there exists a 3-coloring that is eps-pseudorandom and properly colors the induced subgraph on (1-gamma)n vertices, we show how to recover the coloring for (1 - O(gamma + eps)) n vertices in time (rn)^{O(r)}. * For expanding graphs on n vertices, which admit a pseudorandom 3-coloring properly coloring all the vertices, we show how to recover such a coloring in polynomial time. Our results are obtained by combining the method of Alon and Kahale, with eigenspace enumeration methods used for solving constraint satisfaction problems on low threshold-rank graphs.
Keywords
  • Graph Coloring
  • Expanders
  • Spectral algorithms

Metrics

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

References

  1. Noga Alon and Nabil Kahale. A spectral technique for coloring random 3-colorable graphs. SIAM J. Comput., 26(6):1733-1748, 1997. Google Scholar
  2. Sanjeev Arora, Boaz Barak, and David Steurer. Subexponential algorithms for unique games and related problems. In Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on, pages 563-572. IEEE, 2010. Google Scholar
  3. Sanjeev Arora, Boaz Barak, and David Steurer. Subexponential algorithms for unique games and related problems. Journal of the ACM (JACM), 62(5):42, 2015. Google Scholar
  4. Sanjeev Arora and Eden Chlamtac. New approximation guarantee for chromatic number. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, 2006, pages 215-224, 2006. Google Scholar
  5. Sanjeev Arora and Rong Ge. New tools for graph coloring. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - APPROX 2011 Princeton, NJ, USA, August 17-19, 2011. Proceedings, pages 1-12, 2011. Google Scholar
  6. Avrim Blum. New approximation algorithms for graph coloring. J. ACM, 41(3):470-516, 1994. Google Scholar
  7. Avrim Blum and David R. Karger. An õ(n^3/14)-coloring algorithm for 3-colorable graphs. Inf. Process. Lett., 61(1):49-53, 1997. Google Scholar
  8. Avrim Blum and Joel Spencer. Coloring random and semi-random k-colorable graphs. J. Algorithms, 19(2):204-234, 1995. Google Scholar
  9. Eden Chlamtac. Approximation algorithms using hierarchies of semidefinite programming relaxations. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings, pages 691-701, 2007. Google Scholar
  10. Roee David and Uriel Feige. On the effect of randomness on planted 3-coloring models. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 77-90, 2016. Google Scholar
  11. Irit Dinur, Subhash Khot, Will Perkins, and Muli Safra. Hardness of finding independent sets in almost 3-colorable graphs. In Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on, pages 212-221. IEEE, 2010. Google Scholar
  12. Irit Dinur, Elchanan Mossel, and Oded Regev. Conditional hardness for approximate coloring. SIAM Journal on Computing, 39(3):843-873, 2009. Google Scholar
  13. David R. Karger, Rajeev Motwani, and Madhu Sudan. Approximate graph coloring by semidefinite programming. J. ACM, 45(2):246-265, 1998. Google Scholar
  14. Ken-ichi Kawarabayashi and Mikkel Thorup. Coloring 3-colorable graphs with less than n^1/5 colors. J. ACM, 64(1):4:1-4:23, 2017. Google Scholar
  15. Subhash Khot and Rishi Saket. Hardness of finding independent sets in almost q-colorable graphs. In Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on, pages 380-389. IEEE, 2012. Google Scholar
  16. Terence Tao. Structure and randomness: pages from year one of a mathematical blog. American Mathematical Soc., 2008. Google Scholar
  17. Avi Wigderson. Improving the performance guarantee for approximate graph coloring. Journal of the ACM (JACM), 30(4):729-735, 1983. 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