Pith. sign in

REVIEW 4 major objections 4 minor 42 references

A Fast Coloring Oracle for Average Case Hypergraphs

T0 review · 4 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read This paper proves that for a uniformly random 2-colorable k-uniform hypergraph, a coloring oracle can answer each vertex query in constant expected time, with no memory between calls, while always agreeing with a single legal 2-coloring.

desk verdict A promising coloring-oracle model with an elegant algorithmic core, but a factor-exponential error in Lemma 5.4 makes Lemma 2.3 false as stated; likely repairable by recalibrating the 'good' threshold. read the letter →

arxiv 2507.10691 v1 pith:C7737JEM submitted 2025-07-14 cs.DS cs.CCmath.CO

Cassandra Marcussen , Edward Pyne , Ronitt Rubinfeld , Asaf Shapira , Shlomo Tauber This is my paper · ORCID
classification cs.DScs.CCmath.CO MSC 05C1505C6568Q2568W20
keywords hypergraph2-coloringaverage-casecomplexitycoloringoraclelocalcomputationalgorithmK_{ℓℓ}structurePropertyBrandomizedalgorithmsregularity-freemethod
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

Hypergraph 2-colorability is NP-hard in the worst case, but this paper argues that typical 2-colorable k-uniform hypergraphs are easy: a uniformly random 2-colorable k-graph is, with overwhelming probability, 'good' in a precise sense that lets it be colored locally. The paper gives a simple deterministic algorithm with $n^{{O(k)}}$ average-case running time, a randomized one with O(n) expected average time, and its main result, a coloring oracle that answers each vertex query in O(1) expected time on average, with no memory between calls and answers always consistent with one legal 2-coloring. The key is that almost every such hypergraph contains many copies of a small anchored structure K_{ℓ,ℓ} whose unique 2-coloring forces the color of every vertex through short paths, so sampling finds the needed proof in constant time. The interest is that worst-case hardness and average-case ease coexist at the level of single local queries, not just global algorithms.

What carries the argument

The load-bearing object is the 'good' property of Definition 2.2. A 2-colorable k-graph is good if (i) it contains at least $n^{{2ℓ}}$/$2^{{210k}}$ copies of K_{ℓ,ℓ}, the k-graph on two ℓ-element sets A and B with all edges having one vertex in one set and k-1 in the other, for ℓ=5k; and (ii) for every such copy, every vertex u has at least $n^{{k-1}}$/$k^{{4k}}$ (k-1)-tuples of neighbours in either the set of vertices adjacent to A or the set adjacent to B. Claim 2.1 shows K_{ℓ,ℓ} has a unique 2-coloring for ℓ ≥ 2k-3, so this copy acts as an anchor, and condition (ii) means every other vertex's color is forced and witnessed by many length-two paths. Lemma 2.3, that a uniform random 2-colorable k-graph is good with probability at least 1-$2^{{-2n}}$, is the probabilistic engine that turns locality into an average-case guarantee.

What would settle it

The central claim would be falsified if the fraction of good 2-colorable k-graphs is sometimes less than 1-$2^{{-2n}}$. A concrete check is to recompute the Section 5 estimates (the expected number of K_{ℓ,ℓ} copies and the probability that a fixed vertex has a neighbour in a given ℓ-set) and to exhaustively enumerate the bad fraction for small k and n, e.g., all 2-colorable 3-graphs on n = 10 to 14 vertices.

Watch

Extended reading notes

Core claim

The central claim is Theorem 3: there exists a randomized coloring oracle A such that T_A(n) = O(1), where T_A(n) is the average, over all 2-colorable k-graphs on n vertices, of the worst-case-over-vertices expected time to answer a query, and the oracle uses no memory between calls. The algorithm samples a (2ℓ+k-1)-tuple until it finds a copy of K_{ℓ,ℓ} together with a length-two path from vertex 1 that fixes the copy's colors; then it samples a (k-1)-tuple to read off the queried vertex's forced color. Consistency is guaranteed because all answers are derived from the lexicographically first legal 2-coloring, anchored by vertex 1 colored 0. The same machinery yields a deterministic $n^{{O(k)}}$ average-case algorithm (Theorem 1) and an expected O(n) randomized algorithm (Theorem 2), and the lexicographic anchoring converts the oracle into an average-case local computation algorithm with O(1) worst-case probe complexity (Theorem 4).

Load-bearing premise

Everything rests on Lemma 2.3, the claim that a uniformly random 2-colorable k-uniform hypergraph is 'good' with probability at least 1-$2^{{-2n}}$; if typical hypergraphs are not that well-behaved, the constant-time oracle and linear-time randomized algorithm lose their average-case guarantees.

Editorial extensions

If this is right

  • Average-case 2-coloring of k-uniform hypergraphs is solvable in expected linear time, matching the Ω(n) output lower bound.
  • Local queries to a legal 2-coloring can be answered in constant expected time with no shared memory, so external algorithms can probe colors without computing a global coloring.
  • The coloring oracle yields an average-case local computation algorithm with O(1) probe and runtime per query, with no shared randomness.
  • The regularity lemma is bypassed, so the algorithms and bounds are elementary and free of tower-type constants.
  • The method transfers to any distribution over 2-colorable k-graphs in which the 'good' property holds with probability at least 1-2^{-2n}.

Reading between the lines

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

  • The anchored vertex-1 trick suggests a general recipe for building memoryless oracles: pin down the lexicographically first canonical solution, then let every query reconstruct its answer from a locally sampled witness of that solution.
  • If the 'good' property is as robust as the paper's Section 5 suggests, it should support constant-query property testers for 2-colorability, since the oracle's sampling already distinguishes typical colorable inputs from non-colorable ones.
  • The same framework may extend to planted models where the two color classes have unequal sizes, because the proof already handles sets S of size between n/4 and n/2.
  • One could test the 'good' property empirically on small k and n by exhaustive enumeration, comparing the predicted fraction of good hypergraphs with the bound 1-2^{-2n}.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 4 minor

Summary. The paper proposes elementary average-case algorithms for 2-coloring k-uniform hypergraphs, replacing the regularity-based arguments of Person–Schacht and Lee–Molla–Nagle. Its main result is a coloring oracle that, on a uniformly random 2-colorable k-graph, answers each vertex query in O(1) expected time while remaining consistent with one legal 2-coloring and using no memory between queries. The algorithmic framework is built on a structural property called "good" (Definition 2.2): a good hypergraph contains many K_{ℓ,ℓ} copies, and the unique coloring of any such copy propagates to all vertices through length-two paths. Theorems 1–4 all rest on Lemma 2.3, which asserts that a random 2-colorable k-graph is good with probability at least 1 - 2^{-2n}. The proof of Lemma 2.3 reduces the uniform distribution to the planted model T_{S,n} and then invokes Lemmas 5.4–5.6.

Significance. The conceptual contribution is attractive: if Lemma 2.3 were established, the paper would give a strikingly simple, regularity-free average-case algorithm, a constant-query coloring oracle, and one of the first nontrivial average-case LCAs. The algorithmic parts are genuinely clean: Lemmas 3.1 and 4.1 correctly show that a good hypergraph can be colored consistently and efficiently, and the reduction from T_{S,n} to the uniform distribution over 2-colorable hypergraphs is elegant. However, the probabilistic engine of the paper is not currently valid. Lemma 5.4 contains a false numerical inequality that makes the expected number of K_{ℓ,ℓ} copies exponentially smaller than the threshold demanded by Definition 2.2(i), and Lemma 5.5 contains an inverted probability calculation. These errors are load-bearing: Lemma 2.3, and therefore Theorems 1–4, are not supported as written. I regard the central result as plausibly repairable by recalibrating the threshold in Definition 2.2(i), but the submitted manuscript does not prove it.

major comments (4)
  1. [Section 5, Lemma 5.4 and Eq. (2)] The lower bound on the expected number of K_{ℓ,ℓ} copies is false. For fixed A ⊆ S and B ⊆ V\S, each of the 2ℓ·C(ℓ,k-1) edges of K_{ℓ,ℓ} is present with probability 1/2, so the expected number of copies with one side in S and the other in V\S is C(|S|,ℓ)C(n-|S|,ℓ)·2^{-2ℓ C(ℓ,k-1)}. The inequality in Eq. (2) replaces C(n/4,ℓ)^2 by (n/(4ℓ))^{2ℓ} and then bounds (4ℓ)^{2ℓ} by 2^{29k}; since ℓ=5k, this is off by a factor of roughly 2^{2ℓ log(4ℓ)}. For k=3 and ℓ=15, the true expectation is at most n^{30}/2^{3260}, while Definition 2.2(i) demands at least n^{30}/2^{630}. Markov's inequality then gives P(item (i) holds) ≤ 2^{-2629} for H ~ T_{S,n} with |S|=n/2, which is incompatible with Lemma 5.2's claim that item (i) fails with probability at most e^{-n^k/2^{11k}}. Since Lemma 5.2 is the key step in Lemma 2.3, the probabilistic foundation of Theorems 1–4 is not established.
  2. [Section 5, Lemma 5.5] The probability calculation in Lemma 5.5 is inverted. For a fixed B of size ℓ, the probability that a vertex v in S has N(v,B)≠∅ is 1 - 2^{-C(ℓ,k-1)}, not 2^{-C(ℓ,k-1)}. Consequently the probability that all vertices in a fixed set of size n/8 have a neighbor in B is (1-2^{-C(ℓ,k-1)})^{n/8}, which is close to 1, not 2^{-(n/8)C(ℓ,k-1)}. The claimed bound 2^{-5n} is therefore impossible, and the union-bound proof of Lemma 5.5 is invalid as written. The lemma's conclusion may still be true—indeed the corrected probability suggests it is plausible—but the present proof does not establish it, and Lemma 5.2 explicitly relies on Lemma 5.5.
  3. [Definition 2.2(i) and Sections 3–4] The errors in Lemmas 5.4–5.5 show that the "good" threshold in Definition 2.2(i) is miscalibrated. To make Lemma 5.2 true, the threshold n^{2ℓ}/2^{210k} would need to be replaced by something on the order of n^{2ℓ}/2^{Θ(ℓ^k)} (with ℓ=5k), because that is the scale of the actual expected copy count. With such a recalibration, the running-time analyses in Lemmas 3.2 and 4.2 would still give n^{O(k)} and O(1) respectively, since the hidden constants depend only on k. However, as submitted, the proofs of Theorems 1–4 are conditional on a false lemma, and the statement in Section 4 that a positive proportion of 2ℓ-tuples contain a K_{ℓ,ℓ} is not justified by the current item (i).
  4. [Section 4, Lemma 4.2] There is a constants inconsistency in the use of Definition 2.2(ii). Definition 2.2(ii) guarantees either |N(u,N_A)| ≥ n^{k-1}/k^{4k} or |N(u,N_B)| ≥ n^{k-1}/k^{4k}, but Lemma 4.2 says that item (ii) gives at least n^{k-1}/k^{2k}. These differ by a factor of k^{2k}, and the claimed sampling probability k^{-4k} does not match either bound without explanation. This is not fatal once the constants are reconciled, but it should be corrected in a revision.
minor comments (4)
  1. [Section 5, proof of Lemma 5.2] The proof sums failure probabilities as e^{-n^k/2^{11k}} + 2^{-5n} + 2^{-n^{k-1}/k^{9k}}, but Lemma 5.5 states its failure probability as 2^{-3n} rather than 2^{-5n}; this mismatch should be reconciled.
  2. [Section 5, Lemma 5.4] The McDiarmid bound uses c_e ≤ n^{2ℓ-k} for each edge variable, which is acceptable, but the final exponent e^{-n^k/2^{11k}} depends on the false lower bound in Eq. (2) and will need to be recomputed after the threshold is recalibrated.
  3. [Section 1, Abstract and Introduction] The wording "ultimate evidence" and "as efficient as possible" overstates the result slightly, since the O(1) bound is average-case and the hidden constant depends on k; this is a presentation issue rather than a technical flaw.
  4. [References] Reference [Lov74] is listed as "P. Erdos-L Lovasz"; this should be corrected to the standard citation for the Erdős–Lovász paper.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the O(1) oracle is derived from an independently proven combinatorial property; the flagged issues in Lemmas 5.4 and 5.5 are correctness errors, not circular reductions.

full rationale

Walking the derivation chain: Theorem 3's O(1) coloring oracle follows from Lemma 4.1 (consistency) and Lemma 4.2 (runtime), and Lemma 4.2 reduces the runtime to the combinatorial 'good' property of Definition 2.2. That reduction is a counting argument: item (i) gives a constant fraction of K_{ell,ell}-containing tuples and item (ii) gives a constant fraction of witnessing (k-1)-tuples, so the expected number of samples is O(1). This is not a restatement of the desired runtime. Lemma 2.3, the probabilistic input to Theorems 1-3, is then proved in Section 5 from McDiarmid's inequality and a union bound over the planted model T_{S,n}; the proof does not fit any parameter to a target answer and does not assume the algorithm's running time. No fitted input is later renamed as a prediction, and no uniqueness theorem is imported from the authors' prior work. The only self-citation, [BCM+25], supplies the average-case LCA definition and framing; it is not load-bearing for the mathematical claims, which are self-contained given Lemma 2.3. The substantive referee concerns are mathematical: Lemma 5.4's copy-count lower bound appears to use a false inequality, and Lemma 5.5 appears to invert the rare event when estimating the probability that a vertex has a neighbor in a given ell-set. These are correctness risks in the probabilistic estimate, not circularity, because they do not make an output equal to an input by construction. Since no step in the derivation reduces to its own inputs, no circular step is identified.

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

No free parameters are fitted; ℓ=5k and all thresholds are fixed by k. The proofs rely on standard concentration inequalities and on the two probabilistic models described. The paper introduces no new physical or mathematical entities beyond the algorithmic definition of a coloring oracle.

assumptions (3)
  • standard math McDiarmid's bounded-differences inequality (Fact 5.3)
    Used in Lemmas 5.4 and 5.6 to show concentration of the number of K_{ℓ,ℓ} copies and of neighborhood sizes.
  • domain assumption Uniform distribution over 2-colorable k-graphs T^{(k)}_n
    The average-case model for all theorems; all expectations are taken over this distribution.
  • domain assumption Planted partition model T^{(k)}_{S,n} generates each cross edge independently with probability 1/2
    This equivalent generating process is used in Section 5 to prove Lemma 2.3.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A Fast Coloring Oracle for Average Case Hypergraphs." pith.science (2026). https://pith.science/paper/C7737JEM

@misc{pith2026250710691,
  author       = {Pith},
  title        = {Pith review of: A Fast Coloring Oracle for Average Case Hypergraphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/C7737JEM}},
  note         = {Machine review of arXiv:2507.10691}
}
abstract

Hypergraph $2$-colorability is one of the classical NP-hard problems. Person and Schacht [SODA'09] designed a deterministic algorithm whose expected running time is polynomial over a uniformly chosen $2$-colorable $3$-uniform hypergraph. Lee, Molla, and Nagle recently extended this to $k$-uniform hypergraphs for all $k\geq 3$. Both papers relied heavily on the regularity lemma, hence their analysis was involved and their running time hid tower-type constants. Our first result in this paper is a new simple and elementary deterministic $2$-coloring algorithm that reproves the theorems of Person-Schacht and Lee-Molla-Nagle while avoiding the use of the regularity lemma. We also show how to turn our new algorithm into a randomized one with average expected running time of only $O(n)$. Our second and main result gives what we consider to be the ultimate evidence of just how easy it is to find a $2$-coloring of an average $2$-colorable hypergraph. We define a coloring oracle to be an algorithm which, given vertex $v$, assigns color red/blue to $v$ while inspecting as few edges as possible, so that the answers to any sequence of queries to the oracle are consistent with a single legal $2$-coloring of the input. Surprisingly, we show that there is a coloring oracle that, on average, can answer every vertex query in time $O(1)$.

Figures

Figures reproduced from arXiv: 2507.10691 by the authors.

Figure 1
Figure 1. Illustration of how vertices are colored in [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Illustration of how vertices are colored in [PITH_FULL_IMAGE:figures/full_fig_p011_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

42 extracted references · 41 canonical work pages

  1. [1]

    Property testing in bounded degree hypergraphs

    Hugo Aaronson, Gaia Carenini, and Atreyi Chanda. Property testing in bounded degree hypergraphs. CoRR , abs/2502.18382, 2025

    arXiv 2025

  2. [2]

    Assadi, Y

    S. Assadi, Y. Chen, and S. Khanna. Sublinear algorithms for ( + 1) vertex coloring . In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms , SODA '19, pages 767--786. SIAM, 2019

    work page 2019

  3. [3]

    N. Alon, R. A. Duke, H. Lefmann, V. R \"o dl, and R. Yuster. The algorithmic aspects of the regularity lemma . Journal of Algorithms , 16:80--109, 1994

    work page 1994

  4. [4]

    Achlioptas, T

    D. Achlioptas, T. Gouleakis, and F. Iliopoulos. Simple local computation algorithms for the general Lov \'a sz Local Lemma . In Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures , SPAA '20, pages 1--10. ACM, 2020

    work page

  5. [5]

    Coloring 2-colorable hypergraphs with a sublinear number of colors

    Noga Alon, Pierre Kelsen, Sanjeev Mahajan, and Hariharan Ramesh. Coloring 2-colorable hypergraphs with a sublinear number of colors. Nordic J. of Computing , 3(4):425–439, December 1996

    work page 1996

  6. [6]

    Space-efficient local computation algorithms

    Noga Alon, Ronitt Rubinfeld, Shai Vardi, and Ning Xie. Space-efficient local computation algorithms. In Yuval Rabani, editor, Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012 , pages 1132--1139. SIAM , 2012

    work page 2012

  7. [7]

    Beyond Worst Case Local Computation Algorithms

    Amartya Shankha Biswas, Ruidi Cao, Cassandra Marcussen, Edward Pyne, Ronitt Rubinfeld, Asaf Shapira, and Shlomo Tauber. Beyond worst case local computation algorithms. CoRR , abs/2403.00129, 2025

    work page Pith review arXiv 2025

  8. [8]

    Hui Chen and Alan M. Frieze. Coloring bipartite hypergraphs. In Proceedings of the 5th International IPCO Conference on Integer Programming and Combinatorial Optimization , page 345–358, Berlin, Heidelberg, 1996. Springer-Verlag

    work page 1996

Show all 42 references
  1. [9]

    The complexity of ( + 1) coloring in congested clique, massively parallel computation, and centralized local computation

    Yi-Jun Chang, Manuela Fischer, Mohsen Ghaffari, Jara Uitto, and Yufan Zheng. The complexity of ( + 1) coloring in congested clique, massively parallel computation, and centralized local computation. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computin...

    2019

  2. [10]

    Chang, W

    Y. Chang, W. Li, and S. Pettie. An optimal distributed ( + 1)-coloring algorithm? In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing , STOC '18, pages 445--456. ACM, 2018

    2018

  3. [11]

    Sublinear graph augmentation for fast query implementation

    Artur Czumaj, Yishay Mansour, and Shai Vardi. Sublinear graph augmentation for fast query implementation. In Approximation and Online Algorithms: 16th International Workshop, WAOA 2018, Helsinki, Finland, August 23-24, 2018, Revised Selected Papers , page 181–203, Berlin, Heid...

    2018

  4. [12]

    Coloring non-uniform hypergraphs: a new algorithmic approach to the general lov \' a sz local lemma

    Artur Czumaj and Christian Scheideler. Coloring non-uniform hypergraphs: a new algorithmic approach to the general lov \' a sz local lemma. In David B. Shmoys, editor, Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, January 9-11, 2000, San Francis...

    2000

  5. [13]

    A new algorithm approach to the general lov\' a sz local lemma with applications to scheduling and satisfiability problems (extended abstract)

    Artur Czumaj and Christian Scheideler. A new algorithm approach to the general lov\' a sz local lemma with applications to scheduling and satisfiability problems (extended abstract). In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing , STOC '00, pa...

    2000

  6. [14]

    Czumaj and C

    A. Czumaj and C. Sohler. Testing hypergraph coloring . In Automata, Languages and Programming: 28th International Colloquium, ICALP 2001 , volume 2076 of Lecture Notes in Computer Science , pages 493--505. Springer, 2001

    2001

  7. [15]

    Czumaj and C

    A. Czumaj and C. Sohler. Abstract combinatorial programs and efficient property testers . SIAM Journal on Computing , 34(3):580--615, 2005

    2005

  8. [16]

    M. E. Dyer and A. M. Frieze. The solution of some random NP -hard problems in polynomial expected time. J. Algorithms , 10(4):451–489, dec 1989

    1989

  9. [17]

    Dorobisz and J

    A. Dorobisz and J. Kozik. Local Computation Algorithms for Hypergraph Coloring-Following Beck’s Approach . In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) , LIPIcs, Vol. 261, pages 48:1--48:20. Schloss Dagstuhl -- Leibniz-Zentrum f \"u r I...

    2023

  10. [18]

    An improved distributed algorithm for maximal independent set

    Mohsen Ghaffari. An improved distributed algorithm for maximal independent set. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms , SODA '16, page 270–277, USA, 2016. Society for Industrial and Applied Mathematics

    2016

  11. [19]

    Local computation of maximal independent set

    Mohsen Ghaffari. Local computation of maximal independent set. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) , pages 438--449. IEEE, 2022

    2022

  12. [20]

    W. T. Gowers. Hypergraph regularity and the multidimensional S zemer \'e di theorem . Annals of Mathematics , 166(3):897--946, 2007

    2007

  13. [21]

    Ghaffari and J

    J. Ghaffari and J. Uitto. Sparsifying Distributed Algorithms with Ramifications in Massively Parallel Computation and Centralized Local Computation . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms , SODA '19, pages 1636--1653. SIAM, 2019

    2019

  14. [22]

    Kelner, Huy Ngoc Nguyen, and Krzysztof Onak

    Avinatan Hassidim, Jonathan A. Kelner, Huy Ngoc Nguyen, and Krzysztof Onak. Local graph partitions for approximation and testing. 2009 50th Annual IEEE Symposium on Foundations of Computer Science , pages 22--31, 2009

    2009

  15. [23]

    Approximating coloring and maximum independent sets in 3-uniform hypergraphs

    Michael Krivelevich, Ram Nathaniel, and Benny Sudakov. Approximating coloring and maximum independent sets in 3-uniform hypergraphs. Journal of Algorithms , 41(1):99--113, 2001

    2001

  16. [24]

    Approximate coloring of uniform hypergraphs

    Michael Krivelevich and Benny Sudakov. Approximate coloring of uniform hypergraphs. Journal of Algorithms , 49(1):2--12, 2003. 1998 European Symposium on Algorithms

    2003

  17. [25]

    Seshadhri, and Andrew Stolman

    Akash Kumar, C. Seshadhri, and Andrew Stolman. Random walks and forbidden minors III: poly(d/ )-time partition oracles for minor-free graph classes. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022 , pages 257--2...

    2021

  18. [26]

    On two-coloring bipartite uniform hypergraphs

    Boyoon Lee, Theodore Molla, and Brendan Nagle. On two-coloring bipartite uniform hypergraphs. CoRR , 2404.05026, 2024

    2024 arXiv

  19. [27]

    Coverings and colorings of hypergraphs

    L \'a szl \'o Lov \'a sz. Coverings and colorings of hypergraphs. Proc. 4th Southeastern Conference of Combinatorics, Graph Theory, and Computing , pages 3--12, 1973

    1973

  20. [28]

    Erdos-L Lov \'a sz

    P. Erdos-L Lov \'a sz. Problems and results on 3-chromatic hypergraphs and some related questions. Coll Math Soc J Bolyai , 1974

    1974

  21. [29]

    A quasi-polynomial time partition oracle for graphs with an excluded minor

    Reut Levi and Dana Ron. A quasi-polynomial time partition oracle for graphs with an excluded minor. ACM Transactions on Algorithms , 11(3), January 2015

    2015

  22. [30]

    Local computation algorithms for graphs of non-constant degrees

    Reut Levi, Ronitt Rubinfeld, and Anak Yodpinyanee. Local computation algorithms for graphs of non-constant degrees. Algorithmica , 77(4):971--994, 2017

    2017

  23. [31]

    Deterministic hypergraph coloring and its applications

    Chi-Jen Lu. Deterministic hypergraph coloring and its applications. SIAM J. Discret. Math. , 18:320--331, 1998

    1998

  24. [32]

    On the method of bounded differences , page 148–188

    Colin McDiarmid. On the method of bounded differences , page 148–188. London Mathematical Society Lecture Note Series. Cambridge University Press, 1989

    1989

  25. [33]

    A local computation approximation scheme to maximum matching

    Yishay Mansour and Shai Vardi. A local computation approximation scheme to maximum matching. In Prasad Raghavendra, Sofya Raskhodnikova, Klaus Jansen, and Jos \' e D. P. Rolim, editors, APPROX/RANDOM 2013 , volume 8096 of Lecture Notes in Computer Science , pages 260--273. Spr...

    2013

  26. [34]

    Parnas and D

    M. Parnas and D. Ron. Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms . Theoretical Computer Science , 382:183--196, 2007

    2007

  27. [35]

    Person and M

    Y. Person and M. Schacht. Almost all hypergraphs without Fano planes are bipartite . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms , SODA '09, pages 217--226. SIAM, 2009

    2009

  28. [36]

    An expected polynomial time algorithm for coloring 2-colorable 3-graphs

    Yury Person and Mathias Schacht. An expected polynomial time algorithm for coloring 2-colorable 3-graphs. Electronic Notes in Discrete Mathematics , 13:465--469, 01 2011

    2011

  29. [37]

    R \"o dl, B

    V. R \"o dl, B. Nagle, J. Skokan, M. Schacht, and Y. Kohayakawa. The hypergraph regularity method and its applications . Proceedings of the National Academy of Sciences of the United States of America , 102(23):8109--8113, 2005

    2005

  30. [38]

    Radhakrishnan and A

    J. Radhakrishnan and A. Srinivasan. Improved bounds and algorithms for hypergraph two-coloring. In Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280) , pages 684--693, 1998

    1998

  31. [39]

    Fast local computation algorithms

    Ronitt Rubinfeld, Gil Tamir, Shai Vardi, and Ning Xie. Fast local computation algorithms. In Bernard Chazelle, editor, Innovations in Computer Science - ICS 2011, Tsinghua University, Beijing, China, January 7-9, 2011. Proceedings , pages 223--238. Tsinghua University Press, 2011

    2011

  32. [40]

    Szemer \'e di

    E. Szemer \'e di. Regular partitions of graphs . In Probl \`e mes combinatoires et th \'e orie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976) , volume 260 of Colloques Internationaux du CNRS , pages 399--401, Paris, 1978. CNRS

    1976

  33. [41]

    J. S. Turner. Almost all k -colorable graphs are easy to color . J. Algorithms , 9:63--82, 1988

    1988

  34. [42]

    An improved constant-time approximation algorithm for maximum matchings

    Yuichi Yoshida, Masaki Yamamoto, and Hiro Ito. An improved constant-time approximation algorithm for maximum matchings. In Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing , STOC '09, page 225–234, New York, NY, USA, 2009. Association for Computing Machinery

    2009

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.