waashk/dblp huggingface dataset:
optimal tree layout (preliminary version) we consider the problem of finding a minimal cost layout of a tree in euclidian d-space. a tree is an acyclic undirected edge-weighted graph, and a layout is an assignment of a point in d-dimensional euclidian space to each of the nodes of the tree. the &ldquo;length&rdquo; of an edge in the layout is the &ldquo;distance&rdquo; between its endpoints as measured by some norm. the cost of an edge is its length times its weight, and the cost of the whole layout is the sum of the costs of all the edges. we assume the positions of certain nodes are fixed in advance, and we wish to place the remaining nodes so as to minimize the cost of the layout.
fast convergence to wardrop equilibria by adaptive sampling methods. we study rerouting policies in a dynamic round-based variant of a well known game theoretic traffic model due to wardrop. previous analyses (mostly in the context of selfish routing) based on wardrop's model focus mostly on the static analysis of equilibria. in this paper, we ask the question whether the population of agents responsible for routing the traffic can jointly compute or better learn a wardrop equilibrium efficiently. the rerouting policies that we study are of the following kind. in each round, each agent samples an alternative routing path and compares the latency on this path with its current latency. if the agent observes that it can improve its latency then it switches with some probability depending on the possible improvement to the better path.we can show various positive results based on a rerouting policy using an adaptive sampling rule that implicitly amplifies paths that carry a large amount of traffic in the wardrop equilibrium. for general asymmetric games, we show that a simple replication protocol in which agents adopt strategies of more successful agents reaches a certain kind of bicriteria equilibrium within a time bound that is independent of the size and the structure of the network but only depends on a parameter of the latency functions, that we call the relative slope. for symmetric games, this result has an intuitive interpretation: replication approximately satisfies almost everyone very quickly.in order to achieve convergence to a wardrop equilibrium besides replication one also needs an exploration component discovering possibly unused strategies. we present a sampling based replication-exploration protocol and analyze its convergence time for symmetric games. for example, if the latency functions are defined by positive polynomials in coefficient representation, the convergence time is polynomial in the representation length of the latency functions. to the best of our knowledge, all previous results on the speed of convergence towards wardrop equilibria, even when restricted to linear latency functions, were pseudopolynomial.in addition to the upper bounds on the speed of convergence, we can also present a lower bound demonstrating the necessity of adaptive sampling by showing that static sampling methods result in a slowdown that is exponential in the size of the network. a further lower bound illustrates that the relative slope is, in fact, the relevant parameter that determines the speed of convergence.
fast on-line integer multiplication a turing machine multiplies on-line if it receives its inputs low order digits first and it produces the k-th output digit before reading in the (k+1)-st inputs. we present a general method for converting any off-line multiplication algorithm which forms the product of two n-bit binary numbers in time f(n) into an on-line method, and the new algorithm requires time only 0(f(n) log n). applying this technique to the fast multiplication algorithm of sch&ouml;nhage and strassen gives an upper bound of 0(n (log n)2 log log n) for on-line multiplication of integers. other applications are to the on-line problems of products of polynomials over a finite ring, recognition of palindromes, and multiplication by a constant.
computing integrated costs of sequences of operations with application to dictionaries we introduce a notion of integrated cost of a dictionary, as average cost of sequences of search, insert and delete operations. we express generating functions of these sequences in terms of continued fractions; from this we derive an explicit integral expression of integrated costs for three common representations of dictionaries.
on the average case performance of some greedy approximation algorithms for the uncapacitated facility location problem. in combinatorial optimization, a popular approach tonp-hard problems is the design of approximation algorithms. these algorithms typically run in polynomial time and are guaranteed to produce a solution which is within a known multiplicative factor of optimal. unfortunately, the known factor is often known to be large in pathological instances. conventional wisdom holds that, in practice, approximation algorithms will produce solutions closer to optimal than their proven guarantees. in this paper, we use the rigorous-analysis-of-heuristics framework to investigate this conventional wisdom.we analyze the performance of 3 related approximation algorithms for the uncapacitated facility location problem (from [jain, mahdian, markakis, saberi, vazirani, 2003] and [mahdian, ye, zhang, 2002]) when each is applied to an instances created by placing n points uniformly at random in the unit square. we find that, with high probability, these 3 algorithms do not find asymptotically optimal solutions, and, also with high probability, a simple plane partitioning heuristic does find an asymptotically optimal solution.
simple cost sharing schemes for multicommodity rent-or-buy and stochastic steiner tree. in the multi-commodity rent-or-buy network design problem (mrob) we are given a network together with a set of k terminal pairs r = (s_1, t_1), ..., (s_k, t_k). the goal is to install capacities on the edges of the network so that a prescribed amount of flow fi can be routed between all terminal pairs si and ti simultaneously. we can either rent capacity on an edge at some cost per unit flow or buy infinite capacity on an edge at some larger fixed cost. the overall objective is to install capacities at a minimum total cost.the version of the stochastic steiner tree problem (sst) considered here is the steiner tree problem in the model of two-stage stochastic optimization with recourse. in stage one, there is a known probability distribution on subsets of vertices and we can choose to buy a subset of edges at a given cost. in stage two, a subset of vertices t from the prior known distribution is realized, and additional edges can be bought at a possibly higher cost. the objective is to buy a set of edges in stages one and two so that all vertices in t are connected, and the expected cost is minimized.gupta et al. (focs '03) give a randomized scheme for the mrob problem that was both used subsequently to improve the approximation ratio for this problem, and extended to yield the best approximation algorithm for sst. one building block of this scheme is a good approximation algorithm for steiner forests.we present a surprisingly simple 5-approximation algorithm for mrob and 6-approximation for sst, improving on the best previous guarantees of 6.828 and 12.6, and show that no approximation ratio better than 4.67 can be achieved using the above mentioned randomized scheme in combination with the currently best known steiner forest approximation algorithms. a key component of our approach are cost shares that are 3-strict for the unmodified primal-dual steiner forest algorithm.
finding the depth of a flow graph the depth of a flow graph is the maximum number of back edges in a cycle free path, where a back edge is defined by some depth-first spanning tree for the flow graph. in the case of a reducible graph, the depth is independent of the dfst chosen. we show that the computation of the depth of a reducible flow graph may be done in polynomial time. our algorithm is 0(ne) on a flow graph of n nodes and e edges. since e&le;2n for normal flow graphs, our algorithm is really 0(n2). while even an 0(n2) algorithm is not likely to be acceptable, it is suggestive of the possibility of a more efficient algorithm. finally, we show that the general problem of computing the depth of an arbitrary flow graph with respect to an arbitrary dfst is np-complete.
beyond np: the work and legacy of larry stockmeyer. shortly after steve cook and richard karp showed the ex-istence of many natural np-complete languages, researchers started to realize the great importance of the p versus np problem and the difficulty of settling it. one graduate student at the massachusetts institute of technology started to look beyond np, asking what problems have a higher complexity and how do we classify them. larry stockmeyer discovered an amazing structure of complexity classes that continues to direct the research in complexity to this day. stockmeyer passed away on july 31, 2004 at the age of 55 and in this paper we review some of his research and the legacy he has left on the community.
probabilistic computation and linear time in this paper, we give an oracle under which bpp is equal to probabilistic linear time, an unusual collapse of a complexity time hierarchy. in addition, we also give oracles where &dgr;p2 is contained in probabilistic linear time and where bpp has linear sized circuits, as well as oracles for the negation of these questions. this indicates that these questions will not be solved by techniques that relativize. finally, we note that probabilistic linear time can not contain both np and bpp, implying that there are languages solvable by interactive proof systems that can not be solved in probabilistic linear time.
hierarchies for semantic classes. we show that for any constant a, zpp/b(n) strictly contains zptime(na)/b(n) for some b(n) = o(log n log log n). our techniques are very general and give the same hierarchy for all common semantic time classes including rtime, ntime ∩ contime, utime, matime, amtime and bqtime.we show a stronger hierarchy for rtime: for every constant c, rp/1 is not contained in rtime(nc)/(log n)1/2c. to prove this result we first prove a similar statement for np by building on zák's proof of the nondeterministic time hierarchy.
parallelism in random access machines a model of computation based on random access machines operating in parallel and sharing a common memory is presented. the computational power of this model is related to that of traditional models. in particular, deterministic parallel ram's can accept in polynomial time exactly the sets accepted by polynomial tape bounded turing machines; nondeterministic ram's can accept in polynomial time exactly the sets accepted by nondeterministic exponential time bounded turing machines. similar results hold for other classes. the effect of limiting the size of the common memory is also considered.
coresets in dynamic geometric data streams. a dynamic geometric data stream consists of a sequence of m insert/delete operations of points from the discrete space 1,…,δd [26]. we develop streaming (1 + ε)-approximation algorithms for k-median, k-means, maxcut, maximum weighted matching (maxwm), maximum travelling salesperson (maxtsp), maximum spanning tree (maxst), and average distance over dynamic geometric data streams. our algorithms maintain a small weighted set of points(a coreset) that approximates with probability 2/3 the current point set with respect to the considered problem during the m insert/delete operations of the data stream. they use poly (ε-1, log m, log δ) space and update time per insert/delete operation for constant k and dimension dhaving a coreset one only needs a fast approximation algorithm for the weighted problem to compute a solution quickly. in fact, even an exponential algorithm is sometimes feasible as its running time may still be polynomial in n. for example one can compute in poly(log n, exp(o((1+log (1⁄ε)⁄ε)d-1))) time a solution to k-median and k-means [21] where n is the size of the current point set and k and d are constants. finding an implicit solution to maxcut can be done in poly(log n, exp((1⁄ε)o(1))) time. for maxst and average distance we require poly(log n, ε-1) time and for maxwm we require o(n3) time to do this.
communication complexity of secure computation (extended abstract) a secret-ballot vote for a single proposition is an example of a secure distributed computation. the goal is for m participants to jointly compute the output of some n-ary function (in this case, the sum of the votes), while protecting their individual inputs against some form of misbehavior. in this paper, we initiate the investigation of the communication complexity of unconditionally secure multi-party computation, and its relation with various fault-tolerance models. we present upper and lower bounds on communication, as well as tradeoffs among resources. first, we consider the &ldquo;direct sum problem&rdquo; for communications complexity of perfectly secure protocols: can the communication complexity of securely computing a single function f : fn &rarr; f at k sets of inputs be smaller if all are computed simultaneously than if each is computed individually? we show that the answer depends on the failure model. a factor of o(n/log n) can be gained in the privacy model (where processors are curious but correct); specifically, when f is n-ary addition (mod 2), we show a lower bound of &ohgr;(n2 log n) for computing f o(n) times simultaneously. no gain is possible in a slightly stronger fault model (fail-stop mode); specifically, when f is n-ary addition over gf(q), we show an exact bound of &thgr;(kn2 log q) for computing f at k sets of inputs simultaneously (for any k &ge; 1). however, if one is willing to pay an additive cost in fault tolerance (from t to t-k+1), then a variety of known non-cryptographic protocols (including &ldquo;provably unparallelizable&rdquo; protocols from above!) can be systematically compiled to compute one function at k sets of inputs with no increase in communication complexity. our compilation technique is based on a new compression idea of polynomial-based multi-secret sharing. lastly, we show how to compile private protocols into error-detecting protocols at a big savings of a factor of o(n3) (up to a log factor) over the best known error-correcting protocols. this is a new notion of fault-tolerant protocols, and is especially useful when malicious behavior is infrequent, since error-detection implies error-correction in this case.
an algorithm for constructing regions with rectangles: independence and minimum generating sets for collections of intervals we provide an algorithm which solves the following problem: given a polygon with edges parallel to the x and y axes, which is convex in the y direction, find a minimum size collection of rectangles, which cover the polygon and are contained within it. the algorithm is quadratic in the number of vertices of the polygon. our method also yields a new proof of a recent duality theorem equating minimum size rectangle covers to maximum size sets of independent points in the polygon.
small sets supporting fáry embeddings of planar graphs answering a question of rosenstiehl and tarjan, we show that every plane graph with n vertices has a f&aacute;ry embedding (i.e., straight-line embedding) on the 2n - 4 by n - 2 grid and provide an &ogr;(n) space, &ogr;(n log n) time algorithm to effect this embedding. the grid size is asymptotically optimal and it had been previously unknown whether one can always find a polynomial sized grid to support such an embedding. on the other hand we show that any set f, which can support a f&aacute;ry embedding of every planar graph of size n, has cardinality at least n + (1 - &ogr;(1)) &radic;n which settles a problem of mohar.
generalized selection and ranking (preliminary version) selection in a set requires time linear in the size of the set when there are no a priori constraints on the total orders possible for the set. constraints often come for free, however, with sets which arise in applications. linear time selection [bl] can be suboptimal for such problems. we therefore generalize the well known selection problem to admit constraints on the input sets, with a view toward settling the complexity issues which arise. the generalization also applies to the other quantile problems of ranking a given element in the input set and verification of the claim that a given element has a specified rank.
the impact of synchronous communication on the problem of electing a leader in a ring we consider the problem of electing a leader in a synchronous ring of n processors. we obtain both positive and negative results. on the one hand, we show that if processor id's are chosen from some countable set, then there is an algorithm which uses only o(n) messages in the worst case. on the other hand, we obtain two lower bound results: if the algorithm is restricted to use only comparisons of id's, then we obtain an &ohgr;(n log n) lower bound for the number of messages required in the worst case. alternatively, there is a (very fast-growing) function f with the following property. if the number of rounds is required to be bounded by some t in the worst case, and id's are chosen from any set having at least f(n,t) elements, then any algorithm requires &ohgr; (n log n) messages in the worst case.
two applications of a probabilistic search technique: sorting x + y and building balanced search trees let x &equil; {x1,...,xn} and y &equil; {y1,...,yn} be sets of n real numbers. we denote by x + y the multiset {xi + yj; 1 &le; i, j &le; n} of size n2. berklekamp has posed the problem of sorting x + y. harper, payne, savage and strauss [1] show that n21og2n comparisons suffice to sort x + y, thereby saving a factor of 2 over sorting without exploiting the structure of x + y. (given u in x + y, we assume that we know the i,j indices such that u &equil; xi + yj.) furthermore, they show that this bound is tight for a restricted class of comparison algorithms. however, without their restriction the order of magnitude comparison complexity of this problem has remained an open question. in this paper we show that x + y can be sorted with o(n2) comparisons. our proof is unusual for this type of problem in that we do not explicitly exhibit an algorithm. instead, it is a particular application of a more general search technique whose behavior is easily related to information theoretic lower bounds. in the context of sorting, this search method translates into an insertion sort, where the insertions are not performed by means of the usual binary search, but rather as off-centered searches designed so that each comparison, roughly speaking, equally divides the space of remaining possibilities. we draw attention to this search technique because it might find application to other problems, and we illustrate this possibility with a second application. our second application concerns the construction of probabilistically balanced binary search trees.
a near optimal data structure for a type of range query problem let g denote the set of elements of a commutative group whose addition operations is denoted by +, let n be a positive integer, and let a(1) ,..., a(n) denote an array with values in g. we will be concerned with designing data structures for representing the array a, which facilitate efficient implementation of the following two on-line tasks: (1) update(j,x); replace a(j) by a(j) +x. (j and x are inputs, 1&le;j&le;n and x&egr;g) (2) retrieve(j); returns the value of a(1) +...+ a(j). (j is an input, 1&le;j&le;n) as a motivating example, let g be the group of integers with + denoting the usual addition operation. imagine a standardized examination given to large numbers of individuals over an indefinite period of time. assume that each examinee will attain an integer score in the interval [1,n]. if an individual gets j points, this fact is recorded by executing update(j,1). so that a(j) represents the number of individuals to date having scored j points. in order to compute the percentile currently associated with a particular score k, we need the cumulative sum provided by executing retrieve(k).
hidden translation and orbit coset in quantum computing. we give efficient quantum algorithms for the problems of hidden translation and hidden subgroup in a large class of non-abelian groups including solvable groups of constant exponent and of constant length derived series. our algorithms are recursive. for the base case, we solve efficiently hidden translation in z pn, whenever p is a fixed prime. for the induction step, we introduce the problem orbit coset generalizing both hidden translation and hidden subgroup, and prove a powerful self-reducibility result: orbit coset in a finite group g is reducible to orbit coset in g/n and subgroups of n, for any solvable normal subgroup n of g.
efficient testing of groups. we construct an efficient probabilistic algorithm that, given a finite set with a binary operation, tests if it is an abelian group. the distance used is an analogue of the edit distance for strings. the query complexity of the tester is polylogarithmic in the size of the set. previous testers used hamming type distances and had superlinear query complexity. a building block for our construction is a constant query complexity homomorphism tester for functions mapping an given finite group into an arbitrary set equipped with a binary operation.
a proof of alon's second eigenvalue conjecture. a d-regular graph has largest or first (adjacency matrix) eigenvalue λ1 = d. in this paper we show the following conjecture of alon. fix an integer d > 2 and a real ε > 0. then for sufficiently large n we have that "most" d-regular graphs on n vertices have all their eigenvalues except λ1 = d bounded above by 2√d-1 + ε. our methods, being trace methods, also bound those eigenvalues below by -2√d-1 - ε.
the tight deterministic time hierarchy let k be a constant -&-ge; 2, and let us consider only deterministic k-tape turing machines. we assume t2(n) -&-gt; n and t2 is computable in time t2. then there is a language which is accepted in time t2, but not accepted in any time t1 with t1(n) -&-equil; o(t2(n)). furthermore, we obtain a strong hierarchy (isomorphic to the rationals q) for languages accepted in fixed space and variable time.
normal forms for trivalent graphs and graphs of bounded valence a function f is defined, mapping graphs with n vertices onto graphs with vertex set {1,...,n} . f(x) is isomorphic to x and x is isomorphic to y iff f(x) &equil; f(y). for each d, the restriction of f to graphs of valence d is computable in time o(n&tgr;(d)) for a suitable integer &tgr;(d). for d > 3, the proof uses a recent result of l. babai, p.j. cameron and p.p. p&aacute;lfy on the order of primitive groups with bounded composition factors; for the trivalent case a more elementary proof is presented.
finding paths and cycles of superpolylogarithmic length. let $\ell$ be the number of edges in a longest cycle containing a given vertex $v$ in an undirected graph. we show how to find a cycle through $v$ of length $\exp(\omega(\sqrt {\log \ell/\log\log \ell}))$ in polynomial time. this implies the same bound for the longest cycle, longest $vw$-path, and longest path. the previous best bound for longest path is length $\omega( (\log \ell )^2/\, \log\log \ell)$ due to bjo&uml;rklund and husfeldt. our approach, which builds on bjo&uml;rklund and husfeldt&rsquo;s, uses cycles to enlarge cycles. this self-reducibility allows the approximation method to be iterated.
an efficient reduction technique for degree-constrained subgraph and bidirected network flow problems efficient algorithms are given for the bidirected network flow problem and the degree-constrained subgraph problem. four versions of each are solved, depending on whether edge capacities/multiplicities are one or arbitrary, and whether maximum value/maximum cardinality or minimum cost/maximum weight is the objective. a version of the shortest path problem is also efficiently solved. the algorithms use a reduction technique that solves one problem instance by reducing to a number of problems.