waashk/dblp huggingface dataset:
setting lower bounds on truthfulness: extended abstract. we present and discuss general techniques for proving inapproximability results for truthful mechanisms. we make use of these techniques to prove lower bounds on the approximability of several non-utilitarian multi-parameter problems. in particular, we demonstrate the strength of our techniques by exhibiting a lower bound of 2 - 1/m for the scheduling problem with unrelated machines (formulated as a mechanism design problem in the seminal paper of nisan and ronen on algorithmic mechanism design). our lower bound applies to truthful randomized mechanisms (disregarding any computational assumptions on the running time of these mechanisms). moreover, it holds even for the weaker notion of truthfulness for randomized mechanisms - i.e., truthfulness in expectation. this lower bound nearly matches the known 7/4 (randomized) truthful upper bound for the case of two machines (a non-truthful fptas exists). no lower bound for truthful randomized mechanisms in multi-parameter settings was previously known. we show an application of our techniques to the workload-minimization problem in networks. we prove our lower bounds for this problem in the inter-domain routing setting presented by feigenbaum, papadimitriou, sami, and shenker. finally, we discuss several notions of non-utilitarian "fairness" (max-min fairness, min-max fairness, and envy minimization). we show how our techniques can be used to prove lower bounds for these notions.
approximating the spanning star forest problem and its applications to genomic sequence alignment. this paper studies the algorithmic issues of the spanning star forest problem. we prove the following results: (1) there is a polynomial-time approximation scheme for planar unweighted graphs; (2) there is a polynomial-time algorithm with approximation ratio 3/5 for unweighted graphs; (3) it is np-hard to approximate the problem within ratio 545/546 + &epsilon; for unweighted graphs; (4) there is a linear-time algorithm to compute the maximum star forest of a weighted tree; (5) there is a polynomial-time algorithm with approximation ratio 1/2 for weighted graphs. we also show how to apply this spanning star forest model to aligning multiple genomic sequences over a tandem duplication region.
on bregman voronoi diagrams. the voronoi diagram of a point set is a fundamental geometric structure that partitions the space into elementary regions of influence defining a discrete proximity graph and dually a well-shaped delaunay triangulation. in this paper, we investigate a framework for defining and building the voronoi diagrams for a broad class of distortion measures called bregman divergences, that includes not only the traditional (squared) euclidean distance, but also various divergence measures based on entropic functions. as a by-product, bregman voronoi diagrams allow one to define information-theoretic voronoi diagrams in statistical parametric spaces based on the relative entropy of distributions. we show that for a given bregman divergence, one can define several types of voronoi diagrams related to each other by convex duality or embedding. moreover, we can always compute them indirectly as power diagrams in primal or dual spaces, or directly after linearization in an extra-dimensional space as the projection of a euclidean polytope. finally, our paper proposes to generalize bregman divergences to higher-order terms, called &kappa;-jet bregman divergences, and touch upon their voronoi diagrams.
randomization does not help searching predecessors. at stoc'06, we presented a new technique for proving cell-probe lower bounds for static data structures with deterministic queries. this was the first technique which could prove a bound higher than communication complexity, and it gave the first separation between data structures with linear and polynomial space. the new technique was, however, heavily tuned for the deterministic worst-case, demonstrating long query times only for an exponentially small fraction of the input. in this paper, we extend the technique to give lower bounds for randomized query algorithms with constant error probability. our main application is the problem of searching predecessors in a static set of n integers, each contained in a l-bit word. our trade-off lower bounds are tight for any combination of parameters. for small space, i.e. n1+o(1), proving such lower bounds was inherently impossible through known techniques. an interesting new consequence is that for near linear space, the classic van emde boas search time of o(lg l) cannot be improved, even if we allow randomization. this is a separation from polynomial space, since beame and fich [stoc'02] give a predecessor search time of o(lg l/lg lg l) using quadratic space. we also show a tight &omega;(lg lg n) lower bound for 2-dimensional range queries, via a new reduction. this holds even in rank space, where no superconstant lower bound was known, neither randomized nor worst-case. we also slightly improve the best lower bound for the approximate nearest neighbor problem, when small space is available.
ranged hash functions and the price of churn. ranged hash functions generalize hash tables to the setting where hash buckets may come and go over time, a typical case in distributed settings where hash buckets may correspond to unreliable servers or network connections. monotone ranged hash functions are a particular class of ranged hash functions that minimize item reassignments in response to churn: changes in the set of available buckets. the canonical example of a monotone ranged hash function is the ring-based consistent hashing mechanism of karger et al. [13]. these hash functions give a maximum load of &theta; (n/mlogm) when n is the number of items and m is the number of buckets. the question of whether some better bound could be obtained using a more sophisticated hash function has remained open. we resolve this question by showing two lower bounds. first, the maximum load of any randomized monotone ranged hash function is &omega;(&radic;n/mlnm) when n = o(mlogm). this bound covers almost all of the nontrivial case, because when n = &omega;(mlogm) simple random assignment matches the trivial lower bound of &omega;(n/m). we give a matching (though impractical) upper bound that shows that our lower bound is tight over almost all of its range. second, for randomized monotone ranged hash functions derived from metric spaces, there is a further trade-off between the expansion factor of the metric and the load balance, which for the special case of growth-restricted metrics gives a bound of &omega;(n/mlogm), asymptotically equal to that of consistent hashing. these are the first known non-trivial lower bounds for ranged hash functions. they also explain why in ten years no better ranged hash functions have arisen to replace consistent hashing.
why simple hash functions work: exploiting the entropy in a data stream. hashing is fundamental to many algorithms and data structures widely used in practice. for theoretical analysis of hashing, there have been two main approaches. first, one can assume that the hash function is truly random, mapping each data item independently and uniformly to the range. this idealized model is unrealistic because a truly random hash function requires an exponential number of bits to describe. alternatively, one can provide rigorous bounds on performance when explicit families of hash functions are used, such as 2-universal or o(1)-wise independent families. for such families, performance guarantees are often noticeably weaker than for ideal hashing. in practice, however, it is commonly observed that simple hash functions, including 2-universal hash functions, perform as predicted by the idealized analysis for truly random hash functions. in this paper, we try to explain this phenomenon. we demonstrate that the strong performance of universal hash functions in practice can arise naturally from a combination of the randomness of the hash function and the data. specifially, following the large body of literature on random sources and randomness extraction, we model the data as coming from a "block source," whereby each new data item has some "entropy" given the previous ones. as long as the (renyi) entropy per data item is sufficiently large, it turns out that the performance when choosing a hash function from a 2-universal family is essentially the same as for a truly random hash function. we describe results for several sample applications, including linear probing, balanced allocations, and bloom filters.
product growth and mixing in finite groups. we prove the following inequality on the convolution of distributions over a finite group g: {display equation} where x, y are probability distributions over g, the * denotes convolution, u the uniform distribution over g, and || &middot; || the l2-norm; n is the order of g, and m denotes the minimum dimension of nontrivial real representations of g. this inequality can be viewed as a new expansion property of a large class of groups, including all lie-type simple groups of bounded rank, all of which satisfy m > cn&beta; (where c > 0 is an absolute constant and &beta; > 0 depends on the rank bound only). best among them are the groups g = sl2(q) (2 x 2 matrices with determinant 1 over 픽q) where m &sim; n1/3/2. we derive applications of the convolution inequality (0.1) to a variety of areas, ranging from stochastic processes to additive combinatorics to group theory. an immediate consequence is a product growth inequality for subsets of g: if a, b &sube; g then |ab| > n/(1 + &delta;) where &delta; = n2/(m|a||b|). on the one hand, this corollary strengthens a recent result of gowers which served as the inspiration to the present work; on the other hand, it gives a strong (and best possible) affirmative answer to a problem regarding the product growth of subsets of sl2(q) recently posed by venkatesh and green at a conference in the newly flourishing area of "additive combinatorics." another corollary to the main inequality shows that for groups with large m, mixing in the strongest sense (&ell;&infin;-norm) occurs more rapidly than expected; we prove that if x, y, z are distributions over g then {display equation} this generalizes a result of gowers. by easy induction, our main inequality generalizes to the convolution of multiple terms and thereby results in rapid mixing estimates for time-inhomogeneous cayley walks on g. it also gives estimates for the size of the product of several subsets, resulting in diameter estimates for cayley graphs and tying in with the broad subject of "bounded generation" in group theory. an illustration of the connection to diameters: for g = sl2(q) it follows that if a &sube; g and |a| &ge; n2/3+&epsilon; then at = g where t = o(1/&epsilon;); we also show that the elements of g are represented nearly uniformly as words of length t over a. the connection to "bounded generation" is illustrated by one of the main applications of our results: every finite simple group of lie type of characteristic p is the product of 5 sylow p-subgroups. - results of this type are among the ingredients of the recent breakthrough result that all finite simple groups have bounded degree expander cayley graphs [kln]; our results improve and greatly simplify these ingredients. the results and techniques used in this paper were inspired by a link between quasirandomness and group representation theory recently found by gowers [go].
the power of memory in randomized broadcasting. in this paper we analyze the runtime and number of message transmissions generated by simple randomized broadcasting algorithms in random-like networks, and show that an apparently minor change in the ability of the nodes implies an exponential decrease in the average communication overhead produced by these algorithms at an arbitrary node. a natural randomized broadcasting protocol, called random phone call model, has been introduced by karp et al. [20]. in this model it is assumed that in each time step, every node of g calls a neighbor, chosen uniformly at random, and establishes a communication channel with this neighbor. any node u is then allowed to send/receive messages to/from all nodes which have established communication channels with u in the current time step. karp et al. showed that some piece of information r, placed initially on one of the nodes of a complete graph of size n, can be spread with probability 1 - n-&omega;(1) to all nodes of this graph within o(log n) time steps, by using o(n log log n) transmissions related to r. furthermore, they proved that this result is asymptotically optimal among all address-oblivious broadcasting algorithms. in a recent paper [9], we analyzed the random phone call model in traditional random graphs gn,p with p > log2 n/n, and showed that any address-oblivious broadcasting algorithm requires with high probability &omega;(log n) time steps and &omega;(n (log log n + log n/log(pn))) message transmissions to inform all nodes of such a graph. in this paper we consider two simple modifications of the random phone call model, and show that in both cases the number of total message transmissions can be reduced significantly (up to almost a logarithmic factor). in the first case, we allow each node of a random graph gn,p with p > log&delta; n/n, where &lambda; is a properly chosen constant, to call in every time step four different neighbors, chosen uniformly at random, and we prove that the number of message transmissions decreases to o(n log log n). this can be viewed as a "power of multiple choices" type theorem for randomized broadcasting. then we show that if in the random phone call model the nodes are provided with a little memory, i.e., they are able to remember the addresses of the nodes chosen in the most recent three time steps, then the communication overhead decreases substantially, too. finally, we prove the optimality of our results. the algorithms presented in this paper can cope with restricted communication failures, only require rough estimates of the number of nodes, and are robust against slight topological changes. in addition, our results can be extended to the generalized random graph model of [6].
efficient reductions among lattice problems. we give various deterministic polynomial time reductions among approximation problems on point lattices. our reductions are both efficient and robust, in the sense that they preserve the rank of the lattice and approximation factor achieved. our main result shows that for any &gamma; &ge; 1, approximating all the successive minima of a lattice (and, in particular, approximately solving the shortest independent vectors problem, sivp&gamma;) within a factor &gamma; reduces under deterministic polynomial time rank-preserving reductions to approximating the closest vector problem (cvp) within the same factor &gamma;. this solves an open problem posed by bl&ouml;mer in (icalp 2000). as an application, we obtain faster algorithms for the exact solution of sivp that run in time n! &middot; so(1) (where n is the rank of the lattice, and s the size of the input,) improving on the best previously known solution of bl&ouml;mer (icalp 2000) by a factor 3n. we also show that sivp, cvp and many other lattice problems are equivalent in their exact version under deterministic polynomial time rank-preserving reductions.
fast dimension reduction using rademacher series on dual bch codes. the fast johnson-lindenstrauss transform (fjlt) was recently discovered by ailon and chazelle as a novel technique for performing fast dimension reduction with small distortion from &ell;d2 to &ell;d2 in time o(max{d log d,k3}). for k in [&omega;(log d), o(d1/2)] this beats time o(dk) achieved by naive multiplication by random dense matrices, an approach followed by several authors as a variant of the seminal result by johnson and lindenstrauss (jl) from the mid 80's. in this work we show how to significantly improve the running time to o(d log k) for k = o(d1/2&minus;&delta;), for any arbitrary small fixed &delta;. this beats the better of fjlt and jl. our analysis uses a powerful measure concentration bound due to talagrand applied to rademacher series in banach spaces (sums of vectors in banach spaces with random signs). the set of vectors used is a real embedding of dual bch code vectors over gf(2). we also discuss the number of random bits used and reduction to &ell;1 space. the connection between geometry and discrete coding theory discussed here is interesting in its own right and may be useful in other algorithmic applications as well.
delaunay graphs of point sets in the plane with respect to axis-parallel rectangles. given a point set p in the plane, the delaunay graph with respect to axis-parallel rectangles is a graph defined on the vertex set p, whose two points p,q &isin; p are connected by an edge if and only if there is a rectangle parallel to the coordinate axes that contains p and q, but no other elements of p. the following question of even et al. [elrs03] was motivated by a frequency assignment problem in cellular telephone networks. does there exist a constant c > 0 such that the delaunay graph of any set of n points in general position in the plane contains an independent set of size at least cn? we answer this question in the negative, by proving that the largest independent set in a randomly and uniformly selected point set in the unit square is o(n log2 log n/log n), with probability tending to 1. we also show that our bound is not far from optimal, as the delaunay graph of a uniform random set of n points almost surely has an independent set of size at least cn/ log n. we give two further applications of our methods. 1. we construct 2-dimensional n-element partially ordered sets such that the size of the largest independent sets of vertices in their hasse diagrams is o(n). this answers a question of matou&scaron;ek and p&rcaron;&iacute;v&ecaron;tiv&yacute; [map06] and improves a result of k&rcaron;&iacute;&zcaron; and ne&scaron;et&rcaron;il [krn91]. 2. for any positive integers c and d, we prove the existence of a planar point set with the property that no matter how we color its elements by c colors, we find an axis-parallel rectangle containing at least d points, all of which have the same color. this solves an old problem from [brmp05].
the ugc hardness threshold of the &ell; grothendieck problem. for p &ge; 2 we consider the problem of, given an n &times; n matrix a = (aij) whose diagonal entries vanish, approximating in polynomial time the number {display equation} (where optimization is taken over real numbers). when p = 2 this is simply the problem of computing the maximum eigenvalue of a, while for p = &infin; (actually it suffices to take p &ap; log n) it is the grothendieck problem on the complete graph, which was shown to have a o(log n) approximation algorithm in [27, 26, 15], and was used in [15] to design the best known algorithm for the problem of computing the maximum correlation in correlation clustering. thus the problem of approximating optp (a) interpolates between the spectral (p = 2) case and the correlation clustering (p = &infin;) case. from a physics point of view this problem corresponds to computing the ground states of spin glasses in a hard-wall potential well. we design a polynomial time algorithm which, given p &ge; 2 and an n x n matrix a = (aij) with zeros on the diagonal, computes optp (a) up to a factor p/e + 30 log p. on the other hand, assuming the unique games conjecture (ugc) we show that it is np-hard to approximate (1.2) up to a factor smaller than p/e + 1/4. hence as p &rarr; &infin; the ugc-hardness threshold for computing optp (a) is exactly p/e (1 + o(1)).
rapid mixing of gibbs sampling on graphs that are sparse on average. gibbs sampling also known as glauber dynamics is a popular technique for sampling high dimensional distributions defined on graphs. of special interest is the behavior of gibbs sampling on the erd&ouml;s-r&eacute;nyi random graph g(n, d/n), where each edge is chosen independently with probability d/n and d is fixed. while the average degree in g(n, d/n) is d(1 - o(1)), it contains many nodes of degree of order log n/ log log n. the existence of nodes of almost logarithmic degrees implies that for many natural distributions defined on g(n, p) such as uniform coloring (with a constant number of colors) or the ising model at any fixed inverse temperature &beta;, the mixing time of gibbs sampling is at least n1+&omega;(1/log log n). recall that the ising model with inverse temperature &beta; defined on a graph g = (v, e) is the distribution over {&plusmn;}v given by p(&sigma;) = 1/z exp (&beta; &sigma;(v,u)&isin;e &sigma;(v)&sigma;(u)). high degree nodes pose a technical challenge in proving polynomial time mixing of the dynamics for many models including the ising model and coloring. almost all known sufficient conditions in terms of &beta; or number of colors needed for rapid mixing of gibbs samplers are stated in terms of the maximum degree of the underlying graph. in this work we show that for every d < &infin; and the ising model defined on g(n, d/n), there exists a &beta;d > 0, such that for all &beta; < &beta;d with probability going to 1 as n &rarr; &infin;, the mixing time of the dynamics on g(n, d/n) is polynomial in n. our results are the first polynomial time mixing results proven for a natural model on g(n, d/n) for d > 1 where the parameters of the model do not depend on n. they also provide a rare example where one can prove a polynomial time mixing of gibbs sampler in a situation where the actual mixing time is slower than n polylog(n). our proof exploits in novel ways the local treelike structure of erd&odblac;s-r&eacute;nyi random graphs, comparison and block dynamics arguments and a recent result of weitz. our results extend to much more general families of graphs which are sparse in some average sense and to much more general interactions. in particular, they apply to any graph for which every vertex v of the graph has a neighborhood n (v) of radius o (log n) in which the induced subgraph is a tree union at most o(log n) edges and where for each simple path in n(v) the sum of the vertex degrees along the path is o(log n). moreover, our result apply also in the case of arbitrary external fields and provide the first fpras for sampling the ising distribution in this case. we finally present a non markov chain algorithm for sampling the distribution which is effective for a wider range of parameters. in particular, for g(n, d/n) it applies for all external fields and &beta; < &beta;d, where d tanh(&beta;d) = 1 is the critical point for decay of correlation for the ising model on g(n, d/n).
an algorithm for improving graph partitions. we present an algorithm called improve that improves a proposed partition of a graph, taking as input a subset of vertices and returning a new subset of vertices with a smaller quotient cut score. the most powerful previously known method for improving quotient cuts, which is based on parametric flow, returns a partition whose quotient cut score is at least as small as any set contained within the proposed set. for our algorithm, we can prove a stronger guarantee: the quotient score of the set returned is nearly as small as any set in the graph with which the proposed set has a larger-than-expected intersection. the algorithm finds such a set by solving a sequence of polynomially many s -- t minimum cut problems, a sequence that cannot be cast as a single parametric flow problem. we demonstrate empirically that applying improve to the output of various graph partitioning algorithms greatly improves the quality of cuts produced without significantly impacting the running time.