Skip to main content
This website is in trial operation, support us!
We gratefully acknowledge support from all contributors.
Contribute Donate

Data Structures and Algorithms

See recent articles

Showing new listings for Thursday, 25 September 2025

Total of 19 entries
Showing up to 2000 entries per page: fewer | more | all

New submissions (showing 9 of 9 entries )

[1] arXiv:2509.19528 [cn-pdf, pdf, html, other]
Title: A Note on Fine-Grained Quantum Reductions for Linear Algebraic Problems
Kyle Doney, Cameron Musco
Subjects: Data Structures and Algorithms (cs.DS) ; Computational Complexity (cs.CC) ; Numerical Analysis (math.NA)

We observe that any $T(n)$ time algorithm (quantum or classical) for several central linear algebraic problems, such as computing $\det(A)$, $tr(A^3)$, or $tr(A^{-1})$ for an $n \times n$ integer matrix $A$, yields a $O(T(n)) + \tilde O(n^2)$ time \textit{quantum algorithm} for $n \times n$ matrix-matrix multiplication. That is, on quantum computers, the complexity of these problems is essentially equivalent to that of matrix multiplication. Our results follow by first observing that the Bernstein-Vazirani algorithm gives a direct quantum reduction from matrix multiplication to computing $tr(ABC)$ for $n \times n$ inputs $A,B,C$. We can then reduce $tr(ABC)$ to each of our problems of interest. For the above problems, and many others in linear algebra, their fastest known algorithms require $\Theta(n^\omega)$ time, where $\omega \approx 2.37$ is the current exponent of fast matrix multiplication. Our finding shows that any improvements beyond this barrier would lead to faster quantum algorithms for matrix multiplication. Our results complement existing reductions from matrix multiplication in algebraic circuits [BCS13], and reductions that work for standard classical algorithms, but are not tight -- i.e., which roughly show that an $O(n^{3-\delta})$ time algorithm for the problem yields an $O(n^{3-\delta/3})$ matrix multiplication algorithm [WW10].

[2] arXiv:2509.19655 [cn-pdf, pdf, html, other]
Title: A Better-Than-$5/4$-Approximation for Two-Edge Connectivity
Felix Hommelsheim, Alexander Lindermayr, Zhenwei Liu
Subjects: Data Structures and Algorithms (cs.DS)

The 2-Edge-Connected Spanning Subgraph Problem (2ECSS) is a fundamental problem in survivable network design. Given an undirected $2$-edge-connected graph, the goal is to find a $2$-edge-connected spanning subgraph with the minimum number of edges; a graph is 2-edge-connected if it is connected after the removal of any single edge. 2ECSS is APX-hard and has been extensively studied in the context of approximation algorithms. Very recently, Bosch-Calvo, Garg, Grandoni, Hommelsheim, Jabal Ameli, and Lindermayr showed the currently best-known approximation ratio of $\frac{5}{4}$ [STOC 2025]. This factor is tight for many of their techniques and arguments, and it was not clear whether $\frac{5}{4}$ can be improved. We break this natural barrier and present a $(\frac{5}{4} - \eta)$-approximation algorithm, for some constant $\eta \geq 10^{-6}$. On a high level, we follow the approach of previous works: take a triangle-free $2$-edge cover and transform it into a 2-edge-connected spanning subgraph by adding only a few additional edges. For $\geq \frac{5}{4}$-approximations, one can heavily exploit that a $4$-cycle in the 2-edge cover can ``buy'' one additional edge. This enables simple and nice techniques, but immediately fails for our improved approximation ratio. To overcome this, we design two complementary algorithms that perform well for different scenarios: one for few $4$-cycles and one for many $4$-cycles. Besides this, there appear more obstructions when breaching $\frac54$, which we surpass via new techniques such as colorful bridge covering, rich vertices, and branching gluing paths.

[3] arXiv:2509.19662 [cn-pdf, pdf, html, other]
Title: Non-Clairvoyant Scheduling with Progress Bars
Ziyad Benomar, Romain Cosson, Alexander Lindermayr, Jens Schlöter
Comments: NeurIPS 2025
Subjects: Data Structures and Algorithms (cs.DS)

In non-clairvoyant scheduling, the goal is to minimize the total job completion time without prior knowledge of individual job processing times. This classical online optimization problem has recently gained attention through the framework of learning-augmented algorithms. We introduce a natural setting in which the scheduler receives continuous feedback in the form of progress bars: estimates of the fraction of each job completed over time. We design new algorithms for both adversarial and stochastic progress bars and prove strong competitive bounds. Our results in the adversarial case surprisingly induce improved guarantees for learning-augmented scheduling with job size predictions. We also introduce a general method for combining scheduling algorithms, yielding further insights in scheduling with predictions. Finally, we propose a stochastic model of progress bars as a more optimistic alternative to conventional worst-case models, and present an asymptotically optimal scheduling algorithm in this setting.

[4] arXiv:2509.19703 [cn-pdf, pdf, html, other]
Title: SS-GUMAP, SL-GUMAP, SSSL-GUMAP: Fast UMAP Algorithms for Large Graph Drawing
Amyra Meidiana, Seok-Hee Hong
Subjects: Data Structures and Algorithms (cs.DS)

UMAP is a popular neighborhood-preserving dimension reduction (DR) algorithm. However, its application for graph drawing has not been evaluated. Moreover, a naive application of UMAP to graph drawing would include O(nm) time all-pair shortest path computation, which is not scalable to visualizing large graphs. In this paper, we present fast UMAP-based for graph drawing. Specifically, we present three fast UMAP-based algorithms for graph drawing: (1) The SS-GUMAP algorithm utilizes spectral sparsification to compute a subgraph G' preserving important properties of a graph G, reducing the O(nm) component of the runtime to O(n^2 log n) runtime; (2) The SSL-GUMAP algorithm reduces the kNN (k-Nearest Neighbors) graph computation from $O(n \log n)$ time to linear time using partial BFS (Breadth First Search), and the cost optimization runtime from O(n) time to sublinear time using edge sampling; (3) The SSSL-GUMAP algorithm combines both approaches, for an overall O(n) runtime. Experiments demonstrate that SS-GUMAP runs 28% faster than GUMAP, a naive application of UMAP to graph drawing, with similar quality metrics, while SL-GUMAP and SSSL-GUMAP run over 80% faster than GUMAP with less than 15% difference on average for all quality metrics. We also present an evaluation of GUMAP to tsNET, a graph layout based on the popular DR algorithm t-SNE. GUMAP runs 90% faster than tsNET with similar neighborhood preservation and, on average, 10% better on quality metrics such as stress, edge crossing, and shape-based metrics, validating the effectiveness of UMAP for graph drawing.

[5] arXiv:2509.19740 [cn-pdf, pdf, other]
Title: Geometric Interpretation of 3-SAT and Phase Transition
Frederic Gillet
Subjects: Data Structures and Algorithms (cs.DS)

Interpretation of 3-SAT as a volume filling problem, and its use to explore the SAT/UNSAT phase transition.

[6] arXiv:2509.19785 [cn-pdf, pdf, html, other]
Title: BH-tsNET, FIt-tsNET, L-tsNET: Fast tsNET Algorithms for Large Graph Drawing
Amyra Meidiana, Seok-Hee Hong, Kwan-Liu Ma
Subjects: Data Structures and Algorithms (cs.DS)

The tsNET algorithm utilizes t-SNE to compute high-quality graph drawings, preserving the neighborhood and clustering structure. We present three fast algorithms for reducing the time complexity of tsNET algorithm from O(nm) time to O(n log n) time and O(n) time. To reduce the runtime of tsNET, there are three components that need to be reduced: (C0) computation of high-dimensional probabilities, (C1) computation of KL divergence gradient, and (C2) entropy computation. Specifically, we reduce the overall runtime of tsNET, integrating our new fast approaches for C0 and C2 with fast t-SNE algorithms for C1. We first present O(n log n)-time BH-tsNET, based on (C0) new O(n)-time partial BFS-based high-dimensional probability computation and (C2) new O(n log n)-time quadtree-based entropy computation, integrated with (C1) O(n log n)-time quadtree-based KL divergence computation of BH-SNE. We next present faster O(n log n)-time FIt-tsNET, using (C0) O(n)-time partial BFS-based high-dimensional probability computation and (C2) quadtree-based O(n log n)-time entropy computation, integrated with (C1) O(n)-time interpolation-based KL divergence computation of FIt-SNE. Finally, we present the O(n)-time L-tsNET, integrating (C2) new O(n)-time FFT-accelerated interpolation-based entropy computation with (C0) O(n)-time partial BFS-based high-dimensional probability computation, and (C1) O(n)-time interpolation-based KL divergence computation of FIt-SNE. Extensive experiments using benchmark data sets confirm that BH-tsNET, FIt-tsNET, and L-tsNET outperform tsNET, running 93.5%, 96%, and 98.6% faster while computing similar quality drawings in terms of quality metrics (neighborhood preservation, stress, edge crossing, and shape-based metrics) and visual comparison. We also present a comparison between our algorithms and DRGraph, another dimension reduction-based graph drawing algorithm.

[7] arXiv:2509.19914 [cn-pdf, pdf, html, other]
Title: Stealing From the Dragon's Hoard: Online Unbounded Knapsack With Removal
Matthias Gehnen, Moritz Stocker
Subjects: Data Structures and Algorithms (cs.DS)

We introduce the Online Unbounded Knapsack Problem with Removal, a variation of the well-known Online Knapsack Problem. Items, each with a weight and value, arrive online and an algorithm must decide on whether or not to pack them into a knapsack with a fixed weight limit. An item may be packed an arbitrary number of times and items may be removed from the knapsack at any time without cost. The goal is to maximize the total value of items packed, while respecting a weight limit. We show that this is one of the very few natural online knapsack variants that allow for competitive deterministic algorithms in the general setting, by providing an algorithm with competitivity 1.6911. We complement this with a lower bound of 1.5877. We also analyze the proportional setting, where the weight and value of any single item agree, and show that deterministic algorithms can be exactly 3/2-competitive. Lastly, we give lower and upper bounds of 6/5 and 4/3 on the competitivity of randomized algorithms in this setting.

[8] arXiv:2509.20304 [cn-pdf, pdf, html, other]
Title: Ads that Stick: Near-Optimal Ad Optimization through Psychological Behavior Models
Kailash Gopal Darmasubramanian, Akash Pareek, Arindam Khan, Arpit Agarwal
Subjects: Data Structures and Algorithms (cs.DS) ; Machine Learning (cs.LG)

Optimizing the timing and frequency of ads is a central problem in digital advertising, with significant economic consequences. Existing scheduling policies rely on simple heuristics, such as uniform spacing and frequency caps, that overlook long-term user interest. However, it is well-known that users' long-term interest and engagement result from the interplay of several psychological effects (Curmei, Haupt, Recht, Hadfield-Menell, ACM CRS, 2022). In this work, we model change in user interest upon showing ads based on three key psychological principles: mere exposure, hedonic adaptation, and operant conditioning. The first two effects are modeled using a concave function of user interest with repeated exposure, while the third effect is modeled using a temporal decay function, which explains the decline in user interest due to overexposure. Under our psychological behavior model, we ask the following question: Given a continuous time interval $T$, how many ads should be shown, and at what times, to maximize the user interest towards the ads? Towards answering this question, we first show that, if the number of displayed ads is fixed, then the optimal ad-schedule only depends on the operant conditioning function. Our main result is a quasi-linear time algorithm that outputs a near-optimal ad-schedule, i.e., the difference in the performance of our schedule and the optimal schedule is exponentially small. Our algorithm leads to significant insights about optimal ad placement and shows that simple heuristics such as uniform spacing are sub-optimal under many natural settings. The optimal number of ads to display, which also depends on the mere exposure and hedonistic adaptation functions, can be found through a simple linear search given the above algorithm. We further support our findings with experimental results, demonstrating that our strategy outperforms various baselines.

[9] arXiv:2509.20351 [cn-pdf, pdf, html, other]
Title: Testable algorithms for approximately counting edges and triangles in sublinear time and space
Talya Eden, Ronitt Rubinfeld, Arsen Vasilyan
Subjects: Data Structures and Algorithms (cs.DS)

We consider the fundamental problems of approximately counting the numbers of edges and triangles in a graph in sublinear time. Previous algorithms for these tasks are significantly more efficient under a promise that the arboricity of the graph is bounded by some parameter $\overline{\alpha}$. However, when this promise is violated, the estimates given by these algorithms are no longer guaranteed to be correct. For the triangle counting task, we give an algorithm that requires no promise on the input graph $G$, and computes a $(1\pm \epsilon)$-approximation for the number of triangles $t$ in $G$ in time $O^*\left( \frac{m\cdot \alpha(G)}{t} + \frac{m}{t^{2/3}} \right)$, where $\alpha(G)$ is the arboricity of the graph. The algorithm can be used on any graph $G$ (no prior knowledge the arboricity $\alpha(G)$ is required), and the algorithm adapts its run-time on the fly based on the graph $G$. We accomplish this by trying a sequence of candidate values $\tilde{\alpha}$ for $\alpha(G)$ and using a novel algorithm in the framework of testable algorithms. This ensures that wrong candidates $\tilde{\alpha}$ cannot lead to incorrect estimates: as long as the advice is incorrect, the algorithm detects it and continues with a new candidate. Once the algorithm accepts the candidate, its output is guaranteed to be correct with high probability. We prove that this approach preserves - up to an additive overhead - the dramatic efficiency gains obtainable when good arboricity bounds are known in advance, while ensuring robustness against misleading advice. We further complement this result with a lower bound, showing that such an overhead is unavoidable whenever the advice may be faulty. We further demonstrate implications of our results for triangle counting in the streaming model.

Cross submissions (showing 4 of 4 entries )

[10] arXiv:2509.19598 (cross-list from cs.IT) [cn-pdf, pdf, html, other]
Title: Efficient $\varepsilon$-approximate minimum-entropy couplings
Spencer Compton
Subjects: Information Theory (cs.IT) ; Data Structures and Algorithms (cs.DS)

Given $m \ge 2$ discrete probability distributions over $n$ states each, the minimum-entropy coupling is the minimum-entropy joint distribution whose marginals are the same as the input distributions. Computing the minimum-entropy coupling is NP-hard, but there has been significant progress in designing approximation algorithms; prior to this work, the best known polynomial-time algorithms attain guarantees of the form $H(\operatorname{ALG}) \le H(\operatorname{OPT}) + c$, where $c \approx 0.53$ for $m=2$, and $c \approx 1.22$ for general $m$ [CKQGK '23]. A main open question is whether this task is APX-hard, or whether there exists a polynomial-time approximation scheme (PTAS). In this work, we design an algorithm that produces a coupling with entropy $H(\operatorname{ALG}) \le H(\operatorname{OPT}) + \varepsilon$ in running time $n^{O(\operatorname{poly}(1/\varepsilon) \cdot \operatorname{exp}(m) )}$: showing a PTAS exists for constant $m$.

[11] arXiv:2509.19718 (cross-list from math.OC) [cn-pdf, pdf, html, other]
Title: ALNS for Tugboat Scheduling in Inland Waterway
Zihang Ma
Subjects: Optimization and Control (math.OC) ; Data Structures and Algorithms (cs.DS)

This paper focuses on the barges shipping problem, also known as the tugboats scheduling problem, within the context of a scenario where a single tugboat has the capacity to tow multiple barges and conduct multiple trips in a drop-and-pull mode during a daily work shift. The problem is mathematically formalized as mixed-integer programming models. To tackle real-world-sized problem instances, an adaptive large neighborhood search (ALNS) algorithm integrated with a decoding mathematical model is proposed. When applied to large-scale instances, the ALNS algorithm showcases performance superiority over the strengthened mathematical model.

[12] arXiv:2509.19966 (cross-list from quant-ph) [cn-pdf, pdf, html, other]
Title: No Quantum Advantage in Decoded Quantum Interferometry for MaxCut
Ojas Parekh
Comments: 12 pages
Subjects: Quantum Physics (quant-ph) ; Data Structures and Algorithms (cs.DS)

Decoded Quantum Interferometry (DQI) is a framework for approximating special kinds of discrete optimization problems that relies on problem structure in a way that sets it apart from other classical or quantum approaches. We show that the instances of MaxCut on which DQI attains a nontrivial asymptotic approximation guarantee are solvable exactly in classical polynomial time. We include a streamlined exposition of DQI tailored for MaxCut that relies on elementary graph theory instead of coding theory to motivate and explain the algorithm.

[13] arXiv:2509.20183 (cross-list from quant-ph) [cn-pdf, pdf, other]
Title: Dequantization and Hardness of Spectral Sum Estimation
Roman Edenhofer, Atsuya Hasegawa, François Le Gall
Subjects: Quantum Physics (quant-ph) ; Computational Complexity (cs.CC) ; Data Structures and Algorithms (cs.DS)

We give new dequantization and hardness results for estimating spectral sums of matrices, such as the log-determinant. Recent quantum algorithms have demonstrated that the logarithm of the determinant of sparse, well-conditioned, positive matrices can be approximated to $\varepsilon$-relative accuracy in time polylogarithmic in the dimension $N$, specifically in time $\mathrm{poly}(\mathrm{log}(N), s, \kappa, 1/\varepsilon)$, where $s$ is the sparsity and $\kappa$ the condition number of the input matrix. We provide a simple dequantization of these techniques that preserves the polylogarithmic dependence on the dimension. Our classical algorithm runs in time $\mathrm{polylog}(N)\cdot s^{O(\sqrt{\kappa}\log \kappa/\varepsilon)}$ which constitutes an exponential improvement over previous classical algorithms in certain parameter regimes. We complement our classical upper bound with $\mathsf{DQC1}$-completeness results for estimating specific spectral sums such as the trace of the inverse and the trace of matrix powers for log-local Hamiltonians, with parameter scalings analogous to those of known quantum algorithms. Assuming $\mathsf{BPP}\subsetneq\mathsf{DQC1}$, this rules out classical algorithms with the same scalings. It also resolves a main open problem of Cade and Montanaro (TQC 2018) concerning the complexity of Schatten-$p$ norm estimation. We further analyze a block-encoding input model, where instead of a classical description of a sparse matrix, we are given a block-encoding of it. We show $\mathsf{DQC}1$-completeness in a very general way in this model for estimating $\mathrm{tr}[f(A)]$ whenever $f$ and $f^{-1}$ are sufficiently smooth. We conclude our work with $\mathsf{BQP}$-hardness and $\mathsf{PP}$-completeness results for high-accuracy log-determinant estimation.

Replacement submissions (showing 6 of 6 entries )

[14] arXiv:2503.06464 (replaced) [cn-pdf, pdf, other]
Title: Detecting Correlation Efficiently in Stochastic Block Models: Breaking Otter's Threshold in the Entire Supercritical Regime
Guanyi Chen, Jian Ding, Shuyang Gong, Zhangsong Li
Comments: This substantially improves the result in an earlier version. 98 pages, 13 figures
Subjects: Data Structures and Algorithms (cs.DS) ; Probability (math.PR) ; Statistics Theory (math.ST)

Consider a pair of sparse correlated stochastic block models $\mathcal S(n,\tfrac{\lambda}{n},\epsilon;s)$ subsampled from a common parent stochastic block model with two symmetric communities, average degree $\lambda=O(1)$, divergence parameter $\epsilon\in (0,1)$ and subsampling probability $s$. For all $\epsilon\in(0,1)$ and $\Delta>0$, we construct a statistic based on the combination of two low-degree polynomials and show that there exists a sufficiently small constant $\delta=\delta(\epsilon,\lambda,\Delta)>0$ such that if $\epsilon^2 \lambda s>1+\Delta$ and $s>\sqrt{\alpha}-\delta$ where $\alpha\approx 0.338$ is Otter's constant, this statistic can distinguish this model and a pair of independent stochastic block models $\mathcal S(n,\tfrac{\lambda s}{n},\epsilon)$ with probability $1-o(1)$. We also provide an efficient algorithm that approximates this statistic in polynomial time. The crux of our statistic's construction lies in a carefully curated family of multigraphs called \emph{decorated trees}, which enables effective aggregation of the community signal and graph correlation by leveraging the counts of the same decorated tree while suppressing the undesirable correlations among counts of different decorated trees. We believe such construction may be of independent interest.

[15] arXiv:2506.23906 (replaced) [cn-pdf, pdf, html, other]
Title: Segmented Operations using Matrix Multiplications
Aleksandros Sobczyk, Giuseppe Sorrentino, Anastasios Zouzias
Subjects: Data Structures and Algorithms (cs.DS) ; Computational Complexity (cs.CC) ; Distributed, Parallel, and Cluster Computing (cs.DC)

Specialized computational units that perform small matrix multiplications as primitive operations are typically present in modern AI accelerators. However, these Matrix Multiplication Units (MMUs) are often underutilized for many fundamental deep learning operations besides dense matrix multiplications. Coincidentally, the lack of a rigorous theoretical model of computation for such architectures obstructs algorithmic design. In this work, we propose MMV-RAM, a computational model which judiciously extends the Vector-RAM model with an additional MMU. We provide a detailed theoretical analysis and carefully balance the computational power between the matrix and vector units, guided by the circuit complexity lower bound that parity is not in AC{[0]}. Given MMV-RAM, we proceed to algorithm design, starting with two fundamental parallel operations: segmented scan and sum. By expressing them as compositions of elementary parallel primitives (e.g., seg. sum reduces to: scan, compress, and vector differentiation), we can exploit MMUs to perform speculative blocked computations, ultimately leading to provable theoretical speed-ups against vector-only approaches. These results extend to other ubiquitous AI kernels, including dense matrix product, and sparse matrix-vector product. As a case study, we implemented the proposed algorithms on the Ascend 910B AI accelerator, which contains matrix and vector cores. We evaluate these implementations on synthetic and real-world datasets from various applications, including Large Language Models.

[16] arXiv:2210.06140 (replaced) [cn-pdf, pdf, html, other]
Title: Differentially Private Bootstrap: New Privacy Analysis and Inference Strategies
Zhanyu Wang, Guang Cheng, Jordan Awan
Comments: 22 pages before appendices and references. 50 pages total
Subjects: Machine Learning (stat.ML) ; Cryptography and Security (cs.CR) ; Data Structures and Algorithms (cs.DS) ; Machine Learning (cs.LG)

Differentially private (DP) mechanisms protect individual-level information by introducing randomness into the statistical analysis procedure. Despite the availability of numerous DP tools, there remains a lack of general techniques for conducting statistical inference under DP. We examine a DP bootstrap procedure that releases multiple private bootstrap estimates to infer the sampling distribution and construct confidence intervals (CIs). Our privacy analysis presents new results on the privacy cost of a single DP bootstrap estimate, applicable to any DP mechanism, and identifies some misapplications of the bootstrap in the existing literature. For the composition of the DP bootstrap, we present a numerical method to compute the exact privacy cost of releasing multiple DP bootstrap estimates, and using the Gaussian-DP (GDP) framework (Dong et al., 2022), we show that the release of $B$ DP bootstrap estimates from mechanisms satisfying $(\mu/\sqrt{(2-2/\mathrm{e})B})$-GDP asymptotically satisfies $\mu$-GDP as $B$ goes to infinity. Then, we perform private statistical inference by post-processing the DP bootstrap estimates. We prove that our point estimates are consistent, our standard CIs are asymptotically valid, and both enjoy optimal convergence rates. To further improve the finite performance, we use deconvolution with DP bootstrap estimates to accurately infer the sampling distribution. We derive CIs for tasks such as population mean estimation, logistic regression, and quantile regression, and we compare them to existing methods using simulations and real-world experiments on 2016 Canada Census data. Our private CIs achieve the nominal coverage level and offer the first approach to private inference for quantile regression.

[17] arXiv:2410.09296 (replaced) [cn-pdf, pdf, html, other]
Title: The 2020 United States Decennial Census Is More Private Than You (Might) Think
Buxin Su, Weijie J. Su, Chendi Wang
Subjects: Cryptography and Security (cs.CR) ; Data Structures and Algorithms (cs.DS) ; Applications (stat.AP) ; Machine Learning (stat.ML)

The U.S. Decennial Census serves as the foundation for many high-profile policy decision-making processes, including federal funding allocation and redistricting. In 2020, the Census Bureau adopted differential privacy to protect the confidentiality of individual responses through a disclosure avoidance system that injects noise into census data tabulations. The Bureau subsequently posed an open question: Could stronger privacy guarantees be obtained for the 2020 U.S. Census compared to their published guarantees, or equivalently, had the privacy budgets been fully utilized? In this paper, we address this question affirmatively by demonstrating that the 2020 U.S. Census provides significantly stronger privacy protections than its nominal guarantees suggest at each of the eight geographical levels, from the national level down to the block level. This finding is enabled by our precise tracking of privacy losses using $f$-differential privacy, applied to the composition of private queries across these geographical levels. Our analysis reveals that the Census Bureau introduced unnecessarily high levels of noise to meet the specified privacy guarantees for the 2020 Census. Consequently, we show that noise variances could be reduced by $15.08\%$ to $24.82\%$ while maintaining nearly the same level of privacy protection for each geographical level, thereby improving the accuracy of privatized census statistics. We empirically demonstrate that reducing noise injection into census statistics mitigates distortion caused by privacy constraints in downstream applications of private census data, illustrated through a study examining the relationship between earnings and education.

[18] arXiv:2503.20438 (replaced) [cn-pdf, pdf, html, other]
Title: Factorised Representations of Join Queries: Tight Bounds and a New Dichotomy
Christoph Berkholz, Harry Vinall-Smeeth
Comments: 28 pages, 1 figure; v.2. improved presentation and extended discussion on related work
Subjects: Databases (cs.DB) ; Data Structures and Algorithms (cs.DS) ; Logic in Computer Science (cs.LO)

A common theme in factorised databases and knowledge compilation is the representation of solution sets in a useful yet succinct data structure. In this paper, we study the representation of the result of join queries (or, equivalently, the set of homomorphisms between two relational structures). We focus on the very general format of $\{\cup, \times\}$-circuits -- also known as d-representations or DNNF circuits -- and aim to find the limits of this approach. In prior work, it has been shown that there always exists a $\{\cup, \times\}$-circuits-circuit of size $N^{O(subw)}$ representing the query result, where N is the size of the database and subw the submodular width of the query. If the arity of all relations is bounded by a constant, then subw is linear in the treewidth tw of the query. In this setting, the authors of this paper proved a lower bound of $N^{\Omega(tw^{\varepsilon})}$ on the circuit size (ICALP 2023), where $\varepsilon>0$ depends on the excluded grid theorem. Our first main contribution is to improve this lower bound to $N^{\Omega(tw)}$, which is tight up to a constant factor in the exponent. Our second contribution is a $N^{\Omega(subw^{1/4})}$ lower bound on the circuit size for join queries over relations of unbounded arity. Both lower bounds are unconditional lower bounds on the circuit size for well-chosen database instances. Their proofs use a combination of structural (hyper)graph theory with communication complexity in a simple yet novel way. While the second lower bound is asymptotically equivalent to Marx's conditional bound on the decision complexity (JACM 2013), our $N^{\Theta(tw)}$ bound in the bounded-arity setting is tight, while the best conditional bound on the decision complexity is $N^{\Omega(tw/\log tw)}$. Note that, removing this logarithmic factor in the decision setting is a major open problem.

[19] arXiv:2509.13966 (replaced) [cn-pdf, pdf, other]
Title: Smaller Circuits for Bit Addition
Mikhail Goncharov, Alexander S. Kulikov, Georgie Levtsov
Subjects: Computational Complexity (cs.CC) ; Discrete Mathematics (cs.DM) ; Data Structures and Algorithms (cs.DS) ; Logic in Computer Science (cs.LO)

Bit addition arises virtually everywhere in digital circuits: arithmetic operations, increment/decrement operators, computing addresses and table indices, and so on. Since bit addition is such a basic task in Boolean circuit synthesis, a lot of research has been done on constructing efficient circuits for various special cases of it. A vast majority of these results are devoted to optimizing the circuit depth (also known as delay). In this paper, we investigate the circuit size (also known as area) over the full binary basis of bit addition. Though most of the known circuits are built from Half Adders and Full Adders, we show that, in many interesting scenarios, these circuits have suboptimal size. Namely, we improve an upper bound $5n-3m$ to $4.5n-2m$, where $n$ is the number of input bits and $m$ is the number of output bits. In the regimes where $m$ is small compared to $n$ (for example, for computing the sum of $n$ bits or multiplying two $n$-bit integers), this leads to $10\%$ improvement. We complement our theoretical result by an open-source implementation of generators producing circuits for bit addition and multiplication. The generators allow one to produce the corresponding circuits in two lines of code and to compare them to existing designs.

Total of 19 entries
Showing up to 2000 entries per page: fewer | more | all