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).

Given a sequence of samples x_1, … , x_k promised to be drawn from one of two distributions X₀, X₁, a well-studied problem in statistics is to decide which distribution the samples are from. Information theoretically, the maximum advantage in distinguishing the two distributions given k samples is captured by the total variation distance between X₀^{⊗k} and X₁^{⊗k}. However, when we restrict our attention to efficient distinguishers (i.e., small circuits) of these two distributions, exactly characterizing the ability to distinguish X₀^{⊗k} and X₁^{⊗k} is more involved and less understood. In this work, we give a general way to reduce bounds on the computational indistinguishability of X₀ and X₁ to bounds on the information-theoretic indistinguishability of some specific, related variables X̃₀ and X̃₁. As a consequence, we prove a new, tight characterization of the number of samples k needed to efficiently distinguish X₀^{⊗k} and X₁^{⊗k} with constant advantage as k = Θ(d_H^{-2}(X̃₀, X̃₁)), which is the inverse of the squared Hellinger distance d_H between two distributions X̃₀ and X̃₁ that are computationally indistinguishable from X₀ and X₁. Likewise, our framework can be used to re-derive a result of Halevi and Rabin (TCC 2008) and Geier (TCC 2022), proving nearly-tight bounds on how computational indistinguishability scales with the number of samples for arbitrary product distributions. At the heart of our work is the use of the Multicalibration Theorem (Hébert-Johnson, Kim, Reingold, Rothblum 2018) in a way inspired by recent work of Casacuberta, Dwork, and Vadhan (STOC 2024). Multicalibration allows us to relate the computational indistinguishability of X₀, X₁ to the statistical indistinguishability of X̃₀, X̃₁ (for lower bounds on k) and construct explicit circuits to distinguish between X̃₀, X̃₁ and consequently X₀, X₁ (for upper bounds on k).

We study processes of societal knowledge accumulation, where the validity of a new unit of knowledge depends both on the correctness of its derivation and on the validity of the units it depends on. A fundamental question in this setting is: If a constant fraction of the new derivations is wrong, can investing a constant fraction, bounded away from one, of effort ensure that a constant fraction of knowledge in society is valid? Ben-Eliezer, Mikulincer, Mossel, and Sudan (ITCS 2023) introduced a concrete probabilistic model to analyze such questions and showed an affirmative answer to this question. Their study, however, focuses on the simple case where each new unit depends on just one existing unit, and units attach according to a {\em preferential attachment rule}. In this work, we consider much more general families of cumulative knowledge processes, where new units may attach according to varied attachment mechanisms and depend on multiple existing units. We also allow a (random) fraction of insertions of adversarial nodes. We give a robust affirmative answer to the above question by showing that for \textit{all} of these models, as long as many of the units follow simple heuristics for checking a bounded number of units they depend on, all errors will be eventually eliminated. Our results indicate that preserving the quality of large interdependent collections of units of knowledge is feasible, as long as careful but not too costly checks are performed when new units are derived/deposited.

We give an algorithm for testing uniformity of distributions supported on hypergrids [m1] × · · · × [mn], which makes many queries to a subcube conditional sampling oracle with m = maximi. When m is a constant, our algorithm is nearly optimal and strengthens the algorithm of Canonne et al. (SODA 2021) which has the same query complexity but works for hypercubes {±1}n only.