CS Paper Radar

Sharp Bounds for Selector Advice and Oblivious Equilibrium Search

Sebastian Ben Daniel

cs.CC ·submitted 2026-11-18 18:47 UTC · v2
theory

Abstract

Ko's tournament argument recognizes a P-selective language with quadratic advice. We determine the leading coefficient in the selector-query model. On $n$-bit inputs, $n^2/4+O(n)$ ordinary advice bits and $n$ nonadaptive comparisons suffice. Some cuts require $n^2/4-O(n\log n)$ bits even for randomized decoders with adaptive access to individual-degree-two extensions. At degree one the exact fixed advice width is $n+1$. Assuming exponential hardness in $\mathrm E$ against SAT-gate circuits, the quarter bound holds in deterministic polynomial time for every P-selective language. The same fixed point determines the cost of searching for an approximate equilibrium before seeing the payoffs. In an $N$-action symmetric constant-sum game with payoffs in $[0,1]$, let $P$ be the best worst-case probability that one game-independent proposal is an additive $ε$-Nash equilibrium. For each fixed $0<ε<1/2$, \[ -\log_2 P=(1+o(1))\, \frac{(\log_2 N)^2}{4[1-H_2(1/2+ε)]}. \] The algorithm draws uniform actions and proposes their empirical distribution for both players. The lower bound allows arbitrary mixed profiles and $N^{o(1)}$ adaptive payoff inspections before the proposal. For all symmetric two-player games, including general-sum games, the sharp exponent is $(\ln 2/8+o(1))(\log_2 N)^2/ε^2$ when $ε\to0$ and $\log(1/ε)=o(\log N)$. For security strategies in arbitrary zero-sum games the exponent is four times larger, and sampling an optimal strategy attains it. The common mechanism counts successful tuples. A fixed point makes them capture constant sampling probability while controlling a power moment of their distribution.

Closest papers

Nearest neighbours by meaning across the whole index.

Linear Certificates for Membership Comparability, Quadratic Barriers for Selectors

cs.CC ·2026-09-25 ·Sebastian Ben Daniel
similarity 0.62
Abstract

Selectors and comparators supply only partial information about membership: a selector names a member of any pair that meets the language, while a binary membership comparator merely excludes one of the four membership vectors of a pair. We ask how much nonuniform advice turns such information into exact recognition. Our main result extends the optimal nondeterministic advice bound for P-selective sets to every binary membership-comparable language: $2-mc \subseteq NP /(3n+5)\cap\mathrm{coNP}/(3n+5)$, with common fixed advice and certificates of at most $5n+12$ bits. The class is strictly larger; some 2-mc sets are not truth-table reducible to any P-selective set. The proof replaces the tournament king by an independent two-step cover of true signed literals, together with a short-forcing-or-exact-majority dichotomy, and it relativizes. Via an advice-preserving isolation transfer, a deterministic polynomial-time algorithm for promise Unique-Circuit-SAT gives $2-mc \subseteq P/O(n)$. For selectors we determine tight orders of ordinary advice: $Θ(n)$ for errorless average-case computation and $Θ(n^2)$ for worst-case bounded-error computation, the latter independent of the interpreter's coin bound. One oracle realizes both orders on a single language and separates ordinary from coin-dependent advice. The quadratic and linear lower bounds hold for tournament-query procedures and relativized languages, not unconditionally for unrelativized P-selective sets.

0.38

Average-Case Optimal Encodings and Efficient Worst-Case Indices for Element Distinctness Queries

cs.DS ·2026-08-18 ·Philip Bille, Johannes Fischer, Inge Li Gørtz, Filippo Lari
publishedtheoryhot direction similarity 0.61
Abstract · Accepted at SPIRE 2026. Full version

We study the data structure version of the \emph{element distinctness problem}: preprocess an array of $n$ elements from an alphabet of size $σ$ to answer \textsc{All-Distinct} queries, asking whether a given range contains only distinct elements. We first focus on \emph{uniformly random arrays}: in the encoding model, where access to the input at query time is not allowed, we prove a lower bound on the expected space; for instance, the lower bound is $n$, $1.3627n$, $1.5153n$, $1.5824n$ bits for $σ= 2,3,4,5$, and approximately $n\sqrt{π/(2σ)}\,\logσ$ bits for $σ=ω(1)$. We complement this by designing different average-case optimal encodings, supporting \textsc{All-Distinct} queries in worst-case time $O(1)$, $o(\log^{2}{\log{n}})$, or $O(\log\log{n})$ depending on $σ$, and $O(1)$ expected time for any $σ= ω(1)$. We then switch to worst-case (non-random) arrays: in the indexing model, where access to the input is allowed, we prove a cell-probe space-time tradeoff lower bound showing that any index using $n/b$ bits must have $Ω(b/\log{b})$ query time. We conclude by presenting a simple index almost matching this lower bound.

0.39

Zero Knowledge for Free up to Linear Query Bounds: Quasilinear-Size Constant-Query Zero-Knowledge PCPs

cs.CC ·2026-10-21 ·Inhyuk Park, Chenglin Fan
theory similarity 0.61
Abstract · The abstract is shortened due to the length limit of arXiv

We show that for all polynomials $T$ and $b$, every relation in NTIME($T$) has a binary PCP with $O(1)$ non-adaptive queries, perfect completeness, soundness error 1/2 and length $(T+b)\cdot(\log(T+b))^{O(1)}$, which is perfect zero knowledge against every adaptive, possibly malicious verifier making at most $b$ queries. This improves the length $\tilde O(T+b^2)$ of Zeilberger, O'Connor, Gur and Spooner (2026), who observed that Dinur's gap amplification preserves zero knowledge. The simulator runs in expected polynomial time (or in strict polynomial time, with a failure symbol or with negligible statistical error). For $b\le T$ the length is $T\cdot\mathrm{polylog}\,T$, the form of the shortest known constant-query PCPs without zero knowledge. Unless NP $\subseteq$ BPP, the dependence on $b$ is optimal up to the polylogarithmic factor for polynomial-time simulators: zero knowledge is free up to linear query bounds. Zero-knowledge interactive oracle proofs achieved length $\tilde O(T+b)$ in 2016-17; we obtain it for PCPs. Gur, O'Connor and Spooner (STOC 2025) asked whether NP has such PCPs of quasilinear length (their Open Problem 1). This paper answers it for every polynomial query bound, with the simulators above in place of a strict polynomial-time perfect simulator. The proofs were developed with extensive AI assistance and have been checked by the authors. We mask the Reed-Solomon proof of proximity of Ben-Sasson and Sudan at every node of its recursion. By a locator lemma, at every node, whatever $k$ of its proof symbols reveal about its input is determined by $O(k)$ input values. We prove it with the coprime-order argument of Bafna and Vyas (2026); our treatment of domain points is new. Dinur's gap amplification gives constant query complexity. The query count and the polylogarithmic exponent are absolute but very large.

0.10

Query Complexity of Testing Structured Parenthesis Languages

cs.DS cs.CC ·2026-09-29 ·Tim Jackman, Diptaksho Palit, Sofya Raskhodnikova
theory similarity 0.61
Abstract

We study the query complexity of testing membership in structured string languages, focusing on Dyck languages and natural generalizations. A tester receives query access to a word and must distinguish valid inputs from words that are far in Hamming distance, while inspecting only a sublinear number of positions. Our results sharpen the boundary between constant-query testability and polynomial query complexity. First, we prove an $Ω(n^{2/5})$ lower bound for testing Dyck languages $D_m$ with any fixed number $m\ge2$ of parenthesis types, improving the previous $Ω(n^{1/5})$ lower bound of Fischer, Magniez, and Starikovskaya (SODA `18) and nearly matching their upper bound of $O(n^{2/5+o(1)})$. Furthermore, we show that all nonadaptive algorithms for these problems require $Ω(n^{1/2})$ queries. Our lower bounds use a Pólya-urn process to construct the hard distribution; Second, we identify a broad class of weighted-parenthesis languages, which we call {\em excursion languages,} that remain constant-query testable. These languages encode bounded-step walks that stay nonnegative and return to zero. For every fixed excursion language, we give a nonadaptive tester with query complexity $O(1/\varepsilon^2)$, and we prove this dependence on $\varepsilon$ is optimal, even for adaptive algorithms. As a special case, we obtain the tight $Θ(1/\varepsilon^2)$ query complexity of testing $D_1$, improving the previous $O(\log(1/\varepsilon)/\varepsilon^2)$ upper bound and giving the first matching two-sided-error lower bound. Third, we construct a simple hard language, Hidden String, that is generated by a deterministic linear grammar but nevertheless requires $Ω(n^{2/5})$ adaptive queries and $Ω(n^{1/2})$ nonadaptive queries to test. This shows that polynomial query complexity appears even for highly restricted string languages.

0.18

Exact Algorithms and Complexity of the Smallest Grammar Problem

cs.DS ·2026-10-23 ·Xiangle Chen
theory similarity 0.60
Abstract · Revised version with a uniform alphabet-sensitive subexponential algorithm and quantitative transfers to SAT. Source package includes verifi…

The Smallest Grammar Problem (SGP) asks for a smallest straight-line grammar generating a given string, with size measured by the total right-hand-side length. For an input of length $n\ge2$ over at most $σ$ symbols, where $2\leσ\le n$, let $R=\log_σn$. We give a deterministic exact algorithm running in $n^{O(1)}2^{O(n\log\log n/(R\sqrt{\log n}))}$ time and polynomial space, with constants independent of $σ$. This gives time $2^{O(n\log\log n/(\log n)^{3/2})}$ for fixed alphabets and $2^{O(n\log\log n/\sqrt{\log n})}$ for arbitrary alphabets, up to polynomial factors. The algorithm combines pairwise disjoint representative occurrences of dictionary strings, a sparse interval certificate, and the Boolean tensor contraction theorem of OpenAI. It explicitly enforces dictionary membership, rule boundaries, and the grammar-size budget. Independently of that contraction theorem, disjoint representatives yield exact algorithms in $O^*(1.872258^n)$ time and $2^{O((n/R)\log(R+1))}$ time using $O(n)$ words of space. Anchor-based grammar projections establish binary NP-completeness and reductions with tunable alphabet size. We state their consequences as unconditional quantitative transfers from SGP algorithms to sparse SAT algorithms, and quantify the additional loss from sparsifying general formulas.

0.45

The CNF Encoding Complexity of Boolean Functions

cs.CC cs.LO ·2026-11-03 ·Andrew Krapivin, Benjamin Przybocki, Bernardo Subercaseaux
theory similarity 0.60
Abstract · 36 pages, comments are welcome!

We study the minimum number of clauses required to encode a boolean function into a CNF formula with auxiliary variables. Our main result is that if a boolean function can be evaluated in nondeterministic time $t$ (in the RAM model) with $m$ bits of advice such that at most $b$ bits of advice are accessed for each input, then it admits a CNF encoding with $\widetilde{O}(t + \sqrt{mb})$ clauses. This constitutes a nonuniform generalization of Robson's (TCS'91) variant of the Cook--Levin theorem, for which a naïve generalization would yield $\widetilde{O}(t+m)$ clauses; our applications leverage $b = o(m)$ to obtain significantly better bounds. Since preprocessed data structures can be modeled as computation with advice, our result allows us to translate space- and time-efficient data structures to compact CNF encodings. As an application, we derandomize a data structure of Larsen and Williams (SODA'17) to show that every $k$-CNF function on $n$ inputs can be encoded with $n^k/2^{Ω_k(\sqrt{\lg n})}$ clauses. Notably, despite encoding a $k$-CNF function, the encoding itself necessarily contains clauses of unbounded width, since an information-theoretic argument shows that the minimum number of bounded-width clauses to encode such functions is $Ω_k(n^{k}/\lg n)$ in the worst case. In general terms, our results imply that for a wide variety of NP-complete problems, one can reduce to CNF-SAT in a way that results in asymptotically fewer clauses than previously known methods.

0.31

Solving Restricted Versions of #SAT Faster than $2^m$: Algorithms and Lower Bounds

cs.DS ·2026-10-11 ·Sanjay Jain, Junqiang Peng, Frank Stephan, Mingyu Xiao
similarity 0.60
Abstract

Under the Strong Exponential Time Hypothesis (SETH), for any constant $\varepsilon > 0$, the #SAT problem (counting the number of satisfying assignments of a CNF formula) cannot be solved in $\mathcal{O}^*((2-\varepsilon)^n)$ or $\mathcal{O}^*((2-\varepsilon)^m)$ time, where $n$ is the number of variables and $m$ is the number of clauses. On the other hand, simple exhaustive search and the standard inclusion-exclusion give $\mathcal{O}^*(2^n)$-time and $\mathcal{O}^*(2^m)$-time algorithms, respectively. A natural line of research is to beat these SETH-based barriers for restricted versions, such as #$k$-SAT (where each clause contains at most $k$ literals) or #$d$-occ-SAT (where each variable appears in at most $d$ clauses). It is known that the $2^n$-barrier can be broken when $k$ or $d$ is any constant; yet, whether the $2^m$-barrier can also be broken in these cases remains unknown. We present two simple algorithms that overcome the $2^m$-barrier. First, for #$k$-SAT, we give an $\mathcal{O}^*(2^{m(1-1/O(k))})$-time algorithm, thereby breaking the $2^m$-barrier for any constant $k$. Second, for #$2$-occ-SAT (which also includes the problem of counting the number of edge covers in a graph as a special case), we provide an algorithm with runtime $\mathcal{O}^*(2^{mω/3})$, where $ω< 2.3714$ is the matrix multiplication exponent. Furthermore, we demonstrate that both algorithms generalize to the weighted counting setting while preserving the same runtime bounds. On the hardness side, we present a reduction from #Max-$d$-SAT to #$d$-occ-SAT, showing that for any $d\ge 3$, #$d$-occ-SAT admits no $\mathcal{O}^*((2-\varepsilon)^m)$-time algorithm for any constant $\varepsilon>0$, even on positive formulas, under the hypothesis that #Max-3-SAT on $n$ variables admits no $\mathcal{O}^*((2-\varepsilon)^n)$-time algorithm for any such $\varepsilon$.

0.29

Consequences of Polylogarithmic Membership Comparability for SAT

cs.CC ·2026-09-28 ·Sebastian Ben Daniel
similarity 0.60
Abstract

We study the consequences of membership comparators that exclude one possible membership vector, deterministically or with a relative advantage over uniform guessing. For every polynomially bounded arity, a randomized polynomial-time comparator of error at most $(1-1/poly(n))2^{-t}$ gives $ NP/ poly\cap coNP/ poly$ recognition with common advice. The proof uses limited independence, polynomial occurrence certificates, and a self-contained positive-relation advice transfer. For SAT at arity $O((\log n)^d)$, both this relative-gap hypothesis and deterministic comparability imply $PH=S^{NP}$, the uniform bound $PH\subseteq BPTIME(2^{O((\log n)^{d^2})})$, and symmetric verification with polynomial-length certificates and an oracle-free deterministic $2^{O((\log n)^d)}$ predicate. Polynomial-advice deterministic decoding has the same exponent $d$. Applying the randomized simulation to an unconditional diagonal language yields, for every fixed $\varepsilon>0$, $\mathrm{BPP}\subsetneq BPTIME(2^{O((\log n)^{d^2+\varepsilon})})$, without advice. The larger clock remains subexponential under every fixed number of self-compositions. A layered oracle satisfies deterministic comparability and $NP^O=coNP^O$ but excludes randomized NP algorithms with smaller logarithmic power, establishing a relativized limit on the SAT exponent $d$. This expanded version also develops the full weak-advantage regime, where saving $2^{-O((log n)^d)}$ gives randomized SAT exponent $d$ and PH exponent $d^k$ at fixed level $k$; the quasipolynomial and exponential hierarchy consequences; binary-comparator advice bounds; and the certificate-length boundary between the randomized regimes. Under deterministic comparability, uniform deterministic promise-unique search additionally gives $UEXP=EXP$. The ordinary second-level collapse $PH=Σ_2^p$ for $d>1$ remains unproved.

0.12