CS Paper Radar

Differentially Oblivious Priority Queues with Sublogarithmic Cost

Zimai Guo, Cheng Hong, Zhechen Li

cs.DS cs.CC ·submitted 2026-11-03 12:16 UTC · v1
theoryhot direction

Abstract

In this paper, we study exact online integer priority queues under differential obliviousness in the balls-and-bins model. Given a public upper bound $T$ on the number of operations and assuming that the priorities are bounded by a polynomial in $T$, we construct an $(\eps,δ)$-differentially oblivious priority queue supporting insertion and minimum extraction, which requires $\polylog(T)$ private memory. For constant $\varepsilon>0$ and $δ=\exp(-Θ(\log^2 T))$, our construction incurs $O(\log T/\log\log T)$ expected amortized total work per operation, which breaks the $Ω(\log T)$ barrier for fully oblivious priority queues~[Jacob et al., SODA'2019]. Further, we prove a matching lower bound for $(\eps,δ)$-differentially oblivious priority queues with $\varepsilon=O(1)$ and $δ=o(1)$, which indicates that our construction is asymptotically optimal in terms of total work.

Comment
38 pages, 1 figure

Closest papers

Nearest neighbours by meaning across the whole index.

Differentially Private Multicolor Discrepancy and Fair Division of Indivisible Goods

cs.GT ·2026-09-14 ·Max Dupré la Tour
theory similarity 0.67
Abstract

We study the fair division of indivisible goods under pure differential privacy, continuing the line of work initiated by Manurangsi and Suksompong. For $n$ agents with nonnegative additive utilities over $m$ goods and a fixed privacy parameter, we give an entry-private algorithm that, with high probability, achieves consensus envy-freeness up to $O(\sqrt n+\log^3 m)$ goods. This substantially improves the dependence on $n$ over the previous $O(n\log m)$ guarantee for ordinary envy-freeness, while providing the stronger consensus guarantee. A key ingredient is a private algorithm for multicolor discrepancy, which may be of independent interest. Our algorithm may require exponential time. We also obtain substantially stronger guarantees under additional structure: when all item values belong to a public alphabet of size $D$, we give a polynomial-time entry-private algorithm achieving ordinary envy-freeness up to $O(\operatorname{polylog}(mD))$ goods with high probability. Finally, we prove an $Ω(\log n)$ lower bound on the number of goods that must be removed to achieve ordinary envy-freeness under entry privacy, for sufficiently many goods, even with binary utilities.

0.14

Approximating Combinatorial Contracts with Arbitrary Costs

cs.GT cs.DS ·2026-09-18 ·Xiaotie Deng, Hanyu Li, Chenghua Liu
theory similarity 0.66
Abstract

We study single-agent combinatorial contracts under linear payments. Under a reward share $α\in[0,1]$, an agent chooses a subset $S$ of $n$ hidden actions, generating reward $f(S)$ at cost $c(S)$, to maximize $αf(S)-c(S)$, while the principal receives $(1-α)f(S)$. For nonnegative additive rewards and monotone supermodular costs, Dütting et al. (SODA 2026) proved an exponential supply-query lower bound for exact optimization and left open whether a representation-independent approximation is possible. We resolve this question in a stronger form, removing all structural assumptions on the cost function: for nonnegative additive rewards, arbitrary normalized nonnegative set costs, and every $\varepsilon\in(0,1)$, we give a deterministic $(1-\varepsilon)$-approximation using $O(n\log(n+1)/\varepsilon)$ supply queries, with query complexity independent of numerical bit lengths and breakpoint separation. More generally, the same guarantee and asymptotic query complexity hold for normalized monotone subadditive rewards and arbitrary normalized nonnegative costs under exact best-response and value-query access. The key idea is a cost-independent, reward-side scale certificate. The algorithm tries all singleton rewards as candidate anchors; one of them brackets the optimal retained share within a factor $n^2$. Geometric search and monotonicity of the induced response reward then yield the approximation without enumerating best-response breakpoints.

0.26

Sharp Bounds for Truthful-in-Expectation Scheduling

cs.GT ·2026-11-03 ·Yunpeng Li
theory similarity 0.66
Abstract

We study randomized mechanisms for scheduling indivisible jobs on $n$ unrelated machines. Each machine is controlled by a selfish agent who privately knows its processing time for each job. A mechanism assigns every job to a machine and makes payments. We require truthfulness in expectation: no agent can increase its expected payment minus its expected processing cost by misreporting, regardless of the other agents' reports. The makespan is the maximum total processing time assigned to a machine; the objective is to minimize its expectation. We prove that the optimal approximation ratio is $(n+1)/2$ for every $n\ge7$, relative to the minimum makespan of an integral assignment. The lower bound holds for every $n$ and allows unrestricted computation and arbitrary correlations among assignments, assuming finite expected payments and a guarantee uniform over all finite job counts. The matching mechanism uses correlated rounding and runs in expected polynomial bit time on rational inputs. These guarantees hold for all finite nonnegative processing times. For two machines, we characterize the optimal approximation ratio exactly as an analytic constant, approximately $1.505995705434$, and give a mechanism attaining it. For three machines the optimal ratio is $2$. For four, five, and six machines we obtain upper bounds of $3$, $105/32$, and $29/8$, respectively, compared with the general lower bound $(n+1)/2$. The proofs for $n\ge7$ do not rely on computer-assisted certificates; the two- and three-machine results use exact rational computer-assisted certificates.

0.18

Tight Lower Bounds for Differentially Private Continual Counting

cs.DS cs.CR ·2026-09-15 ·Charlie Harrison, Ethan Leeman
theory similarity 0.66
Abstract

The Binary Tree Mechanism is a standard algorithm for differentially private continual counting, but its asymptotic optimality under pure differential privacy has remained unresolved since its introduction. We resolve this question. For fixed $0 < \varepsilon \le 1$, we prove asymptotically tight lower bounds of $Ω(\log^2 n)$ for worst-case expected $\ell_\infty$ error and $Ω(\log^3 n)$ for mean and maximum per-coordinate expected squared error. These bounds hold for arbitrary mechanisms, even when the entire stream is available in advance. The same lower bounds hold under approximate differential privacy whenever $δ\le n^{-c}$, for any fixed $c>0$. Our lower bounds match the Binary Tree Mechanism instantiated with Laplace noise, establishing its asymptotic optimality under both pure differential privacy and approximate differential privacy in the standard regime of $δ\ll1/n$. Our proof uses a single hard distribution with a bounded exponential score on a tree. A simple modification of the score allows the same framework to establish tight lower bounds for all three error measures.

0.42

Amortized Cell-Probe Lower Bounds for Dynamic Boolean Problems

cs.DS cs.CC ·2026-11-08 ·Young Kun Ko
theoryhot direction similarity 0.64
Abstract · 20 pages

We prove the first unconditional amortized $Ω\big((\log N/\log\log N)^2\big)$ cell-probe lower bound for a Boolean dynamic problem. For insert-only multiphase Disjointness with $N$ query sets over $[N]$ and word size $w=Θ(\log N)$, a fixed distribution of interleaved insertions and queries forces this expected average cost per operation, excluding preprocessing. The bound allows sufficiently small constant error for each query of every fixed legal sequence and imposes no restriction on individual operation costs. It transfers to incremental directed reachability, incremental subgraph connectivity, and fully dynamic triangle detection. We also prove $t_q=Ω\big((\log N/\log(t_uw))^2\big)$ for amortized insertion time $1\le t_u=N^{o(1)}$ and expected query time $t_q$, when the number of insertions before the final query is not announced in advance. We reach the quadratic-logarithmic scale with bounded error by combining interleaving with the 2.5-round communication framework [Ko26a, Ko26b] and controlling errors among accepted simulations.

0.27

List Update with Time Windows and Delays without Batch-Serving

cs.DS ·2026-11-12 ·Icey Siyi Ai, Jingwei Li, Clifford Stein
theory similarity 0.63
Abstract

We study list update with time windows and delays when every request requires a separate access. Unlike batch-serving models, serving several requests to one element still incurs one access per request, and each access may change the list for subsequent requests. For time windows of overlap at most $k\ge2$, our deterministic First-Element Removal algorithm is $(3-2/k)$-competitive, hence $3$-competitive in general. Against an oblivious adversary, a randomized adaptation of BIT is $7/4$-competitive on arbitrary $2$-overlap inputs. More generally, on inputs without self-overlap, it is $\left(13/4-9/[2(k+1)]\right)$-competitive for every $k\ge2$. For delays, we give a deterministic $5$-competitive algorithm and a lower bound of $2+\sqrt3$ for deterministic delay-unaware algorithms. Our analyses extend inversion potentials with per-request credits that reconcile different service times and orders.

0.21

Online and Fully-Dynamic Sorting

cs.DS ·2026-11-16 ·Yossi Azar, Sujoy Bhore, Devdan Dey, Debmalya Panigrahi, Or Vardi +1 more
theory similarity 0.63
Abstract

Online sorting asks how to place $n$ sequentially arriving elements in an array to minimize the sum of absolute differences between consecutive elements. Fully-dynamic sorting further extends the problem to allow both element insertions and deletions. Without recourse, these problems face strong lower bounds on the competitive ratio: $Ω(\sqrt{n})$ for online sorting and $Ω(n)$ for fully-dynamic sorting. In sharp contrast, we show that allowing only poly-logarithmic recourse yields at least exponential improvements in the competitive ratio for both problems:(1) Our main algorithmic result is a deterministic fully-dynamic sorting algorithm that is $O(\log^2 n)$-competitive and has $O(\log^4 n)$ amortized recourse per update. We complement this with a lower bound showing that any deterministic algorithm with any $O(\mathrm{polylog}(n))$ competitive ratio has amortized recourse at least $Ω(\sqrt{\log n})$.(2) For the insertion-only setting, we establish a family of approximation--recourse tradeoffs, including $O(\log\log n)$ competitive ratio with $O(\log\log n)$ amortized recourse. Given the lower bound in the fully-dynamic case, this result shows that the insertion-only problem yields exponentially better bounds than the fully-dynamic one.(3) Finally, we show that the stronger approximation-recourse tradeoff for the insertion-only case extends to the fully-dynamic setting when the array has $(1+\varepsilon)n$ space.

0.09

Tight Bounds for Differentially Private Cut Release

cs.DS ·2026-11-14 ·Chenghua Liu, Boning Meng
theory similarity 0.63
Abstract · 24 pages

We give a polynomial-time algorithm for releasing a nonnegative weighted synthetic graph under $(\varepsilon,δ)$-edge differential privacy. Given an $n$-vertex nonnegative weighted graph $G=(V,w_G)$, the output $H=(V,w_H)$ satisfies, with probability at least $1-β$, simultaneously for every $S\subseteq V$, $|w_G(S,V\setminus S)-w_H(S,V\setminus S)| \leγw_G(S,V\setminus S)+O\bigl((n\log n)/(\varepsilonγ)\bigr)$, provided that $γ,\varepsilon,δ,β$ are at least inverse polynomial in $n$. For constant $γ,\varepsilon$ and $δ=β=n^{-10}$, this improves the recently obtained additive error bound of $O(n\log^7 n)$ to $O(n\log n)$. We also prove a matching $Ω(n\log n)$ lower bound. Our algorithm combines degree decomposition with private multiplicative weights, using a degree-sensitive semidefinite oracle to generate update proposals from single Gaussian samples. Each proposal is validated by a noisy check of its exact entropy decrease, and a joint Rényi analysis of sampling and validation avoids additional logarithmic losses.

0.06