CS Paper Radar

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

Tong Qin

cs.CC cs.DS ·submitted 2026-08-31 12:04 UTC · v1

Abstract

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

Comment
11 pages, 1 figure

Closest papers

Nearest neighbours by meaning across the whole index.

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

Exponential Correlation Bounds for Polynomials

cs.CC ·2026-09-23 ·Eshan Chattopadhyay, Pooya Hatami, Chin Ho Lee, Shachar Lovett, Avishay Tal +1 more
publishedtheoryhighly cited similarity 0.64
Abstract · 26 pages. Revision: Generalized the main results to all fields, added new applications and improved some existing ones, and expanded the exp…

We prove that the XOR of $k$ majorities on disjoint blocks of $\ell$ bits has correlation at most $(4d/\sqrt{\ell})^k$ with every Boolean-valued degree-$d$ polynomial over an arbitrary field. By known techniques, we obtain explicit pseudorandom generators that fool such polynomials on $n$ Boolean inputs with seed length $d^2\cdot\polylog(n/\varepsilon)$. The correlation and the generator extend to small $\mathsf{AC}^0[q]$ circuits, for every fixed prime power $q$. These results resolve several long-standing questions in circuit complexity and pseudorandomness.

0.61

Improved lower bounds for decomposable randomized encoding

cs.CC cs.CRcs.DM ·2026-09-16 ·Justin Holmgren, Kewen Wu
theory similarity 0.63
Abstract · 24 pages

A decomposable randomized encoding (DRE) for a function $f$ allows $n$ parties, using shared randomness, to encode their individual inputs locally so that the collection of encodings reveals $f(x_1,\ldots,x_n)$ and nothing else. DREs are widely used in efficient multiparty computation. Their main complexity measure is size, the total bit length of the local encodings. Yet the optimal DRE size remains poorly understood even for the $n$-bit OR function. We prove the first superlinear lower bound for OR and, more generally, for every non-periodic symmetric function. Under an additional symmetry assumption, we prove a sharp $Ω(n\log n)$ lower bound for OR, matching the classic construction of Feige, Kilian, and Naor (STOC 1994). We also prove the first $Ω(n^2)$ lower bound on DRE size for non-explicit Boolean functions.

0.46

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

cs.CC cs.DS ·2026-10-25 ·Khaled Elbassioni
theory similarity 0.61
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.

0.16

A Little Derandomization Goes a Long Way: Unconditional Circuit Lower Bounds using Low-Degree PIT

cs.CC ·2026-11-05 ·Nikolai Chukhin, Karthik Gajulapalli, Alexander Golovnev, Ivan Mihajlin
theory similarity 0.61
Abstract

We prove unconditionally that either NE contains a language requiring Boolean circuits of size at least $2^n/(2n)$, or $VP^0_{\mathbb{Z}}\ne VNP^0_{\mathbb{Z}}$, a constant-free version of Valiant's conjecture over the integers. The Boolean alternative implies that $NP\not\subseteq SIZE[n^k]$ for every constant $k\ge1$. Our proof gives a fine-grained variant of the connection between Polynomial Identity Testing (PIT) and circuit lower bounds established by Kabanets and Impagliazzo (2004). We show that the specific identity tests required by this argument can be performed over the integers without a derandomization assumption. Over a fixed finite field $\mathbb{F}$, we first give a deterministic $O(st^{d-1})$-time algorithm for PIT on size-$s$ circuits computing degree-$d$ polynomials in $t$ variables. We further show that, for any fixed $d\ge2$ and $\varepsilon>0$, improving this running time by a factor of $t^{\varepsilon}$, even nondeterministically, implies either the same Boolean lower bound or an arithmetic circuit lower bound of $t^{1+\varepsilon/2}$ for a polynomial family from $VNP_{\mathbb{F}}$. If nondeterministic PIT instead runs in time $s^{o(d)}t^{(1-\varepsilon)d}$ for infinitely many degrees $d$, then the arithmetic lower bound strengthens to $VP_{\mathbb{F}}\ne VNP_{\mathbb{F}}$. Over the integers, we give a deterministic PIT algorithm for syntactically set-multilinear circuits running in time $s^{O(1)}t^{5d/6}$, which yields the unconditional result above. Combining the Kabanets-Impagliazzo argument with range avoidance, we show that an NP algorithm for PIT over $\mathbb{Z}$ gives a purely arithmetic win-win: either $VP_{\mathbb{Z}}\ne VNP_{\mathbb{Z}}$, or constant-degree polynomials of maximum circuit complexity can be constructed in FNP.

0.23

Characterizing Quantum Advantage for Generalizations of the Boolean Hidden Matching Problem

cs.CC quant-ph ·2026-10-05 ·Mark Bun, Joao F. Doriguello, John Kallaugher, Nadezhda Voronova
similarity 0.61
Abstract

We study the one-way communication complexity of the $f$-Boolean Hidden Partition problem. Here, Alice is given an $n$-bit string and Bob is given $Ω(n)$ disjoint blocks of its indices together with a string of labels. Under the promise that the evaluations of $f$ on these blocks either agree with all of the labels or disagree with all of them, Bob must determine which is the case using a single message from Alice. This problem generalizes the Boolean Hidden Matching and Hidden Hypermatching problems, which capture the special case where $f$ is the parity function. We establish classical and quantum communication bounds for $f$-Boolean Hidden Partition in terms of the sign degree $d$ of $f$, proving a conjecture of Doriguello and Montanaro (TQC 2020). Their prior work gave logarithmic communication upper bounds for classical protocols when $d \le 1$ and quantum protocols when $d \le 2$, as well as polynomial lower bounds for certain structured functions with larger sign degree. We show that for every $f$ of sign degree $d \ge 2$, the randomized classical communication complexity of this problem is $Θ(n^{1-1/d})$ while its quantum communication complexity lies between $Ω(n^{1-2/d})$ and $\bO{n^{1-1/\lceil d/2 \rceil} \log n}$. This completely characterizes the functions $f$ admitting polynomial quantum advantage as those for which $d \ge 2$, with a new infinite family of exponential separations given by the case $d = 2$.

0.06

The Maximum Nonlinearity of 8-variable Balanced Boolean Functions is 116

cs.IT cs.CR ·2026-10-13 ·Yueying Lou, Youle Xu, Qichun Wang
similarity 0.60
Abstract

Does there exist an 8-variable balanced Boolean function with nonlinearity 118? This is a famous and long-standing open problem in Boolean functions. In this paper, we give a negative answer to this open problem, and prove that the maximum nonlinearity of balanced Boolean functions in 8 variables is 116, establishing the 8-variable instance of Dobbertin's conjectured recursion for the minimum Walsh peak of balanced functions. Equivalently, the covering radius of the Reed--Muller code RM(1,8) in 0-resilient Boolean functions is 116. We deduce the result by obtaining a quadratic form of polar rank 6, and reducing the problem to the existence of a 6-variable Boolean function with nonlinearity greater than 26 whose Hamming distance to a bent function is between 4 and 6.

0.30

Block Sensitivity and Certificate Complexity of Rotation Symmetric Boolean Functions

cs.CC math.COcs.DM ·2026-10-12 ·Yuan Li, Jing Zhang
theory similarity 0.60
Abstract · Version 2, 44 pages

We investigate block sensitivity and certificate complexity of monomial rotation-symmetric Boolean functions, obtaining exact formulas and structural classifications for several families. For odd-degree monomial rotation-symmetric functions, the equality $s(f)=n$ established in our earlier work yields $bs(f)=C(f)=n$. For quadratic monomial rotation-symmetric functions, we determine both measures completely and prove that block sensitivity equals certificate complexity. For consecutive quartic monomials, we determine sensitivity, block sensitivity, and certificate complexity in every residue class of the number of variables. Our principal result is an exact global block-sensitivity formula for consecutive monomials of every even degree $d\ge4$. Writing $n=q(d+2)+ρ$, where $0\leρ<d+2$ and $q\ge\max\{2,d/2-1\}$, we prove \[ bs(F_{d,n})=n-\min\left\{\left\lceil\fracρ{2}\right\rceil,d+2-ρ\right\}. \] We also establish the corresponding sensitivity formula by a self-contained argument, yielding arbitrarily large gaps between sensitivity and block sensitivity as the degree varies. For certificate complexity, we obtain exact pointwise formulas for structured run-and-gap configurations and establish additional global equalities, including $C(F_{6,8q+5})=bs(F_{6,8q+5})=8q+2$ for $q\ge2$. Our methods combine cyclic run decomposition, parity arguments, explicit sensitive-block constructions, and constant-subcube certificates. The exact global certificate complexity for arbitrary even degrees remains open.

0.43