REVIEW 1 cited by
A Cheeger Inequality for Small Set Expansion
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
read the original abstract
The discrete Cheeger inequality, due to Alon and Milman (J. Comb. Theory Series B 1985), is an indispensable tool for converting the combinatorial condition of graph expansion to an algebraic condition on the eigenvalues of the graph adjacency matrix. We prove a generalization of Cheeger's inequality, giving an algebraic condition equivalent to small set expansion. This algebraic condition is the p-to-q hypercontractivity of the top eigenspace for the graph adjacency matrix. Our result generalizes a theorem of Barak et al (STOC 2012) to the low small set expansion regime, and has a dramatically simpler proof; this answers a question of Barak (2014).
Forward citations
Cited by 1 Pith paper
-
An Argmax Principle for Sum-of-Squares Relaxations on the Sphere
An argmax principle over high pseudo-moments yields degree-O(sqrt(n/eps)) SoS algorithms for Best Separable State, multiplicative 2->4 norm approximation, and a shorter proof of the known sphere-polynomial convergence bound.
Discussion (0). Continue with ORCID to comment.