Talk information

Date: Sunday, November 23, 2025
Time: 10:10–11:00
Place: Schreiber 309
Speaker: Shlomo Tauber (Tel Aviv University)
Title: A Fast Coloring Oracle for Average Case Hypergraphs

Abstract:

Hypergraph 2-colorability is one of the classical NP-hard problems. Person and Schacht designed a deterministic algorithm whose expected running time is polynomial over a uniformly chosen 2-colorable 3-uniform hypergraph, and Lee, Molla, and Nagle recently extended this to all 2-colorable $k$-uniform hypergraphs for $k\ge 3$. Both works relied heavily on the regularity lemma, leading to highly involved analyses and enormous hidden constants.

In this talk, we discuss a new and simple technique for 2-coloring $k$-uniform hypergraph that reproves the theorems of Person–Schacht and Lee–Molla–Nagle while completely avoiding the use of the regularity lemma. Building on this, we present our main result: a coloring oracle that assigns consistent colors to queried vertices while inspecting only a few edges. Surprisingly, we show that such an oracle can, on average, answer every vertex query in $O(1)$ time while not using any shared memory.

Based on joint work with Cassandra Marcussen, Ted Pyne, Ronitt Rubinfeld, and Asaf Shapira.