CS Paper Radar

Explicit Constructions of Maximum-Cardinality Families of Plateaued Functions with Pairwise Disjoint Walsh Supports

Chen Wang, Xiaoyan Zhang, Chunming Tang, Zhengchun Zhou

cs.IT ·submitted 2026-09-18 06:59 UTC · v2
hot direction

Abstract

Families of plateaued Boolean functions with pairwise disjoint Walsh supports are useful in secondary constructions of cryptographic Boolean functions. Of particular interest are maximum-cardinality families whose members admit no nonzero linear structures. To the best of our knowledge, the previously known general construction attaining both properties is spectral (Hodžić et al., IEEE Trans. Inf. Theory 65(9): 5865--5879, 2019). In that work, explicit algebraic normal forms are not generally provided, and no general method is established for prescribing a common algebraic degree for all family members. In this paper, we present two new explicit algebraic constructions within a unified framework, one based on linear functions and the other on partially linear functions with bent components. Let $p\geq 2$ and $q\geq 0$ satisfy $q<2^p-p-1$, and set $m=p+q$. Both constructions yield maximum-cardinality families of $2^{q+1}$ $(q+1)$-plateaued Boolean functions with pairwise disjoint Walsh supports. No member admits a nonzero linear structure, and every member has an explicit generalized Maiorana--McFarland representation. The first construction produces functions in $m+p+1$ variables and realizes any prescribed common algebraic degree $3\leq d\leq p+1$, provided that $q<\sum_{i=2}^{d-1}\binom{p}{i}$; its maximum attainable degree $p+1$ is optimal. The second construction produces functions in $n+p+1$ variables, where $n>m$ and $n-m$ is even, and realizes any prescribed common algebraic degree $3\leq d\leq p+(n-m)/2$, provided that $q<\sum_{i=2}^{\min\{d-1,p\}}\binom{p}{i}$; its maximum attainable degree $p+(n-m)/2$ is next-to-optimal.

Closest papers

Nearest neighbours by meaning across the whole index.

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

Minimum distances of primitive narrow-sense BCH codes via good zero-sets

cs.IT ·2026-09-18 ·Run Zheng
similarity 0.63
Abstract

Determining the exact minimum distances of BCH codes remains a open problem. We establish the minimum distances of several families of primitive narrow-sense BCH codes, showing that they attain their designed distances. Our approach centers on $\mathbb{F}_q$-good zero-sets, which we introduce through a derivative condition on their vanishing polynomials. We show that a $q$-ary primitive narrow-sense BCH code of length $q^m-1$ and designed distance $2\leqδ\leq q^m-1$ has minimum distance $δ$ if and only if there exists an $\mathbb{F}_q$-good zero-set of cardinality $δ+1$ in the finite field $\mathbb{F}_{q^m}$ with $q^m$ elements. To construct $\mathbb{F}_q$-good zero-sets, we develop several methods based on polynomial substitutions, power maps, and shifted inverses, as well as direct constructions using polynomials of special forms. Together with suitable initial $\mathbb{F}_q$-good zero-sets, including those arising from known minimum-distance results, these methods yield new good zero-sets of various cardinalities and hence families of primitive narrow-sense BCH codes whose minimum distances equal their designed distances. These families cover a broad range of designed distances, with several known minimum-distance results recovered as special cases.

0.38

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

Higher-order nonhomomorphicity under affine restrictions

cs.IT math.CO ·2026-10-11 ·Serge Feukoua, Ana Sălăgean, Pantelimon Stănică
similarity 0.61
Abstract

We study the behavior of the $k$-th-order nonhomomorphicity of Boolean functions under restriction to affine subspaces. For odd $k\ge3$ and $0\le t<n$, we introduce the $t$-restriction $k$-th-order nonhomomorphicity $P_{k,t}(f)$, defined as the minimum of $P_k(f_{\mid A})$ over affine spaces of codimension at most $t$. For a direct sum of $m$ monomials of degrees at least two, we determine $P_{k,t}$ exactly. When $t<m$, a minimum is obtained by setting one variable equal to zero in each of the $t$ monomials of lowest degree. When $m\le t<n$, the minimum is zero. The proof combines multiplicativity of even Walsh moments with a contraction argument for affine restrictions. We establish a general formula for the Walsh transform of a Boolean function restricted to an affine subspace of arbitrary codimension, yielding an exact spectral characterization of the $t$-restriction normalized nonlinearity $\rnnl_t(f)$. As odd $k$ tends to infinity, $(1-2P_{k,t}(f))^{1/(k+1)}$ converges to $1-2\rnnl_t(f)$. We further prove that every non-affine function has a hyperplane restriction with strictly smaller odd-order nonhomomorphicity. Finally, we determine $\rnnl_1(T_{d,n})$ exactly for all threshold functions with $n\ge3$. This proves the two threshold-function conjectures left open in~\cite{SergeAnaPante2025}, including the previously unresolved odd-majority case, where a minimizing hyperplane is $x_1+x_2=0$.

0.23

From Block Orthogonality to Decidability in Complex-Weighted Counting CSP

cs.CC ·2026-08-14 ·Chenghua Liu, Boning Meng
theory similarity 0.60
Abstract · 68 pages; revised proof and exposition, including a correction; Lean repository linked

In a landmark JACM paper recognized with the 2021 Gödel Prize, Cai and Chen established a complexity dichotomy for counting CSPs over arbitrary finite domains with algebraic complex weights. Their tractability criterion consists of three conditions on the infinite family of functions obtained from CSP instances by summing out some variables: the Block Orthogonality and Type Partition conditions, and a Mal'tsev polymorphism condition on support and row-equivalence relations. They left open whether this criterion is decidable from the finite set of constraint functions. We resolve this question by giving a total exact algorithm for every $q$-element domain ($q\ge 1$), with algebraic weights encoded exactly. We also prove that the Block Orthogonality condition implies the other two conditions, reducing the tractability criterion to a single structural property. We obtain similar decidability and structural results for Lin's tractability criterion for $\#\mathrm{CSP}^{d}$, where each variable occurs a multiple of $d$ times. Our method first shows that every failure of Block Orthogonality can be witnessed by a generated function of arity at most $q^2+1$. At each such arity, we reduce checking infinitely many generated functions to finitely many exact algebraic tests, using tensor products and a pinned extension of Young's all-instance isomorphism theorem. For the structural implication, we use powers of generated functions to control complex cancellation and construct functions whose supports encode row equivalence. These constructions yield the Type Partition and Mal'tsev polymorphism conditions.

0.10

The covering radius of the first-order Reed-Muller code in nine variables is 242

cs.IT math.NTmath.CO ·2026-10-31 ·Yi Li
theory similarity 0.59
Abstract · 28 pages

We prove that the covering radius of the binary first-order Reed-Muller code RM(1,9) is exactly 242. Equivalently, the maximum nonlinearity of a Boolean function in nine variables is 242. Our proof combines a one-point rigidity theorem with a spectral and computational exclusion of the two larger candidate nonlinearities. We first show that every nine-variable Boolean function of nonlinearity 243 admits a unique one-point modification that raises its nonlinearity to 244: the point to be changed is the vector sum of its support. This part uses exact Walsh-update identities, integer interpolation, rigidity of a quadratic residue, and a sharp Walsh l1 estimate for cubic Boolean functions. To exclude nonlinearity 244, we use Parseval's identity and congruences of integral Walsh coefficients to force an exceptionally restricted spectrum. An associated cubic residue phase must attain the extremal Walsh l1 bound 10240. We eliminate one equality spectrum by hyperplane slicing; the other forces the original Boolean function from the signs of the cubic phase and yields a double-complement-pairing identity for its cubic top part. The classification of alternating trilinear forms over F2, an exact filter of their representatives, and two exhaustive enumerations of 218 quadratic supplements then rule out every remaining candidate. Together with the known construction attaining nonlinearity 242, these arguments establish the asserted covering radius.

0.12

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.59
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.47

On Non-Deterministic Representation of Boolean Functions

cs.CC ·2026-11-09 ·Sudharshan Rajagopalan, Nitin Saurabh
publishedtheory similarity 0.59
Abstract · 15 pages, to appear in FSTTCS 2026

We study non-deterministic representation of Boolean functions by polynomials, introduced by (de Wolf, 2000). A polynomial $p(x)$ is said to be a non-deterministic polynomial for a Boolean function $f$ if for all $a\in\{0,1\}^n$, $p(a)\neq 0$ iff $f(a)=1$. The non-deterministic degree of $f$, denoted $\mathsf{ndeg}(f)$, is the minimal degree of a non-deterministic polynomial for $f$. In this work, we show the following main results: - Almost all Boolean functions on $n$ variables have non-deterministic degree at most $n/2 + O(\sqrt{n\log n})$. This confirms a conjecture of (Iyer et al., 2023). Together with the lower bound of (Iyer et al., 2023) it establishes a tight bound on the rational degree of a random Boolean function up to lower order terms. - We disprove a conjecture of (Kothari et al., 2026) about effective hypercube nullstellensatz for more than two polynomials. On the positive side, we also identify a constraint under which an effective hypercube nullstellensatz holds for many polynomials.

0.22