waashk/dblp huggingface dataset:
noisy sorting without resampling. in this paper we study noisy sorting without re-sampling. in this problem there is an unknown order {display equation} where &pi; is a permutation on n elements. the input is the status of (n2) queries of the form q(ai, aj), for i < j, where q(ai, aj) = + (-) with probability 1/2 + &gamma; if &pi;(i) > &pi;(j)(&pi;(i) < &pi;(j)) for all pairs i &ne; j, where &gamma; > 0 is a constant. it is assumed that the errors are independent. given the status of the queries the goal is to find the maximum likelihood order. in other words, the goal is find a permutation &sigma; that minimizes the number of pairs &sigma;(i) > &sigma;(j) where q(&sigma;(i), &sigma;(j)) = -. the problem so defined is the feedback arc set problem on distributions of inputs, each of which is a tournament obtained as a noisy perturbation of a linear order. note that when &gamma; < 1/2 and n is large, it is impossible to recover the original order &pi;. it is known that the weighted feedback arc set problem on tournaments is np-hard in general. here we present an algorithm of running time no(&gamma;-4)) and sampling complexity o&gamma; (n log n) that with high probability solves the noisy sorting without re-sampling problem. we also show that if a&sigma;(1), a&sigma;(2), &hellip;, a&sigma;(n) is an optimal solution of the problem then it is "close" to the original order. more formally, with high probability it holds that {display equation}. our results are of interest in applications to ranking, such as ranking in sports, or ranking of search items based on comparisons by experts.
generating random graphs with large girth. we present a simple and efficient algorithm for randomly generating simple graphs without small cycles. these graphs can be used to design high performance low-density parity-check (ldpc) codes. for any constant k, &alpha; &le; 1/2k(k + 3) and m = o(n1+&alpha;), our algorithm generates an asymptotically uniform random graph with n vertices, m edges, and girth larger than k in polynomial time. to the best of our knowledge this is the first polynomial algorithm for the problem. our algorithm generates a graph by sequentially adding m edges to an empty graph with n vertices. recently, this type of sequential process has been very successful for efficiently counting and generating random graphs [35, 18, 11, 7, 5, 6].
fully dynamic algorithm for graph spanners with poly-logarithmic update time. spanner of an undirected graph g = (v, e) is a sub graph which is sparse and yet preserves all-pairs distances approximately. more precisely, a spanner with stretch t &isin; in is a subgraph (v, es), es &sube; e such that the distance between any two vertices in the subgraph is at most t times their distance in g. we present two fully dynamic algorithms for maintaining a sparse t-spanner of an unweighted graph. our first algorithm achieves expected o(7 t/4) time per update independent of the size of the graph. this algorithm is particularly of interest for maintaining small stretch spanners. our second algorithm achieves expected o(polylog |v|) time per update irrespective of the stretch.
quasirandom rumor spreading. we propose and analyse a quasirandom analogue to the classical push model for disseminating information in networks ("randomized rumor spreading"). in the classical model, in each round each informed node chooses a neighbor at random and informs it. results of frieze and grimmett (discrete appl. math. 1985) show that this simple protocol succeeds in spreading a rumor from one node of a complete graph to all others within o(log n) rounds. for the network being a hypercube or a random graph g(n, p) with p &ge; (1 +&epsilon;)(log n)/n, also o(log n) rounds suffice (feige, peleg. raghavan, and upfal, random struct. algorithms 1990). in the quasirandom model, we assume that each node has a (cyclic) list of its neighbors. once informed, it starts at a random position of the list, but from then on informs its neighbors in the order of the list. surprisingly, irrespective of the orders of the lists, the above mentioned bounds still hold. in addition, we also show a o(log n) bound for sparsely connected random graphs g(n, p) with p = (log n + f(n))/n, where f(n) &rarr; &infin; and f(n) = o(log log n). here, the classical model needs &theta;(log2(n)) rounds. hence the quasirandom model achieves similar or better broadcasting times with a greatly reduced use of random bits.
splay trees, davenport-schinzel sequences, and the deque conjecture. we introduce a new technique to bound the asymptotic performance of splay trees. the basic idea is to transcribe, in an indirect fashion, the rotations performed by the splay tree as a davenport-schinzel sequence, none of whose subsequences are isomorphic to a fixed forbidden subsequence. we direct this technique towards tarjan's deque conjecture and prove that n deque operations take only o(n&alpha;*(n)) time, where &alpha;* (n) is the minimum number of applications of the inverse-ackermann function mapping n to a constant. we are optimistic that this approach could be directed towards other open conjectures on splay trees such as the traversal and split conjectures.
fast and reliable reconstruction of phylogenetic trees with very short edges. phylogenetic reconstruction is the problem of reconstructing an evolutionary tree from sequences corresponding to leaves of that tree. a central goal in phylogenetic reconstruction is to be able to reconstruct the tree as accurately as possible from as short as possible input sequences. the sequence length required for correct topological reconstruction depends on certain properties of the tree, such as its depth and minimal edge-weight. fast converging reconstruction algorithms are considered state-of the-art in this sense, as they require asymptotically minimal sequence length in order to guarantee (with high probability) correct topological reconstruction of the entire tree. however, when the original phylogenetic tree contains very short edges, this minimal sequence-length is still too long for practical purposes. short edges are not only very hard to reconstruct; their presence may also prevent the correct reconstruction of long edges. in this paper we present a fast converging reconstruction algorithm which returns a partially resolved topology containing all edges of the original tree whose weight exceeds some (non-trivial) lower bound, which is determined by the input sequence length, as well as some properties of the tree, such as its depth. it does not depend, however, on the minimal edge-weight. this lower bound provides a partial reconstruction guarantee which is strictly stronger than the guarantees given by other fast converging algorithms. our algorithm also has optimal complexity (linear space and quadratic-time) which, together with its partial reconstruction guarantee, makes it appealing for practical use.
algorithms for the coalitional manipulation problem. we investigate the problem of coalitional manipulation in elections, which is known to be hard in a variety of voting rules. we put forward efficient algorithms for the problem in scoring rules, maximum and plurality with runoff, and analyze their windows of error. specifically, given an instance on which an algorithm fails, we bound the additional power the manipulators need in order to succeed. we finally discuss the implications of our results with respect to the popular approach of employing computational hardness to preclude manipulation.
approximating general metric distances between a pattern and a text. let t = t0 &hellip; tn-1 be a text and p = p0 &hellip; pm-1 a pattern taken from some finite alphabet set &sigma;, and let d be a metric on &sigma;. we consider the problem of calculating the sum of distances between the symbols of p and the symbols of substrings of t of length m for all possible offsets. we present an &epsilon;-approximation algorithm for this problem which runs in time o(1/&epsilon;2n &middot; polylog(n, |&sigma;|)). this algorithm is based on a low distortion embedding of metric spaces into normed spaces (especially, into &ell;&infin;), which is done as a preprocessing stage. the algorithm is also based on a technique of sampling.
provably good multicore cache performance for divide-and-conquer algorithms. this paper presents a multicore-cache model that reflects the reality that multicore processors have both per-processor private (l1) caches and a large shared (l2) cache on chip. we consider a broad class of parallel divide-and-conquer algorithms and present a new on-line scheduler, controlled-pdf, that is competitive with the standard sequential scheduler in the following sense. given any dynamically unfolding computation dag from this class of algorithms, the cache complexity on the multicore-cache model under our new scheduler is within a constant factor of the sequential cache complexity for both l1 and l2, while the time complexity is within a constant factor of the sequential time complexity divided by the number of processors p. these are the first such asymptotically-optimal results for any multicore model. finally, we show that a separator-based algorithm for sparse-matrix-dense-vector-multiply achieves provably good cache performance in the multicore-cache model, as well as in the well-studied sequential cache-oblivious model.
better bounds for online load balancing on unrelated machines. we study the problem of scheduling permanent jobs on unrelated machines when the objective is to minimize the lp norm of the machine loads. the problem is known as load balancing under the lp norm. we present an improved upper bound for the greedy algorithm through simple analysis; this bound is also shown to be best possible within the class of deterministic online algorithms for the problem. we also address the question whether randomization helps online load balancing under lp norms on unrelated machines; this is a challenging question which is open for more than a decade even for the l2 norm. we provide a positive answer to this question by presenting the first randomized online algorithms which outperform deterministic ones under any (integral) lp norm for p = 2,&hellip;,137. our algorithms essentially compute in an online manner a fractional solution to the problem and use the fractional values to make random choices. the local optimization criterion used at each step is novel and rather counterintuitive: the values of the fractional variables for each job correspond to flows at an approximate wardrop equilibrium for an appropriately defined non-atomic congestion game. as corollaries of our analysis and by exploiting the relation between the lp norm and the makespan of machine loads, we obtain new competitive algorithms for online makespan minimization, making progress in another longstanding open problem.
approximation algorithms for labeling hierarchical taxonomies. we consider the following taxonomy labeling problem. each node of an n-node tree has to be labeled with the values of k attributes. a partial labeling is given as part of the input. the goal is to complete this labeling, minimizing the maximum variation in labeling along an edge. a special case of this problem (which we call the label extension problem), where every node is either completely labeled or not labeled at all, has been considered previously. we present an o(log2 k)-approximation algorithm based on a natural linear programming relaxation. our results reduce the taxonomy labeling problem to another problem we introduce, called the multicut packing problem (on trees): given k multicommodity flow instances, find a multicut for each instance so as to minimize the maximum number of multicuts that use any single edge. our algorithm yields an o(log2 k)-approximation algorithm for this more general problem. we show that the integrality gap of our relaxation is &omega;(logk), even when applied to the taxonomy labeling problem with 0-1 labels. for the label extension problem, we considerably improve the previous o(log n) approximation guarantee and give the first constant-factor approximation algorithm for this problem. our work relies on relating the label extension problem to questions on lipschitz extensions of functions into banach spaces. in particular, our approximation algorithm builds upon matou&scaron;ek's tree metrics extension theorem. our algorithm also works for other metrics on the label-set, such as edit distance with unit-cost operations, and more generally any shortest path metric induced by an unweighted graph.
incentive compatible regression learning. we initiate the study of incentives in a general machine learning framework. we focus on a game-theoretic regression learning setting where private information is elicited from multiple agents with different, possibly conflicting, views on how to label the points of an input space. this conflict potentially gives rise to untruthfulness on the part of the agents. in the restricted but important case when every agent cares about a single point, and under mild assumptions, we show that agents are motivated to tell the truth. in a more general setting, we study the power and limitations of mechanisms without payments. we finally establish that, in the general setting, the vcg mechanism goes a long way in guaranteeing truthfulness and economic efficiency.
clustering for metric and non-metric distance measures. we study a generalization of the k-median problem with respect to an arbitrary dissimilarity measure d. given a finite set p, our goal is to find a set c of size k such that the sum of errors d(p, c) = &sigma;p&isin;p minc&isin;c{d(p, c)} is minimized. the main result in this paper can be stated as follows: there exists an o(n2k/&epsilon;)o(1)) time (1 + &epsilon;)-approximation algorithm for the k-median problem with respect to d, if the 1-median problem can be approximated within a factor of (1 + &epsilon;) by taking a random sample of constant size and solving the 1-median problem on the sample exactly. using this characterization, we obtain the first linear time (1 + &epsilon;)-approximation algorithms for the k-median problem in an arbitrary metric space with bounded doubling dimension, for the kullback-leibler divergence (relative entropy), for mahalanobis distances, and for some special cases of bregman divergences. moreover, we obtain previously known results for the euclidean k-median problem and the euclidean k-means problem in a simplified manner. our results are based on a new analysis of an algorithm from [20].
strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization. bisubmodular functions are a natural "directed", or "signed", extension of submodular functions with several applications. recently fujishige and iwata showed how to extend the iwata, fleischer, and fujishige (iff) algorithm for submodular function minimization (sfm) to bisubmodular function minimization (bsfm). however, they were able to extend only the weakly polynomial version of iff to bsfm. here we investigate the difficulty that prevented them from also extending the strongly polynomial version of iff to bsfm, and we show a way around the difficulty. this new method gives the first combinatorial strongly polynomial algorithm for bsfm. this further leads to extending iwata's fully combinatorial version of iff to bsfm.
approximate shared-memory counting despite a strong adversary. a new randomized asynchronous shared-memory data structure is given for implementing an approximate counter that can be incremented once by each of n processes in a model that allows up to n&minus;1 crash failures. for any fixed &epsis;, the counter achieves a relative error of &delta; with high probability, at the cost of o(((1/&delta;) log n)o(1/&epsis;)) register operations per increment and o(n4/5+&epsis;((1/&delta;) log n)o(1/&epsis;)) register operations per read. the counter combines randomized sampling for estimating large values with an expander for estimating small values. this is the first counter implementation that is sublinear the number of processes and works despite a strong adversary scheduler that can observe internal states of processes. an application of the improved counter is an improved protocol for solving randomized shared-memory consensus, which reduces the best previously known individual work complexity from o(n log n) to an optimal o(n), resolving one of the last remaining open problems concerning consensus in this model.
two-phase greedy algorithms for some classes of combinatorial linear programs. we present greedy algorithms for some classes of combinatorial packing and cover problems within the general formal framework of hoffman and schwartz' lattice polyhedra. our algorithms compute in a first phase monge solutions for the associated dual cover and packing problems and then proceed to construct greedy solutions for the primal problems in a second phase. we show optimality of the algorithms under certain sub- and supermodular assumptions and monotone constraints. for supermodular lattice polyhedra with submodular constraints, our algorithms offer the farthest reaching generalization of edmonds' polymatroid greedy algorithm currently known.
improved string reconstruction over insertion-deletion channels. consider a binary string x of length n transmitted m times over a memoryless channel that randomly inserts, deletes and flips bits. we consider the problem of reconstructing x from the collection of m binary strings received at the output of the channel. we present an algorithm for this problem and show that, as n tends to infinity, for almost all transmitted strings, the algorithm is guaranteed to reconstruct the transmitted string with probability 1 - o(1), if the channel's flip probability p < 1/2, its insertion and deletion probabilities qi,qd = o(1/log n), and m = &theta;(log n). our algorithm improves on [1] which applies to channels that only delete, and on [2] where qi,qd = o(1/(log n)2). we also show that to reconstruct most strings reliably over any channel with a constant flip probability m = &omega;(log n) transmissions are necessary, and therefore our algorithm is efficient in this sense.
a tight lower bound for parity in noisy communication networks. we show a tight lower bound of &omega;(n log log n) on the number of transmission required to compute the parity of n bits (with constant error) in a network of n randomly placed sensors, communicating using local transmissions, and operating with power near the connectivity threshold. this result settles a question left open by ying, srikant and dullerud (wiopt 06), who showed how the sum of all n bits can be computed using o(n log log n) transmissions. earlier works on lower bounds for communication networks worked with the full broadcast model without using the fact that the communication in real networks is local, determined by the power of the transmitters. in fact, in full broadcast networks parity can be computed using o(n) transmissions. to obtain our lower bound we employ techniques developed by goyal, kindler and saks (focs 05), who showed lower bounds in the full broadcast model by reducing the problem to a model of noisy decision trees. however, in order to capture the limited range of transmissions in real sensor networks, we define and work with a localized version of noisy decision trees. our lower bound is obtained by exploiting special properties of parity computations in such decision trees.
weak &epsilon;-nets and interval chains. we construct weak &epsilon;-nets of almost linear size for certain types of point sets. specifically, for planar point sets in convex position we construct weak 1/r-nets of size o(r&alpha;(r)), where &alpha;(r) denotes the inverse ackermann function. for point sets along the moment curve in ℝd we construct weak 1/r-nets of size r &middot; 2poly(&alpha;(r)), where the degree of the polynomial in the exponent depends (quadratically) on d. our constructions result from a reduction to a new problem, which we call stabbing interval chains with j-tuples. given the range of integers n = [1,n], an interval chain of length k is a sequence of k consecutive, disjoint, nonempty intervals contained in n. a j-tuple &pmacr; is said to stab an interval chain c = i1 &hellip; ik if each pi falls on a different interval of c. the problem is to construct a small-size family z of j-tuples that stabs all k-interval chains in n. let zk(j)(n) denote the minimum size of such a family z. we derive almost-tight upper and lower bounds for zk(j)(n) for every fixed j; our bounds involve functions &alpha;m(n) of the inverse ackermann hierarchy. specifically, we show that for j = 3 we have zk(3)(n) = &theta; for all k &ge; 6. for each j &ge; 4 we construct a pair of functions p'j(m), q'j(m), almost equal asymptotically, such that z(j)p'j(m)(n)=o(n&alpha;m(n)) and z(j)q'j(m)(n)=&omega;(n&alpha;m(n)).
computing large matchings fast. in this paper we present algorithms for computing large matchings in 3-regular graphs, graphs with maximum degree 3, and 3-connected planar graphs. the algorithms give a guarantee on the size of the computed matching and take linear or slightly superlinear time. thus they are faster than the best-known algorithm for computing maximum matchings in general graphs, which runs in o(&radic;nm) time, where n denotes the number of vertices and m the number of edges of the given graph. for the classes of 3-regular graphs and graphs with maximum degree 3 the bounds we achieve are known to be best possible. we also investigate graphs with block trees of bounded degree, where the d-block tree is the adjacency graph of the d-connected components of the given graph. in 3-regular graphs and 3-connected planar graphs with bounded-degree 2- and 4-block trees, respectively, we show how to compute maximum matchings in slightly superlinear time.
parallel monotonicity reconstruction. we investigate the problem of monotonicity reconstruction, as defined in [3], in a parallel setting. we have oracle access to a nonnegative real-valued function f defined on domain [n]d = {1,&hellip;,n}d. we would like to closely approximate f by a monotone function g. this should be done by a procedure (a filter) that given as input a point x &isin; [n]d outputs the value of g(x), and runs in time that is highly sublinear in n. the procedure can (indeed must) be randomized, but we require that all of the randomness be specified in advance by a single short random seed. we construct such an implementation where the the time and space per query is (log n)o(1) and the size of the seed is polynomial in log n and d. furthermore the distance of the approximating function g from f is at most a constant multiple of the minimum distance of any monotone function from f. this implementation allows for parallelization: one can initialize many copies of the filter with the same short random seed, and they can autonomously handle queries, while producing outputs that are consistent with the same approximating function g.
fast approximation of the permanent for very dense problems. approximation of the permanent of a matrix with nonnegative entries is a well studied problem. the most successful approach to date for general matrices uses markov chains to approximately sample from a distribution on weighted permutations, and jerrum, sinclair, and vigoda developed such a method they proved runs in polynomial time in the input. the current bound on the running time of their method is o(n7(log n)4). here we present a very different approach using sequential acceptance/rejection, and show that for a class of dense problems this method has an o(n4 log n) expected running time.