waashk/dblp huggingface dataset:
unique normal forms in term rewriting systems with repeated variables a term rewriting system is a finite set of axiom schemata of the form a@@@@b where a and b are terms that contain variables. an important question for such systems is whether normal forms are unique (i.e. each term has at most one normal form). for schemata without repeated variables (i.e. no variable is repeated on the left side of an axiom schema), o'donnell [o'd] has given sufficient conditions for the confluence property (church-rosser property), a stronger property than unique normal forms. klop [klo] has shown that the confluence property does not necessarily hold in these systems when repeated variables are allowed. this paper shows that normal forms are unique in such systems despite the lack of the confluence property.
clifford algebras and approximating the permanent. we study approximation algorithms for the permanent of an n × n (0,1) matrix a based on the following simple idea: obtain a random matrix b by replacing each 1-entry of a independently by ±e, where e is a random basis element of a suitable algebra; then output |det(b)|2. this estimator is always unbiased, but it may have exponentially large variance. in our first main result we show that, if we take the algebra to be a clifford algebra of dimension polynomial in n, then we get an estimator with small variance. hence, only a constant number of trials suffices to estimate the permanent to good accuracy. the idea of using clifford algebras is a natural extension of earlier work by godsil and gutman, karmarkar et al., and barvinok, who used the real numbers, complex numbers and quaternions, respectively. the above result implies that, in principle, this approach gives a fully-polynomial randomized approximation scheme for the permanent, provided |det(b)|2 can be efficiently computed in the clifford algebras. since these algebras are noncommutative it is not clear how to do this. however, our second main result shows how to compute in polynomial time an estimator with the same mean and variance over the 4-dimensional algebra (which is the quaternions, and is non-commutative); in addition to providing some hope that the computations can be performed in higher dimensions, this quaternion algorithm provides an exponential improvement in the variance over that of the 2-dimensional complex version studied by karmarkar et al.
exponential algorithmic speedup by a quantum walk. we construct a black box graph traversal problem that can be solved exponentially faster on a quantum computer than on a classical computer. the quantum algorithm is based on a continuous time quantum walk, and thus employs a different technique from previous quantum algorithms based on quantum fourier transforms. we show how to implement the quantum walk efficiently in our black box setting. we then show how this quantum walk solves our problem by rapidly traversing a graph. finally, we prove that no classical algorithm can solve the problem in subexponential time.
cooperative asynchronous update of shared memory. the write-all problem for an asynchronous shared-memory system has the objective for the processes to update the contents of a set of shared registers, while minimizing the total number of read and write operations. first abstracted by kanellakis and shvartsman [12], write-all is among the standard problems in distributed computing. the model consists of $n$ asynchronous processes and n registers, where every process can read and write to any register. processes may fail by crashing. the most efficient previously known deterministic algorithm performs o(n1+ε) reads and writes, for an arbitrary fixed constant ε>0, and is due to anderson and woll [4]. this paper presents a new deterministic algorithm that performs o(n polylog n) read/write operations, thus improving the best previously known upper bound from polynomial to polylogarithmic in the average number of read/write operations per process. using an approach to store and retrieve information about progress made in auxiliary registers, the novelty of the new algorithm is in using a family of multi-partite graphs with expansion properties to structure a set of registers as a graph and then have each asynchronous process explore a part of the graph according to its pattern of traversals. an explicit instantiation of our write-all algorithm, based on best-known polynomial-time constructions of lossless expanders and a-expanding graphs, performs n • 2o(log3 log n) reads and writes. in this explicit solution to write-all, the processes perform asymptotically less read/write operations than the most efficient non-explicit solution known before.
collective asynchronous reading with polylogarithmic worst-case overhead. the collect problem for an asynchronous shared-memory system has the objective for the processors to learn all values of a collection of shared registers, while minimizing the total number of read and write operations. first abstracted by saks, shavit, and woll [37], collect is among the standard problems in distributed computing, the model consists of $n$ asynchronous processes, each with a single-writer multi-reader register of a polynomial capacity. the best previously known deterministic solution performs o(n3/2log n) reads and writes, and it is due to ajtai, aspnes, dwork, and waarts [3]. this paper presents a new deterministic algorithm that performs o(n log7 n) read/write operations, thus substantially improving the best previous upper bound. using an approach based on epidemic rumor-spreading, the novelty of the new algorithm is in using a family of expander graphs and ensuring that each of the successive groups of processes collect and propagate sufficiently many rumors to the next group. the algorithm is adapted to the repeatable collect problem, which is an on-line version. the competitive latency of the new algorithm is o(log7 n) vs. the much higher competitive latency o(√nlog n) given in [3]. a result of independent interest in this paper abstracts a gossiping game that is played on a graph and that gives its payoff in terms of expansion.
pricing for fairness: distributed resource allocation for multiple objectives. in this paper, we present a simple distributed algorithm for resource allocation which simultaneously approximates the optimum value for a large class of objective functions. in particular, we consider the class of canonical utility functions&#x00a0;u that are symmetric, non-decreasing, concave, and satisfy&#x00a0;u(0) = 0. our distributed algorithm is based on primal-dual updates. we prove that this algorithm is an&#x00a0;o(log&#x2009;&#x03c1;)-approximation for all canonical utility functions simultaneously, i.e. without any knowledge of &#x00a0;u. the algorithm needs at most&#x00a0;o(log&#x2009;2 &#x03c1;) iterations where &#x00a0;&#x03c1; is the biggest one among the number of flows, the number of edges, and the ratio between the maximum capacity and the minimum capacity of the edges in the network. this result is refined for multi-path routing problem, and also extended to a natural pricing mechanism that results in a simple and practical protocol for bandwidth allocation in a network.
efficient fault tolerant algorithms for resource allocation in distributed systems solutions to resource allocation problems in distributed systems are examined with respect to the measures of response time, message complexity, and failure locality. response time measures the time it takes for an algorithm to respond to the requests of a process, message complexity measures the number of messages sent and received by a process, and failure locality characterizes the size of the network that is affected by the failure of a single process. an algorithm that achieves a constant failure locality of four along with a quadratic response time and a quadratic message complexity is presented.
the price of anarchy of finite congestion games. we consider the price of anarchy of pure nash equilibria in congestion games with linear latency functions. for asymmetric games, the price of anarchy of maximum social cost is θ(√n), where n is the number of players. for all other cases of symmetric or asymmetric games and for both maximum and average social cost, the price of anarchy is 5/2. we extend the results to latency functions that are polynomials of bounded degree. we also extend some of the results to mixed nash equilibria.
self-organizing sequential search and hilbert's inequalities in this paper we describe a general technique which can be used to solve an old problem in analyzing self-organizing sequential search. we prove that the average time required for the move-to-front heuristic is no more than &pgr;/2 times that of the optimal order and this bound is best possible. hilbert's inequalities will be used to derive large classes of inequalities some of which can be applied to obtain tight worst-case bounds for several self-organizing heuristics.
asymmetric k-center is log -hard to approximate. in the asymmetric k-center problem, the input is an integer k and a complete digraph over n points together with a distance function obeying the directed triangle inequality. the goal is to choose a set of k points to serve as centers and to assign all the points to the centers, so that the maximum distance of any point to its center is as small as possible. we show that the asymmetric k-center problem is hard to approximate up to a factor of log* n - θ(1) unless np ⊆ dtime(nlog log n). since an o(log* n)-approximation algorithm is known for this problem, this essentially resolves the approximability of this problem. this is the first natural problem whose approximability threshold does not polynomially relate to the known approximation classes. we also resolve the approximability threshold of the metric k-center problem with costs.
hardness of cut problems in directed graphs. we study the approximability of the multicut and the (non-bipartite) sparsest cut problems in directed graphs. in the multicut problem, we are a given a graph g along with k source-sink pairs, and the goal is to find a smallest subset of edges whose deletion separates all source-sink pairs. the sparsest cut problem has the same input, but the goal is to find a subset of edges to delete so as to minimize the ratio of deleted edges to the number of source-sink pairs that are separated by this deletion. study of algorithms for cut problems is intimately connected to the dual notion of flows in networks, and many approximation algorithms for cut problems use a flow solution as a starting point. the best known approximation algorithm for directed multicut is based on this approach and gives an o(√n)-approximation. on the other hand, the gap between the maximum multicommodity flow and the minimum multicut is known to be ω(min(k , log n)). while this flow-cut gap may be interpreted as an evidence of inherent difficulty in designing good approximation algorithms for directed multicut, the strongest hardness result known is an apx-hardness. even assuming the unique games conjecture, only an ω(1)-hardness is known. similar bounds hold for the directed sparsest cut problem.our main result is that directed multicut is ω(log n / log log n)-hard to approximate unless np ⊆ dtime (npolylog n). we show that this hardness result holds even when we allow a bicriteria relaxation, where the approximate solution is required to separate only a constant fraction of the pairs. this bicriteria hardness allows us to infer an ω(log n / log log n)-hardness for the directed (non-bipartite) sparsest cut problem.
new hardness results for congestion minimization and machine scheduling. we study the approximability of two natural np-hard problems. the first problem is congestion minimization in directed networks. we are given a directed capacitated graph and a set of source-sink pairs. the goal is to route all pairs with minimum congestion on the network edges. a special well-studied case of this problem is the edge-disjoint paths problem, where all edges have unit capacities. the second problem is discrete machine scheduling, where we are given a set of jobs, and for each job a list of intervals in which it can be scheduled. the goal is to find the smallest number of machines on which all jobs can be scheduled, such that no two jobs assigned to the same machine overlap. both problems are known to be o(log n/log log n)-approximable via the randomized rounding technique of raghavan and thompson. however, until recently, only a max snp hardness was known for each problem. we make some progress in closing this gap by showing that both problem are ω(log log n)-hard to approximate unless np ⊆ dtime(no(log log log n)). our hardness proof for congestion minimization holds even for the special case of the edge-disjoint paths problem.
a new strategy for querying priced information. this paper focuses on competitive function evaluation in the context of computing with priced information. a function f is given together with a cost cx for each variable x of f. the cost cx has to be paid to read the value of x. the problem is to design algorithms that query the values of the variables sequentially in order to compute the function while trying to minimize the total cost incurred. competitive analysis is employed to evaluate the performance of the algorithms. we describe a novel approach for devising efficient algorithms in this setting. we apply our approach to several classes of functions which have been studied in the literature of computing with priced information. in all cases considered, our approach provides algorithms that achieve better bounds than the best known algorithm for the same class of functions.more precisely, for the class of monotone boolean functions, we give a polynomial time algorithm with extremal competitiveness (k+l - √ min(k,l)) where k (l) denotes the minimum number of variables that one must read, in the worst case, in order to prove that the function under consideration evaluates to 1 (0). this dramatically improves upon the best known result which is an exponential time 2 max(k, l)-competitive algorithm. for the subclass of monotone boolean functions known as threshold trees we further improve our bounds and give a polynomial time algorithm with extremal competitive ratio 1.618 max(k, l).we then apply our methodology to classes of non-boolean functions. we consider the case of the so called game trees. we improve upon previously published results for this class of functions providing a polynomial time algorithm with extremal competitive ratio 1.5 γ(f), where γ(f) is a lower bound on the extremal competitive ratio of any deterministic algorithm.finally, we consider the case when f is the function min (minimum). in this case, we are able to determine the optimal competitiveness for the problem. in fact we provide an algorithm with an (n-2)-competitive ratio, which matches the known lower bound.
a probabilistic algorithm for the post office problem the post office problem is the following: points in d-dimensional space, so that given an arbitrary point p, the closest points in s to p can be found quickly. we consider the case of this problem where the euclidean norm is the measure of distance. the previous best algorithm for this problem for d>2 requires &ogr;(n2d+1) preprocessing time to build a data structure allowing an &ogr;(log n query time. we will show that a data structure can be built in expected &ogr;(n(d-1)(1+k)) time, for any fixed k;>&ogr;, so that closest-point queries can be answered in &ogr;(log n) worstcase time. (the constant factors depend on d and k.) the algorithm employs random sampling, so the expected time holds for any set of points. a variant of this algorithm (for the variant problem where only one closest point of s to the query point is desired) requires &ogr;(n&lceil;d/2&rceil;) &ogr;(n&lceil;d/2&rceil;) preprocessing time for &ogr;(nt) worst-case query time, for any fixed &egr;>0. these results approach the &ohgr;(n&lceil;d/2&rceil;) preprocessing time required for any algorithm constructing the voronoi diagram of the input points. implementation of these algorithms requires not too much more than a random sampling procedure and a procedure for constructing the voronoi diagram of that random sample.
market equilibrium via the excess demand function. we consider the problem of computing market equilibria and show three results. (i) for exchange economies satisfying weak gross substitutability we analyze a simple discrete version of tâtonnement, and prove that it converges to an approximate equilibrium in polynomial time. this is the first polynomial-time approximation scheme based on a simple atonnement process. it was only recently shown, using vastly more sophisticated techniques, that an approximate equilibrium for this class of economies is computable in polynomial time. (ii) for fisher's model, we extend the frontier of tractability by developing a polynomial-time algorithm that applies well beyond the homothetic case and the gross substitutes case. (iii) for production economies, we obtain the first polynomial-time algorithms for computing an approximate equilibrium when the consumers' side of the economy satisfies weak gross substitutability and the producers' side is restricted to positive production.
polylog-time and near-linear work approximation scheme for undirected shortest paths. shortest paths computations constitute one of the most fundamental network problems. nonetheless, known parallel shortest-paths algorithms are generally inefficient: they perform significantly more work (product of time and processors) than their sequential counterparts. this gap, known in the literature as the &ldquo;transitive closure bottleneck,&rdquo; poses a long-standing open problem. our main result is an omne0+s m+n1+e0 work polylog-time randomized algorithm that computes paths within (1 + o(1/polylog n) of shortest from s source nodes to all other nodes in weighted undirected networks with n nodes and m edges (for any fixed &egr;0>0). this work bound nearly matches the o&d5;sm sequential time. in contrast, previous polylog-time algorithms required nearly mino&d5; n3,o&d5; m2 work (even when s=1), and previous near-linear work algorithms required near-o(n) time. we also present faster sequential algorithms that provide good approximate distances only between &ldquo;distant&rdquo; vertices: we obtain an om+snne 0 time algorithm that computes paths of weight (1+o(1/polylog n) dist + o(wmax polylog n), where dist is the corresponding distance and wmax is the maximum edge weight. our chief instrument, which is of independent interest, are efficient constructions of sparse hop sets. a (d,&egr;)-hop set of a network g=(v,e) is a set e* of new weighted edges such that mimimum-weight d-edge paths in v,e&cup;e* have weight within (1+&egr;) of the respective distances in g. we construct hop sets of size on1+e0 where &egr;=o(1/polylog n) and d=o(polylog n).
pushdown store machines and real-time computation a comparison is made of the computing capabilities of pushdown store machines and real-time iterative arrays of finite-state machines with the following results. every pushdown store computation can be performed by some iterative array in real time. the latter are strictly more powerful, since they can recognize the set of palindromes in real time, which is impossible for pushdown-store machines even without a real-time constraint. versions of pushdown store machines, the tabulator machines and the n-dimensional pushdown store machines, are introduced during the development. by imposing a real-time constraint and letting the number of tabs and the number of dimensions vary, these form infinite hierarchies whose unions are equivalent to the pushdown store machine.
pricing network edges for heterogeneous selfish users. we study the negative consequences of selfish behavior in a congested network and economic means of influencing such behavior. we consider a model of selfish routing in which the latency experienced by network traffic on an edge of the network is a function of the edge congestion, and network users are assumed to selfishly route traffic on minimum-latency paths. the quality of a routing of traffic is measured by the sum of travel times (the total latency).it is well known that the outcome of selfish routing (a nash equilibrium) does not minimize the total latency. an ancient strategy for improving the selfish solution is the principle of marginal cost pricing, which asserts that on each edge of the network, each network user on the edge should pay a tax offsetting the congestion effects caused by its presence. by pricing network edges according to this principle, the inefficiency of selfish routing can always be eradicated.this result, while fundamental, assumes a very strong homogeneity property: all network users are assumed to trade off time and money in an identical way. the guarantee also ignores both the algorithmic aspects of edge pricing and the unfortunate possibility that an efficient routing of traffic might only be achieved with exorbitant taxes. motivated by these shortcomings, we extend this classical work on edge pricing in several different directions and prove the following results.we prove that the edges of a single-commodity network can always be priced so that an optimal routing of traffic arises as a nash equilibrium, even for very general heterogeneous populations of network users.when there are only finitely many different types of network users and all edge latency functions are convex, we show how to compute such edge prices efficiently.we prove that an easy-to-check mathematical condition on the population of heterogeneous network users is both necessary and sufficient for the existence of edge prices that induce an optimal routing while requiring only moderate taxes.
searching dynamic point sets in spaces with bounded doubling dimension. we present a new data structure that facilitates approximate nearest neighbor searches on a dynamic set of points in a metric space that has a bounded doubling dimension. our data structure has linear size and supports insertions and deletions in o(log n) time, and finds a (1+ε)-approximate nearest neighbor in time o(log n) + (1/ε)o(1). the search and update times hide multiplicative factors that depend on the doubling dimension; the space does not. these performance times are independent of the aspect ratio (or spread) of the points.
dictionary matching and indexing with errors and don't cares. this paper considers various flavors of the following online problem: preprocess a text or collection of strings, so that given a query string p, all matches of p with the text can be reported quickly. in this paper we consider matches in which a bounded number of mismatches are allowed, or in which a bounded number of "don't care" characters are allowed. the specific problems we look at are: indexing, in which there is a single text t, and we seek locations where p matches a substring of t; dictionary queries, in which a collection of strings is given upfront, and we seek those strings which match p in their entirety; and dictionary matching, in which a collection of strings is given upfront, and we seek those substrings of a (long) p which match an original string in its entirety. these are all instances of an all-to-all matching problem, for which we provide a single solution.the performance bounds all have a similar character. for example, for the indexing problem with n=|t| and m=|p|, the query time for k substitutions is o(m + (c1 log n)k⁄k! + # matches), with a data structure of size o(n (c2 log n)k⁄k!) and a preprocessing time of o(n (c2 log n)k⁄k!), where c1,c2 > 1 are constants. the deterministic preprocessing assumes a weakly nonuniform ram model; this assumption is not needed if randomization is used in the preprocessing.