97 research outputs found
Private Counting of Distinct Elements in the Turnstile Model and Extensions
No full textPrivately counting distinct elements in a stream is a fundamental data analysis problem with many applications in machine learning. In the turnstile model, Jain et al. [NeurIPS2023] initiated the study of this problem parameterized by the maximum flippancy of any element, i.e., the number of times that the count of an element changes from 0 to above 0 or vice versa. They give an item-level (ϵ, δ)differentially private algorithm whose additive error is tight with respect to that parameterization. In this work, we show that a very simple algorithm based on the sparse vector technique achieves a tight additive error for item-level (ϵ, δ)-differential privacy and item-level ϵ-differential privacy with regards to a different parameterization, namely the sum of all flippancies. Our second result is a bound which shows that for a large class of algorithms, including all existing differentially private algorithms for this problem, the lower bound from item-level differential privacy extends to event-level differential privacy. This partially answers an open question by Jain et al. [NeurIPS2023]
The Power of Vertex Sparsifiers in Dynamic Graph Algorithms
No full textWe introduce a new algorithmic framework for designing dynamic graph algorithms in minor-free graphs, by exploiting the structure of such graphs and a tool called vertex sparsification, which is a way to compress large graphs into small ones that well preserve relevant properties among a subset of vertices and has previously mainly been used in the design of approximation algorithms.
Using this framework, we obtain a Monte Carlo randomized fully dynamic algorithm for (1 + epsilon)-approximating the energy of electrical flows in n-vertex planar graphs with tilde{O}(r epsilon^{-2}) worst-case update time and tilde{O}((r + n / sqrt{r}) epsilon^{-2}) worst-case query time, for any r larger than some constant. For r=n^{2/3}, this gives tilde{O}(n^{2/3} epsilon^{-2}) update time and tilde{O}(n^{2/3} epsilon^{-2}) query time. We also extend this algorithm to work for minor-free graphs with similar approximation and running time guarantees. Furthermore, we illustrate our framework on the all-pairs max flow and shortest path problems by giving corresponding dynamic algorithms in minor-free graphs with both sublinear update and query times. To the best of our knowledge, our results are the first to systematically establish such a connection between dynamic graph algorithms and vertex sparsification.
We also present both upper bound and lower bound for maintaining the energy of electrical flows in the incremental subgraph model, where updates consist of only vertex activations, which might be of independent interest
LIPIcs
No full textOblivious routing is a well-studied paradigm that uses static precomputed routing tables for selecting routing paths within a network. Existing oblivious routing schemes with polylogarithmic competitive ratio for general networks are tree-based, in the sense that routing is performed according to a convex combination of trees. However, this restriction to trees leads to a construction that has time quadratic in the size of the network and does not parallelize well.
In this paper we study oblivious routing schemes based on electrical routing. In particular, we show that general networks with n vertices and m edges admit a routing scheme that has competitive ratio O(log² n) and consists of a convex combination of only O(√m) electrical routings. This immediately leads to an improved construction algorithm with time Õ(m^{3/2}) that can also be implemented in parallel with Õ(√m) depth
Incremental Approximate Maximum Flow via Residual Graph Sparsification
No full textWe give an algorithm that, with high probability, maintains a (1-ε)-approximate s-t maximum flow in undirected, uncapacitated n-vertex graphs undergoing m edge insertions in Õ(m+ n F^*/ε) total update time, where F^{*} is the maximum flow on the final graph. This is the first algorithm to achieve polylogarithmic amortized update time for dense graphs (m = Ω(n²)), and more generally, for graphs where F^* = Õ(m/n).
At the heart of our incremental algorithm is the residual graph sparsification technique of Karger and Levine [SICOMP '15], originally designed for computing exact maximum flows in the static setting. Our main contributions are (i) showing how to maintain such sparsifiers for approximate maximum flows in the incremental setting and (ii) generalizing the cut sparsification framework of Fung et al. [SICOMP '19] from undirected graphs to balanced directed graphs
A Comparison of Techniques for Sampling Web Pages
No full textAs the World Wide Web is growing rapidly, it is getting increasingly challenging to gather representative information about it. Instead of crawling the web exhaustively one has to resort to other techniques like sampling to determine the properties of the web. A uniform random sample of the web would be useful to determine the percentage of web pages in a specific language, on a topic or in a top level domain. Unfortunately, no approach has been shown to sample the web pages in an unbiased way. Three promising web sampling algorithms are based on random walks. They each have been evaluated individually, but making a comparison on different data sets is not possible. We directly compare these algorithms in this paper. We performed three random walks on the web under the same conditions and analyzed their outcomes in detail. We discuss the strengths and the weaknesses of each algorithm and propose improvements based on experimental results
Scheduling multicasts on unit-capacity trees and meshes
No full textThis paper studies the multicast routing and admission control problem on unit-capacity tree and mesh topologies in the throughput model. The problem is a generalization of the edge-disjoint paths problem and is NP-hard both on trees and meshes. We study both the offline and the online version of the problem: In the offline setting.. we give the first constant-factor approximation algorithm for trees, and an O((log log n)(2))-factor approximation algorithm for meshes. In the online setting, we give the first polylogarithmic competitive online algorithm for tree and mesh topologies. No polylogarithmic-competitive algorithm is possible on general network topologies (Lower bounds for on-line graph problems with application to on-line circuits and optical routing, in: Proceedings of the 28th ACM Symposium on Theory of Computing, 1996, pp. 531-540) and there exists a polylogarithmic lower bound on the competitive ratio of any online algorithm on tree topologies (Making commitments in the face of uncertainity: how to pick a winner almost every time, in: Proceedings of the 28th Annual ACM Symposium on Theory of Computing, 1996, pp. 519-530). We prove the same lower bound for meshes. (C) 2003 Elsevier Science (USA). All rights reserved
Experimental Evaluation of Fully Dynamic k-Means via Coresets
No full textFor a set of points in , the Euclidean -means problems
consists of finding centers such that the sum of distances squared from
each data point to its closest center is minimized. Coresets are one the main
tools developed recently to solve this problem in a big data context. They
allow to compress the initial dataset while preserving its structure: running
any algorithm on the coreset provides a guarantee almost equivalent to running
it on the full data.
In this work, we study coresets in a fully-dynamic setting: points are added
and deleted with the goal to efficiently maintain a coreset with which a
k-means solution can be computed. Based on an algorithm from Henzinger and Kale
[ESA'20], we present an efficient and practical implementation of a fully
dynamic coreset algorithm, that improves the running time by up to a factor of
20 compared to our non-optimized implementation of the algorithm by Henzinger
and Kale, without sacrificing more than 7% on the quality of the k-means
solution.Comment: Accepted at ALENEX 2
Exploring Unknown Environments
No full text. We consider exploration problems where a robot has to construct a complete map of an unknown environment. We assume that the environment is modeled by a directed, strongly connected graph. The robot's task is to visit all nodes and edges of the graph using the minimum number R of edge traversals. Koutsoupias [16] gave a lower bound for R of \Omega\Gamma d 2 m), and Deng and Papadimitriou [12] showed an upper bound of d O(d) m, where m is the number of edges in the graph and d is the minimum number of edges that have to be added to make the graph Eulerian. We give the first sub-exponential algorithm for this exploration problem, which achieves an upper bound of d O(log d) m. We also show a matching lower bound of d\Omega\Gamma274 d) m for our algorithm. Additionally, we give lower bounds of 2 \Omega\Gamma d) m, resp. d\Omega\Gamma207 d) m for various other natural exploration algorithms. Key words. directed graph, exploration algorithm AMS subject classifications. 05C20,..
Sampling to provide or to bound: With applications to fully dynamic graph algorithms
No full textIn dynamic graph algorithms the following provide-or-bound problem has to be solved quickly: Given a set S containing a subset R and a way of generating random elements from S testing for membership in R, either (i) provide an element of R, or (ii) give a (small) upper bound on the size of R that holds with high probability. We give an optimal algorithm for this problem. This algorithm improves the time per operation for various dynamic graph algorithms by a factor of O(log n). For example, it improves the time per update for fully dynamic connectivity from O(log3n) to O(log2n).LTA
Exploring Unknown Environments
No full textWe consider exploration problems where a robot has to construct a complete map of an unknown environment. We assume that the environment is modeled by a directed, strongly connected graph. The robot's task is to visit all nodes and edges of the graph using the minimum number R of edge traversals. Koutsoupias [12] gave a lower bound for R of \Omega\Gamma d 2 m), and Deng and Papadimitriou [9] showed an upper bound of d O(d) m, where m is the number edges in the graph and d is the minimum number of edges that have to be added to make the graph Eulerian. We give the first sub-exponential algorithm for this exploration problem, which achieves an upper bound of d O(log d) m. We also show a matching lower bound of d\Omega\Gamma207 d) m for our algorithm. Additionally, we give lower bounds of 2 \Omega\Gamma d) m, resp. d \Omega\Gamma828 d) m for various other natural exploration algorithms. 1 Introduction Suppose that a robot has to construct a complete map of an unknown envir..
- …
