waashk/dblp huggingface dataset:
the effect of updates in binary search trees if a binary search tree is created by inserting n keys in random order using the usual insertion algorithm, then it is well known that the average search path is about 1.4lgn. however, if deletions, using the frequently recommended hibbard's algorithm, are interspersed with the insertions, then virtually nothing has been proven except for knuth and jonassen's very difficult, but complete, analysis of the case n = 3. in this paper it is shown that after a sufficient number of updates the average search path is &thgr;(n1/2). an improved algorithm given by knuth is shown to have the same asymptotic behavior.
the omega-sequence equivalence problem for dol systems is decidable the following problem is shown to be decidable. given are homomorphisms h1 and h2 from &sgr;* to &sgr;* and strings &sgr;1 and &sgr;2 over &sgr; such that hni(&sgr;i) is a proper prefix of hn+1i (&sgr;i) for i &equil; 1, 2 and all n &ge; 0, i.e. for i &equil; 1, 2, hi generates from &sgr;i an infinite string &agr;i with prefixes hni(&sgr;i) for all n &ge; 0. test whether &agr;1 &equil; &agr;2. from this result easily follows the decidability of limit language equivalence (&ohgr;-equivalence) for dol systems.
average case selection it is shown that n + k - o(1) comparisons are necessary, on average, to find the kth smallest of n numbers (k &lne; n/2). this lower bound matches the behavior of the technique of floyd and rivest to within a lower-order term. 7n/4 &plusmn; o(n) comparisons, on average, are shown to be necessary and sufficient to find the maximum and median of a set. an upper bound of 9n/4 &plusmn; o(n) and a lower bound of 2n - o(n) are shown for the max-min-median problem.
an approach to the k paths problem the k paths problem asks whether it is possible to find k edge-disjoint paths joining k given pairs of vertices in a graph. we show that this problem can be solved in polynomial time for k&le;5 if the input graph is k+2 -connected. it follows from this result that under the same restriction, the subgraph homeomorphism problem is polynomial for any pattern graph with five or fewer edges.
selfish traffic allocation for server farms. we investigate the price of selfish routing in non-cooperative networks in terms of the coordination and bicriteria ratios in the recently introduced game theoretic network model of koutsoupias and papadimitriou. we present the first thorough study of this model for general, monotone families of cost functions and for cost functionsm from queueing theory. our main results can be summarized as follows.we give a precise characterization of cost functions having a bounded/unbounded coordination ratio. for example, cost functions that describe the expected delay in queueing systems have an unbounded coordination ratio.we show that an unbounded coordination ratio implies additionally an extremely high performance degradation under bicriteria measures. we demonstrate that the price of selfish routing can be as high as a bandwidth degradation by a factor that is linear in the network size.we separate the game theoretic (integral) allocation model from the (fractional) flow model by demonstrating that even a very small, in fact negligible, amount of integrality can lead to a dramatic performance degradation.we unify recent results on selfish routing under different objectives by showing that an unbounded coordination ratio under the min-max objective implies an unbounded coordination ratio under the average-cost (or total-latency) objective and vice versa..our special focus lies on cost functions describing the behavior of web servers that can open only a limited number of tcp connections. in particular, we compare the performance of queueing systems that serve all incoming requests with servers that reject requests in case of overload.from the result presented in this paper we conclude that queuing systems without rejection cannot give any reasonable guarantee on the expected delay of requests under selfish routing even when the injected load is far away from the capacity of the system. in contrast, web server farms that are allowed to reject requests can guarantee a high quality of service for every individual request stream even under relatively high injection rates.
estimating the weight of metric minimum spanning trees in sublinear-time. in this paper we present a sublinear-time $(1+\varepsilon)$-approximation randomized algorithm to estimate the weight of the minimum spanning tree of an $n$-point metric space. the running time of the algorithm is $\widetilde{\mathcal{o}}(n/\varepsilon^{\mathcal{o}(1)})$. since the full description of an $n$-point metric space is of size $\theta(n^2)$, the complexity of our algorithm is sublinear with respect to the input size. our algorithm is almost optimal as it is not possible to approximate in $o(n)$ time the weight of the minimum spanning tree to within any factor. we also show that no deterministic algorithm can achieve a $b$-approximation in $o(n^2/b^3)$ time. furthermore, it has been previously shown that no $o(n^2)$ algorithm exists that returns a spanning tree whose weight is within a constant times the optimum.
the complexity of multiway cuts (extended abstract) in the multiway cut problem we are given an edge-weighted graph and a subset of the vertices called terminals, and asked for a minimum weight set of edges that separates each terminal from all the others. when the number k of terminals is two, this is simply the min-cut, max-flow problem, and can be solved in polynomial time. we show that the problem becomes np-hard as soon as k = 3, but can be solved in polynomial time for planar graphs for any fixed k. the planar problem is np-hard, however, if k is not fixed. we also describe a simple approximation algorithm for arbitrary graphs that is guaranteed to come within a factor of 2&ndash;2/k of the optimal cut weight.
self-testing of universal and fault-tolerant sets of quantum gates. we consider the design of self-testers for quantum gates. a self-tester for the gates $\boldsymbol{f}_1,\ldots, \boldsymbol{f}_m$ is a procedure that, given any gates $\boldsymbol{g}_1, \ldots, \boldsymbol{g}_m$, decides with high probability if each $\boldsymbol{g}_i$ is close to $\boldsymbol{f}_i$. this decision has to rely only on measuring in the computational basis the effect of iterating the gates on the classical states. it turns out that, instead of individual gates, we can design only procedures for families of gates. to achieve our goal we borrow some elegant ideas of the theory of program testing: we characterize the gate families by specific properties, develop a theory of robustness for them, and show that they lead to self-testers. in particular we prove that the universal and fault-tolerant set of gates consisting of a hadamard gate, a $\mathrm{c\text{-}not}$ gate, and a phase rotation gate of angle $\pi/4$ is self-testable.
adaptive versus nonadaptive attribute-efficient learning. we study the complexity of learning arbitrary boolean functions of n variables by membership queries, if at most r variables are relevant. problems of this type have important applications in fault searching, e.g. logical circuit testing and generalized group testing. previous literature concentrates on special classes of such boolean functions and considers only adaptive strategies. first we give a straightforward adaptive algorithm using o(r2r log n) queries, but actually, most queries are asked nonadaptively. this leads to the problem of purely nonadaptive learning. we give a graph-theoretic characterization of nonadaptive learning families, called r-wise bipartite connected families. by the probabilistic method we show the existence of such families of size o(r2r log n + r22r). this implies that nonadaptive attribute-efficient learning is not essentially more expensive than adaptive learning. we also sketch an explicit pseudopolynomial construction, though with a slightly worse bound. it uses the common derandomization technique of small-biased k-independent sample spaces. for the special case r &equals; 2, we get roughly 2.275 log n adaptive queries, which is fairly close to the obvious lower bound of 2 log n. for the class of monotone functions, we prove that the optimal query number o(2r + r log n) can be already achieved in o(r) stages. on the other hand, &omega;(2r log n) is a lower bound on nonadaptive queries.
non-interactive and reusable non-malleable commitment schemes. we consider non-malleable (nm) and universally composable (uc) commitment schemes in the common reference string (crs) model. we show how to construct non-interactive nm commitments that remain non-malleable even if the adversary has access to an arbitrary number of commitments from honest players - rather than one, as in several previous schemes. we show this is a strictly stronger security notion. our construction is the first non-interactive scheme achieving this that can be based on the minimal assumption of existence of one-way functions. but it can also be instantiated in a very efficient version based on the strong rsa assumption. for uc commitments, we show that existence of a uc commitment scheme in the crs model (interactive or not) implies key exchange and - for a uniform reference string - even implies oblivious transfer. this indicates that uc commitment is a strictly stronger primitive than nm. finally, we show that our strong rsa based construction can be used to improve the most efficient known uc commitment scheme so it can work with a crs of size independent of the number of players, without loss of efficiency.
the complexity of computing a nash equilibrium. in 1951, john f. nash proved that every game has a nash equilibrium [ann. of math. (2), 54 (1951), pp. 286-295]. his proof is nonconstructive, relying on brouwer's fixed point theorem, thus leaving open the questions, is there a polynomial-time algorithm for computing nash equilibria? and is this reliance on brouwer inherent? many algorithms have since been proposed for finding nash equilibria, but none known to run in polynomial time. in 1991 the complexity class ppad (polynomial parity arguments on directed graphs), for which brouwer's problem is complete, was introduced [c. papadimitriou, j. comput. system sci., 48 (1994), pp. 489-532], motivated largely by the classification problem for nash equilibria; but whether the nash problem is complete for this class remained open. in this paper we resolve these questions: we show that finding a nash equilibrium in three-player games is indeed ppad-complete; and we do so by a reduction from brouwer's problem, thus establishing that the two problems are computationally equivalent. our reduction simulates a (stylized) brouwer function by a graphical game [m. kearns, m. littman, and s. singh, graphical model for game theory, in 17th conference in uncertainty in artificial intelligence (uai), 2001], relying on &ldquo;gadgets,&rdquo; graphical games performing various arithmetic and logical operations. we then show how to simulate this graphical game by a three-player game, where each of the three players is essentially a color class in a coloring of the underlying graph. subsequent work [x. chen and x. deng, setting the complexity of 2-player nash-equilibrium, in 47th annual ieee symposium on foundations of computer science (focs), 2006] established, by improving our construction, that even two-player games are ppad-complete; here we show that this result follows easily from our proof.
optimal phylogenetic reconstruction. one of the major tasks of evolutionary biology is the reconstruction of phylogenetic trees from molecular data. the evolutionary model is given by a markov chain on the true evolutionary tree. given samples from this markov chain at the leaves of the tree, the goal is to reconstruct the evolutionary tree.it is well known that in order to reconstruct a tree on n leaves, sequences of length ω(log n) are needed. it was conjectured by m. steel that for the cfn evolutionary model, if the mutation probability on all edges of the tree is less than p* = (√2-1)/23/2, then the tree can be recovered from sequences of length o(log n). this was proven by the second author in the special case where the tree is "balanced". the second author also proved that if all edges have mutation probability larger than p* then the length needed is nω(1). this "phase-transition" in the number of samples needed is closely related to the phase transition for the reconstruction problem (or extremality of free measure) studied extensively in statistical physics, probability and computer science.here we complete the proof of steel's conjecture and give a reconstruction algorithm using optimal (up to a multiplicative constant) sequence length. our results further extend to obtain an optimal reconstruction algorithm for the jukes-cantor model with short edges. all reconstruction algorithms run in polynomial time.
denotational semantics of concurrency a general framework for the denotational treatment of concurrency is introduced. the key idea is the notion of process which is element of a domain obtained as solution of a domain equation in the style as considered previously by plotkin. we use tools from metric topology as advocated by nivat to solve this equation, show how operations upon processes can be defined conveniently, and illustrate the approach with the definition of a variety of concepts as encountered in the study of concurrency. only few proofs of the supporting mathematical theory are given; full proofs will appear in the final version of the paper.
online trading algorithms and robust option pricing. in this work we show how to use efficient online trading algorithms to price the current value of financial instruments, such as an option. we derive both upper and lower bounds for pricing an option, using online trading algorithms.our bounds depend on very minimal assumptions and are mainly derived assuming that there are no arbitrage opportunities.
some connections between mathematical logic and complexity theory however difficult the fundamental problems of theoretical computer science may seem, there is very little to suggest that they are anything more than knotty combinatorial problems. so, when we look for reasons for our inability to resolve p &equil; np and related questions, we most likely find them dealing with a lack of understanding of particular computational problems and their lower bounds. this is the sense of hopcroft's prediction: &ldquo;...within the next five years, nobody will prove that any of these problems takes more than let's say n2 time. i think that's a reasonably safe conjecture and it also illustrates how little we know about lower bounds.&rdquo; [mt]. hopcroft's guess is uncanny in its accuracy&mdash;after six years and considerable effort by many researchers, his conjecture remains unchallenged. the results in this paper offer a possible explanation for our failure to resolve these problems. roughly, the main result of the sequel links lower bounds and a branch of mathematical logic known as model theory. in particular, we prove that the existence of nonpolynomial lower bounds is equivalent to the existence of nonstandard models of a sizable fragment of arithmetic. since these are deep logical issues and there are very few techniques for handling them, and since the nonstandard models in question are non-effective, it seems plausible that this linking of complexity theory and logic explains our failure to obtain nontrivial lower bounds. one of the aims of mathematical logic is to clarify the relation between mathematical theories and their interpretations&mdash;or models.
the consistency of ``p = np'' and related problems with fragments of number theory the main results of this paper demonstrate the consistency of &ldquo;p &equil; np&rdquo; and a variant of &ldquo;np @@@@ conp&rdquo; with certain natural fragments of number theory to be defined precisely in the sequel.@@@@ consistency results represent an approach to the lower bound problems of complexity theory which points to a number of interesting lines of inquiry. our ultimate goal is to make precise the difficulty of proving certain nontrivial lower bounds. among the possibilities which follow from this approach are: (1) that logical techniques may help us resolve the p &equil; np question, (2) that showing why certain arguments must fail may lead to mathematical tools capable of resolving the problems, and (3) that the special character of model theoretic methods in complexity theory may lead to new results which are of purely logical interest. we will address these possibilities below.
cryptographic protocols a cryptographic transformation is a mapping f from a set of cleartext messages, m, to a set of ciphertext messages. since for m e m, f(m) should hide the contents of m from an enemy, f-1 should, in a certain technical sense, be difficult to infer from f(m) and public knowledge about f. a cryptosystem is a model of computation and communication which permits the manipulation of messages by cryptographic transformations.
liveness properties as convergence in metric spaces four liveness properties of concurrent programs are characterized by the fact that their computations, represented as sequences of partial orderings of events, are convergent in suitable metric spaces. the corresponding topological completions do not therefore contain the infinite computations without the desired properties. the properties are: vitality (i.e. every running process will eventually produce an observable event), global and local fairness, and deadlock freedom. this approach proves fruitful since a universal scheduler is defined, which, when supplied with a particular metric, generates all and only convergent computations. thus, this scheduler can be used to generate all and only vital, fair or deadlock free computations.
a new approach to dynamic all pairs shortest paths. we study novel combinatorial properties of graphs that allow us to devise a completely new approach to dynamic all pairs shortest paths problems. our approach yields a fully dynamic algorithm for general directed graphs with non-negative real-valued edge weights that supports any sequence of operations in o(n2log3n) amortized time per update and unit worst-case time per distance query, where n is the number of vertices. we can also report shortest paths in optimal worst-case time. these bounds improve substantially over previous results and solve a long-standing open problem. our algorithm is deterministic, uses simple data structures, and appears to be very fast in practice.
on the complexity of equilibria. we prove complexity, approximability, and inapproximability results for the problem of finding an exchange equilibrium in markets with indivisible (integer) goods, most notably a polynomial-time algorithm that approximates the market equilibrium arbitrarily closely when the number of goods is bounded and the utilities are linear. we also show a communication complexity lower bound, implying that the ideal informational economy of a market with unique individual optima is unattainable in general.
the spending constraint model for market equilibrium: algorithmic, existence and uniqueness results. the traditional model of market equilibrium supports impressive existence results, including the celebrated arrow-debreu theorem. however, in this model, polynomial time algorithms for computing (or approximating) equilibria are known only for linear utility functions. we present a new, and natural, model of market equilibrium that not only admits existence and uniqueness results paralleling those for the traditional model but is also amenable to efficient algorithms.
integrality gaps for sparsest cut and minimum linear arrangement problems. arora, rao and vazirani [2] showed that the standard semi-definite programming (sdp) relaxation of the sparsest cut problem with the triangle inequality constraints has an integrality gap of o(√log n). they conjectured that the gap is bounded from above by a constant. in this paper, we disprove this conjecture (referred to as the arv-conjecture) by constructing an ω(log log n) integrality gap instance. khot and vishnoi [16] had earlier disproved the non-uniform version of the arv-conjecture.a simple "stretching" of the integrality gap instance for the sparsest cut problem serves as an ω(log log n) integrality gap instance for the sdp relaxation of the minimum linear arrangement problem. this sdp relaxation was considered in [6, 11], where it was shown that its integrality gap is bounded from above by o(√log n log log n).
alpha-shapes and flow shapes are homotopy equivalent. in this paper we establish a topological similarity between two apparently different shape constructors from a set of points. shape constructors are geometric structures that transform finite point sets into continuous shapes. due to their immense practical importance in geometric modeling various shape constructors have been proposed recently. understanding the relations among them often leads to new insights that are potentially helpful in applications. here we discover a topological equivalence among two such geometric structures, namely α shapes and flow shapes. both shapes found applications in surface reconstruction and molecular modelin.
maintaining order in a linked list we present a new representation for linked lists. this representation allows one to efficiently insert objects into the list and to quickly determine the order of list elements. the basic data structure, called an indexed 2-3 tree, allows one to do n inserts in o(nlogn) steps and to determine order in constant time. we speed up the algorithm by dividing the data structure up into log*n layers. the improved algorithm does n insertions and comparisons in o(nlog*n) steps. the paper concludes with two applications: determining ancestor relationships in a growing tree and maintaining a tree structured environment (context tree).
two algorithms for maintaining order in a list the order maintenance problem is that of maintaining a list under a sequence of insert and delete operations, while answering order queries (determine which of two elements comes first in the list). we give two new algorithms for this problem. the first algorithm matches the o(1) amortized time per operation of the best previously known algorithm, and is much simpler. the second algorithm permits all operations to be performed in o(1) worst-case time.
almost random graphs with simple hash functions. we describe a simple randomized construction for generating pairs of hash functions h1,h2 from a universe u to ranges v = [m] = (0,1,...,m-1) and w = [m] so that for every key set s ⊆ u with n = |s| ≤ m/(1 + ε) the (random) bipartite (multi)graph with node set v ∪ w and edge set (h1(x),h2(x))| x ∈ s exhibits a structure that is essentially random. the construction combines d-wise independent classes for d a relatively small constant with the well-known technique of random offsets. while keeping the space needed to store the description of h1 and h2 at o(nζ), for ζ < 1 fixed arbitrarily, we obtain a much smaller (constant) evaluation time than previous constructions of this kind, which involved siegel's high-performance hash classes. the main new technique is the combined analysis of the graph structure and the inner structure of the hash functions, as well as a new way of looking at the cycle structure of random (multi)graphs. the construction may be applied to improve on pagh and rodler's "cuckoo hashing" (2001), to obtain a simpler and faster alternative to a recent construction of ostlin and pagh (2002/03) for simulating uniform hashing on a key set s, and to the simulation of shared memory on distributed memory machines. we also describe a novel way of implementing (approximate) d-wise independent hashing without using polynomials.