Pith. sign in

REVIEW 2 major objections 2 minor 242 references

Hardness and Approximation for Coloring Digraphs

T0 review · 2 major / 2 minor · reviewed 2026-05-20 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Approximating the dichromatic number and acyclic number of digraphs is as hard as undirected graph coloring, even restricted to tournaments.

desk verdict The tournament hardness results are the clearest advance, though the reduction details need verification to confirm the gap holds. read the letter →

arxiv 2605.19654 v1 pith:OSNLNSCJ submitted 2026-05-19 cs.DS

Parinya Chalermsook , Harmender Gahlawat , Felix Klingelhoefer , Alantha Newman , Chaoliang Tang This is my paper · ORCID
classification cs.DS
keywords dichromaticnumberacyclicdigraphcoloringapproximationalgorithmshardnessoftournamentsdirectedgraphs
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper establishes that for any ε greater than zero, approximating both the dichromatic number and the acyclic number of a digraph to within a factor of n to the power 1 minus ε is hard, and this holds even when the digraph is a tournament. A sympathetic reader would care because tournaments are the directed analogue of complete graphs, so the result shows that directing the edges does not make these coloring-style problems easier. The authors also give concrete approximation algorithms that work for digraphs whose dichromatic number is bounded by a small constant ℓ, and they derive bounds for two families of dense digraphs expressed in terms of the independence number of the underlying undirected graph.

What carries the argument

The dichromatic number of a digraph, defined as the minimum number of vertex subsets that partition the vertex set so each subset induces an acyclic digraph, together with polynomial-time reductions that preserve the approximation gap from undirected graph coloring.

What would settle it

A polynomial-time algorithm that returns an acyclic induced subdigraph whose size is at least n^ε times the optimum, for some fixed ε>0, on an arbitrary tournament.

Watch

Extended reading notes

Core claim

For every ε > 0 it is hard to approximate both the acyclic number and the dichromatic number up to a factor of n^{1-ε} even when the input is restricted to tournaments. In addition, any ℓ-dicolorable digraph can be colored with at most ℓ n^{1-1/ℓ} colors in O(n^{2ℓ}) time, and improved bounds on the dichromatic number are obtained for digraphs with no directed triangles and for digraphs whose dichromatic number is at most 2, each expressed as a function of the independence number of the underlying undirected graph.

Load-bearing premise

The reductions that establish hardness for undirected graph coloring can be adapted to tournaments while keeping the same approximation gap intact.

Editorial extensions

If this is right

  • Any 2-dicolorable digraph admits a polynomial-time coloring with 2√n colors.
  • The same style of algorithm colors an ℓ-dicolorable digraph with ℓ n^{1-1/ℓ} colors in time O(n^{2ℓ}).
  • For digraphs with no directed triangles the dichromatic number is bounded by a function of the independence number of the underlying undirected graph.
  • The same function-of-independence-number bound holds for every digraph whose dichromatic number is at most 2.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The tournament hardness suggests that many other directed variants of coloring problems may also inherit the full undirected hardness.
  • The polynomial-time √n approximation for 2-dicolorable digraphs raises the question of whether a sub-polynomial approximation is possible when the dichromatic number is fixed.
  • The bounds for triangle-free digraphs invite comparison with known extremal results that relate directed triangle-free graphs to their undirected independence number.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Request a human review

A listed scientist reviews the paper for a fee and the review publishes here regardless of verdict. See the reviewers or get listed.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 2 minor

Summary. The paper studies the dichromatic number vec χ(D) and acyclic number vec α(D) of digraphs from an approximation viewpoint. It proves that for every ε > 0, approximating both parameters to within n^{1-ε} is NP-hard even when restricted to tournaments, via reductions from undirected graph coloring. It also gives an O(n^{2ℓ})-time algorithm that colors any ℓ-dicolorable digraph with at most ℓ · n^{1-1/ℓ} colors (in particular 2√n colors for 2-dicolorable digraphs) and presents improved bounds on vec χ for dense digraphs that are 2-dicolorable or triangle-free, expressed in terms of the independence number α of the underlying undirected graph.

Significance. If the tournament reductions are correct, the hardness result shows that digraph coloring inherits the full inapproximability of undirected coloring even on this highly structured subclass, which is a notable strengthening. The algorithmic results supply explicit, polynomial-time approximations for restricted classes together with concrete time bounds and generalizations of prior tools; these constructive aspects are strengths of the manuscript.

major comments (2)
  1. [§3] §3 (Hardness for Tournaments): The central claim that the n^{1-ε} approximation gap is preserved under reduction to tournaments requires an explicit construction showing how an arbitrary undirected graph G is oriented into a tournament T such that every acyclic set in T corresponds to an independent set in G (and vice versa) without introducing extra acyclic partitions that would shrink the gap. The abstract asserts the extension occurs, but the concrete orientation step and the precise relation between χ(G) and vec χ(T) must be verified to ensure the gap does not collapse by more than a constant factor.
  2. [§4.2] §4.2, Theorem 4.3: the stated bound vec χ(D) ≤ f(α) for triangle-free digraphs is presented as an improvement, yet the precise functional form of f and the quantitative improvement over the best previously known bound (in terms of the exponent or leading constant) are not compared directly; this comparison is needed to assess whether the new algorithm is load-bearing for the claimed advance.
minor comments (2)
  1. [Throughout] Notation: the symbols vec α and vec χ are introduced in the abstract but occasionally appear without the vector arrow in later sections; consistent use throughout would improve readability.
  2. [§4.1] The running-time analysis in the ℓ-dicolorable coloring algorithm cites O(n^{2ℓ}) but does not discuss whether the exponent 2ℓ is tight or can be reduced for fixed small ℓ beyond the ℓ=2 case.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We address the major comments point by point below.

read point-by-point responses

  1. Referee: [§3] §3 (Hardness for Tournaments): The central claim that the n^{1-ε} approximation gap is preserved under reduction to tournaments requires an explicit construction showing how an arbitrary undirected graph G is oriented into a tournament T such that every acyclic set in T corresponds to an independent set in G (and vice versa) without introducing extra acyclic partitions that would shrink the gap. The abstract asserts the extension occurs, but the concrete orientation step and the precise relation between χ(G) and vec χ(T) must be verified to ensure the gap does not collapse by more than a constant factor.

    Authors: Section 3 provides the reduction from undirected graph coloring to the dichromatic number of tournaments. The construction orients the edges of G to form T such that independent sets in G correspond exactly to acyclic sets in T, with the orientation of non-edges chosen to avoid creating additional large acyclic sets that would collapse the gap. This yields χ(G) ≤ vec χ(T) ≤ O(χ(G)), preserving the n^{1-ε} inapproximability factor up to constants. We will expand the explicit description of the orientation rule and the precise gap relation in the revised manuscript for easier verification. revision: yes

  2. Referee: [§4.2] §4.2, Theorem 4.3: the stated bound vec χ(D) ≤ f(α) for triangle-free digraphs is presented as an improvement, yet the precise functional form of f and the quantitative improvement over the best previously known bound (in terms of the exponent or leading constant) are not compared directly; this comparison is needed to assess whether the new algorithm is load-bearing for the claimed advance.

    Authors: Theorem 4.3 states the bound explicitly as a function of α (the independence number of the underlying undirected graph) and the surrounding text notes that the algorithm generalizes and improves prior tools for triangle-free digraphs. To make the quantitative improvement fully transparent, we will add a direct comparison (including the functional form of f and the change in exponent or leading constant relative to the best previous bound) in the revised version. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: hardness via independent reductions, algorithms via explicit constructions

full rationale

The paper derives hardness for tournaments by polynomial-time reductions from known undirected graph coloring hardness results (which predate this work and are externally established). Approximation algorithms are given by direct constructions with explicit time bounds and color guarantees, without fitting parameters to the target quantities or redefining inputs in terms of outputs. No self-citation is load-bearing for the central claims, and no step reduces by construction to its own inputs. The derivation chain is self-contained against external benchmarks.

Assumptions & free parameters 0 free parameters · 0 assumptions · 0 invented entities

This is a pure theoretical computer science paper on complexity and approximation. It introduces no free parameters, no ad-hoc axioms beyond standard graph-theoretic definitions, and no invented entities.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Hardness and Approximation for Coloring Digraphs." pith.science (2026). https://pith.science/paper/OSNLNSCJ

@misc{pith2026260519654,
  author       = {Pith},
  title        = {Pith review of: Hardness and Approximation for Coloring Digraphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/OSNLNSCJ}},
  note         = {Machine review of arXiv:2605.19654}
}
abstract

The dichromatic number $\vec\chi(D)$ of a digraph is the minimum number $k$ such that $V(D)$ can be partitioned into $k$ subsets, each inducing an acyclic digraph. The acyclic number $\vec\alpha(D)$ is the cardinality of a largest induced acyclic subdigraph of $D$. We study these problems from an approximation point of view. We begin with establishing that even when restricted to tournaments, approximating $\vec\chi$ and $\vec\alpha$ remain as challenging as their undirected counterparts on general graphs. Specifically, we establish that for every $\epsilon >0$, it is hard to approximate both $\vec\alpha$ and $\vec\chi$ up to a factor of $n^{1-\epsilon}$ even when restricted to tournaments. We next consider approximate coloring of digraphs in special cases. We begin with establishing that we can color $\ell$-dicolorable digraphs using at most $\ell \cdot n^{1-\frac{1}{\ell}}$ colors in time $O(n^{2\ell})$; in particular, we can color $2$-dicolorable digraphs with $2\sqrt{n}$ colors in polynomial time. We then focus on bounding the dichromatic number of dense digraphs as a function of the independence number $\alpha$ of the underlying graph. We consider two special cases in this regard: digraphs with $\vec\chi(D)\leq 2$ and digraphs that do not contain any directed triangle. For these cases, we present algorithms which generalize and improve existing tools and results.

Figures

Figures reproduced from arXiv: 2605.19654 by the authors.

Figure 1
Figure 1. An illustration of Dσ G(H) after Step 1. Each vertex of G is replaced by a copy of H [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. A (local) view of Dσ G(H) after Step 2. Arcs are added between every pair of vertices in cloud(x) and cloud(y). The directions of these arcs are chosen independently at random where blue and red arcs are oriented to the right and left respectively. 6 [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

242 extracted references · 242 canonical work pages

  1. [1]

    Informs Journal on Computing , volume=

    Coloring graphs using two colors while avoiding monochromatic cycles , author=. Informs Journal on Computing , volume=

    work page

  2. [2]

    Theoretical Computer Science , volume=

    Efficient algorithms for acyclic colorings of graphs , author=. Theoretical Computer Science , volume=. 2000 , publisher=

    work page 2000

  3. [3]

    2025 , month =

    Tung Nguyen , title =. 2025 , month =

    work page 2025

  4. [4]

    Journal of Graph Theory , volume=

    Heroes in oriented complete multipartite graphs , author=. Journal of Graph Theory , volume=

    work page

  5. [5]

    Journal of Combinatorial Theory, Series B , volume=

    The dichromatic number of a digraph , author=. Journal of Combinatorial Theory, Series B , volume=

    work page

  6. [6]

    Aboulker, Pierre and Aubian, Guillaume and Charbit, Pierre and Thomass. (. The Electronic Journal of Combinatorics , volume=31, number = 4, pages=

    work page

  7. [7]

    Linear Algebra and its Applications , volume=

    Eigenvalues and colorings of digraphs , author=. Linear Algebra and its Applications , volume=

    work page

  8. [8]

    SIAM Journal on Computing , volume=

    A min-max theorem on tournaments , author=. SIAM Journal on Computing , volume=

    work page

Show all 242 references
  1. [9]

    Journal of Combinatorial Theory, Series B , volume=

    The removal lemma for tournaments , author=. Journal of Combinatorial Theory, Series B , volume=

  2. [10]

    Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC) , pages=

    Better coloring of 3-Colorable graphs , author=. Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC) , pages=

  3. [11]

    Journal of the ACM , volume=

    Approximate graph coloring by semidefinite programming , author=. Journal of the ACM , volume=

  4. [12]

    Journal of the ACM , volume=

    Improving the performance guarantee for approximate graph coloring , author=. Journal of the ACM , volume=

  5. [13]

    Induced subgraph density

    Nguyen, Tung and Scott, Alex and Seymour, Paul , journal=. Induced subgraph density

  6. [14]

    Pure pairs

    Chudnovsky, Maria and Scott, Alex and Seymour, Paul and Spirkl, Sophie , journal=. Pure pairs

  7. [15]

    Journal of Graph Theory , volume=

    Short proofs of classical theorems , author=. Journal of Graph Theory , volume=

  8. [16]

    Discrete Applied Mathematics , volume=

    Ramsey-type theorems , author=. Discrete Applied Mathematics , volume=

  9. [17]

    Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    Graph products revisited: Tight approximation hardness of induced matching, poset dimension and more , author=. Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

  10. [18]

    Pre-reduction graph products:

    Chalermsook, Parinya and Laekhanukit, Bundit and Nanongkai, Danupon , booktitle=. Pre-reduction graph products:

  11. [19]

    On a problem of

    Nguyen, Tung and Scott, Alex and Seymour, Paul , journal=. On a problem of

  12. [20]

    Journal of Combinatorial Theory, Series B , volume=

    Some results and problems on tournament structure , author=. Journal of Combinatorial Theory, Series B , volume=

  13. [21]

    Combinatorica , volume=

    Coloring dense digraphs , author=. Combinatorica , volume=

  14. [22]

    Journal of Combinatorial Theory, Series B , volume=

    Tournaments and colouring , author=. Journal of Combinatorial Theory, Series B , volume=

  15. [23]

    Journal of Combinatorial Theory, Series B , volume=

    Coloring tournaments: From local to global , author=. Journal of Combinatorial Theory, Series B , volume=

  16. [24]

    Journal of Graph Theory , volume=

    The circular chromatic number of a digraph , author=. Journal of Graph Theory , volume=

  17. [25]

    Theory Of Computing , volume=

    Hardness of Vertex Deletion and Project Scheduling , author=. Theory Of Computing , volume=

  18. [26]

    Theory of Computing , volume=

    Simple proof of hardness of feedback vertex set , author=. Theory of Computing , volume=. 2016 , publisher=

    2016

  19. [27]

    SIAM Journal on Discrete Mathematics , volume=

    Coloring tournaments with few colors: Algorithms and complexity , author=. SIAM Journal on Discrete Mathematics , volume=

  20. [28]

    Combinatorica , volume=

    Bounding the chromatic number of dense digraphs by arc neighborhoods , author=. Combinatorica , volume=

  21. [29]

    Nordic Journal of Computing , volume=

    Coloring 2-colorable hypergraphs with a sublinear number of colors , author=. Nordic Journal of Computing , volume=

  22. [30]

    International Conference on Integer Programming and Combinatorial Optimization (IPCO) , pages=

    Coloring bipartite hypergraphs , author=. International Conference on Integer Programming and Combinatorial Optimization (IPCO) , pages=

  23. [31]

    Theory of Computing Systems , volume=

    Digraph coloring and distance to acyclicity , author=. Theory of Computing Systems , volume=. 2024 , publisher=

    2024

  24. [32]

    arXiv preprint arXiv:2403.02298 , year=

    Minimum acyclic number and maximum dichromatic number of oriented triangle-free graphs of a given order , author=. arXiv preprint arXiv:2403.02298 , year=

  25. [33]

    Proceedings of the thirty-eighth Annual ACM Symposium on Theory of Computing (STOC) , pages=

    Conditional hardness for approximate coloring , author=. Proceedings of the thirty-eighth Annual ACM Symposium on Theory of Computing (STOC) , pages=

  26. [34]

    Journal of the ACM , volume=

    New approximation algorithms for graph coloring , author=. Journal of the ACM , volume=. 1994 , publisher=

    1994

  27. [35]

    , journal=

    Blum, Avrim and Karger, David R. , journal=. An

  28. [36]

    Discrete Mathematics , volume=

    Ordered colourings , author=. Discrete Mathematics , volume=

  29. [37]

    Journal of Discrete Algorithms , volume=

    Graph unique-maximum and conflict-free colorings , author=. Journal of Discrete Algorithms , volume=. 2011 , publisher=

    2011

  30. [38]

    Journal of Computing and System Sciences , year =

    Uriel Feige and Joe Kilian , title =. Journal of Computing and System Sciences , year =

  31. [39]

    Proceedings of the thirty-eighth Annual ACM Symposium on Theory of Computing (STOC) , pages=

    New approximation guarantee for chromatic number , author=. Proceedings of the thirty-eighth Annual ACM Symposium on Theory of Computing (STOC) , pages=

  32. [40]

    Random Structures Algorithms , FJOURNAL =

    Parzanchevski, Ori and Rosenthal, Ron , TITLE =. Random Structures Algorithms , FJOURNAL =. 2017 , NUMBER =. doi:10.1002/rsa.20657 , URL =

    2017 doi

  33. [41]

    European J

    Lubotzky, Alexander and Samuels, Beth and Vishne, Uzi , TITLE =. European J. Combin. , FJOURNAL =. 2005 , NUMBER =. doi:10.1016/j.ejc.2004.06.007 , URL =

    2005 doi

  34. [42]

    Anari, Nima and Liu, Kuikui and Gharan, Shayan Oveis and Vinzant, Cynthia , TITLE =. S. 2019 , MRCLASS =. doi:10.1145/3313276.3316385 , URL =

    2019 doi

  35. [43]

    Anari, Nima and Liu, Kuikui and Gharan, Shayan Oveis , TITLE =. 2020. [2020] 2020 , MRCLASS =. doi:10.1109/FOCS46700.2020.00125 , URL =

    2020 doi

  36. [44]

    Kaufman, Tali and Mass, David , TITLE =. 8th. 2017 , MRCLASS =

    2017

  37. [45]

    Abdolazimi, Dorna and Liu, Kuikui and Gharan, Shayan Oveis , TITLE =. 2021. [2022] 2022 , MRCLASS =

    2021

  38. [46]

    Israel J

    Lubotzky, Alexander and Samuels, Beth and Vishne, Uzi , TITLE =. Israel J. Math. , FJOURNAL =. 2005 , PAGES =. doi:10.1007/BF02772543 , URL =

    2005 doi

  39. [47]

    Theory Comput

    Louis, Anand and Makarychev, Yury , TITLE =. Theory Comput. , FJOURNAL =. 2016 , PAGES =. doi:10.4086/toc.2016.v012a017 , URL =

    2016 doi

  40. [48]

    Hubert and Louis, Anand and Tang, Zhihao Gavin and Zhang, Chenzi , TITLE =

    Chan, T.-H. Hubert and Louis, Anand and Tang, Zhihao Gavin and Zhang, Chenzi , TITLE =. J. ACM , FJOURNAL =. 2018 , NUMBER =. doi:10.1145/3178123 , URL =

    2018 doi

  41. [49]

    Dikstein, Yotam and Dinur, Irit , TITLE =. 2019. [2019] 2019 , MRCLASS =. doi:10.1109/FOCS.2019.00088 , URL =

    2019 doi

  42. [50]

    Proceedings of the

    Raghavendra, Prasad and Tan, Ning , TITLE =. Proceedings of the. 2012 , MRCLASS =

    2012

  43. [51]

    Kolla, Alexandra , TITLE =. Comput. Complexity , FJOURNAL =. 2011 , NUMBER =. doi:10.1007/s00037-011-0011-7 , URL =

    2011 doi

  44. [52]

    Alexandra Kolla and Madhur Tulsiani , title =

  45. [53]

    Arora, Sanjeev and Barak, Boaz and Steurer, David , TITLE =. 2010. 2010 , MRCLASS =

    2010

  46. [54]

    Yevgeny Levanzov , title =

  47. [55]

    Proceedings of the Tenth Annual ACM Symposium on Theory of Computing , pages =

    Yannakakis, Mihalis , title =. Proceedings of the Tenth Annual ACM Symposium on Theory of Computing , pages =. 1978 , isbn =. doi:10.1145/800133.804355 , abstract =

    1978 doi

  48. [56]

    , biburl =

    Cheng, Yizong and Church, George M. , biburl =. Biclustering of Expression Data. , url =. ISMB , editor =

  49. [57]

    41st Hawaii International International Conference on Systems Science

    Yun Zhang , title =. 41st Hawaii International International Conference on Systems Science. 2008 , url =. doi:10.1109/HICSS.2008.507 , timestamp =

    2008 doi

  50. [58]

    Polynomial algorithms for special cases of the balanced complete bipartite subgraph problem , volume =

    Arbib, Claudio and Mosca, Raffaele , year =. Polynomial algorithms for special cases of the balanced complete bipartite subgraph problem , volume =

  51. [59]

    Agarwal, Amit and Charikar, Moses and Makarychev, Konstantin and Makarychev, Yury , TITLE =. S. 2005 , MRCLASS =. doi:10.1145/1060590.1060675 , URL =

    2005 doi

  52. [60]

    Approximation, randomization, and combinatorial optimization

    Ghoshal, Suprovat and Louis, Anand and Raychaudhury, Rahul , TITLE =. Approximation, randomization, and combinatorial optimization. 2019 , MRCLASS =

    2019

  53. [61]

    Approximation Algorithms and Hardness for Strong Unique Games , booktitle =

    Suprovat Ghoshal and Anand Louis , editor =. Approximation Algorithms and Hardness for Strong Unique Games , booktitle =. 2021 , url =. doi:10.1137/1.9781611976465.26 , timestamp =

    2021 doi

  54. [62]

    Beyond the Worst-Case Analysis of Algorithms , DOI=

    Roughgarden, Tim , place=. Beyond the Worst-Case Analysis of Algorithms , DOI=

  55. [63]

    Random Structures Algorithms , FJOURNAL =

    Alon, Noga and Krivelevich, Michael and Sudakov, Benny , TITLE =. Random Structures Algorithms , FJOURNAL =. 1998 , NUMBER =. doi:10.1002/(SICI)1098-2418(199810/12)13:3/4<457::AID-RSA14>3.3.CO;2-K , URL =

    1998 doi

  56. [64]

    Random Structures Algorithms , FJOURNAL =

    Feige, Uriel and Krauthgamer, Robert , TITLE =. Random Structures Algorithms , FJOURNAL =. 2000 , NUMBER =. doi:10.1002/(SICI)1098-2418(200003)16:2<195::AID-RSA5>3.3.CO;2-1 , URL =

    2000 doi

  57. [65]

    and Hall, Georgina , TITLE =

    Abbe, Emmanuel and Bandeira, Afonso S. and Hall, Georgina , TITLE =. IEEE Trans. Inform. Theory , FJOURNAL =. 2016 , NUMBER =. doi:10.1109/TIT.2015.2490670 , URL =

    2016 doi

  58. [66]

    and Xiao, Ying , TITLE =

    Feldman, Vitaly and Grigorescu, Elena and Reyzin, Lev and Vempala, Santosh S. and Xiao, Ying , TITLE =. S. 2013 , MRCLASS =. doi:10.1145/2488608.2488692 , URL =

    2013 doi

  59. [67]

    and Kelner, Jonathan and Kothari, Pravesh and Moitra, Ankur and Potechin, Aaron , TITLE =

    Barak, Boaz and Hopkins, Samuel B. and Kelner, Jonathan and Kothari, Pravesh and Moitra, Ankur and Potechin, Aaron , TITLE =. 57th. 2016 , MRCLASS =

    2016

  60. [68]

    A New Algorithm for the Robust Semi-random Independent Set Problem , booktitle =

    Theo McKenzie and Hermish Mehta and Luca Trevisan , editor =. A New Algorithm for the Robust Semi-random Independent Set Problem , booktitle =. 2020 , url =. doi:10.1137/1.9781611975994.45 , timestamp =

    2020 doi

  61. [69]

    Chen, Yudong and Xu, Jiaming , TITLE =. J. Mach. Learn. Res. , FJOURNAL =. 2016 , PAGES =

    2016

  62. [70]

    , TITLE =

    Vu, Van H. , TITLE =. Combinatorica , FJOURNAL =. 2007 , NUMBER =. doi:10.1007/s00493-007-2190-z , URL =

    2007 doi

  63. [71]

    Ludek Kucera , title =. Discret. Appl. Math. , volume =. 1995 , url =. doi:10.1016/0166-218X(94)00103-K , timestamp =

    1995 doi

  64. [72]

    Ng and Michael I

    Andrew Y. Ng and Michael I. Jordan and Yair Weiss , editor =. On Spectral Clustering: Analysis and an algorithm , booktitle =. 2001 , url =

    2001

  65. [73]

    Louis, Anand and Raghavendra, Prasad and Tetali, Prasad and Vempala, Santosh , TITLE =. S. 2012 , MRCLASS =. doi:10.1145/2213977.2214079 , URL =

    2012 doi

  66. [74]

    and Oveis, Shayan Gharan and Trevisan, Luca , TITLE =

    Lee, James R. and Oveis, Shayan Gharan and Trevisan, Luca , TITLE =. S. 2012 , MRCLASS =. doi:10.1145/2213977.2214078 , URL =

    2012 doi

  67. [75]

    2013 , eprint=

    Improved ARV Rounding in Small-set Expanders and Graphs of Bounded Threshold Rank , author=. 2013 , eprint=

    2013

  68. [77]

    Approximation, randomization, and combinatorial optimization , SERIES =

    Louis, Anand and Raghavendra, Prasad and Tetali, Prasad and Vempala, Santosh , TITLE =. Approximation, randomization, and combinatorial optimization , SERIES =. 2011 , MRCLASS =. doi:10.1007/978-3-642-22935-0\_27 , URL =

    2011 doi

  69. [78]

    McSherry, Frank , TITLE =. 42nd. 2001 , MRCLASS =

    2001

  70. [79]

    Vu, Van , TITLE =. Combin. Probab. Comput. , FJOURNAL =. 2018 , NUMBER =. doi:10.1017/S0963548317000463 , URL =

    2018 doi

  71. [80]

    Kumar, Akash and Louis, Anand and Tulsiani, Madhur , TITLE =. 37th. 2017 , MRCLASS =

    2017

  72. [81]

    Coja-Oghlan, Amin , TITLE =. Combin. Probab. Comput. , FJOURNAL =. 2007 , NUMBER =. doi:10.1017/S0963548306007917 , URL =

    2007 doi

  73. [82]

    and Bracher, Annina and Singer, Amit , TITLE =

    Abbe, Emmanuel and Bandeira, Afonso S. and Bracher, Annina and Singer, Amit , TITLE =. IEEE Trans. Network Sci. Eng. , FJOURNAL =. 2014 , NUMBER =. doi:10.1109/TNSE.2014.2368716 , URL =

    2014 doi

  74. [83]

    Louis, Anand and Venkat, Rakesh , TITLE =. 45th. 2018 , MRCLASS =

    2018

  75. [84]

    Louis, Anand and Venkat, Rakesh , TITLE =. 39th. 2019 , MRCLASS =

    2019

  76. [85]

    2018 , PAGES =

    Vershynin, Roman , TITLE =. 2018 , PAGES =. doi:10.1017/9781108231596 , URL =

    2018 doi

  77. [86]

    Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications , volume =

    Garg, Naveen and Vazirani, Vijay and Yannakakis, Mihalis , year =. Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications , volume =. SIAM Journal on Computing , doi =

  78. [87]

    2009 50th

    Bansal, Nikhil and Khot, Subhash , TITLE =. 2009 50th. 2009 , MRCLASS =. doi:10.1109/FOCS.2009.23 , URL =

    2009 doi

  79. [88]

    Agrawal and P

    A. Agrawal and P. Klein and S. Rao and R. Ravi , booktitle =. Approximation through multicommodity flow , year =. doi:10.1109/FSCS.1990.89595 , url =

    1990 doi

  80. [89]

    and Johnson, David S

    Garey, Michael R. and Johnson, David S. , TITLE =. 1979 , PAGES =

    1979

  81. [90]

    Proceedings of the thirty-eighth annual ACM symposium on Theory of computing , pages=

    Linear degree extractors and the inapproximability of max clique and chromatic number , author=. Proceedings of the thirty-eighth annual ACM symposium on Theory of computing , pages=

  82. [91]

    The NP-completeness column: An ongoing guide , journal =

    David S Johnson , abstract =. The NP-completeness column: An ongoing guide , journal =. 1987 , issn =. doi:https://doi.org/10.1016/0196-6774(87)90021-6 , url =

    1987 doi

  83. [92]

    2004 , PAGES =

    Boyd, Stephen and Vandenberghe, Lieven , TITLE =. 2004 , PAGES =. doi:10.1017/CBO9780511804441 , URL =

    2004 doi

  84. [93]

    arXiv preprint arXiv:1907.00061 , year=

    Complexity of acyclic colorings of graphs and digraphs with degree and girth constraints , author=. arXiv preprint arXiv:1907.00061 , year=

    1907

  85. [94]

    Clique is hard to approximate within n^

    Johan H. Clique is hard to approximate within n^. Acta Mathematica , volume=

  86. [95]

    Uriel Feige and Shimon Kogan , title =

  87. [96]

    Manurangsi, Pasin , TITLE =. 44th. 2017 , MRCLASS =

    2017

  88. [97]

    The maximum edge biclique problem is

    Peeters, Ren\'. The maximum edge biclique problem is. Discrete Appl. Math. , FJOURNAL =. 2003 , NUMBER =. doi:10.1016/S0166-218X(03)00333-0 , URL =

    2003 doi

  89. [98]

    Eppstein, David , TITLE =. Inform. Process. Lett. , FJOURNAL =. 1994 , NUMBER =. doi:10.1016/0020-0190(94)90121-X , URL =

    1994 doi

  90. [99]

    Feige, Uriel and Ron, Dorit , TITLE =. 21st. 2010 , MRCLASS =

    2010

  91. [100]

    Bioinformatics , year=

    Discovering statistically significant biclusters in gene expression data , author=. Bioinformatics , year=

  92. [101]

    A Spectral Technique for Coloring Random 3-Colorable Graphs , journal =

    Noga Alon and Nabil Kahal. A Spectral Technique for Coloring Random 3-Colorable Graphs , journal =

  93. [102]

    Avrim Blum and Joel Spencer , title =. J. Algorithms , volume =

  94. [103]

    Khanna, Yash and Louis, Anand , TITLE =. 40th. 2020 , MRCLASS =

    2020

  95. [104]

    Independent Sets in Semi-random Hypergraphs

    Khanna, Yash and Louis, Anand and Paul, Rameesh. Independent Sets in Semi-random Hypergraphs. Algorithms and Data Structures. 2021

    2021

  96. [105]

    Makarychev, Konstantin and Makarychev, Yury and Vijayaraghavan, Aravindan , TITLE =. S. 2014 , MRCLASS =

    2014

  97. [106]

    Makarychev, Konstantin and Makarychev, Yury and Vijayaraghavan, Aravindan , TITLE =. S. 2012 , MRCLASS =. doi:10.1145/2213977.2214013 , URL =

    2012 doi

  98. [107]

    IEEE Trans

    Hajek, Bruce and Wu, Yihong and Xu, Jiaming , TITLE =. IEEE Trans. Inform. Theory , FJOURNAL =. 2016 , NUMBER =. doi:10.1109/TIT.2016.2546280 , URL =

    2016 doi

  99. [108]

    IEEE Trans

    Hajek, Bruce and Wu, Yihong and Xu, Jiaming , TITLE =. IEEE Trans. Inform. Theory , FJOURNAL =. 2016 , NUMBER =. doi:10.1109/TIT.2016.2594812 , URL =

    2016 doi

  100. [109]

    2016 , eprint=

    Semidefinite Programs for Exact Recovery of a Hidden Community , author=. 2016 , eprint=

    2016

  101. [110]

    Bhaskara, Aditya and Charikar, Moses and Chlamtac, Eden and Feige, Uriel and Vijayaraghavan, Aravindan , TITLE =. S. 2010 , MRCLASS =

    2010

  102. [111]

    , TITLE =

    Tropp, Joel A. , TITLE =. Found. Comput. Math. , FJOURNAL =. 2012 , NUMBER =. doi:10.1007/s10208-011-9099-z , URL =

    2012 doi

  103. [112]

    Bui, T. N. and Chaudhuri, S. and Leighton, F. T. and Sipser, M. , TITLE =. Combinatorica , FJOURNAL =. 1987 , NUMBER =. doi:10.1007/BF02579448 , URL =

    1987 doi

  104. [113]

    Dyer, M. E. and Frieze, A. M. , TITLE =. J. Algorithms , FJOURNAL =. 1989 , NUMBER =. doi:10.1016/0196-6774(89)90001-1 , URL =

    1989 doi

  105. [114]

    , TITLE =

    Jerrum, Mark and Sorkin, Gregory B. , TITLE =. Discrete Appl. Math. , FJOURNAL =. 1998 , NUMBER =. doi:10.1016/S0166-218X(97)00133-9 , URL =

    1998 doi

  106. [115]

    Proceedings of the

    Carson, Ted and Impagliazzo, Russell , TITLE =. Proceedings of the. 2001 , MRCLASS =

    2001

  107. [116]

    , TITLE =

    Condon, Anne and Karp, Richard M. , TITLE =. Random Structures Algorithms , FJOURNAL =. 2001 , NUMBER =. doi:10.1002/1098-2418(200103)18:2<116::AID-RSA1001>3.0.CO;2-2 , URL =

    2001 doi

  108. [117]

    , booktitle=

    Boppana, Ravi B. , booktitle=. Eigenvalues and graph bisection: An average-case analysis , year=

  109. [118]

    2017 , PAGES =

    Mitzenmacher, Michael and Upfal, Eli , TITLE =. 2017 , PAGES =

    2017

  110. [119]

    1976 , institution =

    The largest clique in a random graph , author =. 1976 , institution =

    1976

  111. [120]

    Barak, Boaz and Raghavendra, Prasad and Steurer, David , TITLE =. 2011. 2011 , MRCLASS =. doi:10.1109/FOCS.2011.95 , URL =

    2011 doi

  112. [121]

    Alev, Vedat Levi and Jeronimo, Fernando Granha and Tulsiani, Madhur , TITLE =. 2019. [2019] 2019 , MRCLASS =. doi:10.1109/FOCS.2019.00021 , URL =

    2019 doi

  113. [122]

    2020 , issn =

    Exact recovery in the hypergraph stochastic block model: A spectral algorithm , journal =. 2020 , issn =. doi:https://doi.org/10.1016/j.laa.2020.01.039 , url =

    2020 doi

  114. [123]

    Dinur, Irit and Kaufman, Tali , TITLE =. 58th. 2017 , MRCLASS =. doi:10.1109/FOCS.2017.94 , URL =

    2017 doi

  115. [124]

    Discrete Comput

    Oppenheim, Izhar , TITLE =. Discrete Comput. Geom. , FJOURNAL =. 2020 , NUMBER =. doi:10.1007/s00454-019-00117-7 , URL =

    2020 doi

  116. [125]

    Kaufman, Tali and Oppenheim, Izhar , TITLE =. S. 2018 , MRCLASS =. doi:10.1145/3188745.3188782 , URL =

    2018 doi

  117. [126]

    Approximation, randomization, and combinatorial optimization

    Kaufman, Tali and Oppenheim, Izhar , TITLE =. Approximation, randomization, and combinatorial optimization. 2018 , MRCLASS =

    2018

  118. [127]

    2007 , PAGES =

    Handbook of linear algebra , SERIES =. 2007 , PAGES =

    2007

  119. [128]

    https://math.stackexchange.com/q/3892650 , URL =

    Singular values of product of matrices , AUTHOR =. https://math.stackexchange.com/q/3892650 , URL =

  120. [129]

    Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with

    Venkatesan Guruswami and Ali Kemal Sinop , editor =. Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with. 2011 , url =. doi:10.1109/FOCS.2011.36 , timestamp =

    2011 doi

  121. [130]

    arXiv preprint arXiv:1204.4688 , year=

    Markov chain methods for small-set expansion , author=. arXiv preprint arXiv:1204.4688 , year=

    arXiv

  122. [131]

    On Expansion and Topological Overlap , booktitle =

    Dominic Dotterrer and Tali Kaufman and Uli Wagner , editor =. On Expansion and Topological Overlap , booktitle =. 2016 , url =. doi:10.4230/LIPIcs.SoCG.2016.35 , timestamp =

    2016 doi

  123. [132]

    Nathan Linial and Roy Meshulam , title =. Comb. , volume =. 2006 , url =. doi:10.1007/s00493-006-0027-9 , timestamp =

    2006 doi

  124. [133]

    Wallach , title =

    Roy Meshulam and N. Wallach , title =. Random Struct. Algorithms , volume =. 2009 , url =. doi:10.1002/rsa.20238 , timestamp =

    2009 doi

  125. [134]

    Bounded degree cosystolic expanders of every dimension , booktitle =

    Shai Evra and Tali Kaufman , editor =. Bounded degree cosystolic expanders of every dimension , booktitle =. 2016 , url =. doi:10.1145/2897518.2897543 , timestamp =

    2016 doi

  126. [135]

    Overlap properties of geometric expanders , booktitle =

    Jacob Fox and Mikhail Gromov and Vincent Lafforgue and Assaf Naor and J. Overlap properties of geometric expanders , booktitle =. 2011 , url =. doi:10.1137/1.9781611973082.90 , timestamp =

    2011 doi

  127. [136]

    Tessler , title =

    Ori Parzanchevski and Ron Rosenthal and Ran J. Tessler , title =. Comb. , volume =. 2016 , url =. doi:10.1007/s00493-014-3002-x , timestamp =

    2016 doi

  128. [137]

    Higher dimensional discrete Cheeger inequalities , journal =

    Anna Gundert and May Szedl. Higher dimensional discrete Cheeger inequalities , journal =. 2015 , url =. doi:10.20382/jocg.v6i2a4 , timestamp =

    2015 doi

  129. [138]

    Klivans and Sayan Mukherjee , title =

    John Steenbergen and Caroline J. Klivans and Sayan Mukherjee , title =. Adv. Appl. Math. , volume =. 2014 , url =. doi:10.1016/j.aam.2014.01.002 , timestamp =

    2014 doi

  130. [139]

    Cheeger Inequalities for Submodular Transformations , booktitle =

    Yuichi Yoshida , editor =. Cheeger Inequalities for Submodular Transformations , booktitle =. 2019 , url =. doi:10.1137/1.9781611975482.160 , timestamp =

    2019 doi

  131. [140]

    1971 , edition =

    Kenneth Hoffman and Ray Kunze , title =. 1971 , edition =

    1971

  132. [141]

    High Dimensional Expanders: Eigenstripping, Pseudorandomness, and Unique Games , booktitle =

    Mitali Bafna and Max Hopkins and Tali Kaufman and Shachar Lovett , editor =. High Dimensional Expanders: Eigenstripping, Pseudorandomness, and Unique Games , booktitle =. 2022 , url =. doi:10.1137/1.9781611977073.47 , timestamp =

    2022 doi

  133. [142]

    Near-linear time decoding of Ta-Shma's codes via splittable regularity , booktitle =

    Fernando Granha Jeronimo and Shashank Srivastava and Madhur Tulsiani , editor =. Near-linear time decoding of Ta-Shma's codes via splittable regularity , booktitle =. 2021 , url =. doi:10.1145/3406325.3451126 , timestamp =

    2021 doi

  134. [143]

    arXiv preprint arXiv:2302.01069 , year=

    Cheeger inequalities on simplicial complexes , author=. arXiv preprint arXiv:2302.01069 , year=

  135. [144]

    2012 , url =

    Luca Trevisan , title =. 2012 , url =. doi:10.1137/090773714 , timestamp =

    2012 doi

  136. [145]

    Israel Journal of Mathematics , volume=

    On eigenvalues of random complexes , author=. Israel Journal of Mathematics , volume=. 2016 , publisher=

    2016

  137. [146]

    Approximation, randomization, and combinatorial optimization

    Dikstein, Yotam and Dinur, Irit and Filmus, Yuval and Harsha, Prahladh , TITLE =. Approximation, randomization, and combinatorial optimization. 2018 , MRCLASS =

    2018

  138. [147]

    Frieze and Ravi Kannan , title =

    Alan M. Frieze and Ravi Kannan , title =. 37th Annual Symposium on Foundations of Computer Science,. 1996 , url =. doi:10.1109/SFCS.1996.548459 , timestamp =

    1996 doi

  139. [148]

    Correlation Clustering with Sherali-Adams , booktitle =

    Vincent Cohen. Correlation Clustering with Sherali-Adams , booktitle =. 2022 , url =. doi:10.1109/FOCS54457.2022.00068 , timestamp =

    2022 doi

  140. [149]

    Handling Correlated Rounding Error via Preclustering:

    Vincent Cohen. Handling Correlated Rounding Error via Preclustering:. 64th. 2023 , url =. doi:10.1109/FOCS57990.2023.00065 , timestamp =

    2023 doi

  141. [150]

    Moses Charikar and Venkatesan Guruswami and Anthony Wirth , title =. J. Comput. Syst. Sci. , volume =. 2005 , url =. doi:10.1016/j.jcss.2004.10.012 , timestamp =

    2005 doi

  142. [151]

    A Logarithmic Additive Integrality Gap for Bin Packing , booktitle =

    Rebecca Hoberg and Thomas Rothvoss , editor =. A Logarithmic Additive Integrality Gap for Bin Packing , booktitle =. 2017 , url =. doi:10.1137/1.9781611974782.172 , timestamp =

    2017 doi

  143. [152]

    Approximating Bin Packing within O(log

    Thomas Rothvo. Approximating Bin Packing within O(log. 54th Annual. 2013 , url =. doi:10.1109/FOCS.2013.11 , timestamp =

    2013 doi

  144. [153]

    Karp , title =

    Narendra Karmarkar and Richard M. Karp , title =. 23rd Annual Symposium on Foundations of Computer Science, Chicago, Illinois, USA, 3-5 November 1982 , pages =. 1982 , url =. doi:10.1109/SFCS.1982.61 , timestamp =

    1982 doi

  145. [154]

    Christensen and Arindam Khan and Sebastian Pokutta and Prasad Tetali , title =

    Henrik I. Christensen and Arindam Khan and Sebastian Pokutta and Prasad Tetali , title =. Comput. Sci. Rev. , volume =. 2017 , url =. doi:10.1016/j.cosrev.2016.12.001 , timestamp =

    2017 doi

  146. [155]

    Guntram Scheithauer and Johannes Terno , title =. Oper. Res. Lett. , volume =. 1997 , url =. doi:10.1016/S0167-6377(96)00047-8 , timestamp =

    1997 doi

  147. [156]

    Bin Packing via Discrepancy of Permutations , journal =

    Friedrich Eisenbrand and D. Bin Packing via Discrepancy of Permutations , journal =. 2013 , url =. doi:10.1145/2483699.2483704 , timestamp =

    2013 doi

  148. [157]

    The entropy rounding method in approximation algorithms , booktitle =

    Thomas Rothvo. The entropy rounding method in approximation algorithms , booktitle =. 2012 , url =. doi:10.1137/1.9781611973099.32 , timestamp =

    2012 doi

  149. [158]

    53rd Annual

    Alantha Newman and Ofer Neiman and Aleksandar Nikolov , title =. 53rd Annual. 2012 , url =. doi:10.1109/FOCS.2012.84 , timestamp =

    2012 doi

  150. [159]

    Near-optimal algorithms for unique games , booktitle =

    Moses Charikar and Konstantin Makarychev and Yury Makarychev , editor =. Near-optimal algorithms for unique games , booktitle =. 2006 , url =. doi:10.1145/1132516.1132547 , timestamp =

    2006 doi

  151. [160]

    47th Annual

    Eden Chlamtac and Konstantin Makarychev and Yury Makarychev , title =. 47th Annual. 2006 , url =. doi:10.1109/FOCS.2006.36 , timestamp =

    2006 doi

  152. [161]

    CoRR , volume =

    Anand Louis and Rameesh Paul and Arka Ray , title =. CoRR , volume =. 2022 , url =. doi:10.48550/arXiv.2212.13406 , eprinttype =. 2212.13406 , timestamp =

    2022 doi

  153. [162]

    CoRR , volume =

    Arka Ray and Sai Sandeep , title =. CoRR , volume =. 2023 , url =. doi:10.48550/arXiv.2301.09272 , eprinttype =. 2301.09272 , timestamp =

    2023 doi

  154. [163]

    Information Processing Letters , volume =

    Arka Ray , title =. Information Processing Letters , volume =. 2024 , issn =. doi:10.1016/j.ipl.2023.106430 , url =

    2024 doi

  155. [164]

    Frits C. R. Spieksma , title =. Comput. Oper. Res. , volume =. 1994 , url =. doi:10.1016/0305-0548(94)90059-0 , timestamp =

    1994 doi

  156. [165]

    Harald Dyckhoff , title =. Oper. Res. , volume =. 1981 , url =. doi:10.1287/opre.29.6.1092 , timestamp =

    1981 doi

  157. [166]

    International Journal of Production Economics , volume=

    The pallet loading problem: A survey , author=. International Journal of Production Economics , volume=. 1992 , publisher=

    1992

  158. [167]

    Vazirani , title =

    Vijay V. Vazirani , title =. 2001 , url =

    2001

  159. [168]

    ACM Sigact News , volume=

    Approximation algorithms for NP-hard problems , author=. ACM Sigact News , volume=. 1997 , publisher=

    1997

  160. [169]

    2012 , publisher=

    Approximation algorithms and semidefinite programming , author=. 2012 , publisher=

    2012

  161. [170]

    2011 , publisher=

    The Design of Approximation Algorithms , author=. 2011 , publisher=

    2011

  162. [171]

    Cormen and Charles E

    Thomas H. Cormen and Charles E. Leiserson and Ronald L. Rivest and Clifford Stein , title =. 2009 , url =

    2009

  163. [172]

    2006 , publisher=

    Algorithm design , author=. 2006 , publisher=

    2006

  164. [173]

    Goemans and David P

    Michel X. Goemans and David P. Williamson , editor =. 879-approximation algorithms for. Proceedings of the Twenty-Sixth Annual. 1994 , url =. doi:10.1145/195058.195216 , timestamp =

    1994 doi

  165. [174]

    Karger and Rajeev Motwani and Madhu Sudan , title =

    David R. Karger and Rajeev Motwani and Madhu Sudan , title =. Journal of the ACM , volume =. 1998 , url =. doi:10.1145/274787.274791 , timestamp =

    1998 doi

  166. [175]

    Johnson , title =

    David S. Johnson , title =. J. Comput. Syst. Sci. , volume =. 1974 , url =. doi:10.1016/S0022-0000(74)80044-9 , timestamp =

    1974 doi

  167. [176]

    Hochbaum , title =

    Dorit S. Hochbaum , title =. 1982 , url =. doi:10.1137/0211045 , timestamp =

    1982 doi

  168. [177]

    Coloring Tournaments with Few Colors: Algorithms and Complexity , booktitle =

    Felix Klingelh. Coloring Tournaments with Few Colors: Algorithms and Complexity , booktitle =. 2023 , url =. doi:10.4230/LIPIcs.ESA.2023.71 , timestamp =

    2023 doi

  169. [178]

    Coloring 3-Colorable Graphs with Less than

    Ken. Coloring 3-Colorable Graphs with Less than. Journal of the ACM , volume =. 2017 , url =. doi:10.1145/3001582 , timestamp =

    2017 doi

  170. [179]

    Journal of Algorithms , volume =

    Michael Krivelevich and Ram Nathaniel and Benny Sudakov , title =. Journal of Algorithms , volume =. 2001 , url =. doi:10.1006/jagm.2001.1173 , timestamp =

    2001 doi

  171. [180]

    Journal of Computer and System Sciences , volume=

    Zero knowledge and the chromatic number , author=. Journal of Computer and System Sciences , volume=. 1998 , publisher=

    1998

  172. [181]

    Discrete Applied Mathematics , volume=

    A hierarchy of relaxations and convex hull characterizations for mixed-integer zero—one programming problems , author=. Discrete Applied Mathematics , volume=. 1994 , publisher=

    1994

  173. [182]

    SIAM Journal on optimization , volume=

    Global optimization with polynomials and the problem of moments , author=. SIAM Journal on optimization , volume=. 2001 , publisher=

    2001

  174. [183]

    Jabeen Begum and T

    S. Jabeen Begum and T. Purusothaman , title =. Mob. Networks Appl. , volume =. 2016 , url =. doi:10.1007/s11036-015-0649-5 , timestamp =

    2016 doi

  175. [184]

    Erez Hartuv and Ron Shamir , title =. Inf. Process. Lett. , volume =. 2000 , url =. doi:10.1016/S0020-0190(00)00142-3 , timestamp =

    2000 doi

  176. [185]

    Journal of molecular biology , volume=

    Automatic clustering of orthologs and in-paralogs from pairwise species comparisons , author=. Journal of molecular biology , volume=. 2001 , publisher=

    2001

  177. [186]

    Genome Research , volume=

    High-throughput genotyping with single nucleotide polymorphisms , author=. Genome Research , volume=. 2001 , publisher=

    2001

  178. [187]

    NeuroImage , volume=

    Semi-supervised cluster analysis of imaging data , author=. NeuroImage , volume=. 2011 , publisher=

    2011

  179. [188]

    Computational Linguistics , volume=

    Clustering and diversifying web search results with graph-based word sense induction , author=. Computational Linguistics , volume=. 2013 , publisher=

    2013

  180. [189]

    Linearly Ordered Colourings of Hypergraphs , journal =

    Tamio. Linearly Ordered Colourings of Hypergraphs , journal =. 2022 , url =. doi:10.1145/3570909 , timestamp =

    2022 doi

  181. [190]

    Friedman , title =

    Trevor Hastie and Robert Tibshirani and Jerome H. Friedman , title =. 2009 , url =. doi:10.1007/978-0-387-84858-7 , isbn =

    2009 doi

  182. [191]

    40th Annual Symposium on Foundations of Computer Science,

    Moses Charikar and Sudipto Guha , title =. 40th Annual Symposium on Foundations of Computer Science,. 1999 , url =. doi:10.1109/SFFCS.1999.814609 , timestamp =

    1999 doi

  183. [192]

    Vazirani , title =

    Kamal Jain and Vijay V. Vazirani , title =. J. 2001 , url =. doi:10.1145/375827.375845 , timestamp =

    2001 doi

  184. [193]

    Schulman , editor =

    Leonard J. Schulman , editor =. Clustering for edge-cost minimization (extended abstract) , booktitle =. 2000 , url =. doi:10.1145/335305.335373 , timestamp =

    2000 doi

  185. [194]

    Nikhil Bansal and Avrim Blum and Shuchi Chawla , title =. Mach. Learn. , volume =. 2004 , url =. doi:10.1023/B:MACH.0000033116.57574.95 , timestamp =

    2004 doi

  186. [195]

    Nir Ailon and Moses Charikar and Alantha Newman , title =. J. 2008 , url =. doi:10.1145/1411509.1411513 , timestamp =

    2008 doi

  187. [196]

    Near Optimal

    Shuchi Chawla and Konstantin Makarychev and Tselil Schramm and Grigory Yaroslavtsev , editor =. Near Optimal. Proceedings of the Forty-Seventh Annual. 2015 , url =. doi:10.1145/2746539.2746604 , timestamp =

    2015 doi

  188. [197]

    Handling Correlated Rounding Error via Preclustering:

    Vincent Cohen. Handling Correlated Rounding Error via Preclustering:. CoRR , volume =. 2023 , url =. doi:10.48550/arXiv.2309.17243 , eprinttype =. 2309.17243 , timestamp =

    2023 doi

  189. [198]

    Sivakumar , title =

    Shuchi Chawla and Robert Krauthgamer and Ravi Kumar and Yuval Rabani and D. Sivakumar , title =. Comput. Complex. , volume =. 2006 , url =. doi:10.1007/s00037-006-0210-9 , timestamp =

    2006 doi

  190. [199]

    Demaine and Dotan Emanuel and Amos Fiat and Nicole Immorlica , title =

    Erik D. Demaine and Dotan Emanuel and Amos Fiat and Nicole Immorlica , title =. Theor. Comput. Sci. , volume =. 2006 , url =. doi:10.1016/j.tcs.2006.05.008 , timestamp =

    2006 doi

  191. [200]

    Local Correlation Clustering with Asymmetric Classification Errors , booktitle =

    Jafar Jafarov and Sanchit Kalhan and Konstantin Makarychev and Yury Makarychev , editor =. Local Correlation Clustering with Asymmetric Classification Errors , booktitle =. 2021 , url =

    2021

  192. [201]

    Theory Comput

    Ioannis Giotis and Venkatesan Guruswami , title =. Theory Comput. , volume =. 2006 , url =. doi:10.4086/toc.2006.v002a013 , timestamp =

    2006 doi

  193. [202]

    Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems , booktitle =

    Marek Karpinski and Warren Schudy , editor =. Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems , booktitle =. 2009 , url =. doi:10.1145/1536414.1536458 , timestamp =

    2009 doi

  194. [203]

    Correlation Clustering: maximizing agreements via semidefinite programming , booktitle =

    Chaitanya Swamy , editor =. Correlation Clustering: maximizing agreements via semidefinite programming , booktitle =. 2004 , url =

    2004

  195. [204]

    Thompson , title =

    Prabhakar Raghavan and Clark D. Thompson , title =. Comb. , volume =. 1987 , url =. doi:10.1007/BF02579324 , timestamp =

    1987 doi

  196. [205]

    Goemans and David P

    Michel X. Goemans and David P. Williamson , title =. J. 1995 , url =. doi:10.1145/227683.227684 , timestamp =

    1995 doi

  197. [206]

    Optimization methods and software , volume=

    Semidefinite relaxation and nonconvex quadratic optimization , author=. Optimization methods and software , volume=. 1998 , publisher=

    1998

  198. [207]

    Approximation schemes via Sherali-Adams hierarchy for dense constraint satisfaction problems and assignment problems , booktitle =

    Yuichi Yoshida and Yuan Zhou , editor =. Approximation schemes via Sherali-Adams hierarchy for dense constraint satisfaction problems and assignment problems , booktitle =. 2014 , url =. doi:10.1145/2554797.2554836 , timestamp =

    2014 doi

  199. [208]

    A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs , booktitle =

    Pasin Manurangsi and Prasad Raghavendra , editor =. A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs , booktitle =. 2017 , url =. doi:10.4230/LIPICS.ICALP.2017.78 , timestamp =

    2017 doi

  200. [209]

    Vempala , editor =

    He Jia and Aditi Laddha and Yin Tat Lee and Santosh S. Vempala , editor =. Reducing isotropy and volume to. 2021 , url =. doi:10.1145/3406325.3451018 , timestamp =

    2021 doi

  201. [210]

    Kane and Pravesh K

    Ainesh Bakshi and Ilias Diakonikolas and He Jia and Daniel M. Kane and Pravesh K. Kothari and Santosh S. Vempala , editor =. Robustly learning mixtures of. 2022 , url =. doi:10.1145/3519935.3519953 , timestamp =

    2022 doi

  202. [211]

    Kothari and Santosh S

    He Jia and Pravesh K. Kothari and Santosh S. Vempala , title =. 64th. 2023 , url =. doi:10.1109/FOCS57990.2023.00147 , timestamp =

    2023 doi

  203. [212]

    List Decoding of Direct Sum Codes , booktitle =

    Vedat Levi Alev and Fernando Granha Jeronimo and Dylan Quintana and Shashank Srivastava and Madhur Tulsiani , editor =. List Decoding of Direct Sum Codes , booktitle =. 2020 , url =. doi:10.1137/1.9781611975994.85 , timestamp =

    2020 doi

  204. [213]

    Optimal algorithms and inapproximability results for every CSP? , booktitle =

    Prasad Raghavendra , editor =. Optimal algorithms and inapproximability results for every CSP? , booktitle =. 2008 , url =. doi:10.1145/1374376.1374414 , timestamp =

    2008 doi

  205. [214]

    Proceedings of the 17th Annual

    Subhash Khot , title =. Proceedings of the 17th Annual. 2002 , url =. doi:10.1109/CCC.2002.1004334 , timestamp =

    2002 doi

  206. [215]

    A Still Better Performance Guarantee for Approximate Graph Coloring , journal =

    Magn. A Still Better Performance Guarantee for Approximate Graph Coloring , journal =. 1993 , url =. doi:10.1016/0020-0190(93)90246-6 , timestamp =

    1993 doi

  207. [216]

    Journal of the ACM , volume =

    Avi Wigderson , title =. Journal of the ACM , volume =

  208. [217]

    M. R. Garey and David S. Johnson and Larry J. Stockmeyer , title =. Theor. Comput. Sci. , volume =. 1976 , url =. doi:10.1016/0304-3975(76)90059-1 , timestamp =

    1976 doi

  209. [218]

    Algorithmica , volume =

    Bonnie Berger and John Rompel , title =. Algorithmica , volume =. 1990 , url =. doi:10.1007/BF01840398 , timestamp =

    1990 doi

  210. [219]

    New approximation guarantee for chromatic number , booktitle =

    Sanjeev Arora and Eden Chlamtac , editor =. New approximation guarantee for chromatic number , booktitle =. 2006 , url =. doi:10.1145/1132516.1132548 , timestamp =

    2006 doi

  211. [220]

    48th Annual

    Eden Chlamtac , title =. 48th Annual. 2007 , url =. doi:10.1109/FOCS.2007.13 , timestamp =

    2007 doi

  212. [221]

    Combinatorial Coloring of 3-Colorable Graphs , booktitle =

    Ken. Combinatorial Coloring of 3-Colorable Graphs , booktitle =. 2012 , url =. doi:10.1109/FOCS.2012.16 , timestamp =

    2012 doi

  213. [222]

    Hardness of Approximate Hypergraph Coloring , journal =

    Venkatesan Guruswami and Johan H. Hardness of Approximate Hypergraph Coloring , journal =. 2002 , url =. doi:10.1137/S0097539700377165 , timestamp =

    2002 doi

  214. [223]

    Smyth , title =

    Irit Dinur and Oded Regev and Clifford D. Smyth , title =. Combinatorica , volume =. 2005 , url =. doi:10.1007/S00493-005-0032-4 , timestamp =

    2005 doi

  215. [224]

    CoRR , volume =

    Marcin Wrochna , title =. CoRR , volume =. 2022 , url =. doi:10.48550/ARXIV.2205.14719 , eprinttype =. 2205.14719 , timestamp =

    2022 doi

  216. [225]

    Unique-Maximum and Conflict-Free Coloring for Hypergraphs and Tree Graphs , journal =

    Panagiotis Cheilaris and Bal. Unique-Maximum and Conflict-Free Coloring for Hypergraphs and Tree Graphs , journal =. 2013 , url =. doi:10.1137/120880471 , timestamp =

    2013 doi

  217. [226]

    2007 , url =

    Xujin Chen and Xiaodong Hu and Wenan Zang , title =. 2007 , url =. doi:10.1137/060649987 , timestamp =

    2007 doi

  218. [227]

    Jacob Fox and Lior Gishboliner and Asaf Shapira and Raphael Yuster , title =. J. Comb. Theory, Ser. 2019 , url =. doi:10.1016/J.JCTB.2018.10.001 , timestamp =

    2019 doi

  219. [228]

    Karp , editor =

    Richard M. Karp , editor =. Reducibility Among Combinatorial Problems , booktitle =. 1972 , url =. doi:10.1007/978-1-4684-2001-2\_9 , timestamp =

    1972 doi

  220. [229]

    Combinatorica , volume=

    Ramsey-type theorems with forbidden subgraphs , author=. Combinatorica , volume=

  221. [230]

    Ramsey-type theorems , journal =

    Paul Erd. Ramsey-type theorems , journal =. 1989 , url =. doi:10.1016/0166-218X(89)90045-0 , timestamp =

    1989 doi

  222. [231]

    Journal of Graph Theory , volume=

    Maria Chudnovsky , title =. Journal of Graph Theory , volume=

  223. [232]

    Vazirani , title =

    Sanjeev Arora and Satish Rao and Umesh V. Vazirani , title =. Journal of the ACM , volume =. 2009 , url =. doi:10.1145/1502793.1502794 , timestamp =

    2009 doi

  224. [233]

    Algebraic Approach to Promise Constraint Satisfaction , journal =

    Libor Barto and Jakub Bul. Algebraic Approach to Promise Constraint Satisfaction , journal =. 2021 , url =. doi:10.1145/3457606 , timestamp =

    2021 doi

  225. [234]

    Improved hardness for

    Marcin Wrochna and Stanislav Zivn. Improved hardness for. Proceedings of the 2020. 2020 , url =. doi:10.1137/1.9781611975994.86 , biburl =

    2020 doi

  226. [235]

    Joshua Brakensiek and Venkatesan Guruswami , title =

  227. [236]

    Dichotomy for Symmetric

    Miron Ficak and Marcin Kozik and Miroslav Ols. Dichotomy for Symmetric. 46th International Colloquium on Automata, Languages, and Programming (ICALP) , series =

  228. [237]

    An algorithmic blend of

    Brakensiek, Joshua and Guruswami, Venkatesan , booktitle=. An algorithmic blend of

  229. [238]

    Promise constraint satisfaction problems , author =

  230. [239]

    Approximations of Weighted Independent Set and Hereditary Subset Problems , journal =

    Magn. Approximations of Weighted Independent Set and Hereditary Subset Problems , journal =. 2000 , url =. doi:10.7155/JGAA.00020 , timestamp =

    2000 doi

  231. [240]

    Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform Hypergraphs , booktitle =

    Marek Filakovsk. Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform Hypergraphs , booktitle =

  232. [241]

    Berg , title =

    Libor Barto and Diego Battistelli and Kevin M. Berg , title =. 38th International Symposium on Theoretical Aspects of Computer Science (STACS) , series =

  233. [242]

    arXiv preprint arXiv:2504.02992 , year=

    A Dense Neighborhood Lemma: Applications of Partial Concept Classes to Domination and Chromatic Number , author=. arXiv preprint arXiv:2504.02992 , year=

  234. [243]

    Felix Klingelhoefer , title =

Pith tools

Reviewed May 20, 2026 · model on record in the stance chip above.