CS Paper Radar

Sharp Logarithmic-Product Bounds for List Replicability of Sign Matrices

Guangjian Zhang

cs.LG math.CO ·submitted 2026-11-07 02:43 UTC · v1
theory

Abstract

List replicability measures how many accurate hypotheses suffice to contain the output of a learning rule with arbitrarily high confidence. We prove that every nonempty class of $m$ binary concepts on $n$ domain points has list replicability at most $805\ln(2m)\ln(2n)$. This resolves the logarithmic-product conjecture of Blondal, Hatami, Hatami, Lalov, and Tretiak. Hanner matrices give lower bounds of the same order, for square matrices and for explicit families with unequal logarithmic aspect ratios. The upper bound is obtained by constructing nested acyclic sets in the faces of a cube. A critical-point estimate supplies highly connected regions, weighted cell attachments keep the sets compatible across faces, and a cubical carrier theorem converts them into accurate finite covers and learning rules. Appending one constant coordinate turns list replicability into an exact geometric quantity, the face width, and graph-orientation classes satisfy exact product formulas. In particular, there are explicit classes with list replicability $4k+1$ and equivariant index $3k$, so the additive gap between the two is unbounded. We also develop entropy-tilting and two-sided Gibbs constructions, give combinatorial upper bounds adapted to structured matrices, compute exact values on classical families, and study the index of Paley matrices.

Comment
292 pages

Closest papers

Nearest neighbours by meaning across the whole index.

A polylogarithmic bound for list replicability

cs.LG stat.MLmath.CO ·2026-10-14 ·Ari Blondal, Hamed Hatami, Pooya Hatami, Chavdar Lalov, Sivan Tretiak
theory similarity 0.69
Abstract

Zhang [Zha26] recently posted a manuscript announcing that the list-replicability number of every class of $M\ge 2$ binary concepts on $N\ge 2$ domain points is $O(\log^2 M\log N)$, which would be the first polylogarithmic upper bound on this quantity. In this note, we present a short, self-contained proof of this bound, following the high-level approach of the manuscript but with considerably simpler arguments.

0.21

Near-Optimal List Replicability from Littlestone Dimension

cs.LG ·2026-10-23 ·Ari Blondal, Pooya Hatami, Chavdar Lalov, Sivan Tretiak
theory similarity 0.61
Abstract · 14 pages

We study the list replicability number in the realizable PAC learning framework and prove that every concept class $H$ over a countable domain with Littlestone dimension $d$ and dual VC dimension $v^*$ satisfies \[ \mathrm{LR}(H)\leq 2^{O(d\min\{\log d,v^*\})}. \] This matches the worst-case lower bound of $2^{Ω(d)}$ up to a logarithmic factor in the exponent and exponentially improves the previous best upper bound $\mathrm{LR}(H)\le 2^{2^{O(d)}}$ of Bun, Livni, and Moran [FOCS 2020]. Unlike earlier bounds of $2^{O_ε(d^2)}$ for fixed accuracy $ε>0$ implied by the work of Ghazi, Golowich, Kumar, and Manurangsi [STOC 2021] and Lyu [STOC 2026], our bound is independent of $ε$. The $2^{O(d\log d)}$ bound follows from a new inductive framework for bounding list replicability that builds on the recent notion of irreducibility from differentially private learning. The $2^{O(dv^*)}$ bound follows from a simple globally stable learner that takes the majority vote of multiple empirical risk minimizers, with stability established using tools from stable regularity.

0.19

Unconditional Boolean Dynamic Lower Bounds from Disjointness

cs.DS cs.CC ·2026-10-07 ·Young Kun Ko
theory similarity 0.60
Abstract · 48 pages, 3 figures. v2: main result stated for the multiphase problem; appendix extended to further dynamic problems; introduction revised.…

We prove an unconditional $Ω((\log n/\log\log n)^2)$ lower bound on the maximum of the worst-case update time and expected query time for the insert-only version of Patrascu's multiphase Disjointness problem [STOC 2010]. The bound holds in the zero-error cell-probe model with logarithmic word size. Patrascu's reductions transfer it to directed reachability under edge insertions, already on directed acyclic graphs of depth $2$. This improves the $\widetildeΩ(\log^{3/2} n)$ bound of Larsen and Yu [SICOMP 2025] to the quadratic-logarithmic scale previously attained for dynamic range counting and multiphase Inner Product. The bound also transfers to a broad collection of dynamic graph, algebraic, geometric, and string problems. We also obtain a separation between amortized and worst-case time for streaming regular-expression membership. For a simple family of expressions of maximum length $M$ over a polynomial-size alphabet, a deterministic algorithm uses $O(1)$ amortized time per symbol on every input stream, whereas every zero-error cell-probe algorithm with word size $w=Θ(\log M)$ requires $Ω((\log M/\log\log M)^2)$ time on some symbol. The proof adapts Ko's 2.5-round multiphase communication framework [FOCS 2026] from Inner Product to Disjointness. Our main technical observation is that the protocol's verification step allows a one-sided corruption bound to replace the discrepancy property used for Inner Product.

0.24

Local Modifications of Nearest-Neighbor and Min-Plus Representations

cs.CC cs.DM ·2026-11-10 ·Liliia Redina
theory similarity 0.59
Abstract · 19 pages, 2 figures

We study how changing a Boolean-valued function at $d$ inputs affects the size and precision of its exact representations. Starting from a representation of size $m$, we prove four bounds, two for nearest-neighbor (NN) representations and two for integer min-plus representations. (i) For NN representations on a finite subset of $\mathbb{R}^n$ with $n\ge2$, at most $m+2d$ anchors suffice. The coefficient $2$ is optimal: on a three-point domain, changing one value can increase the minimum number of anchors from one to three. (ii) For NN representations on the Boolean cube with rational anchors, let $R$ be the maximum original coordinate bit length, and let $Δ$ be the maximum bit length of the least common denominator of any one original anchor's coordinates. We construct a representation with at most $m+3d$ anchors on a common dyadic grid and coordinate bit length $O(R+Δ+\log(n+1))$. (iii) For integer min-plus representations on the Boolean cube, we give a construction that keeps the original $m$ forms and their labels and adds at most $d$ new forms. Its maximum weight is at most $W+2n$, where $W$ is the largest absolute original coefficient, including constant terms. (iv) For integer min-plus representations on a finite rational domain $X\subset\mathbb{Q}^n$, at most $m+2d$ forms suffice. Their maximum weight is polynomially bounded in $m,d,W,n,|X|$, the coordinate bound, and the common denominator of $X$. The coefficient $2$ is again optimal: on a three-point domain, changing one value can increase the minimum number of forms from one to three. These bounds imply stability under polynomially many changes on the cube for polynomial-size representations, including those with polynomially bounded NN coordinate bit length or min-plus weight.

0.26

Improved Algorithms for the Remote Point Problem

cs.CC cs.DS ·2026-09-22 ·Ben Lee Volk
published similarity 0.59
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

Complete bipartite embeddings, lattice non-embeddability, and non-Euclidean powers of information distance

cs.IT ·2026-09-30 ·Fengqi Hou
similarity 0.58
Abstract · 15 pages. Lean formalization included as ancillary files

We encode the vertices of every finite complete bipartite graph as binary strings at each scale. The information distances between these strings approximate the scaled graph distances with an additive error bounded by a constant independent of the scale. We also assign one fixed infinite binary sequence to each vertex; suitable prefixes satisfy the same distance estimate with logarithmic error. This extends Hutter's construction for $K_{3,3}$ and resolves his open problem on scale-embeddings of finite complete bipartite graphs. Combined with his complete bipartite obstruction, these embeddings show that no positive power of information distance can be represented exactly by distances in a real Hilbert space, resolving his question about such representations. For conditional prefix complexity, we further prove that at most $2^{δ+C}$ strings lie between any two strings with total distance exceeding their mutual distance by at most $δ$, where $C$ is independent of the endpoints. This bound rules out scale-embeddings of the integer line and every positive-dimensional integer lattice, resolving Hutter's lattice embedding problem for both string and sequence embeddings. Restriction to the integer lattice gives the same conclusion for $(\mathbb R^m,\|\cdot\|_1)$ for every $m\ge1$.

0.12

Counting and Covering in Nearest-Neighbour Representations of Boolean Functions

cs.DM cs.LGmath.CO ·2026-09-19 ·Martin Anthony
theory similarity 0.58
Abstract · 55 pages, 1 diagram, 1 table

We study the number of prototypes needed to represent Boolean functions by nearest-neighbour classification. There are two distinct settings: the prototypes may be arbitrary points of Euclidean space, or they may themselves be required to lie in the Boolean cube. For unrestricted prototypes, we strengthen a known lower bound for almost all Boolean functions. The bound applies simultaneously to nearest-neighbour voting rules with any number of voting neighbours, and substantially narrows the gap with the known general upper bound. We obtain a VC-dimension bound for classes with a bounded number of prototypes, and show that it is sharp in order in dimensions at least four. We then study Boolean prototypes, beginning with symmetric threshold functions. A connection with covering designs expresses the minimum number of prototypes at every threshold level exactly in terms of a covering number, and leads to further exact results for related monotone functions, including disjunctive extensions and a characterisation of when a representation with a single negative prototype is possible. For a uniformly random Boolean function, the Boolean nearest-neighbour complexity, as a proportion of the cube, is asymptotically close either to one half or to one, with explicit limiting probabilities. In particular, almost every Boolean function requires at least approximately half as many prototypes as there are points in the cube, and one half is the largest proportion for which such a lower bound holds. Finally, we consider arbitrary symmetric Boolean functions. Their Boolean nearest-neighbour complexity is closely approximated by a weighted vertex-cover problem on paths. As a consequence, a uniformly random symmetric function typically requires prototypes amounting to $11/20$ of the cube. This is much larger than the upper bounds known when the prototypes are allowed to lie anywhere in Euclidean space.

0.31

Combinatorial Boolean Matrix Multiplication in $n^3 / 2^{Ω(\sqrt{\log n})}$ Time

cs.DS ·2026-11-04 ·Piaoyang Cui, Yiming Liu, David P. Woodruff
similarity 0.58
Abstract

For over fifty years, combinatorial algorithms for Boolean matrix multiplication (BMM) and triangle detection saved only polylogarithmic factors over cubic time. At STOC 2024, Abboud, Fischer, Kelley, Lovett, and Meka broke this barrier with a deterministic $O(n^3 / 2^{Ω((\log n)^{1/7})})$-time algorithm, and asked whether $n^3 / 2^{Ω(\sqrt{\log n})}$ time is achievable. We answer this question in the affirmative, giving deterministic combinatorial algorithms for both BMM and triangle detection running in $O(n^3 / 2^{Ω(\sqrt{\log n})})$ time. Following Abboud et al., we decompose $(A,B)$ into pairs of submatrices $(A_k,B_k)$, called \emph{pieces}, each of which is either sparse or pseudorandom in a sense that forces $A_k\star B_k$ to be nearly all-ones on its vertex sets. Whereas their decomposition produces $2^{O(d^7)}$ pieces at regularity parameter $d$, we obtain $2^{O(d^2)}$ pieces, directly improving the runtime exponent from $(\log n)^{1/7}$ to $\sqrt{\log n}$. Prior work found pseudorandom pieces by repeatedly restricting to denser submatrices, paying worst-case vertex losses at each step that compounded across nested recursion levels, together with an expensive derandomization step. We eliminate the extra powers of $d$ by matching the vertex loss at each step to the size of its density jump so losses telescope across scales, derandomizing witness search via $L_d$-norm estimation so the sampler length stays $2^{O(d)}$, and bounding overlap across the recursion with a fractional density-weighted volume budget rather than raw submatrix volume.

0.20