CS Paper Radar

Unconditional Lower Bounds for the Fredman--Khachiyan Algorithms for Monotone Boolean Duality Testing

Khaled Elbassioni

cs.CC cs.DS ·submitted 2026-10-25 17:55 UTC · v3
theory

Abstract

We prove unconditional lower bounds on the number of recursive calls made by the two algorithms of Fredman and Khachiyan (1996) for monotone Boolean duality testing, as a function of the explicit input size $N$. For Algorithm A we show a lower bound of $N^{Ω(\log N)}$ on the dual pairs $(\HH_k,\LL_k)$ obtained from the read-once family of Gurvich and Khachiyan. The proof lower-bounds the number of leaves of every binary decision tree computing the function by the modulus of its multilinear polynomial evaluated at a complex point of the unit circle. It therefore applies to every choice of branching variables and, more generally, to the class of two-child variable-restriction procedures whose terminal calls have polynomially bounded decision-tree complexity. On this family the number of calls is exactly $N^{Θ(\log N)}$. For Algorithm B, a symmetric specialization of the polynomial padding construction of Kobayashi, Kurita, and Wasa, with full polynomial blocks, yields at least $q^{(t-1)k-t(t-1)/2}$ calls, where $k=4t^2$ and $q=Θ(t^2)$; as a function of $N$ this is $N^{Ω(\sqrt{\log N/\log\log N})}$ along an infinite family. The same padded family forces Berge multiplication, for every edge ordering, to generate an intermediate family of size $N^{Ω(\sqrt{\log N/\log\log N})}$. In an appendix we show that applying the padding construction directly to Algorithm A gives $Ω(2^n)$ calls on a dual pair obtained from an unsatisfiable $n$-variable formula, which is only $N^{Ω(\sqrt{\log N/\log\log N})}$ in terms of the input size. No complexity-theoretic assumption is used. The proofs allow every branching-variable choice permitted by the respective algorithm. They concern the original recursive procedures, counting every invocation separately, without sharing calls or adding positive stopping tests.

Closest papers

Nearest neighbours by meaning across the whole index.

A Width Hierarchy of Monotone Algebraic Branching Programs

cs.CC ·2026-11-04 ·Julian Dörfler, Alexander Rogovskyy
theory similarity 0.66
Abstract · 28 pages, submitted to STOC 2027

It is well known that $\mathsf{VF} = \mathsf{VBP}_{3}$ (Ben-Or-Cleve'92), i.e. the width of any constant-width algebraic branching program can be reduced to width $3$ with only a polynomial overhead to size. We prove that this is not the case for the monotone equivalents. In particular, we prove that there is an infinite hierarchy $\mathsf{mVBP}_{2} \subsetneq \mathsf{mVBP}_{3} \subsetneq \ldots$ by showing that $\mathrm{imm}_{k,n}$ requires width $w$ mABPs to have depth at least $\left(\frac{k}{w-1}\right)^{\frac{1}{2}\left\lfloor n^{\frac{1}{(w-2)}} \right\rfloor - 1}$ whenever $3 \leq w < k$. We prove this lower bound using support-based techniques. Since this lower bound is exact instead of asymptotic, it allows some width separations even for superconstant width. Moreover, it allows us to show that the expressive power of poly-sized monotone formulas of depth $2d$ is not reached by poly-sized mABPs of width $d-1$ but a width of $2d+1$ is sufficient. We contrast this to unbounded-depth monotone formulas, which are proven to be stronger than constant-width mABPs, but weaker than $\log$-width mABPs and incomparable for most widths in between. Finally, we generalize Snir's framework (Snir'80) for showing lower bounds on the number of leaves of monotone formulas to monotone formulas of multiplication depth $d^{\times}$, giving a lower bound of $n \cdot k^{d^{\times}(n^{\frac{1}{d^{\times}}} - 1)}$ for the iterated matrix multiplication polynomial and $\left(\left(e+o(1)\right) \ln^{\circ(d^{\times}-1)}(n)\right)^n$ for the permanent.

0.32

Parity Tests under Ties: A One-Test Lifting Theorem

cs.DS cs.CC ·2026-09-26 ·Ron Kupfer
theory similarity 0.64
Abstract

In the unrestricted polynomial decision-tree model, only the number of polynomial sign tests is charged. A parity test asks for the sign of a product of pairwise differences. Such tests underlie low-depth randomized algorithms for maximum finding and top-$k$ selection, but their usual analysis assumes distinct inputs because a tie makes the product vanish. We give a black-box lifting theorem that removes this assumption. After $O(\log n)$ polynomial tests determine the number of nonzero pairwise differences, every subsequent parity test is simulated by one polynomial test, consistently with a fixed lexicographic tie-breaking order. The simulator is an elementary symmetric polynomial in masked first and second powers of all pairwise differences. Thus a depth-$D$ parity-test tree on distinct inputs becomes a polynomial decision tree of depth $D+O(\log n)$ on arbitrary inputs, with no increase in randomized pointwise error for order-selection problems. We obtain maximum finding in depth $O(\log n[\log n+\log(1/δ)])$ with error $δ$, and top-$k$ selection in depth $O(\log^2 n+k\log n)$ with inverse-polynomial error, both without any promise on ties.

0.27

Sensitivity and Block Sensitivity of Elementary Symmetric Boolean Functions of Arbitrary Degree

cs.DM math.CO ·2026-09-20 ·Yuan Li, Jing Zhang
theoryhot direction similarity 0.62
Abstract · 26 pages

Let $σ_{n,d}$ denote the elementary symmetric Boolean function of $n$ variables and degree $d$. We completely determine the sensitivity, average sensitivity, and block sensitivity of $σ_{n,d}$ for every $1\le d\le n$. Using Lucas' theorem, we obtain a uniform binary description of the Hamming-weight value sequence, from which the sensitivity and average-sensitivity formulas follow and the computation of block sensitivity reduces to at most four explicit candidates. Combining these results with the arbitrary-degree formula for certificate complexity, we determine the exact relations among sensitivity, block sensitivity, and certificate complexity. We also prove a general result for symmetric Boolean functions: every nonconstant symmetric Boolean function $f$ satisfies \[ \bs(f)\le \max\{s(f),C(f)-1\}. \] Consequently, only the three patterns \[ s=\bs=C,\qquad s=\bs<C,\qquad s<\bs<C \] can occur for nonconstant symmetric Boolean functions. For elementary symmetric Boolean functions, we give necessary and sufficient conditions for each of these three patterns, thereby completely classifying the relations among $s(σ_{n,d})$, $\bs(σ_{n,d})$, and $C(σ_{n,d})$. In particular, we obtain a necessary and sufficient characterization of the full strict hierarchy \[ s(σ_{n,d})<\bs(σ_{n,d})<C(σ_{n,d}), \] and exhibit infinite families for which it holds.

0.48

An ETH-based quasipolynomial lower bound for Dualization

cs.DS cs.DM ·2026-10-08 ·Yasuaki Kobayashi, Kazuhiro Kurita, Kunihiro Wasa
theory similarity 0.61
Abstract

Dualizing monotone Boolean functions (or equivalently, enumerating minimal transversals in hypergraphs) is a long-standing problem whose output-polynomial-time solvability remains open. While various special cases have been extensively studied, the state-of-the-art algorithm for the general case, due to Fredman and Khachiyan, runs in quasipolynomial time. This paper presents a subexponential-time reduction from \textsc{3SAT} to the complement of \textsc{Dual}: Given a 3CNF formula with $n$ variables, the reduction constructs hypergraphs $H$ and $L$ of total size $2^{O(n^{2/3}(\log n)^{1/3})}$ such that $L \subseteq Tr(H)$ and the formula is satisfiable if and only if $L\neq Tr(H)$, where $Tr(H)$ is the set of minimal transversals of $H$. As a consequence of this reduction, assuming the Exponential Time Hypothesis (ETH), neither \textsc{Dual} nor \textsc{Dualization} admits an algorithm running in $N^{o(\sqrt{\log N/\log\log N})}$ time, where $N$ is the input size for \textsc{Dual} and the combined input and output size for \textsc{Dualization}. In particular, \textsc{Dualization} cannot be solved in output-polynomial time under ETH.

0.57

Upper and lower bounds on the OBDD-width of a special integer multiplication

cs.CC cs.DS ·2026-08-31 ·Tong Qin
similarity 0.61
Abstract · 11 pages, 1 figure

We consider the Boolean function ${\rm SMul}_{n-1}^n(\boldsymbol{x},\boldsymbol{y})$, which computes the middle bit of the multiplication of two natural numbers represented as $n$-bit binary strings $\boldsymbol{x}$ and $\boldsymbol{y}$, drawn from a restricted domain. We investigate the width of OBDDs computing ${\rm SMul}_{n-1}^n$. We introduce a combinatorially defined function $s_*(n)$ and show that the width of such OBDDs is $Θ(2^{s_*(n)})$.

0.23

A New Characterization of Streaming Decidability of Boolean CSPs Under Deletions

cs.CC ·2026-11-05 ·Aditya Bandekar, Amatya Sharma, Santhoshini Velusamy
theory similarity 0.60
Abstract

We characterize the single-pass streaming space complexity of Boolean CSP satisfiability in the strict-turnstile model for every fixed constraint language $Γ$ of $k$-ary Boolean relations that is not trivially satisfiable. Constraints can be inserted or deleted with nonnegative multiplicities; satisfiability is decided for those remaining at the end. While Sharma and Velusamy [ESA 2026] characterized insertion-only complexity via non-redundancy (up to logarithmic factors), we show that strict-turnstile complexity is governed by the integer capturing degree. For $R\subseteq\{0,1\}^k$, let $d_R$ be the minimum degree of an integer-coefficient polynomial vanishing exactly on $R$ over the Boolean hypercube, and set $d_Γ=\max_{R\inΓ}d_R$. On polynomial-length streams, we obtain an $O_k(n^{d_Γ}\operatorname{polylog} n)$-space randomized algorithm and an $Ω_k(n^{d_Γ}/\log n)$ lower bound for all algorithms. Moreover, our algorithm outputs a sparse instance preserving every satisfying assignment. This yields, to our knowledge, the first insertion-only versus turnstile separation for streaming CSPs. It also differs from the Fourier-degree characterization of exact optimization by Kol, Paramonov, Saxena, and Yu [ITCS 2023]. For $k\ge3$, $k$-XOR with literals has three distinct space complexities: $\widetildeΘ(n)$ for insertion-only satisfiability, $\widetildeΘ(n^{\lceil k/2\rceil})$ for strict-turnstile satisfiability, and $\widetildeΘ(n^k)$ for exact optimization in either model.

0.15

Polyhedral Methods for Cooperative Games: Small Lifts and Hard Faces

cs.GT cs.CCmath.COmath.OC ·2026-09-21 ·Michel Grabisch and. Hans Raj Tiwary
similarity 0.60
Abstract

We study the computational complexity of fundamental algorithmic problems -- membership testing, separation, valid-inequality testing, and linear optimization -- over polytopes and cones arising from cooperative games (also known as pseudo-Boolean functions). A central obstacle in the study of such problems is that a general cooperative game on $n$ players requires $2^n$ values, so the input size is $2^n$ for a game with $n$ players, making these computational tasks theoretically trivial. Restricting to $k$-additive games reduces the input size to $O(n^k)$, making such games a natural target for meaningful questions about the existence of efficient algorithms. On the positive side, we give an explicit extended formulation of size $O(n^k)$ for the core of $k$-additive $k$-monotone games, allowing all four problems to be solved by a single polynomial-size linear program -- in particular, circumventing the ellipsoid method that is needed when building from earlier tractability results of Deng and Papadimitriou, or of Edmonds. For the cone of $k$-additive $(k{-}1)$-monotone games, we give a complete characterization of its extreme rays and derive the same $O(n^k)$ bound on extension complexity, yielding a geometry-based proof and generalization of a result of Billionnet and Minoux. On the negative side, we show that for $l \leq k-2$ the cone of $k$-additive $l$-monotone games is computationally intractable: membership testing is not in NP (unless NP\,=\,coNP), valid-inequality testing is NP-complete, and extension complexity is at least $1.5^n$. Our hardness results yield, as a special case, a result of Crama and of Gallo and Simone. Furthermore, our hardness results also explain the lack of any good characterization of the extreme rays of the cone of $k$-additive $(k{-}2)$-monotone games.

0.27

Asymptotically Optimal Bounds for Counting Near-Minimum Circuits in Regular Matroids

cs.DM math.CO ·2026-11-11 ·Robert P. Streit
theory similarity 0.60
Abstract · 28 pages

For a regular matroid on $m$ elements with positive weights and weighted girth $g_w$, we prove that the number of circuits of weight at most $αg_w$ is bounded by $(Km)^{2α}$, for every real $α\ge1$ and an absolute constant $K$. This improves the previous $m^{O(α^2)}$ bound of Gurjar and Vishnoi and matches classic graph cut and cycle counting bounds of Karger and Subramanian. We also show this is asymptotically optimal for all real $α\geq 1$ under the Erdős girth conjecture, while unconditional optimality holds for half-integer $α$ by prior results. As consequences, we resolve a recent conjecture by Khanna, Putterman, and Song implying the existence of a parallel basis search algorithm for regular matroids terminating in logarithmically many rounds of independence queries, and obtain improved bounds on the number of near-minimum weight codewords in regular codes and near-shortest vectors in totally unimodular lattices under $\ell_p$-norms.

0.23