Fetching the paper…

Reading the bibliography…

2020

A simpler strong refutation of random $k$-XOR

Ahn, Kwangjun

Original
PDF
Post on X

Understand

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 algorithm and analysis.

A simpler strong refutation of random $k$-XOR · Around

Built on

The performance of an eigenvalue bound on the max-cut problem in some classes of graphs
Charles Delorme and Svatopluk Poljak · 1993
Earlier work this paper cites.
Strong refutation heuristics for random k k -SAT
Amin Coja-Oghlan, Andreas Goerdt, and André Lanka · 2007
Earlier work this paper cites.
User-friendly tail bounds for sums of random matrices
Joel A Tropp · 2012
Earlier work this paper cites.

Similar

How to refute a random CSP
Sarah R Allen, Ryan O’Donnell, and David Witmer · 2015
Cited alongside, same era.
Noisy tensor completion via the sum-of-squares hierarchy
Boaz Barak and Ankur Moitra · 2016
Cited alongside, same era.
Sum-of-Squares Certificates for Maxima of Random Tensors on the Sphere
Vijay Bhattiprolu, Venkatesan Guruswami, and Euiwoong Lee · 2017
Cited alongside, same era.

Then

Strongly refuting random CSPs below the spectral threshold
Prasad Raghavendra, Satish Rao, and Tselil Schramm · 2017
Later among the works it cites.
The kikuchi hierarchy and tensor pca
Alexander S Wein, Ahmed El Alaoui, and Cristopher Moore · 2019
Later among the works it cites.
Graph matrices: Norm bounds and applications
Kwangjun Ahn, Dhruv Medarametla, and Aaron Potechin · 2020
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…