CS Paper Radar

Tight Lower Bounds for Algebraic Communication and Applications

Manon Blanc, Prateek Dwivedi, Magnus Rahbek Dalgaard Hansen, Nutan Limaye, Meena Mahajan

cs.CC ·submitted 2026-09-15 12:19 UTC · v2
publishedtheory

Abstract

Communication complexity studies how much information must be exchanged to solve a problem whose input is split among two or more parties. In this work, we study an algebraic variant, where the inputs are vectors over a field $\mathbb{F} \in \{\mathbb{R}, \mathbb{C}\}$. There are two players, Alice and Bob, with inputs $X\in \mathbb{F}^n$ and $Y\in \mathbb{F}^n$, respectively. In the polynomial evaluation problem, the goal is to compute the value of a polynomial $g\in \mathbb{F}[X,Y]$ on the given input. In the set-recognition problem, the goal is to decide whether $(X,Y)\in S$, for a given set $S\subseteq \mathbb{F}^{n} \times \mathbb{F}^n$. In both settings, Alice and Bob send evaluations of polynomials depending only on their own inputs. In the set-recognition problem, a referee receives the messages and may apply polynomial tests to the messages received so far; the outcomes of these tests determine acceptance or rejection. The protocols may be deterministic or probabilistic. We give non-trivial upper bounds for a range of natural polynomial evaluation and set-recognition problems. We also prove reductions between different problems. Our main technical contribution is a general framework for proving lower bounds for algebraic set-recognition problems. Using this framework, we prove several probabilistic lower bounds for natural problems. In a number of cases, these lower bounds match the corresponding upper bounds, giving tight or near-tight characterizations of their algebraic communication. Finally, we give two applications of our framework. First, we use the communication lower bounds to prove lower bounds for a class of left-to-right algebraic algorithms, which we call algebraic scanners. Second, we show that our lower bound arguments extend beyond polynomials to a more general algebraic computational setting inspired by the Blum--Shub--Smale model.

Comment
Strengthened the deterministic Equality lower bound, thereby also proving the Unordered Equality lower bound. Minor improvements to the presentation

Closest papers

Nearest neighbours by meaning across the whole index.

Improved Local Leakage Resilience of Shamir Secret Sharing and Worst-Case Optimal Polynomial Intersection

cs.CR quant-phcs.DMcs.IT ·2026-10-08 ·Yihang Sun, Mary Wootters
similarity 0.63
Abstract · 82 pages, 3 figures; v2 adds near-optimal OPI discrepancy for random Reed-Solomon codes

We study two problems: Local Leakage Resilience (LLR) for Shamir secret sharing, and worst-case Optimal Polynomial Intersection (OPI), over a prime field $\mathbb{F}_p$. For a polynomial $Q(X)$ of degree less than $k$, LLR for Shamir secret sharing asks what a few leaked bits from each of the $n$ shares $Q(α_1), \ldots, Q(α_n)$ reveal about $Q(0)$. Given (worst-case) input lists $S_1, \ldots, S_n \subset \mathbb{F}_p$, OPI seeks a polynomial $Q(X)$ so that $Q(α_i) \in S_i$ for as many $i$ as possible. Leveraging recent connections between these two problems due to (Sun, Wootters 2026), we improve the state-of-the-art for both problems. For LLR, we show that there is some constant $δ> 0$ so that Shamir secret-sharing is one-bit LLR (only a negligible amount about $Q(0)$ is learned) whenever $R := k/n \geq 1/2 - δ$. This is the first result to break the so-called ``one-half barrier'' for LLR, and improves over the previous best known result, requiring $R \geq 0.668$ (Kasser, 2025). For OPI, we give a quantum algorithm that finds a polynomial $Q(X)$ that agrees with at least a $\mathsf{SCL}_ρ(R)-\varepsilon$ fraction of the lists, for every fixed $\varepsilon>0$, where $\mathsf{SCL}_ρ$ is the \emph{semicircle law} of (Jordan et al., 2025). This improves previous algorithmic (and existential) results of (Jo, 2026) and (Horinaga, Yamakawa, 2026). We also give further improved existential results for all OPI instances; and when the evaluation points $α_i$ are chosen at random, for every rate $R > 0$ we show that, with high probability, for worst-case $S_i$ there exists \emph{perfect} solution. Finally, we adapt the hardness result of (Yamakawa, Zhandry, 2024) to apply to OPI (rather than a folded version); this gives an unconditional separation between the quantum and classical hardness of OPI relative to a membership oracle.

0.49

Improved Algorithms for the Remote Point Problem

cs.CC cs.DS ·2026-09-22 ·Ben Lee Volk
published similarity 0.62
Abstract

The Remote Point Problem (RPP) is an algorithmic problem that asks, given a linear subspace $L \subseteq \mathbb{F}^n$ of dimension $k$, to deterministically find a vector $v \in \mathbb{F}^n$ far in Hamming distance from $L$. This problem was introduced by Alon, Panigrahy and Yekhanin [APY09], motivated in part by the matrix rigidity approach for proving circuit lower bounds. An algorithm is said to achieve remoteness $d$ if it finds a vector $v$ whose Hamming distance from $L$ is at least $d$. We observe that over the rational numbers, the problem admits a deterministic polynomial-time algorithm that achieves optimal remoteness $n-k$. Over finite fields, we obtain a (modest) improvement of a result of Alon, Panigrahy and Yekhanin [APY09], and give an algorithm that achieves remoteness $Ω\left(\frac{n}{\max\{k, \log n\}} \log n\right)$.

0.35

Generalized Hamming weights of codes arising from complete intersection

cs.IT math.AC ·2026-08-20 ·Eduardo Camps Moreno, Flavio Salizzoni, Rodrigo San-José
similarity 0.61
Abstract · 5 pages

We provide a positive answer to a conjecture proposed by Tohǎneanu and Van Tuyl regarding the minimum distance of codes whose underlying set of points is a reduced complete intersection. Despite the technical nature of the conjecture, we show that it follows directly from a not-well-known refinement of the classical Bézout bound for overdetermined polynomial systems. For completeness, this paper presents a self-contained proof of this refined bound. Furthermore, we show that using the same approach, it is possible to obtain a bound on the generalized Hamming weights of such a code and, more generally, to control the minimum distance of the codes obtained by evaluating forms of degree $d$ on the points of a zero-dimensional complete intersection.

0.33

Capacity regimes for Boolean function computation via channels

cs.IT ·2026-08-11 ·Jingge Zhu, Matthias Frey
similarity 0.61
Abstract · A part of this work has been reported in https://arxiv.org/pdf/2601.12640

Consider a point-to-point communication system in which the transmitter holds a binary message of length $m$ and transmits a corresponding codeword of length $n$. The receiver's goal is to recover a Boolean function of that message, where the function is unknown to the transmitter, but chosen from a known class $F$. We are interested in the asymptotic relationship of $m$ and $n$: given $n$, how large can $m$ be (asymptotically), such that the value of the Boolean function can be recovered reliably? This problem generalizes the identification-via-channels framework introduced by Ahlswede and Dueck. In this paper, we formulate the notion of computation capacity, and derive achievability and converse results for a large class of functions $F$, characterized by the Hamming weight of functions. Different from the classical transmission problem, the performance of the function computation problem is jointly characterized by the computation capacity and the rate function, namely how $m$ scales with $n$ asymptotically. Our results give a complete characterization of the rate function of the computation problem, and provide upper and lower bounds on the computation capacity, where they differ by a factor of at most $2$.

0.52

Plotkin-type Bound on Function-Correcting Codes for Monomial Mappings

cs.IT ·2026-10-03 ·Kanchana Lokshmii Jagatti, B. Sundar Rajan
published similarity 0.59
Abstract · Proceedings of IEEE International Conference on Advanced Networks and Telecommunications Systems (ANTS), 2026 (To appear)

Function-correcting codes, recently introduced by Lenz et al.\ (2023), provide a framework for the receiver to provide a higher level of protection against channel errors than the level of protection for messages. In this paper, we derive a generalised Plotkin-type bound on the redundancy of FCCs under the Hamming metric for arbitrary functions over finite fields. The proposed bound recovers the classical Plotkin bound for classical error-correcting codes as a special case. We further obtain explicit Plotkin-type bounds for linear functions, Hamming-weight functions, and Hamming-weight threshold functions. In addition, we study FCCs for monomial mappings $f(x)=x^n$ over $\mathbb{F}_{q^k}$, which are widely utilised in coding theory, cryptography, and finite geometry, and derive an explicit Plotkin-type redundancy bound.

0.14

Approximate Polynomial Satisfiability is in the Counting Hierarchy

cs.CC ·2026-09-30 ·Nikhil Balaji, Mahsa Shirmohammadi, Sébastien Tavenas, James Worrell
theory similarity 0.59
Abstract

The Approximate polynomial satisfiability problem (APS), introduced by Guo, Saxena, and Sinhababu (CCC 2018), asks whether the zero vector lies in the Zariski closure of the image of a given polynomial map. Specifically, for a field $k$ with algebraic closure~$K$, the problem asks whether $\boldsymbol 0 \in\overline{\boldsymbol f(K^n)}$ for a polynomial map $\boldsymbol f=(f_1,\ldots,f_m)$ with $f_i\in k[X_1,\ldots,X_n]$. APS is a natural topological analogue of Hilbert's Nullstellensatz, namely the question of whether a given system of polynomial equations has a common zero. APS captures several problems in algebraic complexity, including border rank, hitting sets for border classes, and null-cone membership; it is known to be NP-hard and in PSPACE. We show that APS lies in the Counting Hierarchy (CH) over both the rationals and finite fields, substantially improving the known PSPACE upper bound. Our proof builds on a recent breakthrough due to Andrews, Garg, and Schost (FOCS 2026) on deciding Hilbert's Nullstellensatz in CH. As a corollary, our result improves the complexity of certifying hitting sets for border classes from PSPACE to CH. We also give a polynomial-time reduction of Hilbert's Nullstellensatz to APS, valid in any characteristic. In characteristic zero, we give a reduction of APS to the decision problem for the existential theory of real closed fields. Overall, our results place approximate polynomial satisfiability closer in complexity to exact polynomial feasibility and as a byproduct give improved complexity bounds for several problems arising in approximative complexity.

0.53

New bounds for the support of input-output equations in differential-algebraic systems

cs.SC math.AG ·2026-09-03 ·Gabriela Jeronimo, Leonardo Lanciano
theory similarity 0.59
Abstract · 26 pages

Given a polynomial dynamical system $\mathbf{x}'=\mathbf{f}(\mathbf{x},\mathbf{u})$ together with an observation function $y=g(\mathbf{x},\mathbf{u})$, where $\mathbf{x}=(x_1,\ldots,x_n)$, $\mathbf{u}=(u_1,\ldots,u_m)$ and $y$ are differential variables, and $\mathbf{f}=(f_1,\ldots,f_n)$, $g$ are polynomials with coefficients in a differential field, we study the problem of determining a minimal polynomial differential equation satisfied by the inputs $\mathbf{u}$ and the output $y$ which follows as a differential consequence of the system. We provide a characterization of a finite superset of the set of monomials appearing with non-zero coefficients in this input-output equation. Specifically, we establish an upper bound for the degree of the minimal polynomial and a family of inequalities that define a polytope containing its Newton polytope. These results extend recent work by Mukhina and Pogudin for systems with constant parameters, and enable the use of evaluation-interpolation techniques for the efficient computation of such eliminant polynomials.

0.30

Deterministic Shift Equivalence Testing for Sparse Polynomials

cs.DS cs.CC ·2026-10-19 ·Markus Bläser, Pranjal Dutta, Sagnik Dutta, Gorav Jindal
top venue similarity 0.59
Abstract · To appear in SODA 2027

We study the shift equivalence testing problem for high-degree sparse multivariate polynomials. Given explicit spar se representations of two polynomials $f,g\in\mathbb{Q}[x_1,\ldots,x_n]$, with exponents encoded in binary, sparsities $s$ and $t$, and total degree at most $d$, the task is to decide whether there is a vector $\mathbf{a}\in\mathbb{Q}^n$ such that $f(\mathbf{x}+\mathbf{a})\equiv g(\mathbf{x})$. Furthermore, one needs to output such a vector if it exists. Dvir, Oliveira, and Shpilka (ICALP 2014) studied shift equivalence for low-degree arithmetic circuits. Their framew ork does not apply directly to sparse polynomials, which are not closed under shifts, and they left open whether shift equivalence of sparse polynomials admits an efficient deterministic algorithm. We answer this question positively over $\mathbb{Q}$. If the input coefficients have bit-size at most $τ$, we sh ow that a rational shift of polynomial bit-size exists whenever the polynomials are shift equivalent. Moreover, our alg orithm outputs such a shift and has a running time of $\operatorname{poly}(n,s,t,τ,\log d)$ in the bit model. The ar ithmetic and structural parts of our result also hold over any field of characteristic zero or characteristic larger th an $d$.

0.37