waashk/dblp huggingface dataset:
the unreasonable effectiveness of martingales. 1 three questions. &bull; let g be a d-regular graph on n vertices where 3 &le; d < n. perform bond percolation with p = 1/d-1 and let c1 be the largest open cluster. is e|c1| = o(n2/3)? (this is well known, and sharp, for d = n - 1, the erd&ouml;s-renyi random graph.) &bull; let g be an infinite connected graph with maximal degree d. does simple rw on g always satisfy pt(x, y) &le; c(d)/&radic; t? &bull; simple rw on {0, 1}k, started uniformly, is a stationary, reversible markov chain that for t < k/4, escapes at a positive speed (in the l1 metric) from its starting point. is there a chain with these properties in the l2 metric? and on a tree?
on distributing symmetric streaming computations. a common approach for dealing with large data sets is to stream over the input in one pass, and perform computations using sublinear resources. for truly massive data sets, however, even making a single pass over the data is prohibitive. therefore, streaming computations must be distribued over many machines. in practice, obtaining significant speedups using distributed computations has numerous challenges including synchronization, load balancing, overcoming processor failures, and data distribution. successful systems in practice such as google's mapreduce and apache's hadoop address these problems by only allowing a certain class of highly distributable tasks defined by local computations that can be applied in any order to the input. the fundamental question that arises is: how does the class of computational tasks supported by these systems differ from the class for which streaming solutions exist? we introduce a simple algorithmic model for massive, unordered, distributed (mud) computation, as implemented by these systems. we show that in principle, mud algorithms are equivalent in power to symmetric streaming algorithms. more precisely, we show that any symmetric (order-invariant) function that can be computed by a steraming algorithm can also be computed by a mud algorithym, with comparable space and communication complexity. our simulation uses savitch's theorem and therefore has superpolynomial time complexity. we extend our simulation result to some natural classes of approximate and randomized steraming algorithms. we also give negative results, using communication complexity arguments to prove that extensions to private randomness, promise problems and indeterminate functions are impossible. we also introduce an extension of the mud model to multiple keys and multiple rounds.
loopless generation of multiset permutations using a constant number of variables by prefix shifts. this paper answers the following mathematical question: can multiset permutations be ordered so that each permutation is a prefix shift of the previous permutation? previously, the answer was known for the permutations of any set, and the permutations of any multiset whose corresponding set contains only two elements. this paper also answers the following algorithmic question: can multiset permutations be generated by a loopless algorithm that uses sublinear additional storage? previously, the best loopless algorithm used a linear amount of additional storage. the answers to these questions are both yes.
succinct geometric indexes supporting point location queries. we propose to design data structures called succinct geometric indexes of negligible space (more precisely, o(n) bits) that support geometric queries in optimal time, by taking advantage of the n points in the data set permuted and stored elsewhere as a sequence. our first and main result is a succinct geometric index that can answer point location queries, a fundamental problem in computational geometry, on planar triangulations in o(lg n) time. we also design three variants of this index. the first supports point location using lg n + 2 &radic;lg n + o(lg1/4n) point-line comparisons. the second supports point location in o(lg n) time when the coordinates are integers bounded by u. the last variant can answer point location queries in o(h + 1) expected time, where h is the entropy of the query distribution. these results match the query efficiency of previous point location structures that occupy o(n) words or o(n lg n) bits, while saving drastic amounts of space. we generalize our succinct geometric index to planar subdivisions, and design indexes for other types of queries. finally, we apply our techniques to design the first implicit data structures that support point location in o(lg2 n) time.
on clustering to minimize the sum of radii. given a metric d defined on a set v of points (a metric space), we define the ball b(v, r) centered at u &isin; v and having radius r &ge; 0 to be the set {q &isin; v/d(v, q) &le;r}. in this work, we consider the problem of computing a minimum cost k-cover for a given set p &sube; v of n points, where k > 0 is some given integer which is also part of the input. for k &ge; 0, a k-cover for subset q &sube; p is a set of at most k balls, each centered at a point in p, whose union covers (contains) q. the cost of a set d of balls, denoted cost(d), is the sum of the radii of those balls.
approximating submodular functions everywhere. submodular functions are a key concept in combinatorial optimization. algorithms that involve submodular functions usually assume that they are given by a (value) oracle. many interesting problems involving submodular functions can be solved using only polynomially many queries to the oracle, e.g., exact minimization or approximate maximization. in this paper, we consider the problem of approximating a non-negative, monotone, submodular function f on a ground set of size n everywhere, after only poly(n) oracle queries. our main result is a deterministic algorithm that makes poly(n) oracle queries and derives a function f such that, for every set s, f(s) approximates f(s) within a factor &alpha;(n), where &alpha;(n) = &radic;n+1 for rank functions of matroids and &alpha;(n), = o(&radic;n log n) for general monotone submodular functions. our result is based on approximately finding a maximum volume inscribed ellipsoid in a symmetrized polymatroid, and the analysis involves various properties of submodular functions and polymatroids. our algorithm is tight up to logarithmic factors. indeed, we show that no algorithm can achieve a factor better than &omega;(&radic;n/log n), even for rank functions of a matroid.
parameterized approximation scheme for the multiple knapsack problem. the multiple knapsack problem (mkp) is a well-known generalization of the classical knapsack problem. we are given a set a of n items and set b of m bins (knapsacks) such that each item a &isin; a has a size size(a) and a profit value profit(a), and each bin b &isin; b has a capacity c(b). the goal is to find a subset u &sub; a of maximum total profit such that u can be packed into b without exceeding the capacities. the decision version of mkp is strongly np-complete, since it is a generalization of the classical knapsack and bin packing problem. furthermore, mkp does not admit an fptas even if the number m of bins is two. kellerer gave a ptas for mkp with identical capacities and chekuri and khanna presented a ptas for mkp with general capacities with running time no(log(1/&epsilon;)/&epsilon;8). in this paper we propose an eptas with parameterized running time 2o(log(1/&epsilon;)/&epsilon;5) &middot; poly(n) + o(m) for mkp. this solves also an open question by chekuri and khanna.
the extended -tree algorithm. consider the following problem: given k = 2q random lists of n-bit vectors, l1, ..., lk, each of length m, find x1 &isin; l1, ..., xk &isin; lk such that x1 + ... + xk = 0, where + is the xor operation. this problem has applications in a number of areas, including cryptanalysis, coding theory, finding shortest lattice vectors, and learning theory. the so-called k-tree algorithm, due to wagner, solves this problem in &otilde;(2q+n/(q+1)) expected time provided the length m of the lists is large enough, specifically if m &ge; 2n/(q+1). in many applications, however, it is necessary to work with lists of smaller length, where the above algorithm breaks down. in this paper we generalize the algorithm to work for significantly smaller values of the list length m, all the way down to the threshold value for which a solution exists with reasonable probability. our algorithm exhibits a tradeoff between the value of m and the running time. we also provide the first rigorous bounds on the failure probability of both our algorithm and that of wagner.
improved bounds and new techniques for davenport--schinzel sequences and their generalizations. we present several new results regarding &lambda;s(n), the maximum length of a davenport--schinzel sequence of order s on n distinct symbols. first, we prove that &lambda;s(n) &leq; n &sdot; 2(1/t&excel;)&alpha;(n)t + o(&alpha;(n)t&minus;1) for s &geq; 4 even, and &lambda;s(n) &leq; n &sdot; 2(1/t&excel;)&alpha;(n)t log2 &alpha;(n) + o(&alpha;(n)t) for s&geq; 3 odd, where t &equals; &lfloor;(s&minus;2)/2&rfloor;, and &alpha;(n) denotes the inverse ackermann function. the previous upper bounds, by agarwal et al. &lsqb;1989&rsqb;, had a leading coefficient of 1 instead of 1/t&excel; in the exponent. the bounds for even s are now tight up to lower-order terms in the exponent. these new bounds result from a small improvement on the technique of agarwal et al. more importantly, we also present a new technique for deriving upper bounds for &lambda;s(n). this new technique is very similar to the one we applied to the problem of stabbing interval chains &lsqb;alon et al. 2008&rsqb;. with this new technique we: (1) re-derive the upper bound of &lambda;3(n) &leq; 2n &alpha;(n) + o(n &sqrt;&alpha;(n)) (first shown by klazar &lsqb;1999&rsqb;); (2) re-derive our own new upper bounds for general s and (3) obtain improved upper bounds for the generalized davenport--schinzel sequences considered by adamec et al. &lsqb;1992&rsqb;. regarding lower bounds, we show that &lambda;3(n) &geq; 2n &alpha;(n) &minus; o(n) (the previous lower bound (sharir and agarwal, 1995) had a coefficient of 1/2), so the coefficient 2 is tight. we also present a simpler variant of the construction of agarwal et al. &lsqb;1989&rsqb; that achieves the known lower bounds of &lambda;s(n) &geq; n &sdot; 2(1/t&excel;) &alpha;(n)t &minus; o(&alpha;(n)t&minus;1) for s &geq; 4 even.
stream sampling for variance-optimal estimation of subset sums. from a high volume stream of weighted items, we want to maintain a generic sample of a certain limited size k that we can later use to estimate the total weight of arbitrary subsets. this is the classic context of on-line reservoir sampling, thinking of the generic sample as a reservoir. we present an efficient reservoir sampling scheme, varoptk, that dominates all previous schemes in terms of estimation quality. varoptk provides variance optimal unbiased estimation of subset sums. more precisely, if we have seen n items of the stream, then for any subset size m, our scheme based on k samples minimizes the average variance over all subsets of size m. in fact, the optimality is against any off-line scheme with k samples tailored for the concrete set of items seen. in addition to optimal average variance, our scheme provides tighter worst-case bounds on the variance of particular subsets than previously possible. it is efficient, handling each new item of the stream in o(log k) time, which is optimal even on the word ram. finally, it is particularly well suited for combination of samples from different streams in a distributed setting.
approximate line nearest neighbor in high dimensions. we consider the problem of approximate nearest neighbors in high dimensions, when the queries are lines. in this problem, given n points in rd, we want to construct a data structure to support efficiently the following queries: given a line l, report the point p closest to l. this problem generalizes the more familiar nearest neighbor problem. from a practical perspective, lines, and low-dimensional flats in general, may model data under linear variation, such as physical objects under different lighting. for approximation 1 + &epsilon;, we achieve a query time of d3n0.5+t, for arbitrary small t > 0, with a space of d2no(1/&epsilon;2+1/t2). to the best of our knowledge, this is the first algorithm for this problem with polynomial space and sub-linear query time.
clique-width: on the price of generality. many hard problems can be solved efficiently when the input is restricted to graphs of bounded treewidth. by the celebrated result of courcelle, every decision problem expressible in monadic second order logic is fixed parameter tractable when parameterized by the treewidth of the input graph. moreover, for every fixed k &ge; 0, such problems can be solved in linear time on graphs of treewidth at most k. in particular, this implies that basic problems like dominating set, graph coloring, clique, and hamiltonian cycle are solvable in linear time on graphs of bounded treewidth. a significant amount of research in graph algorithms has been devoted to extending this result to larger classes of graphs. it was shown that some of the algorithmic meta-theorems for treewidth can be carried over to graphs of bounded clique-width. courcelle, makowsky, and rotics proved that the analogue of courcelle's result holds for graphs of bounded clique-width when the logical formulas do not use edge set quantifications. despite of its generality, this does not resolve the parameterized complexity of many basic problems concerning edge subsets (like edge dominating set), vertex partitioning (like graph coloring), or global connectivity (like hamiltonian cycle). there are various algorithms solving some of these problems in polynomial time on graphs of clique-width at most k. however, these are not fixed parameter tractable algorithms and have typical running times o(nf(k)), where n is the input length and f is some function. it was an open problem, explicitly mentioned in several papers, whether any of these problems is fixed parameter tractable when parameterized by the clique-width, i.e. solvable in time o(g(k)&middot;nc), for some function g and a constant c not depending on k. in this paper we resolve this problem by showing that edge dominating set, hamiltonian cycle, and graph coloring are w[1]-hard parameterized by clique-width. this shows that the running time o(nf(k)) of many clique-width based algorithms is essentially the best we can hope for (up to a widely believed assumption from parameterized complexity, namely fpt &ne; w[1])---the price we pay for generality.
hardness of embedding simplicial complexes in . let embedk&rarr;d be the following algorithmic problem: given a finite simplicial complex k of dimension at most k, does there exist a (piecewise linear) embedding of k into rd? known results easily imply polynomiality of embedk&rarr;2 (k = 1, 2; the case k = 1, d = 2 is graph planarity) and of embedk&rarr;2k for all k &ge; 3 (even if k is not considered fixed). we show that the celebrated result of novikov on the algorithmic unsolvability of recognizing the 5-sphere implies that embedd&rarr;d and embed(d-1)&rarr;d are undecidable for each d &ge; 5. our main result is np-hardness of embed2&rarr;4 and, more generally, of embedk&rarr;d for all k, d with d &rarr; 4 and d &rarr; k &rarr; (2d - 2)/3.
on the approximability of the maximum feasible subsystem problem with 0/1-coefficients. given a system of constraints li &le; atix &le; ui, where ai &isin; {0, 1}n, and li, ui &isin; r+, for i = 1,..., m, we consider the problem mrfs of finding the largest subsystem for which there exists a feasible solution x &ge; 0. we present approximation algorithms and inapproximability results for this problem, and study some important special cases. our main contributions are: 1. in the general case, where ai &epsilon; {0, 1}n, a sharp separation in the approximability between the case when l = max{l1, ..., lm} is bounded above by a polynomial in n and m, and the case when it is not. 2. in the case where a is an interval matrix, a sharp separation in approximability between the case where we allow a violation of the upper bounds by at most a (1 + &epsilon;) factor, for any fixed &epsilon; > 0 and the case where no violations are allowed. along the way, we prove that the induced matching problem on bipartite graphs is inapproximable beyond a factor of &omega;(n1/3-&epsilon;), for any &epsilon; > 0 unless np=zpp. finally, we also show applications of mrfs to some recently studied pricing problems.
a near-linear time algorithm for constructing a cactus representation of minimum cuts. we present an &otilde;(m) (near-linear) time monte carlo algorithm for constructing the cactus data structure, a useful representation of all the global minimum edge cuts of an undirected graph. our algorithm represents a fundamental improvement over the best previous (quadratic time) algorithms: because there can be quadratically many min-cuts, our algorithm must avoid looking at all min-cuts during the construction, but nonetheless builds a data structure representing them all. our result closes the gap between the (near-linear) time required to find a single min-cut and that for (implicitly) finding all the min-cuts.
reasoning about online algorithms with weighted automata. we describe an automata-theoretic approach for the competitive analysis of online algorithms. our approach is based on weighted automata, which assign to each input word a cost in r&ge;0. by relating the &ldquo;unbounded look ahead&rdquo; of optimal offline algorithms with nondeterminism, and relating the &ldquo;no look ahead&rdquo; of online algorithms with determinism, we are able to solve problems about the competitive ratio of online algorithms, and the memory they require, by reducing them to questions about determinization and approximated determinization of weighted automata.
decomposition of multiple coverings into more parts. we prove that for every centrally symmetric convex polygon q, there exists a constant &#x03b1; such that any locally finite &#x03b1; k-fold covering of the plane by translates of q can be decomposed into k coverings. this improves on a quadratic upper bound proved by pach and t&#x00f3;th. the question is motivated by a sensor network problem, in which a region has to be monitored by sensors with limited battery life.
overcoming the non-embeddability barrier: algorithms for product metrics. a common approach for solving computational problems over a difficult metric space is to embed the "hard" metric into l1 which admits efficient algorithms and is thus considered an "easy" metric. this approach has proved successful or partially successful for important spaces such as the edit distance, but it also has inherent limitations: it is provably impossible to go below certain approximation for some metrics. we propose a new approach, of embedding the difficult space into richer host spaces, namely iterated products of standard spaces like l1 and l&infin;. we show that this class is rich since it contains useful metric spaces with only a constant distortion, and, at the same time, it is tractable and admits efficient algorithms. using this approach, we obtain for example the first nearest neighbor data structure with o(log log d) approximation for edit distance in non-repetitive strings (the ulam metric). this approximation is exponentially better than the lower bound for embedding into l1. furthermore, we give constant factor approximation for two other computational problems. along the way, we answer positively a question posed in [ajtai, jayram, kumar, and sivakumar, stoc 2002]. one of our algorithms has already found applications for smoothed edit distance over 0--1 strings [andoni and krauthgamer, icalp 2008].
a quadratic kernel for feedback vertex set. we prove that given an undirected graph g on n vertices and an integer k, one can compute in polynomial time in n a graph g' with at most 5k2 + k vertices and an integer k' such that g has a feedback vertex set of size at most k iff g' has a feedback vertex set of size at most k'. this result improves a previous o(k11) kernel of burrage et al. [6], and a more recent cubic kernel of bodlaender [3]. this problem was communicated by fellows in [5].
on risks of using cuckoo hashing with simple universal hash classes. cuckoo hashing, introduced by pagh and rodler [10], is a dynamic dictionary data structure for storing a set s of n keys from a universe u, with constant lookup time and amortized expected constant insertion time. for the analysis, space (2+&epsilon;)n and &omega;(log n)-wise independence of the hash functions is sufficient. in experiments mentioned in [10], several weaker hash classes worked well; however, a certain simple multiplicative hash family worked badly. in this paper, we prove that the failure probability is high when cuckoo hashing is run with the multiplicative class or with the very common class of linear hash functions over a prime field, even if space 4n is provided. the key set s is fully random, but it must be relatively dense in the universe u of all keys (like |s| &ge; |u|11/12). the bad behavior and the fact that this effect depends on the density of s in u can also be observed in experiments. the result transfers to larger universes if the keys are chosen from a suitable smaller domain. viewed from a different perspective, our result illustrates that care must be taken when applying a recent result of mitzenmacher and vadhan ([12], soda 2008) proving good behavior of universal hash classes in combination with key sets that have some entropy. their result is applicable to cuckoo hashing. a technical hypothesis in [12], namely the assumption that either the "collision probability" or the "maximum probability" is small, translates into the condition that |s| is relatively small in comparison to |u|. our result shows that the result from [12] on 2-universal classes ceases to hold if |s|/|u| is not small enough, even for very common 2-universal hash classes and fully random key sets.
computing the nucleolus of weighted voting games. weighted voting games (wvg) are coalitional games in which an agent's contribution to a coalition is given by his weight, and a coalition wins if its total weight meets or exceeds a given quota. these games model decision-making in political bodies as well as collaboration and surplus division in multiagent domains. the computational complexity of various solution concepts for weighted voting games received a lot of attention in recent years. in particular, elkind et al.(2007) studied the complexity of stability-related solution concepts in wvgs, namely, of the core, the least core, and the nucleolus. while they have completely characterized the algorithmic complexity of the core and the least core, for the nucleolus they have only provided an np-hardness result. in this paper, we solve an open problem posed by elkind et al. by showing that the nucleolus of wvgs, and, more generally, k-vector weighted voting games with fixed k, can be computed in pseudopolynomial time, i.e., there exists an algorithm that correctly computes the nucleolus and runs in time polynomial in the number of players n and the maximum weight w. in doing so, we propose a general framework for computing the nucleolus, which may be applicable to a wider of class of games.
sorting by placement and shift. in sorting situations where the final destination of each item is known, it is natural to repeatedly choose items and place them where they belong, allowing the intervening items to shift by one to make room. (in fact, a special case of this algorithm is commonly used to hand-sort files.) however, it is not obvious that this algorithm necessarily terminates. we show that in fact the algorithm terminates after at most 2n-1-1 steps in the worst case (confirming a conjecture of l. larson), and that there are super-exponentially many permutations for which this exact bound can be achieved. the proof involves a curious symmetrical binary representation.