waashk/dblp huggingface dataset:
fast leader-election protocols with bounded cheaters' edge. we study the leader election problem on n players in the asynchronous full-information model. our main contention is that the most commonly used performance measure for leader-election protocols, called resilience, is unable to discern whether a small number of players can exercise disproportionate influence on the outcome of a protocol, or not. as a remedy we propose a new quantity, named cheaters' edge, which roughly describes by what multiplicative factor malicious players may increase, through cheating, their probability of getting elected. arguably, a good protocol must have bounded cheaters' edge.we present polynomial-time constructions of new leader-election protocols that are fast, in terms of the rounds required (5, 5 log n, and log n rounds, respectively), but moreover exhibit bounded cheaters' edge under progressively looser restrictions on the number t of malicious players: t < θn / log n, t < θn / √log n log log n, and, eventually, no restriction at all---without relying on any a priori knowledge of t. the latter of these three protocols constitutes the first constructive solution to a problem posed by alon and naor more than a decade ago.
the complexity of analytic tableaux. the method of analytic tableaux is employed in many introductory texts and has also been used quite extensively as a basis for automated theorem proving. in this paper, we discuss the complexity of the system as a method for refuting contradictory sets of clauses, and resolve several open questions. we discuss the three forms of analytic tableaux: clausal tableaux, generalized clausal tableaux, and binary tableaux. we resolve the relative complexity of these three forms of tableaux proofs and also resolve the relative complexity of analytic tableaux versus resolution. we show that there is a quasi-polynomial simulation of tree resolution by analytic tableaux; this simulation cannot be improved, since we give a matching lower bound that is tight to within a polynomial.
cache-oblivious priority queue and graph algorithm applications. (math) in this paper we develop an optimal cache-oblivious priority queue data structure, supporting insertion, deletion, and deletemin operations in o(1 \over b logm/bn \over b) amortized memory transfers, where m and b are the memory and block transfer sizes of any two consecutive levels of a multilevel memory hierarchy. in a cache-oblivious data structure, m and b are not used in the description of the structure. the bounds match the bounds of several previously developed external-memory (cache-aware) priority queue data structures, which all rely crucially on knowledge about m and b. priority queues are a critical component in many of the best known external- memory graph algorithms, and using our cache-oblivious priority queue we develop several cache- oblivious graph algorithms.
a difference in efficiency between synchronous and asynchronous systems a system of parallel processes is said to be synchronous if all processes run using the same clock, and it is asynchronous if each process has its own independent clock. for any s, n, a particular distributed problem is defined involving system behavior at n &ldquo;ports&rdquo;. this problem can be solved in time s by a synchronous system but requires time at least (s-1) log n on any asynchronous system.
cutting triangular cycles of lines in space. we show that n lines in 3-space can be cut into o(n2-1/69log16/69n) pieces, such that all depth cycles defined by triples of lines are eliminated. this partially resolves a long-standing open problem in computational geometry, motivated by hidden-surface removal in computer graphics.
distinct distances in three and higher dimensions. improving an old result of clarkson, edelsbrunner, guibas, sharir and welzl, we show that the number of distinct distances determined by a set $p$ of $n$ points in three-dimensional space is $\omega(n^{77/141-\varepsilon})=\omega(n^{0.546})$, for any $\varepsilon>0$. moreover, there always exists a point $p\in p$ from which there are at least so many distinct distances to the remaining elements of $p$. the same result holds for points on the three-dimensional sphere. as a consequence, we obtain analogous results in higher dimensions.
new approximation guarantee for chromatic number. we describe how to color every 3-colorable graph with o(n0.2111) colors, thus improving an algorithm of blum and karger from almost a decade ago. our analysis uses new geometric ideas inspired by the recent work of arora, rao, and vazirani on sparsest cut, and these ideas show promise of leading to further improvements.
fitting algebraic curves to noisy data. we introduce the following problem which is motivated by applications in vision and pattern detection: we are given pairs of datapoints (x1,y1), (x2,y2),...,(xm, ym) ∈ [- 1, 1] × [- 1, 1], a noise parameter δ > 0, a degree bound d, and a threshold ρ > 0. we desire an algorithm that enlists every degree d polynomial h such that |h(xi) - yi| ≤ δ for at least δ fraction of the indices i. if δ = 0, this is just the list decoding problem that has been popular in complexity theory and for which sudan gave a poly(m,d) time algorithm. however, for δ > 0, the problem as stated becomes ill-posed and one needs a careful reformulation (see the introduction). we prove a few basic results about this (reformulated) problem. we show that the problem has no polynomial-time algorithm (our counterexample works for ρ = 0.5). this is shown by exhibiting an instance of the problem where the number of solutions is as large as exp(d0.5-ε) and every pair of solutions is far from each other in ℓ∞ norm. on the algorithmic side, we give a rigorous analysis of a brute force algorithm that runs in exponential time. also, in surprising contrast to our lowerbound, we give a polynomial-time algorithm for learning the polynomials assuming the data is generated using a mixture model in which the mixing weights are "nondegenerate."
approximation schemes for minimum latency problems. the minimum latency problem, also known as the traveling repairman problem, is a variant of the traveling salesman problem in which the starting node of the tour is given and the goal is to minimize the sum of the arrival times at the other nodes. we present a quasi-polynomial time approximation scheme (qptas) for this problem when the instance is a weighted tree, when the nodes lie in $\mathbb{r}^d$ for some fixed d, and for planar graphs. we also present a polynomial time constant factor approximation algorithm for the general metric case. the currently best polynomial time approximation algorithm for general metrics, due to goemans and kleinberg, computes a 3.59-approximation.
euclidean distortion and the sparsest cut. we prove that every n-point metric space of negative type (in particular, every n-point subset of l1) embeds into a euclidean space with distortion o(√log n log log n), a result which is tight up to the o(log log n) factor. as a consequence, we obtain the best known polynomial-time approximation algorithm for the sparsest cut problem with general demands. if the demand is supported on a subset of size k, we achieve an approximation ratio of o(√log k log log k).
expander flows, geometric embeddings and graph partitioning. we give a o(&sqrt;log n)-approximation algorithm for the sparsest cut, edge expansion, balanced separator, and graph conductance problems. this improves the o(log n)-approximation of leighton and rao (1988). we use a well-known semidefinite relaxation with triangle inequality constraints. central to our analysis is a geometric theorem about projections of point sets in rd, whose proof makes essential use of a phenomenon called measure concentration. we also describe an interesting and natural &ldquo;approximate certificate&rdquo; for a graph's expansion, which involves embedding an n-node expander in it with appropriate dilation and congestion. we call this an expander flow.
local search heuristic for k-median and facility location problems. we analyze local search heuristics for the metric k-median and facility location problems. we define the locality gap of a local search procedure for a minimization problem as the maximum ratio of a locally optimum solution (obtained using this procedure) to the global optimum. for k-median, we show that local search with swaps has a locality gap of 5. furthermore, if we permit up to p facilities to be swapped simultaneously, then the locality gap is 3+2/p. this is the first analysis of a local search for k-median that provides a bounded performance guarantee with only k medians. this also improves the previous known 4 approximation for this problem. for uncapacitated facility location, we show that local search, which permits adding, dropping, and swapping a facility, has a locality gap of 3. this improves the bound of 5 given by m. korupolu, c. plaxton, and r. rajaraman [analysis of a local search heuristic for facility location problems, technical report 98-30, dimacs, 1998]. we also consider a capacitated facility location problem where each facility has a capacity and we are allowed to open multiple copies of a facility. for this problem we introduce a new local search operation which opens one or more copies of a facility and drops zero or more facilities. we prove that this local search has a locality gap between 3 and 4.
space-efficient approximate voronoi diagrams. (math) given a set $s$ of $n$ points in $\ir^d$, a {\em $(t,\epsilon)$-approximate voronoi diagram (avd)} is a partition of space into constant complexity cells, where each cell $c$ is associated with $t$ representative points of $s$, such that for any point in $c$, one of the associated representatives approximates the nearest neighbor to within a factor of $(1+\epsilon)$. like the voronoi diagram, this structure defines a spatial subdivision. it also has the desirable properties of being easy to construct and providing a simple and practical data structure for answering approximate nearest neighbor queries. the goal is to minimize the number and complexity of the cells in the avd.(math) we assume that the dimension $d$ is fixed. given a real parameter $\gamma$, where $2 \le \gamma \le 1/\epsilon$, we show that it is possible to construct a $(t,\epsilon)$-avd consisting of \[o(n \epsilon^{\frac{d-1}{2}} \gamma^{\frac{3(d-1)}{2}} \log \gamma) \] cells for $t = o(1/(\epsilon \gamma)^{(d-1)/2})$. this yields a data structure of $o(n \gamma^{d-1} \log \gamma)$ space (including the space for representatives) that can answer $\epsilon$-nn queries in time $o(\log(n \gamma) + 1/(\epsilon \gamma)^{(d-1)/2})$. (hidden constants may depend exponentially on $d$, but do not depend on $\epsilon$ or $\gamma$).(math) in the case $\gamma = 1/\epsilon$, we show that the additional $\log \gamma$ factor in space can be avoided, and so we have a data structure that answers $\epsilon$-approximate nearest neighbor queries in time $o(\log (n/\epsilon))$ with space $o(n/\epsilon^{d-1})$, improving upon the best known space bounds for this query time. in the case $\gamma = 2$, we have a data structure that can answer approximate nearest neighbor queries in $o(\log n + 1/\epsilon^{(d-1)/2})$ time using optimal $o(n)$ space. this dramatically improves the previous best space bound for this query time by a factor of $o(1/\epsilon^{(d-1)/2})$.(math) we also provide lower bounds on the worst-case number of cells assuming that cells are axis-aligned rectangles of bounded aspect ratio. in the important extreme cases $\gamma \in \{2, 1/\epsilon\}$, our lower bounds match our upper bounds asymptotically. for intermediate values of $\gamma$ we show that our upper bounds are within a factor of $o((1/\epsilon)^{(d-1)/2}\log \gamma)$ of the lower bound.
on the importance of idempotence. range searching is among the most fundamental problems in computational geometry. an n-element point set in rd is given along with an assignment of weights to these points from some commutative semigroup. subject to a fixed space of possible range shapes, the problem is to preprocess the points so that the total semigroup sum of the points lying within a given query range η can be determined quickly. in the approximate version of the problem we assume that η is bounded, and we are given an approximation parameter ε > 0. we are to determine the semigroup sum of all the points contained within η and may additionally include any of the points lying within distance ε • diam(η) of η's boundar.in this paper we contrast the complexity of range searching based on semigroup properties. a semigroup (s,+) is idempotent if x + x = x for all x ∈ s, and it is integral if for all k ≥ 2, the k-fold sum x + ... + x is not equal to x. for example, (r, min) and (0,1, ∨) are both idempotent, and (n, +) is integral. to date, all upper and lower bounds hold irrespective of the semigroup. we show that semigroup properties do indeed make a difference for both exact and approximate range searching, and in the case of approximate range searching the differences are dramatic.first, we consider exact halfspace range searching. the assumption that the semigroup is integral allows us to improve the best lower bounds in the semigroup arithmetic model. for example, assuming o(n) storage in the plane and ignoring polylog factors, we provide an ω*(n2/5) lower bound for integral semigroups, improving upon the best lower bound of ω*(n1/3), thus closing the gap with the o(n1/2) upper bound.we also consider approximate range searching for euclidean ball ranges. we present lower bounds and nearly matching upper bounds for idempotent semigroups. we also present lower bounds for range searching for integral semigroups, which nearly match existing upper bounds. these bounds show that the advantages afforded by idempotency can result in major improvements. in particular, assuming roughly linear space, the exponent in the ε-dependencies is smaller by a factor of nearly 1/2. all our results are presented in terms of space-time tradeoffs, and our lower and upper bounds match closely throughout the entire spectrum.to our knowledge, our results provide the first proof that semigroup properties affect the computational complexity of range searching in the semigroup arithmetic model. these are the first lower bound results for any approximate geometric retrieval problems. the existence of nearly matching upper bounds, throughout the range of space-time tradeoffs, suggests that we are close to resolving the computational complexity of both idempotent and integral approximate spherical range searching in the semigroup arithmetic model.
edge-deletion and edge-contraction problems for a property -&-pgr; on graphs, the corresponding edge-deletion problem ped(-&-pgr;) (edge-contraction problem pec(-&-pgr;), resp.) is defined as follows: given a graph g, find a set of edges of minimum cardinality whose deletion (contraction, resp.) results in a graph satisfying property -&-pgr;. in this paper we show that the edge-deletion problem ped (-&-pgr;) (edge-contraction problem pec (-&-pgr;), resp.) is np-hard if -&-pgr; is hereditary on subgraphs (contractions, resp.) and is determined by the 3-connected components.
the distance trisector curve. given points p and q in the plane, we are interested in separating them by two curves c1 and c2 such that every point of c1 has equal distance to p and to c2, and every point of c2 has equal distance to c1 and to q. we show by elementary geometric means that such c1 and c2 exist and are unique. moreover, for p = (0,1) and q = (0,-1), c1 is the graph of a function ƒ: r → r, c2 is the graph of -f, and f is convex and analytic (i.e., given by a convergent power series at a neighborhood of every point). we conjecture that f is not expressible by elementary functions and, in particular, not algebraic. we provide an algorithm that, given x ∈ r and ε > 0, computes an approximation to f(x) with error at most ε in time polynomial in log 1+|x|/ε.the separation of two points by two "trisector" curves considered here is a special (two-point) case of a new kind of voronoi diagram, which we call the voronoi diagram with neutral zone and which we investigate in a companion paper.
lower bounds for distributed coin-flipping and randomized consensus. we examine a class of collective coin-flipping games that arises from randomized distributed algorithms with halting failures. in these games, a sequence of local coin flips is generated, which must be combined to form a single global coin flip. an adversary monitors the game and may attempt to bias its outcome by hiding the result of up to t local coin flips. we show that to guarantee at most constant bias, &ohgr;(t2) local coins are needed, even if (a) the local coins can have arbitrary distributions and ranges, (b) the adversary is required to decide immediately wheter to hide or reveal each local coin, and (c) the game can detect which local coins have been hidden. if the adversary is permitted to control the outcome of the coin except for cases whose probability is polynomial in t, &ohgr;(t2/log2t) local coins are needed. combining this fact with an extended version of the well-known fischer-lynch-paterson impossibility proof of deterministic consensus, we show that given an adaptive adversary, any t-resilient asynchronous consensus protocol requires &ohgr;(t2/log2t) local coin flips in any model that can be simulated deterministically using atomic registers. this gives the first nontrivial lower bound on the total work required by wait-free consensus and is tight to within logarithmic factors.
wait-free consensus with infinite arrivals. a randomized algorithm is given that solves the wait-free consensus problem for a shared-memory model with infinitely many processes. the algorithm is based on a weak shared coin algorithm that uses weighted voting to achieve a majority outcome with at least constant probability that cannot be disguised even if a strong adversary is allowed to destroy infinitely many votes. the number of operations performed by process i is a polynomial function of i. additional algorithms are given for solving consensus more efficiently in models with an unknown upper bound b on concurrency or an unknown upper bound n on the number of active processes; under either of these restrictions, it is also shown that the problem can be solved even with infinitely many anonymous processes by prefixing each instance of the shared coin with a naming algorithm that breaks symmetry with high probability. for many of these algorithms, matching lower bounds are proved that show that their per-process work is nearly optimal as a function of i, b, or n. the case of n active processes gives an algorithm for anonymous, adaptive consensus that requires only o(n log2 n) per-process work, which is within a constant factor of the best previously known non-adaptive algorithm for a strong adversary. finally, it is shown that standard universal constructions based on consensus continue to work with infinitely many processes with only slight modifications. this shows that in infinite distributed systems, as in finite ones, with randomness all things are possible.
graph problems on a mesh-connected processor array (preliminary version) we give o(n) step algorithms for solving a number of graph problems on an n-&-times;n array of processors. the problems considered include: marking the bridges of an undirected graph, marking the articulation points of such a graph, finding the length of a shortest cycle, finding a minimum spanning tree, and a number of other problems.
a correctness condition for high-performance multiprocessors (extended abstract) hybrid consistency, a new consistency condition for shared memory multiprocessors, attempts to capture the guarantees provided by contemporary high-performance architectures. it combines the expressiveness of strong consistency conditions(e.g., sequential consistency, linearizability) and the efficiency of weak consistency conditions (e.g., pipelined ram, causal memory). memory access operations are classified either strong or weak. a global ordering of strong operations at different processes is guaranteed, but there is very little guarantee on the ordering of weak operations at different processes, except for what is implied by their interleaving with the strong operations. a formal and precise definition of this condition is given. an efficient implementation of hybrid consistency on distributed memory machines is presented. in this implementation, weak opearations are executed instantaneously, while the response time for strong operations is linear in the network delay. (it is proven that this is within a constant factor of the optimal time bounds.) to motivate hybrid consistency it is shown that weakly consistent memories do not support non-cooperative (in particular, non-centralized) algorithms for mutual exclusion.
computing with faulty arrays we present and o(1) slowdown emulation of a fault-free n x n two dimensional mesh with a slack of o(log n log log n) by a faulty mesh of the same size and slack. all components of the faulty mesh, including the memory modules, are assumed to be subject to failure. the faults may occur at any time during the emulation and the system readjusts dynamically.
on bounds on the number of steps to compute functions let f be a partial recursive function defined in terms of other functions g1,...,gn such that f converges if and only if some well defined assertions about the convergency of g1,...,gn hold: then we can find a total function (depending on the number of steps required to compute g1,...,gn) that bounds the step counting function of f almost everywhere f is defined. it is also shown that, in that case, to compute the bound to the step counting function is not much harder than computing the step counting function itself.
on the problem of computational time and complexity of arithmetic functions the time and incremental complexity required to perform two-operand addition using logical circuitry are compared for nonredundant and minimally redundant encodings of the operands. the comparison is extended to multi-operand addition and two-operand multiplication.
improved approximation guarantees for minimum-weight -trees and prize-collecting salesmen. consider a salesperson that must sell some quota of brushes in order to win a trip to hawaii. this salesperson has a map (a weighted graph) in which each city has an attached demand specifying the number of brushes that can be sold in that city. what is the best route to take to sell the quota while traveling the least distance possible? notice that unlike the standard traveling salesman problem, not only do we need to figure out the order in which to visit the cities, but we must decide the more fundamental question: which cities do we want to visit? in this paper we give the first approximation algorithms with poly-logarithmic performance guarantees for this problem, as well as for the slightly more general pctsp problem of balas, and a variation we call the "bank-robber problem" (also called the "orienteering problem" by golden, levi, and vohra). we do this by providing an o(log^2 k) approximation to the k-mst problem which is defined as follows. given an undirected graph on n nodes with non-negative edge weights and an integer k > n, find the tree of least weight that spans k vertices. (if desired, one may specify in the problem a "root vertex" that must be in the tree as well.) our result improves on the previous best bound of o(k^0.5) of ravi et al. and comes quite close to the bound of o(log k) of garg and hochbaum for the special case of points in 2-dimensional euclidean space.