CS Paper Radar

Linear Set Reconciliation with $O(d)$ Additive Redundancy

Tianren Liu, Rui Xu, Tong Yang, Kangyang Zhou

cs.DS cs.IT ·submitted 2026-11-08 14:23 UTC · v1

Abstract

In set reconciliation, two parties holding sets $A, B \subseteq [n]$ with $|A \triangle B| \le d$ seek to recover their symmetric difference from short $\mathbb{F}_2$-linear sketches, which is equivalent to recovering a $d$-sparse vector $x = \mathbf{1}_{A \triangle B} \in \mathbb{F}_2^n$ from its syndrome $Hx \in \mathbb{F}_2^m$. While the information-theoretic counting bound requires $L(n,d) := \log \sum_{i=0}^d \binom{n}{i} = d\log(n/d) + Θ(d)$ bits, existing polynomial-time schemes either use at least $d\lceil\log(n+1)\rceil$ bits (algebraic sketches, leaving an $Ω(d\log d)$-bit gap) or incur a multiplicative $(1+δ)L(n,d)$ overhead (peeling-based sketches), raising the question of whether $L(n,d) + O(d)$ bits is achievable with fast updates and decoding. We construct a public-coin randomized $\mathbb{F}_2$-linear sketch of length $L(n,d) + O(d) + λ\log^{O(1)} n$ that recovers each fixed input of weight at most $d$ with probability at least $1 - 2^{-λ}$, with $\log^{O(1)} n$ update time and $d\exp(O((\log\log n)^2)) = dn^{o(1)}$ worst-case decoding time. In particular, for $n \le 2^{\operatorname{polylog}(d)}$ and $λ\le d^{1-Ω(1)}$, this achieves $L(n,d) + O(d)$ bits with $\operatorname{polylog}(d)$ update time and $d^{1+o(1)}$ decoding time. Our construction encodes $d$ permuted rows via randomly scaled Pinsketch syndromes and sketches the resulting bit array column by column. Decoding columns sequentially from prefix predictions cancels recovered rows and exposes undecided rows as decoder-side hints, reducing each column to a hinted sparse recovery problem that we solve via a recursive sketch, HintSketch.

Closest papers

Nearest neighbours by meaning across the whole index.

Improved Algorithms for Beck--Fiala with Bounded Sets

cs.DS cs.DMmath.COmath.PR ·2026-09-17 ·Dylan J. Altschuler
similarity 0.65
Abstract · 11 pages, comments welcome

We give an efficient algorithm with improved algorithmic guarantees for the (offline) Beck--Fiala problem when the sets have bounded size. Let $A$ be an arbitrary matrix $A\in\{0,1\}^{m\times n}$ with at most $d$ ones per column and at most $s$ ones per row. Let $\log^*$ denote the iterated logarithm and $\ell_j$ denote the $j$-fold composition of log. Assume $s\le\exp(O(\sqrt d))$. We provide an efficient algorithm that, for arbitrary sparsity $d$, gives $O(\sqrt d(1+\log^*n))$ discrepancy. Moreover, if $d\ge\ell_j(n)$ for a fixed integer $j\ge1$, the algorithm gives $O_j(\sqrt d)$ discrepancy. The proof is a bootstrapping scheme using the Bansal-Jiang algorithm.

0.46

Toward Optimal Time-Space Tradeoffs for Set Reconciliation

cs.DS ·2026-09-13 ·Rui Xu, Kangyang Zhou, Jiachen Xu, Jiarui Guo, Boyu Xian +3 more
theorycode/data similarity 0.65
Abstract

Set reconciliation, where two parties each holding a large set of elements aim to identify their set difference, is a fundamental task in many areas. Time (computation cost) and space (communication cost) are two important metrics in this problem, and much existing work optimizes one at the expense of the other, creating a clear trade-off. We study this trade-off through algorithmic upper bounds and matching space lower bounds. On one side, we propose XYZ-Sketch. For sufficiently large $d$, XYZ-Sketch achieves high-probability reconciliation for sets whose differing elements are uniformly random, using only $(1+\varepsilon)d$ elements for communication, while achieving $O(\log(1/\varepsilon))$ insertion time and expected $O(d\log V\log^{3/2}(1/\varepsilon))$ decoding time, where $d$ and $V$ denote the size of the difference between two sets and the universe size, respectively. On the other side, we establish a broad fixed-support canonical model and prove a matching space lower bound, establishing the asymptotic optimality of XYZ-Sketch. Our proof also establishes an extremality theorem resolving Walzer's conjecture. Experiments demonstrate the practical advantages of XYZ-Sketch, and the source code is available at https://github.com/djwj233/XYZ-Sketch.

0.52

Deterministic Streaming Lower Bounds for Approximate Maximum Clique and Maximum Independent Set

cs.DS ·2026-09-16 ·Adithya Diddapur
theory similarity 0.63
Abstract · 25 pages, 1 figure

We study the canonical \textsf{Maximum Clique} and \textsf{Maximum Independent Set} problems in the one-pass edge-arrival graph streaming setting. Here, the edges of some input graph $G = (V,E)$ are presented one at a time (possibly including deletions), before an algorithm needs to produce either a large clique or independent set at the end of the stream, with the focus being on space complexity. We are interested in finding $β$-approximate solutions, for any $β\geq 1$. Previous work gave an algorithm using $\tilde{O}\left(n^2/β^2\right)$ bits of space, together with a corresponding $\tildeΩ\left(n^2/β^2\right)$ two-party communication lower bound [Halldórsson et al., ICALP'12], seeming to resolve the problem. However, their algorithm crucially relies on randomness, and the best known deterministic algorithm remains a folklore derandomisation using $O\left(n^2/β\right)$ bits of space, leaving a (deterministic) gap of size $\tilde{O}(β)$. We make progress towards this gap with a strong lower bound for a restricted range of $β$: whenever $β\leq \sqrt{n}/36\log n$, any deterministic algorithm for either problem must use $Ω\left(\frac{n^2}{β\cdot\log n}\right)$ bits of space. Our proof is via a two-party one-way communication lower bound, and highlights the power of randomness when approaching either of these problems.

0.30

An Improved Upper Bound for Recovering Pairs

cs.IT math.CO ·2026-10-02 ·Simone Costa
theory similarity 0.61
Abstract · Computational supplement, verifiers and outputs are available at https://doi.org/10.5281/zenodo.23093260

We prove that every recovering pair $(\mathcal{A},\mathcal{B})$ of nonempty families of subsets of an $n$-element set satisfies $$|\mathcal{A}||\mathcal{B}|\le\left(\frac{223949}{100000}\right)^n=(2.23949)^n.$$ A result of Mond, Souza and Versteegen, combined with the sharp $(9/4)^n$ bound of Fang and Huang for cancellative pairs, gives $(2.2499)^n$ for recovering pairs. We improve this to $(2.23949)^n$. The proof combines two entropy inequalities. One is derived directly from the recovering property, while the other applies the Fang-Huang bound to families obtained from the original pair by a construction of Mond, Souza and Versteegen. The two inequalities are then combined by a convex combination.

0.25

Improved Algorithms for the Remote Point Problem

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

An alternate proof of the QMA lower bound for set-size estimation

cs.CC quant-ph ·2026-11-16 ·Chinmay Nirkhe
theory similarity 0.61
Abstract · 5 pages

In the set-size estimation query task, a query algorithm decides whether an $N$-bit input has Hamming weight $\ge B$ or $\le A$ (with $\ge B$ as the yes instances and $\le A$ as the no instances). When $B = 2A$, this is sometimes called approximate counting. The query complexity for this problem with a quantum witness (i.e., $\mathsf{QMA}$ query bounds) was resolved by Aaronson, Kothari, Kretschmer, and Thaler (CCC 2020) and proved using Laurent polynomials. Here we give a morally similar but distinct proof of the lower bound using the polynomial method.

0.34

Revisiting Non-Adaptive Set Membership Schemes: Removing the Logarithmic Factor

cs.DS ·2026-10-14 ·Mirza Galib Anwarul Husain Baig, Aman Kumar, Pawan Kumar Saw, Vikash Tripathi
theory similarity 0.61
Abstract

We study non-adaptive bit-probe schemes for static set membership. Each query reads a fixed number of bits and answers by strict majority. We revisit the random bipartite-graph construction of Garg and Radhakrishnan [STACS, 2017]. The main observation is that a slightly stronger expansion property already bounds the number of exceptional elements. This makes a separate probabilistic estimate for exceptional elements unnecessary. A detailed union-bound calculation then gives, for every fixed $t\ge5$, a logarithm-free existence bound of $O_t(m^{1/c}n^{1-1/c})$, where $c=\lfloor(t-1)/2\rfloor$. For odd $t$, this removes the logarithmic factor from the general upper bound of Garg and Radhakrishnan [STACS, 2017].

0.17

Approximating Independent Sets Using Additive Combinatorics

cs.DS cs.CCmath.CO ·2026-10-18 ·Shachar Lovett
published similarity 0.61
Abstract

We give a deterministic quasi-polynomial time algorithm for approximating the largest independent set in a graph. We show that if an $N$-vertex graph contains an independent set of size $2^{-t} N$, then we can find an independent set of size $2^t$ in quasi-polynomial time, for all $t$ up to a constant factor of $(\log N)^{1/3}$. This gives an approximation factor of $N / \exp((\log N)^{1/3})$, which has the same shape as known hardness results for quasi-polynomial time algorithms, up to a different exponent of the logarithm. The algorithm builds on a structural principle: a graph containing a large independent set must also contain a large sparse structured set, and such a set can be found efficiently. A greedy algorithm then extracts an independent set from it. Our proof draws on tools in additive combinatorics, in particular spreadness and sifting, to obtain the combinatorial structural results. We then convert these to efficient algorithms using pseudo-marginals obtained by semidefinite programming.

0.60