CS Paper Radar

Linear Certificates for Membership Comparability, Quadratic Barriers for Selectors

Sebastian Ben Daniel

cs.CC ·submitted 2026-09-25 09:43 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Consequences of Polylogarithmic Membership Comparability for SAT

cs.CC ·2026-09-28 ·Sebastian Ben Daniel
similarity 0.69
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

The Tournament Equilibrium Set Is PSPACE-Complete, Even under Hereditary Uniqueness

cs.GT cs.CC ·2026-11-12 ·Ethan Dickey, Athina Terzoglou
theory similarity 0.64
Abstract · 51 pages, 11 figures

The tournament equilibrium set (TEQ), proposed by Schwartz in 1990, is a classical voting rule based on pairwise majority comparisons. Its definition is recursive: an alternative is judged by the alternatives that beat it, called its dominators, and by which of those dominators TEQ itself selects. Deciding whether a given alternative belongs to TEQ was known to be NP-hard and to lie in PSPACE. We close this gap by proving that the problem is PSPACE-complete. To our knowledge, this is the first PSPACE-completeness result for membership in a tournament solution. The hardness persists even when every nonempty subtournament has a unique minimal retentive set, the property conjectured by Schwartz to hold for all tournaments. Moreover, every such subtournament in our hard instances contains an alternative with at most three dominators. We prove that a single alternative with at most four dominators suffices both to guarantee uniqueness and to find a TEQ winner in $O(N^2)$ time. Thus, on our hard instances, finding one winner is efficient even though recognizing a specified winner is PSPACE-complete. We also study how the complexity changes with the dominator bound. If every nonempty subtournament has an alternative with at most one dominator, the entire TEQ can be computed in quadratic time; allowing two dominators makes membership NP-hard. Under the same condition with four dominators, all $t$ winners can be computed in $O(2^t N^2)$ time, where $N$ is the number of alternatives.

0.24

On the Power of Alternating Local Certification with Constant-Size Certificates

cs.DC ·2026-10-16 ·Pedro Montealegre, Martín Ríos-Wilson, Jukka Suomela, Guillaume Theyssier
similarity 0.63
Abstract

We study alternation hierarchies for distributed decision in anonymous networks with constant-size certificates. A prover and a disprover alternately assign certificates to nodes over a constant number of rounds, after which each node decides whether to accept based on its own input and the certificates observed in its neighborhood. An instance is accepted if all nodes accept. Unlike previous work on distributed alternation hierarchies, which considered restricted local computation (Reiter, PODC 2024) or logarithmic-size certificates (Feuilloley et al., ICALP 2016), we focus on constant-size certificates and the role of neighborhood information in determining expressive power. We consider three models: SET, where nodes observe only the set of certificate sequences of their neighbors; MULTISET, where multiplicities are also visible; and PORTS, where neighbors can additionally be distinguished by local port numbers. We establish that SET is strictly weaker than MULTISET, which is in turn strictly weaker than PORTS, and that all three alternation hierarchies are strict at every level. Despite their severe restrictions, these models are remarkably expressive: LEADER belongs to the third level of SET. Our main characterization shows that, over finite input alphabets, SET coincides exactly with monadic second-order logic (MSO$_1$). Moreover, every language definable in counting monadic second-order logic (CMSO$_1$) belongs to PORTS, while MULTISET already contains languages that are not CMSO$_1$-definable. Nevertheless, this expressive power has fundamental limitations. PORTS does not capture MSO$_2$: neither Hamiltonicity nor the existence of a perfect matching belongs to PORTS. Furthermore, over unbounded input alphabets, PORTS cannot verify that every node has been given the correct network size.

0.19

Constant-Probability Witness Isolation Implies $\mathrm{NP}\subseteq\mathrm{P/poly}$

cs.CC ·2026-09-24 ·Sebastian Ben Daniel
published similarity 0.63
Abstract

Valiant and Vazirani isolate a satisfying assignment of a circuit with probability $Ω(1/n)$. Dell, Kabanets, van Melkebeek, and Watanabe showed that success above $2/3$ implies $\mathrm{NP}\subseteq\mathrm{P/poly}$ and asked about the range in between. We show that every positive constant already implies the collapse: if a randomized nonuniform polynomial-size pruning procedure succeeds with probability $ε$ on affine circuit inputs with at most $2^{\lfloor 2/ε\rfloor}$ satisfying assignments, then $\mathrm{NP}\subseteq\mathrm{P/poly}$. Success $10/\log L$ on affine inputs with at most $L^{1/3}$ satisfying assignments suffices, where $L$ is the description length, and on inputs with one or two satisfying assignments the threshold $2/3$ drops to $3/5$. No cryptographic assumption is used, and the procedure may read the entire circuit. The proof compiles a pool of circuits into one circuit whose satisfying assignments are indexed by tags in $\mathbb{F}_2^d$. Each member is assigned an affine region of tag space, and if one member is unsatisfiable, the satisfying set shrinks to that member's region. Because regions may overlap and have different dimensions, the collapse reduces to a combinatorial bound: no set of tags meets more than a $2/d$ fraction of an equally weighted family of affine subspaces of all dimensions below $d$ in exactly one point. This regional counting cannot go below order $1/\log L$. The range between $Θ(1/n)$, achieved by affine hashing, and $O(1/\log n)$ remains open.

0.62

Min-CSPs on Complete Instances III: Nearly Optimal Characterizations of Approximation for Symmetric CSPs

cs.DS ·2026-11-10 ·Yihwan Chae, Chenglin Fan, Donghyeon Lee, Euiwoong Lee
similarity 0.62
Abstract · 45 pages. Adjusted the placement of Table 1

This paper studies complete Min-$k$-CSPs: an instance on $n$ variables has one nontrivial constraint for every $k$-set of variables (so $\binom{n}{k}$ constraints in total), and the goal is to find an assignment that minimizes the number of unsatisfied constraints. They are motivated by the connections to machine learning and data science, as well as the possibility of being testbeds for new algorithmic techniques. Previous recent results presented polynomial-time algorithms for the decision version of every complete Boolean $k$-CSP, which is a necessary condition for any multiplicative approximations for the minimization version, but nontrivial approximation results have been limited to fragile CSPs, 2-SAT, and NAE-3-SAT, leaving the approximability of most complete Boolean Min-CSPs open, including complete Min-$k$-SAT. In this paper, we resolve this question, up to nearly matching factors, for the natural class of symmetric Boolean predicates. Given $A \subseteq \{0, \dots, k\}$, Min-CSP($A$) is a Min-$k$-CSP where each constraint is specified by $k$ literals and is satisfied if the number of true literals belongs to $A$. Let $w(A)$ be the maximum number of consecutive integers in $A$. Our main results for complete Min-CSP($A$) are (1) a QPTAS for $w(A) \leq 2$ and (2) an $\widetilde{O}(n^{w(A)-3})$-approximation for $w(A) \geq 3$, as well as almost matching hardness results for the latter. Our QPTAS for $w(A)=2$ significantly improves the previous $O(1)$-approximation for Min-2-SAT and the $\operatorname{polylog}(n)$-approximation for Min-NAE-3-SAT, as well as extends the PTAS for fragile CSPs (i.e., $w(A) = 1$).

0.23

Near-Inverse-Linear Barriers for Explicit Affine Witness Isolation

cs.CC ·2026-10-08 ·Sebastian Ben Daniel
similarity 0.62
Abstract

We study randomized nonuniform polynomial-size transformations that output explicit binary affine filters for circuit inputs whose nonempty satisfying sets are affine. The filter may depend on the entire input description; no affine basis is supplied. For every fixed $δ<1$, a worst-case singleton success guarantee $Ω(n^{-δ})$, where $n$ is the witness arity, implies $NP\subseteq P/poly$. More generally, any success guarantee $ω(\log n/n)$ yields satisfiability circuits of size $(s+2)^{O(1)}2^{o(v)}$ for length-$s$ descriptions with at most $v$ witness variables, hence subexponential in $v$ when $s=v^{O(1)}$. Conversely, SAT search-to-decision gives deterministic perfect isolation, making polynomial-resource fixed-exponent strong affine isolation equivalent to $NP\subseteq P/poly$. For explicit unions of at most $n^β$ affine components, success $Ω(n^{-δ})$ implies the same collapse whenever $β,δ\ge0$ and $β+δ<1$. The inverse-linear endpoint is not claimed.

0.07

Sharp Bounds for Selector Advice and Oblivious Equilibrium Search

cs.CC ·2026-11-18 ·Sebastian Ben Daniel
theory similarity 0.62
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.

0.27

Remote Matching: Exact-Cardinality Approximation and Tight UGC Hardness

cs.DS ·2026-09-22 ·Arash Ahadi, Morteza Alimi, Sharareh Alipour, Shayan Tayefeh
similarity 0.60
Abstract

In the unrestricted max--min metric $T$-join problem, one seeks an even terminal set $T$ maximizing the cost of a minimum $T$-join. Iwata and Ravi gave a factor-$3/2$ approximation for this problem. We show that this guarantee is tight under the Unique Games Conjecture: no polynomial-time approximation with factor strictly smaller than $3/2$ exists under UGC. We then consider the exact-cardinality variant, which prescribes an even number \(k\) of terminals. Writing \(p:=k/n\), we give a deterministic polynomial-time \(ρ(p)\)-approximation for every feasible cardinality, where \[ ρ(p)= \begin{cases} 7/2, & \makebox[1.5em][r]{$0$}<p\le2/7,\\ 1/p, & 2/7\le p\le2/3,\\ 1/[2(1-p)], & 2/3\le p\le7/8,\\ 4, & 7/8\le p<1. \end{cases} \] In particular, a factor-\(4\) approximation holds throughout the entire feasible cardinality range, the factor is at most \(7/2\) whenever \(0<k\le 6n/7\), and equals \(3/2\) at \(k=2n/3\). The algorithmic framework is based on optimal laminar cut packings, their weighted tree representations, exact-cardinality rounding, and tree dynamic programming.

0.13