Document Open Access Logo

A Simpler Strong Refutation of Random k-XOR

Author Kwangjun Ahn

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2020.2.pdf
  • Filesize: 0.53 MB
  • 15 pages

Document Identifiers

Author Details

Kwangjun Ahn
  • Department of EECS, Massachusetts Institute of Technology, Cambridge, MA, USA

Funding

  • Ahn, Kwangjun: Supported by the the NSF CAREER grant (number: 1846088) and the Kwanjeong Educational Foundation scholarship.

Acknowledgements

The author thanks Vijay Bhattiprolu for suggesting the idea of re-scaling entries of the matrix representation for simpler refutation algorithm. The author also thanks anonymous reviewers for various comments that indeed help the author improve the presentation.

Cite As Get BibTex

Kwangjun Ahn. A Simpler Strong Refutation of Random k-XOR. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 2:1-2:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.2

Abstract

Strong refutation of random CSPs is a fundamental question in theoretical computer science that has received particular attention due to the long-standing gap between the information-theoretic limit and the computational limit. This gap is recently bridged by Raghavendra, Rao and Schramm where they study sub-exponential algorithms for the regime between the two limits. In this work, we take a simpler approach to their algorithms and analyses.

Subject Classification

ACM Subject Classification
  • Theory of computation
Keywords
  • Strong refutation
  • Random k-XOR
  • Spectral method
  • Trace power method

Metrics

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

References

  1. Kwangjun Ahn, Dhruv Medarametla, and Aaron Potechin. Graph matrices: Norm bounds and applications. arXiv, 2020. URL: http://arxiv.org/abs/1604.03423.
  2. Sarah R Allen, Ryan O'Donnell, and David Witmer. How to refute a random CSP. In Proceedings of the 56th FOCS, pages 689-708. IEEE, 2015. Google Scholar
  3. Boaz Barak and Ankur Moitra. Noisy tensor completion via the sum-of-squares hierarchy. In COLT, pages 417-445, 2016. Google Scholar
  4. Vijay Bhattiprolu, Venkatesan Guruswami, and Euiwoong Lee. Sum-of-Squares Certificates for Maxima of Random Tensors on the Sphere. In APPROX/RANDOM 2017, volume 81, pages 31:1-31:20. LIPIcs, 2017. Google Scholar
  5. Amin Coja-Oghlan, Andreas Goerdt, and André Lanka. Strong refutation heuristics for random k-SAT. Combinatorics, Probability and Computing, 16(1):5-28, 2007. Google Scholar
  6. Charles Delorme and Svatopluk Poljak. The performance of an eigenvalue bound on the max-cut problem in some classes of graphs. Discrete Mathematics, 111(1-3):145-156, 1993. Google Scholar
  7. Prasad Raghavendra, Satish Rao, and Tselil Schramm. Strongly refuting random CSPs below the spectral threshold. In Proceedings of the 49th STOC, pages 121-131. ACM, 2017. URL: http://arxiv.org/abs/1605.00058.
  8. Joel A Tropp. User-friendly tail bounds for sums of random matrices. Foundations of computational mathematics, 12(4):389-434, 2012. Google Scholar
  9. Alexander S Wein, Ahmed El Alaoui, and Cristopher Moore. The kikuchi hierarchy and tensor pca. In Proceedings of the 60th FOCS, pages 1446-1468. IEEE, 2019. 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