2026-07-21T14:10:58Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24427 2025-12-12T15:01:46Z ddc:004 open_access

A Fast Coloring Oracle for Average Case Hypergraphs Marcussen, Cassandra Pyne, Edward Rubinfeld, Ronitt Shapira, Asaf Tauber, Shlomo average-case algorithms local computation algorithms graph coloring 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 ≥ 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Cassandra Marcussen and Edward Pyne and Ronitt Rubinfeld and Asaf Shapira and Shlomo Tauber 2025 Is Part Of LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2025.61 urn:nbn:de:0030-drops-244272 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.61 eng https://creativecommons.org/licenses/by/4.0/legalcode