Aaron Potechin

activity

20242026

collaborators

Showing 2024Show all

3 papers · 1 filter

math.PR2024

Hardness of sampling for the anti-ferromagnetic Ising model on random graphs

Neng Huang, Will Perkins, Aaron Potechin

We prove a hardness of sampling result for the anti-ferromagnetic Ising model on random graphs of average degree $d$ for large constant $d$ , proving that when the normalized invers…

cs.DS2024

Sum-of-Squares Lower Bounds for Independent Set in Ultra-Sparse Random Graphs

Pravesh Kothari, Aaron Potechin, Jeff Xu

We prove that for every $D \in N$ , and large enough constant $d \in N$ , with high probability over the choice of $G \sim G (n, d / n)$ , the \Erdos-\Renyi random graph distribution, t…

cs.CC2024

Clique Is Hard on Average for Sherali-Adams with Bounded Coefficients

Susanna F. de Rezende, Aaron Potechin, Kilian Risse

We prove that Sherali-Adams with polynomially bounded coefficients requires proofs of size $n^{Ω (d)}$ to rule out the existence of an $n^{Θ (1)}$ -clique in Erdős-Rényi random graphs…