We study the tasks of deterministically condensing and extracting from Online Non-Oblivious Symbol Fixing (oNOSF) sources, a natural model of defective randomness where extraction is impossible in many parameter regimes [AORSV, EUROCRYPT'20]. A $(g,\ell)$-oNOSF source is a sequence of $\ell$ blocks where at least $g$ blocks are good (independent, with min-entropy) and the remaining bad blocks are controlled by an online adversary and can be arbitrarily correlated with prior blocks. Previously, [CGR, FOCS'24] proved impossibility of condensing beyond rate $1/2$ when $g\le 0.5 \ell$ and showed existence of condensers for when $g \ge 0.51\ell$ and $n$ is exponential in $\ell$. In this work, not only do we construct the first explicit condensers matching the existential results of [CGR, FOCS'24], but we make a doubly exponential improvement by handling the case when $g\ge 0.51\ell$ and $n$ is only polylogarithmic in $\ell$. We also obtain a much improved explicit construction for transforming low-entropy oNOSF sources into uniform oNOSF sources. Next, we essentially resolve the question of the existence of condensers for oNOSF sources by showing the existence of condensers even when $n$ is a large enough constant and $\ell$ is growing (provided $g \ge 0.51\ell$). We apply our condensers to collective coin flipping and collective sampling, widely studied problems in fault-tolerant distributed computing, and provide very simple protocols for them. Finally, we study the possibility of extraction from oNOSF sources. For lower bounds, we introduce the notion of online influence - extending the notion of influence of boolean functions - and establish tight bounds that imply extraction lower bounds. We also construct explicit extractors via leader election protocols that beat standard resilient functions [AL, Combinatorica'93].

We show that Inner Product in 2n variables, IP_n(x, y) = x₁y₁ ⊕ … ⊕ x_ny_n, can be computed by depth-3 bottom fan-in 2 circuits of size poly(n)⋅ (9/5)ⁿ, matching the lower bound of Göös, Guan, and Mosnoi (Inform. Comput.'24). Our construction is obtained via the following steps. 1) We provide a general template for constructing optimal depth-3 circuits with bottom fan-in k for an arbitrary function f. We do this in two steps. First, we partition f^{-1}(1) into orbits of its automorphism group. Second, for each orbit, we construct one k-CNF that (a) accepts the largest number of inputs from that orbit and (b) rejects all inputs rejected by f. 2) We instantiate the template for IP_n and k = 2. Guided by the intuition (which we call modularity principle) that optimal 2-CNFs can be constructed by taking the conjunction of variable-disjoint copies of smaller 2-CNFs, we use computer search to identify a small set of building block 2-CNFs over at most 4 variables. 3) We again use computer search to discover appropriate combinations (disjoint conjunctions) of building blocks to arrive at optimal 2-CNFs and analyze them using techniques from analytic combinatorics. We believe that the approach outlined in this paper can be applied to a wide range of functions to determine their depth-3 complexity.

Random selection is a fundamental task in fault-tolerant distributed computing where processors select a random outcome from some domain. Two special cases of this, leader election (where the processors designate a leader amongst themselves) and collective coin flipping (where the processors agree on a common random bit), have been especially widely studied. We study these problems in the full-information model, where processors communicate via a single broadcast channel, have access to private randomness, and face a computationally unbounded adversary that controls some of the processors. Despite decades of study, key gaps remain in our understanding of the trade-offs between round complexity, communication per player in each round, and adversarial resilience. We make progress by proving new lower bounds for coin flipping protocols and both new upper and lower bounds for leader election and random selection protocols.

Gurumukhani et al. (CCC'24) proposed the local enumeration problem Enum(k, t) as an approach to break the Super Strong Exponential Time Hypothesis (SSETH): for a natural number $k$ and a parameter $t$, given an $n$-variate $k$-CNF with no satisfying assignment of Hamming weight less than $t(n)$, enumerate all satisfying assignments of Hamming weight exactly $t(n)$. Furthermore, they gave a randomized algorithm for Enum(k, t) and employed new ideas to analyze the first non-trivial case, namely $k = 3$. In particular, they solved Enum(3, n/2) in expected $1.598^n$ time. A simple construction shows a lower bound of $6^{\frac{n}{4}} \approx 1.565^n$. In this paper, we show that to break SSETH, it is sufficient to consider a simpler local enumeration problem NAE-Enum(k, t): for a natural number $k$ and a parameter $t$, given an $n$-variate $k$-CNF with no satisfying assignment of Hamming weight less than $t(n)$, enumerate all Not-All-Equal (NAE) solutions of Hamming weight exactly $t(n)$, i.e., those that satisfy and falsify some literal in every clause. We refine the algorithm of Gurumukhani et al. and show that it optimally solves NAE-Enum(3, n/2), namely, in expected time $poly(n) \cdot 6^{\frac{n}{4}}$.

Depth-3 circuit lower bounds and k-SAT algorithms are intimately related; the state-of-the-art Σ^k_3-circuit lower bound (Or-And-Or circuits with bottom fan-in at most k) and the k-SAT algorithm of Paturi, Pudlák, Saks, and Zane (J. ACM'05) are based on the same combinatorial theorem regarding k-CNFs. In this paper we define a problem which reveals new interactions between the two, and suggests a concrete approach to significantly stronger circuit lower bounds and improved k-SAT algorithms. For a natural number k and a parameter t, we consider the Enum(k, t) problem defined as follows: given an n-variable k-CNF and an initial assignment α, output all satisfying assignments at Hamming distance t(n) of α, assuming that there are no satisfying assignments of Hamming distance less than t(n) of α. We observe that an upper bound b(n, k, t) on the complexity of Enum(k, t) simultaneously implies depth-3 circuit lower bounds and k-SAT algorithms: - Depth-3 circuits: Any Σ^k_3 circuit computing the Majority function has size at least binom(n,n/2)/b(n, k, n/2). - k-SAT: There exists an algorithm solving k-SAT in time O(∑_{t=1}^{n/2}b(n, k, t)). A simple construction shows that b(n, k, n/2) ≥ 2^{(1 - O(log(k)/k))n}. Thus, matching upper bounds for b(n, k, n/2) would imply a Σ^k_3-circuit lower bound of 2^Ω(log(k)n/k) and a k-SAT upper bound of 2^{(1 - Ω(log(k)/k))n}. The former yields an unrestricted depth-3 lower bound of 2^ω(√n) solving a long standing open problem, and the latter breaks the Super Strong Exponential Time Hypothesis. In this paper, we propose a randomized algorithm for Enum(k, t) and introduce new ideas to analyze it. We demonstrate the power of our ideas by considering the first non-trivial instance of the problem, i.e., Enum(3, n/2). We show that the expected running time of our algorithm is 1.598ⁿ, substantially improving on the trivial bound of 3^{n/2} ≃ 1.732ⁿ. This already improves Σ^3_3 lower bounds for Majority function to 1.251ⁿ. The previous bound was 1.154ⁿ which follows from the work of Håstad, Jukna, and Pudlák (Comput. Complex.'95). By restricting ourselves to monotone CNFs, Enum(k, t) immediately becomes a hypergraph Turán problem. Therefore our techniques might be of independent interest in extremal combinatorics.

While the existence of randomness extractors, both seeded and seedless, has been studied for many sources of randomness, currently, not much is known regarding the existence of seedless condensers in many settings. Here, we prove several new results for seedless condensers in the context of three related classes of sources: Non-Oblivious Symbol Fixing (NOSF) sources, online NOSF (oNOSF) sources (originally defined as SHELA sources in [1]), and almost Chor-Goldreich (CG) sources as defined in [2]. We will think of these sources as a sequence of random variables$\mathbf{X}=\mathbf{X}_{1}, \ldots,\mathbf{X}_{\ell}$on$\ell$symbols where at least$g$out of these$\ell$symbols are “good” (i.e., have some min-entropy requirement), denoted as a$(g, \ell)-\mathbf{source}$, and the remaining “bad”$\ell-g$symbols may adversarially depend on these$g$good blocks. The difference between each of these sources is realized by restrictions on the power of the adversary, with the adversary in NOSF sources having no restrictions. Prior to our work, the only known seedless condenser upper or lower bound in these settings is due to [2], where they explicitly construct a seedless condenser for a restricted subset of$(g,\ell)- \mathbf{adversarial}$CG sources. The following are our main results concerning seedless condensers for each of these sources. 1) oNOSF sources a) When$g\leq\ell/2$, we prove that condensing with error 0.99 above rate$\frac{1}{\lfloor\ell/g\rfloor}$is impossible. In fact, we show that this is tight. b) Quite surprisingly, for$g > \ell/2$, we show the existence of excellent condensers for uniform oNOSF sources. In addition, we show the existence of similar condensers for oNOSF sources with only logarithmic min-entropy. Our results are based on a new type of two-source extractors, called output-light two-source extractors, that we introduce and prove the existence of. 2) Adversarial CG sources a) We observe that uniform adversarial CG sources are equivalent to uniform oNOSF sources and consequently inherit the same results. b) We show that one cannot condense beyond the min-entropy gap of each block or condense low min-entropy CG sources above rate 1/2. 3) NOSF sources a) We show that condensing with constant error above rate$\frac{g}{\ell}$is impossible for uniform NOSF sources for any$g$and$\ell$, thus ruling out the possibility of any non-trivial condensing. This shows an interesting distinction between NOSF and oNOSF sources.

We define a class of problems whose input is an n-sized set of d-dimensional vectors, and where the problem is first-order definable using comparisons between coordinates. This class captures a wide variety of tasks, such as complex types of orthogonal range search, model-checking first-order properties on geometric intersection graphs, and elementary questions on multidimensional data like verifying Pareto optimality of a choice of data points. Focusing on constant dimension d, we show that any k-quantifier, d-dimensional such problem is solvable in O(n^{k-1} log^{d-1} n) time. Furthermore, this algorithm is conditionally tight up to subpolynomial factors: we show that assuming the 3-uniform hyperclique hypothesis, there is a k-quantifier, (3k-3)-dimensional problem in this class that requires time Ω(n^{k-1-o(1)}). Towards identifying a single representative problem for this class, we study the existence of complete problems for the 3-quantifier setting (since 2-quantifier problems can already be solved in near-linear time O(nlog^{d-1} n), and k-quantifier problems with k > 3 reduce to the 3-quantifier case). We define a problem Vector Concatenated Non-Domination VCND_d (Given three sets of vectors X,Y and Z of dimension d,d and 2d, respectively, is there an x ∈ X and a y ∈ Y so that their concatenation x∘y is not dominated by any z ∈ Z, where vector u is dominated by vector v if u_i ≤ v_i for each coordinate 1 ≤ i ≤ d), and determine it as the "unique" candidate to be complete for this class (under fine-grained assumptions).