pith. sign in

arxiv: 2605.19654 · v1 · pith:OSNLNSCJnew · submitted 2026-05-19 · 💻 cs.DS

Hardness and Approximation for Coloring Digraphs

Parinya Chalermsook , Harmender Gahlawat , Felix Klingelhoefer , Alantha Newman , Chaoliang Tang This is my paper

Pith reviewed 2026-05-20 02:25 UTC · model grok-4.3

classification 💻 cs.DS
keywords dichromatic numberacyclic numberdigraph coloringapproximation algorithmshardness of approximationtournamentsdirected graphs
0
0 comments X

The pith

Approximating the dichromatic number and acyclic number of digraphs is as hard as undirected graph coloring, even restricted to tournaments.

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

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.

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.

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.

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.

Where Pith is reading between the lines

These are 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.

Load-bearing premise

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

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.

Figures

Figures reproduced from arXiv: 2605.19654 by Alantha Newman, Chaoliang Tang, Felix Klingelhoefer, Harmender Gahlawat, Parinya Chalermsook.

Figure 1
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. 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 ↗
read the original 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.

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.

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

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.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 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.

pith-pipeline@v0.9.0 · 5834 in / 1027 out tokens · 38500 ms · 2026-05-20T02:25:10.116360+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

242 extracted references · 242 canonical work pages · 1 internal anchor

  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

  9. [9]

    Journal of Combinatorial Theory, Series B , volume=

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

    work page

  10. [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=

    work page

  11. [11]

    Journal of the ACM , volume=

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

    work page

  12. [12]

    Journal of the ACM , volume=

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

    work page

  13. [13]

    Induced subgraph density

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

    work page

  14. [14]

    Pure pairs

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

    work page

  15. [15]

    Journal of Graph Theory , volume=

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

    work page

  16. [16]

    Discrete Applied Mathematics , volume=

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

    work page

  17. [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=

    work page

  18. [18]

    Pre-reduction graph products:

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

    work page

  19. [19]

    On a problem of

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

    work page

  20. [20]

    Journal of Combinatorial Theory, Series B , volume=

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

    work page

  21. [21]

    Combinatorica , volume=

    Coloring dense digraphs , author=. Combinatorica , volume=

    work page

  22. [22]

    Journal of Combinatorial Theory, Series B , volume=

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

    work page

  23. [23]

    Journal of Combinatorial Theory, Series B , volume=

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

    work page

  24. [24]

    Journal of Graph Theory , volume=

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

    work page

  25. [25]

    Theory Of Computing , volume=

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

    work page

  26. [26]

    Theory of Computing , volume=

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

    work page 2016

  27. [27]

    SIAM Journal on Discrete Mathematics , volume=

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

    work page

  28. [28]

    Combinatorica , volume=

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

    work page

  29. [29]

    Nordic Journal of Computing , volume=

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

    work page

  30. [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=

    work page

  31. [31]

    Theory of Computing Systems , volume=

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

    work page 2024

  32. [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=

    work page arXiv

  33. [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=

    work page

  34. [34]

    Journal of the ACM , volume=

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

    work page 1994

  35. [35]

    , journal=

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

    work page

  36. [36]

    Discrete Mathematics , volume=

    Ordered colourings , author=. Discrete Mathematics , volume=

    work page

  37. [37]

    Journal of Discrete Algorithms , volume=

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

    work page 2011

  38. [38]

    Journal of Computing and System Sciences , year =

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

    work page

  39. [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=

    work page

  40. [40]

    Random Structures Algorithms , FJOURNAL =

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

    work page doi:10.1002/rsa.20657 2017

  41. [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 =

    work page doi:10.1016/j.ejc.2004.06.007 2005

  42. [42]

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

    work page doi:10.1145/3313276.3316385 2019

  43. [43]

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

    work page doi:10.1109/focs46700.2020.00125 2020

  44. [44]

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

    work page 2017

  45. [45]

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

    work page 2021

  46. [46]

    Israel J

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

    work page doi:10.1007/bf02772543 2005

  47. [47]

    Theory Comput

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

    work page doi:10.4086/toc.2016.v012a017 2016

  48. [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 =

    work page doi:10.1145/3178123 2018

  49. [49]

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

    work page doi:10.1109/focs.2019.00088 2019

  50. [50]

    Proceedings of the

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

    work page 2012

  51. [51]

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

    work page doi:10.1007/s00037-011-0011-7 2011

  52. [52]

    Alexandra Kolla and Madhur Tulsiani , title =

    work page

  53. [53]

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

    work page 2010

  54. [54]

    Yevgeny Levanzov , title =

    work page

  55. [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 =

    work page doi:10.1145/800133.804355 1978

  56. [56]

    , biburl =

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

    work page

  57. [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 =

    work page doi:10.1109/hicss.2008.507 2008

  58. [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 =

    work page

  59. [59]

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

    work page doi:10.1145/1060590.1060675 2005

  60. [60]

    Approximation, randomization, and combinatorial optimization

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

    work page 2019

  61. [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 =

    work page doi:10.1137/1.9781611976465.26 2021

  62. [62]

    Beyond the Worst-Case Analysis of Algorithms , DOI=

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

    work page

  63. [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 =

    work page doi:10.1002/(sici)1098-2418(199810/12)13:3/4 1998

  64. [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 =

    work page doi:10.1002/(sici)1098-2418(200003)16:2 2000

  65. [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 =

    work page doi:10.1109/tit.2015.2490670 2016

  66. [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 =

    work page doi:10.1145/2488608.2488692 2013

  67. [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 =

    work page 2016

  68. [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 =

    work page doi:10.1137/1.9781611975994.45 2020

  69. [69]

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

    work page 2016

  70. [70]

    , TITLE =

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

    work page doi:10.1007/s00493-007-2190-z 2007

  71. [71]

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

    work page doi:10.1016/0166-218x(94)00103-k 1995

  72. [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 =

    work page 2001

  73. [73]

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

    work page doi:10.1145/2213977.2214079 2012

  74. [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 =

    work page doi:10.1145/2213977.2214078 2012

  75. [75]

    2013 , eprint=

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

    work page 2013

  76. [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 =

    work page doi:10.1007/978-3-642-22935-0 2011

  77. [78]

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

    work page 2001

  78. [79]

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

    work page doi:10.1017/s0963548317000463 2018

  79. [80]

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

    work page 2017

  80. [81]

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

    work page doi:10.1017/s0963548306007917 2007

Showing first 80 references.