arxiv: 2605.05618 · v1 · submitted 2026-05-07 · 💻 cs.DS · cs.CC· cs.DM· math.CO· math.PR

Recognition: unknown

Algorithmic Phase Transition for Large Independent Sets in Dense Hypergraphs

Abhishek Dhawan, Bayram A. \c{S}ahin, Eren C. K{\i}z{\i}lda\u{g}, Neeladri Maitra, Nhi U. Dinh

Authors on Pith no claims yet

Pith reviewed 2026-05-08 06:17 UTC · model grok-4.3

classification 💻 cs.DS cs.CCcs.DMmath.COmath.PR

keywords dense random hypergraphsindependent setsonline algorithmsapproximation factorsErdős-Rényi hypergraphsr-partite hypergraphsalgorithmic thresholdscomputational gaps

0 comments

The pith

Online algorithms achieve tight multiplicative approximations for the largest independent sets in dense random hypergraphs and prove no online method can do better.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes the size of the largest independent set in two dense hypergraph models and shows that online algorithms attain specific approximation factors while proving these factors are optimal. For uniform r-uniform Erdős-Rényi hypergraphs the factor is r to the power 1 over r minus 1; for the r-partite balanced case it is the inverse of the largest coordinate in the balance vector γ raised to 1 over r minus 1. A sympathetic reader cares because dense regimes rely on online methods rather than the local or low-degree polynomial approaches that succeed in sparse settings, revealing sharp computational thresholds that separate the two regimes.

Core claim

In dense r-uniform Erdős-Rényi hypergraphs the maximum independent set size is pinpointed exactly, and online algorithms achieve a multiplicative approximation factor of r^{1/(r-1)}. In dense r-uniform r-partite hypergraphs the analogous factor for γ-balanced independent sets is (max_i γ_i)^{-1/(r-1)}. Matching lower bounds prove that no online algorithm can exceed these factors, establishing that the gaps are sharp.

What carries the argument

Online algorithms that make irrevocable decisions on vertex inclusion without requiring stability, applied to dense Erdős-Rényi hypergraph models to achieve and match the approximation factors.

If this is right

The exact size of the largest independent set is known asymptotically in both models.
The stated multiplicative factors are the best possible performance any online algorithm can guarantee.
No online algorithm can improve upon these ratios even slightly.
Low-degree polynomial methods are not needed or expected to work in these dense settings.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same online technique could be tested on finite but large hypergraphs to measure how quickly the asymptotic factors appear.
Other dense random combinatorial structures may admit similar sharp online thresholds.
The separation between sparse and dense regimes suggests density itself dictates which algorithmic paradigms become tight.

Load-bearing premise

The dense Erdős-Rényi hypergraph models together with the online algorithm restriction correctly capture the fundamental limits on finding large independent sets.

What would settle it

An explicit online algorithm that achieves a strictly smaller approximation factor than r^{1/(r-1)} on large instances of dense r-uniform Erdős-Rényi hypergraphs would disprove the lower bound.

read the original abstract

We study the algorithmic tractability of finding large independent sets in dense random hypergraphs. In the sparse regime, much of the natural algorithms can be formulated within either the local or the low-degree polynomial (LDP) framework, and a rich literature has subsequently identified nearly sharp algorithmic thresholds within these classes by exploiting their stability. In the dense setting, however, the algorithmic paradigms are fundamentally different: they are online and thus need not be stable. Perhaps more crucially, even for the classical Erd\H{o}s-R\'enyi random graph $G(n,p)$, LDPs are conjectured to fail in the 'easy' regime accessible to online algorithms, thereby challenging their viability for dense models. Our focus is on two models: (i) finding large independent sets in dense $r$-uniform Erd\H{o}s-R\'enyi hypergraphs, and (ii) the more challenging problem of finding large $\gamma$-balanced independent sets in dense $r$-uniform $r$-partite hypergraphs, where the $i$-th coordinate of $\gamma\in\mathbb{Q}^r$ specifies the proportion of vertices from $V_i$ in the independent set. For both models, we pinpoint the size of the largest independent set and design online algorithms that achieve a multiplicative approximation factor of $r^{1/(r-1)}$ in the uniform and $(\max_i \gamma_i)^{-1/(r-1)}$ in the $r$-partite model. Furthermore, we establish matching algorithmic lower bounds, showing that these computational gaps are sharp: no online algorithms can breach these gaps.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper gives exact independence numbers w.h.p. for dense r-uniform ER hypergraphs and balanced r-partite versions, plus online algorithms hitting the factors r^{1/(r-1)} and (max γ_i)^{-1/(r-1)} with matching lower bounds.

read the letter

The core result is that in these dense models the largest independent set has a precise size that a simple first-moment argument pins down, and there is an online greedy procedure that gets within the stated multiplicative factor of that size. The lower bound comes from an adversary that forces any online rule to lose that factor on a positive fraction of vertices. This is new because the dense regime forces online algorithms rather than the local or low-degree methods that dominate the sparse literature, and the paper shows the gaps are tight for the online class. The analysis uses standard tools: first-moment for the upper bound on the independence number, differential equations or martingales for the algorithm's performance, and a direct adversary construction for the impossibility result. No appeal to unproven LDPs or stability assumptions appears in the argument. The main limitation is that everything is restricted to online algorithms, so the computational gap they prove does not rule out better non-online methods. The models themselves are the standard dense ER and balanced partite hypergraphs, which is fine for the theoretical question but leaves open how much carries over to other dense hypergraph distributions. The citation pattern looks clean; they position the work against the sparse results without over-claiming. This is the kind of paper that researchers working on random hypergraph algorithms or online approximation will want to see. It is coherent on its own terms and the claims are backed by explicit calculations rather than fitting. I would send it to a serious referee.

Referee Report

0 major / 2 minor

Summary. The paper studies algorithmic tractability of large independent sets in dense random hypergraphs. It considers two models: dense r-uniform Erdős-Rényi hypergraphs and dense r-uniform r-partite hypergraphs, where the goal is to find large γ-balanced independent sets. The central claims are that the independence number is pinpointed exactly (w.h.p.) via first-moment calculations in both models; that explicit online algorithms achieve multiplicative approximation factors of r^{1/(r-1)} (uniform case) and (max_i γ_i)^{-1/(r-1)} (partite case), analyzed via differential equations or martingales; and that matching lower bounds are established via adversary constructions showing no online algorithm can improve on these factors.

Significance. If the results hold, the work provides sharp, explicit algorithmic thresholds for online algorithms in dense hypergraph models, contrasting with the stability-based analysis typical in sparse regimes. It directly addresses the conjecture that LDPs fail in dense 'easy' regimes by exhibiting tight online algorithms and lower bounds without relying on unproven LDPs or hidden stability assumptions. Strengths include the parameter-free first-moment upper bound on the independence number, the concrete greedy online procedure, and the adversary argument establishing computational gaps. This advances the understanding of how algorithmic paradigms shift from sparse to dense random structures and supplies falsifiable, constructive predictions for online performance.

minor comments (2)

The abstract mentions the failure of LDPs in dense regimes but does not cite the specific conjecture or prior work; adding a reference would improve context for readers unfamiliar with the sparse-vs-dense distinction.
Notation for the γ-balanced independent set and the online decision rule could be introduced with a brief formal definition in the introduction to aid readability before the technical sections.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive and encouraging review, which recommends acceptance of the manuscript. We appreciate the referee's recognition of the significance of our results on sharp algorithmic thresholds for online algorithms in dense hypergraph models, the contrast with sparse regimes, and the constructive nature of the predictions.

Circularity Check

0 steps flagged

No circularity: direct first-moment upper bound, explicit greedy online algorithm, and adversary lower bound are self-contained.

full rationale

The paper derives the independence number via a standard first-moment calculation on the dense ER hypergraph model, constructs an explicit online greedy procedure whose approximation ratio is analyzed via differential equations or martingales, and proves matching lower bounds via an adversary that forces any online algorithm to lose the factor on a positive-density set. None of these steps reduce to fitted parameters, self-definitions, or load-bearing self-citations; the online paradigm is chosen precisely because it differs from the LDP framework used in sparse regimes, with no ansatz smuggled in or uniqueness theorem imported from prior author work. The derivation chain is therefore independent of its own outputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard definitions of dense random hypergraph models and the distinction between online and stable algorithms; no free parameters or invented entities are apparent from the abstract.

axioms (2)

domain assumption Dense random r-uniform Erdős-Rényi hypergraphs and r-partite variants are the models under study
Defines the input distribution for both problems studied.
domain assumption Online algorithms form the relevant class for tractability analysis in the dense regime
Paper states that dense setting requires online paradigms as LDPs are conjectured to fail.

pith-pipeline@v0.9.0 · 5630 in / 1410 out tokens · 112466 ms · 2026-05-08T06:17:33.350417+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

111 extracted references · 27 canonical work pages · 2 internal anchors

[1]

Algorithmic barriers from phase transitions

Dimitris Achlioptas and Amin Coja-Oghlan. “Algorithmic barriers from phase transitions”. In:2008 49th Annual IEEE Symposium on Foundations of Computer Science. IEEE. 2008, pp. 793–802 (cit. on pp. 7, 12)

2008
[2]

Random k-SAT: Two moments suffice to cross a sharp threshold

Dimitris Achlioptas and Cristopher Moore. “Random k-SAT: Two moments suffice to cross a sharp threshold”. In:SIAM Journal on Computing36.3 (2006), pp. 740–762 (cit. on p. 12)

2006
[3]

On the solution-space geometry of ran- dom constraint satisfaction problems

Dimitris Achlioptas and Federico Ricci-Tersenghi. “On the solution-space geometry of ran- dom constraint satisfaction problems”. In:Proceedings of the thirty-eighth annual ACM symposium on Theory of computing. 2006, pp. 130–139 (cit. on pp. 7, 12)

2006
[4]

SDP-based algorithms for maximum independent set problems on hypergraphs

Geir Agnarsson, Magn´ us M Halld´ orsson, and Elena Losievskaja. “SDP-based algorithms for maximum independent set problems on hypergraphs”. In:Theoretical Computer Science470 (2013), pp. 1–9 (cit. on p. 12). 36

2013
[5]

Generating hard instances of lattice problems

Mikl´ os Ajtai. “Generating hard instances of lattice problems”. In:Proceedings of the twenty- eighth annual ACM symposium on Theory of computing. 1996, pp. 99–108 (cit. on p. 12)

1996
[6]

Extremal un- crowded hypergraphs

Mikl´ os Ajtai, J´ anos Koml´ os, Janos Pintz, Joel Spencer, and Endre Szemer´ edi. “Extremal un- crowded hypergraphs”. In:Journal of Combinatorial Theory, Series A32.3 (1982), pp. 321– 335 (cit. on pp. 3, 8)

1982
[7]

John Wiley & Sons, 2016 (cit

Noga Alon and Joel H Spencer.The probabilistic method. John Wiley & Sons, 2016 (cit. on p. 5)

2016
[8]

Two sufficient conditions for the existence of hamiltonian cycles in bipartite graphs

P. Ash. “Two sufficient conditions for the existence of hamiltonian cycles in bipartite graphs”. In:Ars Comb. A16 (1983), pp. 33–37 (cit. on p. 9)

1983
[9]

Bipartite independence number in graphs with bounded maximum degree

M. Axenovich, J.S. Sereni, R. Snyder, and L. Weber. “Bipartite independence number in graphs with bounded maximum degree”. In:SIAM Journal on Discrete Mathematics35.2 (2021), pp. 1136–1148 (cit. on p. 9)

2021
[10]

The bipartite k2, 2-free process and bipartite ramsey number b (2, t)

Deepak Bal and Patrick Bennett. “The bipartite k2, 2-free process and bipartite ramsey number b (2, t)”. In:Electronic Journal of Combinatorics27.4 (2020), pp. 1–13 (cit. on p. 9)

2020
[11]

Notes on computational-to- statistical gaps: predictions using statistical physics

Afonso S Bandeira, Amelia Perry, and Alexander S Wein. “Notes on computational-to- statistical gaps: predictions using statistical physics”. In:arXiv preprint arXiv:1803.11132 (2018) (cit. on pp. 2, 12)

work page arXiv 2018
[12]

Finding a dense submatrix of a random matrix. Sharp bounds for online algorithms

Shankar Bhamidi, David Gamarnik, and Shuyang Gong. “Finding a dense submatrix of a random matrix. Sharp bounds for online algorithms”. In:arXiv preprint arXiv:2507.19259 (2025) (cit. on pp. 12, 13)

work page arXiv 2025
[13]

The strong chromatic index ofK {t, t}-free graphs

Richard Bi, Peter Bradshaw, Abhishek Dhawan, and Jingwei Xu. “The strong chromatic index ofK {t, t}-free graphs”.https://arxiv.org/abs/2603.15207(preprint). 2026 (cit. on p. 8)

work page arXiv 2026
[14]

The Average-Case Complexity of Counting Cliques in Erd¨ os-R´ enyi Hypergraphs

Enric Boix-Adser` a, Matthew Brennan, and Guy Bresler. “The Average-Case Complexity of Counting Cliques in Erd¨ os-R´ enyi Hypergraphs”. In:SIAM Journal on Computing0 (2021), FOCS19–39 (cit. on p. 12)

2021
[15]

The diameter of random graphs

B´ ela Bollob´ as. “The diameter of random graphs”. In:Transactions of the American Math- ematical Society267.1 (1981), pp. 41–52 (cit. on p. 8)

1981
[16]

B´ ela Bollob´ as.Random Graphs. 2nd ed. Cambridge Studies in Advanced Mathematics. Cam- bridge University Press, 2001 (cit. on p. 2)

2001
[17]

Cliques in random graphs

B´ ela Bollob´ as and Paul Erd¨ os. “Cliques in random graphs”. In:Mathematical Proceedings of the Cambridge Philosophical Society. Vol. 80. 3. Cambridge University Press. 1976, pp. 419– 427 (cit. on p. 1)

1976
[18]

Cores of random r-partite hy- pergraphs

Fabiano C Botelho, Nicholas Wormald, and Nivio Ziviani. “Cores of random r-partite hy- pergraphs”. In:Information Processing Letters112.8-9 (2012), pp. 314–319 (cit. on p. 12)

2012
[19]

Matchings in multipartite hypergraphs

Candida Bowtell and Richard Mycroft. “Matchings in multipartite hypergraphs”.https: //arxiv.org/abs/2403.05219. 2024 (cit. on p. 12)

work page arXiv 2024
[20]

The Algorithmic Phase Transition of Randomk-SAT for Low Degree Polynomials

Guy Bresler and Brice Huang. “The Algorithmic Phase Transition of Randomk-SAT for Low Degree Polynomials”. In:arXiv preprint arXiv:2106.02129(2021) (cit. on pp. 7, 12). 37

work page arXiv 2021
[21]

Extremal bipartite independence number and balanced coloring

D. Chakraborti. “Extremal bipartite independence number and balanced coloring”. In:Eu- ropean Journal of Combinatorics113 (2023), p. 103750 (cit. on p. 9)

2023
[22]

Suboptimal- ity of local algorithms for a class of max-cut problems

Wei-Kuo Chen, David Gamarnik, Dmitry Panchenko, and Mustazee Rahman. “Suboptimal- ity of local algorithms for a class of max-cut problems”. In:The Annals of Probability47.3 (2019), pp. 1587–1618 (cit. on p. 12)

2019
[23]

On independent sets in random graphs

Amin Coja-Oghlan and Charilaos Efthymiou. “On independent sets in random graphs”. In: Random Structures & Algorithms47.3 (2015), pp. 436–486 (cit. on p. 2)

2015
[24]

Hypergraph independent sets

Jonathan Cutler and AJ Radcliffe. “Hypergraph independent sets”. In:Combinatorics, Prob- ability and Computing22.1 (2013), pp. 9–20 (cit. on p. 8)

2013
[25]

Graph structure via local occupancy,https://arxiv.org/abs/2003.14361 (preprint), 2020 (cit

E. Davies, R.J. Kang, F. Pirot, and J.-S. Sereni. “Graph structure via local occupancy”. https://arxiv.org/abs/2003.14361(preprint). 2020 (cit. on p. 3)

work page arXiv 2003
[26]

Balanced independent sets and colorings of hypergraphs

Abhishek Dhawan. “Balanced independent sets and colorings of hypergraphs”. In:Journal of Graph Theory109.1 (2025), pp. 43–51 (cit. on p. 9)

2025
[27]

List colorings ofk-partitek-graphs

Abhishek Dhawan. “List colorings ofk-partitek-graphs”. In:Electronic Journal of Combi- natorics32.2 (2025), p. 2.16 (cit. on p. 12)

2025
[28]

Fractional coloring via entropy

Abhishek Dhawan. “Fractional coloring via entropy”.https://arxiv.org/abs/2603.17730 (preprint). 2026 (cit. on pp. 3, 8)

work page internal anchor Pith review Pith/arXiv arXiv 2026
[29]

Independent sets and colorings ofK t,t,t-free graphs

Abhishek Dhawan, Oliver Janzer, and Abhishek Methuku. “Independent sets and colorings ofK t,t,t-free graphs”.https://arxiv.org/abs/2511.17191(preprint). 2025 (cit. on p. 3)

work page arXiv 2025
[30]

Sharp Online Hardness for Large Balanced Independent Sets

Abhishek Dhawan, Eren C Kızılda˘ g, and Neeladri Maitra. “Sharp Online Hardness for Large Balanced Independent Sets”. In:arXiv preprint arXiv:2508.20785(2025) (cit. on pp. 2, 5, 7, 8, 12, 13)

work page arXiv 2025
[31]

Detection of Dense Subhypergraphs by Low-Degree Polynomials

Abhishek Dhawan, Cheng Mao, and Alexander S Wein. “Detection of Dense Subhypergraphs by Low-Degree Polynomials”. In:Random Structures & Algorithms66.1 (2025), e21279 (cit. on p. 12)

2025
[32]

The low-degree hardness of finding large independent sets in sparse random hypergraphs

Abhishek Dhawan and Yuzhou Wang. “The low-degree hardness of finding large independent sets in sparse random hypergraphs”. In:SIAM Journal on Discrete Mathematics40.1 (2026), pp. 374–419 (cit. on pp. 1–3, 5–12)

2026
[33]

The algorithmic phase transition of random graph alignment problem

Hang Du, Shuyang Gong, and Rundong Huang. “The algorithmic phase transition of random graph alignment problem”. In:Probability Theory and Related Fields(2025), pp. 1–56 (cit. on pp. 12, 13)

2025
[34]

Relations between average case complexity and approximation complexity

Uriel Feige. “Relations between average case complexity and approximation complexity”. In:Proceedings of the thiry-fourth annual ACM symposium on Theory of computing. 2002, pp. 534–543 (cit. on p. 3)

2002
[35]

Hardness of approximation of the balanced complete bipar- tite subgraph problem

Uriel Feige and Shimon Kogan. “Hardness of approximation of the balanced complete bipar- tite subgraph problem”. In:Dept. Comput. Sci. Appl. Math., Weizmann Inst. Sci., Rehovot, Israel, Tech. Rep. MCS04-04(2004) (cit. on p. 3)

2004
[36]

On the hardness of computing the permanent of random matrices

Uriel Feige and Carsten Lund. “On the hardness of computing the permanent of random matrices”. In:Proceedings of the twenty-fourth annual ACM symposium on Theory of com- puting. ACM. 1992, pp. 643–654 (cit. on p. 9). 38

1992
[37]

Coloring powers of random graphs

Alan Frieze, Ross Kang, Aditya Raut, Michelle Sweering, and Hilde Verbeek. “Coloring powers of random graphs”.https://arxiv.org/abs/2604.14006(preprint). 2026 (cit. on p. 8)

work page internal anchor Pith review Pith/arXiv arXiv 2026
[38]

Algorithmic theory of random graphs

Alan Frieze and Colin McDiarmid. “Algorithmic theory of random graphs”. In:Random Structures & Algorithms10.1-2 (1997), pp. 5–42 (cit. on p. 2)

1997
[39]

Coloring simple hypergraphs

Alan Frieze and Dhruv Mubayi. “Coloring simple hypergraphs”. In:Journal of Combinato- rial Theory, Series B103.6 (2013), pp. 767–794 (cit. on pp. 3, 8)

2013
[40]

Random k-SAT: A tight threshold for moderately growing k

Alan Frieze and Nicholas C Wormald. “Random k-SAT: A tight threshold for moderately growing k”. In:Combinatorica25.3 (2005), pp. 297–306 (cit. on p. 2)

2005
[41]

On the independence number of random graphs

Alan M Frieze. “On the independence number of random graphs”. In:Discrete Mathematics 81.2 (1990), pp. 171–175 (cit. on p. 2)

1990
[42]

Computing the partition function of the Sherrington-Kirkpatrick model is hard on average

David Gamarnik. “Computing the partition function of the Sherrington-Kirkpatrick model is hard on average”. In:arXiv preprint arXiv:1810.05907(2018) (cit. on p. 12)

work page arXiv 2018
[43]

The overlap gap property: A topological barrier to optimizing over ran- dom structures

David Gamarnik. “The overlap gap property: A topological barrier to optimizing over ran- dom structures”. In:Proceedings of the National Academy of Sciences118.41 (2021) (cit. on pp. 2, 7, 12)

2021
[44]

Turing in the shadows of Nobel and Abel: an algorithmic story behind two recent prizes

David Gamarnik. “Turing in the shadows of Nobel and Abel: an algorithmic story behind two recent prizes”. In:arXiv preprint arXiv:2501.15312(2025) (cit. on pp. 2, 12)

work page arXiv 2025
[45]

The overlap gap property and approximate mes- sage passing algorithms forp-spin models

David Gamarnik and Aukosh Jagannath. “The overlap gap property and approximate mes- sage passing algorithms forp-spin models”. In:The Annals of Probability49.1 (2021), pp. 180–205 (cit. on p. 12)

2021
[46]

Shattering in the Ising p-spin glass model

David Gamarnik, Aukosh Jagannath, and Eren C Kızılda˘ g. “Shattering in the Ising p-spin glass model”. In:Probability Theory and Related Fields193.1 (2025), pp. 89–141 (cit. on p. 12)

2025
[47]

Low-degree hardness of ran- dom optimization problems

David Gamarnik, Aukosh Jagannath, and Alexander S Wein. “Low-degree hardness of ran- dom optimization problems”. In:2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS). IEEE. 2020, pp. 131–140 (cit. on pp. 2, 7, 12, 13)

2020
[48]

Circuit Lower Bounds for the p-Spin Optimization Problem

David Gamarnik, Aukosh Jagannath, and Alexander S Wein. “Circuit Lower Bounds for the p-Spin Optimization Problem”. In:arXiv preprint arXiv:2109.01342(2021) (cit. on p. 13)

work page arXiv 2021
[49]

Geometric barriers for stable and online algorithms for discrepancy minimization

David Gamarnik, Eren C Kizilda˘ g, Will Perkins, and Changji Xu. “Geometric barriers for stable and online algorithms for discrepancy minimization”. In:The Thirty Sixth Annual Conference on Learning Theory. PMLR. 2023, pp. 3231–3263 (cit. on pp. 12, 13)

2023
[50]

Algorithmic obstructions in the random number partitioning problem

David Gamarnik and Eren C Kızılda˘ g. “Algorithmic obstructions in the random number partitioning problem”. In:The Annals of Applied Probability33.6B (2023), pp. 5497–5563 (cit. on p. 12)

2023
[51]

Algorithms and barriers in the symmetric binary perceptron model

David Gamarnik, Eren C Kızılda˘ g, Will Perkins, and Changji Xu. “Algorithms and barriers in the symmetric binary perceptron model”. In:2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS). IEEE. 2022, pp. 576–587 (cit. on pp. 12, 13)

2022
[52]

Optimal Hardness of Online Algo- rithms for Large Independent Sets

David Gamarnik, Eren C Kızılda˘ g, and Lutz Warnke. “Optimal Hardness of Online Algo- rithms for Large Independent Sets”. In:arXiv preprint arXiv:2504.11450(2025) (cit. on pp. 2, 5–8, 12, 13, 18). 39

work page arXiv 2025
[53]

Finding a large submatrix of a Gaussian random matrix

David Gamarnik and Quan Li. “Finding a large submatrix of a Gaussian random matrix”. In:The Annals of Statistics46.6A (2018), pp. 2511–2561 (cit. on p. 6)

2018
[54]

Disordered systems insights on computational hardness

David Gamarnik, Cristopher Moore, and Lenka Zdeborov´ a. “Disordered systems insights on computational hardness”. In:Journal of Statistical Mechanics: Theory and Experiment 2022.11 (2022), p. 114015 (cit. on pp. 2, 3, 12)

2022
[55]

Limits of local algorithms over sparse random graphs

David Gamarnik and Madhu Sudan. “Limits of local algorithms over sparse random graphs”. In:Proceedings of the 5th conference on Innovations in theoretical computer science. 2014, pp. 369–376 (cit. on pp. 2, 5–7, 12)

2014
[56]

Limits of local algorithms over sparse random graphs

David Gamarnik and Madhu Sudan. “Limits of local algorithms over sparse random graphs”. In:Ann. Probab.45.4 (July 2017), pp. 2353–2376.doi:10.1214/16-AOP1114.url:https: //doi.org/10.1214/16-AOP1114(cit. on pp. 6, 7, 12)

work page doi:10.1214/16-aop1114.url:https: 2017
[57]

Performance of sequential local algorithms for the random NAE-K-SAT problem

David Gamarnik and Madhu Sudan. “Performance of sequential local algorithms for the random NAE-K-SAT problem”. In:SIAM Journal on Computing46.2 (2017), pp. 590–619 (cit. on p. 12)

2017
[58]

On colouring random graphs

G. R. Grimmett and C. J. H. McDiarmid. “On colouring random graphs”. In:Mathematical Proceedings of the Cambridge Philosophical Society77.2 (1975), pp. 313–324.doi:10.1017/ S0305004100051124(cit. on p. 1)

1975
[59]

Inapproximability of minimum vertex cover on k-uniform k-partite hypergraphs

Venkatesan Guruswami, Sushant Sachdeva, and Rishi Saket. “Inapproximability of minimum vertex cover on k-uniform k-partite hypergraphs”. In:SIAM Journal on Discrete Mathemat- ics29.1 (2015), pp. 36–58 (cit. on p. 12)

2015
[60]

The complexity of finding independent sets in bounded degree (hyper) graphs of low chromatic number

Venkatesan Guruswami and Ali Kemal Sinop. “The complexity of finding independent sets in bounded degree (hyper) graphs of low chromatic number”. In:Proceedings of the Twenty- Second Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM. 2011, pp. 1615–1626 (cit. on p. 12)

2011
[61]

Streaming algorithms for independent sets in sparse hypergraphs

Bjarni V Halld´ orsson, Magn´ us M Halld´ orsson, Elena Losievskaja, and Mario Szegedy. “Streaming algorithms for independent sets in sparse hypergraphs”. In:Algorithmica76 (2016), pp. 490–501 (cit. on p. 12)

2016
[62]

Independent sets in bounded-degree hyper- graphs

Magn´ us M Halld´ orsson and Elena Losievskaja. “Independent sets in bounded-degree hyper- graphs”. In:Discrete applied mathematics157.8 (2009), pp. 1773–1786 (cit. on p. 12)

2009
[63]

Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs

Eran Halperin. “Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs”. In:SIAM Journal on Computing31.5 (2002), pp. 1608–1623 (cit. on p. 12)

2002
[64]

Clique is hard to approximate withinn 1−ϵ

Johan H˚ astad. “Clique is hard to approximate withinn 1−ϵ”. In:Acta Mathematica182.1 (1999), pp. 105–142 (cit. on p. 1)

1999
[65]

Limits of locally–globally convergent graph sequences

Hamed Hatami, L´ aszl´ o Lov´ asz, and Bal´ azs Szegedy. “Limits of locally–globally convergent graph sequences”. In:Geometric and Functional Analysis24.1 (2014), pp. 269–296 (cit. on p. 7)

2014
[66]

Introduction to online convex optimization

Elad Hazan et al. “Introduction to online convex optimization”. In:Foundations and Trends®in Optimization2.3-4 (2016), pp. 157–325 (cit. on p. 13)

2016
[67]

Statistical inference and the sum of squares method

Samuel Brink Klevit Hopkins. “Statistical inference and the sum of squares method”. In: (2018) (cit. on p. 2). 40

2018
[68]

Tight Lipschitz Hardness for Optimizing Mean Field Spin Glasses

Brice Huang and Mark Sellke. “Tight Lipschitz Hardness for Optimizing Mean Field Spin Glasses”. In:arXiv preprint arXiv:2110.07847(2021) (cit. on pp. 7, 12)

work page arXiv 2021
[69]

Algorithmic threshold for multi-species spherical spin glasses

Brice Huang and Mark Sellke. “Algorithmic threshold for multi-species spherical spin glasses”. In:arXiv preprint arXiv:2303.12172(2023) (cit. on pp. 7, 12)

work page arXiv 2023
[70]

Strong Low Degree Hardness for Stable Local Optima in Spin Glasses

Brice Huang and Mark Sellke. “Strong Low Degree Hardness for Stable Local Optima in Spin Glasses”. In:arXiv preprint arXiv:2501.06427(2025) (cit. on pp. 2, 5, 7, 12)

work page arXiv 2025
[71]

Large cliques elude the Metropolis process

Mark Jerrum. “Large cliques elude the Metropolis process”. In:Random Structures & Al- gorithms3.4 (1992), pp. 347–359 (cit. on p. 1)

1992
[72]

Sum-of-squares lower bounds for densest k-subgraph

Chris Jones, Aaron Potechin, Goutham Rajendran, and Jeff Xu. “Sum-of-squares lower bounds for densest k-subgraph”. In:Proceedings of the 55th Annual ACM Symposium on Theory of Computing. 2023, pp. 84–95 (cit. on p. 12)

2023
[73]

The distance-t chromatic index of graphs

Tom´ aˇ s Kaiser and Ross J Kang. “The distance-t chromatic index of graphs”. In:Combina- torics, Probability and Computing23.1 (2014), pp. 90–101 (cit. on p. 8)

2014
[74]

Bounded colorings of multipartite graphs and hypergraphs

Nina Kamˇ cev, Benny Sudakov, and Jan Volec. “Bounded colorings of multipartite graphs and hypergraphs”. In:European journal of combinatorics66 (2017), pp. 235–249 (cit. on p. 12)

2017
[75]

The probabilistic analysis of some combinatorial search algorithms

Richard M. Karp. “The probabilistic analysis of some combinatorial search algorithms.” In: (1976) (cit. on pp. 1, 5)

1976
[76]

Independent sets in semi-random hyper- graphs

Yash Khanna, Anand Louis, and Rameesh Paul. “Independent sets in semi-random hyper- graphs”. In:Algorithms and Data Structures: 17th International Symposium, WADS 2021, Virtual Event, August 9–11, 2021, Proceedings 17. Springer. 2021, pp. 528–542 (cit. on p. 12)

2021
[77]

Improved inapproximability results for maxclique, chromatic number and approximate graph coloring

Subhash Khot. “Improved inapproximability results for maxclique, chromatic number and approximate graph coloring”. In:Proceedings 42nd IEEE Symposium on Foundations of Computer Science. IEEE. 2001, pp. 600–609 (cit. on p. 1)

2001
[78]

Planted random number partitioning problem

Eren C Kızılda˘ g. “Planted random number partitioning problem”. In:arXiv preprint arXiv:2309.15115(2023) (cit. on p. 12)

work page arXiv 2023
[79]

Sharp Thresholds for the Overlap Gap Property: Isingp-Spin Glass and Randomk-SAT

Eren C Kızılda˘ g. “Sharp Thresholds for the Overlap Gap Property: Isingp-Spin Glass and Randomk-SAT”. In:arXiv preprint arXiv:2309.09913(2025) (cit. on p. 12)

work page arXiv 2025
[80]

Large Average Subtensor Problem: Ground- State, Algorithms, and Algorithmic Barriers

Abhishek Hegade KR and Eren C Kizildag. “Large Average Subtensor Problem: Ground- State, Algorithms, and Algorithmic Barriers”. In:37th International Conference on Algo- rithmic Learning Theory. 2026 (cit. on p. 12)

2026

Showing first 80 references.