waashk/dblp huggingface dataset:
threshold functions and bounded depth monotone circuits we prove an exponential lower bound for the majority function on constant depth monotone circuits, solving an open problem of a. yao's.. in particular, we prove that computing majority on depth d monotone circuits requires exp&ohgr;(n1/(d-1)) size. using this result we also get exponential lower bounds for other problems, such as connectivity and cliques.
optimal separations between concurrent-write parallel machines we obtain tight bounds on the relative powers of the priority and common models of parallel random-access machines (prams). specifically we prove that: the element distinctness function of n integers, though solvable in constant time on a priority pram with n processors, requires &ohgr;(a(n,p)) time to solve on a common pram with p &ge; n processors, where a(n,p) = n log n/p log (n/p log n + 1). one step of a priority pram with n processors can be simulated on a common pram with p processors in &ogr;(a(n,p)) steps. as an example, the results show that the time separation between priority and common prams each with n processors is &thgr;(log n/log log n).
quantum complexity theory. in this paper we study quantum computation from a complexity theoretic viewpoint. our first result is the existence of an efficient universal quantum turing machine in deutsch's model of a quantum turing machine (qtm) [proc. roy. soc. london ser. a, 400 (1985), pp. 97--117]. this construction is substantially more complicated than the corresponding construction for classical turing machines (tms); in fact, even simple primitives such as looping, branching, and composition are not straightforward in the context of quantum turing machines. we establish how these familiar primitives can be implemented and introduce some new, purely quantum mechanical primitives, such as changing the computational basis and carrying out an arbitrary unitary transformation of polynomially bounded dimension.we also consider the precision to which the transition amplitudes of a quantum turing machine need to be specified. we prove that $o(\log t)$ bits of precision suffice to support a $t$ step computation. this justifies the claim that the quantum turing machine model should be regarded as a discrete model of computation and not an analog one. we give the first formal evidence that quantum turing machines violate the modern (complexity theoretic) formulation of the church--turing thesis. we show the existence of a problem, relative to an oracle, that can be solved in polynomial time on a quantum turing machine, but requires superpolynomial time on a bounded-error probabilistic turing machine, and thus not in the class $\bpp$. the class $\bqp$ of languages that are efficiently decidable (with small error-probability) on a quantum turing machine satisfies $\bpp \subseteq \bqp \subseteq \ptime^{\sp}$. therefore, there is no possibility of giving a mathematical proof that quantum turing machines are more powerful than classical probabilistic turing machines (in the unrelativized setting) unless there is a major breakthrough in complexity theory.
the k-steiner ratio in graphs. a steiner minimum tree (smt) is the shortest-length tree in a metric space interconnecting a set of points, called the regular points, possibly using additional vertices. a k-size steiner minimum tree (ksmt) is one that can be split into components where all regular points are leaves and all components have at most k leaves. the k-steiner ratio, $\rho_{k}$, is the infimum of the ratios smt/ksmt over all finite sets of regular points in all possible metric spaces, where the distances are given by a complete graph. previously, only $\rho_{2}$ and $\rho_{3}$ were known exactly in graphs, and some bounds were known for other values of k. in this paper, we determine $\rho_{k}$ exactly for all k. from this we prove a better approximation ratio for the steiner tree problem in graphs.
a characterization of the class of functions computable in polynomial time on random access machines enumeration problems constitute a major part of combinatorial mathematics. combinatorial mathematics expresses the solution of enumeration problems by means of solving formulas, generally based on the usual arithmetic operations [7]. these solving formulas can be formally represented as programs for a random access machine (ram) with arithmetical primitives, for which the natural complexity measure is the arithmetical complexity [1].
graph limits and parameter testing. we define a distance of two graphs that reflects the closeness of both local and global properties. we also define convergence of a sequence of graphs, and show that a graph sequence is convergent if and only if it is cauchy in this distance. every convergent graph sequence has a limit in the form of a symmetric measurable function in two variables. we use these notions of distance and graph limits to give a general theory for parameter testing. as examples, we provide short proofs of the testability of maxcut and the recent result of alon and shapira about the testability of hereditary graph properties.
solving convex programs by random walks. minimizing a convex function over a convex set in n-dimensional space is a basic, general problem with many interesting special cases. here, we present a simple new algorithm for convex optimization based on sampling by a random walk. it extends naturally to minimizing quasi-convex functions and to other generalizations.
sharp threshold and scaling window for the integer partitioning problem. we consider the problem of partitioning n integers chosen randomly between 1 and 2^m into two subsets such that the discrepancy, the absolute value of the difference of their sums, is minimized. a partition is called perfect if the optimum discrepancy is 0 when the sum of all n integers in the original set is even, or 1 when the sum is odd. parameterizing the random problem in terms of &kgr; = m/n, we prove that the problem has a sharp threshold at &kgr; = 1, in the sense that for &kgr; , there are many perfect partitions with probability tending to 1 as n \to \infty, while for 1, there are no perfect partitions with probability tending to 1. moreover, we show that the derivative of the so-called entropy is discontinuous at &kgr;=1.we also determine the scaling window about the transition point: &kgr;_n = 1 - (2n)^{-1}\log_2 n + &lgr;_n / n, by showing that the probability of a perfect partition tends to 0, 1, or some explicitly computable p(&lgr;) \in (0,1), depending on whether &lgr;_n tends to -\infty$, $\infty$, or $&lgr; \in (-\infty, \infty), respectively. for &lgr;_n \to -\infty fast enough, we show that the number of perfect partitions is gaussian in the limit. for &lgr;_n \to \infty, we prove that with high probability the optimum partition is unique, and that the optimum discrepancy is &thgr;(&lgr;_n). within the window, i.e., if |&lgr;_n| is bounded, we prove that the optimum discrepancy is bounded. both for &lgr;_n \to \infty and within the window, the limiting distribution of the (scaled) discrepancy
how to assemble tree machines (extended abstract) many researchers have proposed that ensembles of processing elements be organized as trees. this paper explores how large tree machines may be assembled efficiently from smaller components. a principal constraint that we consider is the limited number of external connections from an integrated circuit chip. we also explore the emerging capability of restructurable vlsi which allows a chip to be customized after fabrication. we give a linear-area chip of m processors and only four off-chip connections which can be used as the sole building block to construct an arbitrarily large complete binary tree. we also present a restructurable linear-area layout of m processors with o(lg m) pins that can realize an arbitrary binary tree. this layout is based on a solution to the graph-theoretic problem: given a tree in which each vertex is either black or white, determine how many edges need be cut in order to bisect the tree into equal-size components, each containing exactly half the black and half the white vertices.
solving fractional packing problems in (1/?) iterations. we adapt a method proposed by nesterov [16] to design an algorithm that computes ε-optimal solutions to fractional packing problems by solving o*(ε-1 √kn) separable convex quadratic programs, where k is the maximum number of non-zeros per row and n is the number of variables. we also show that the quadratic program can be approximated to any degree of accuracy by an appropriately defined piecewise-linear program. for the special case of the maximum concurrent flow problem on a graph g =(v,e) with rational capacities and demands we obtain an algorithm that computes an ε-optimal flow by solving o*(ε-1 k3/2|e| √|v| (log 1/ε+ lu + ld)) shortest path problems, where k is the number of commodities, and lu, ld are, respectively, the number of bits needed to store the capacities and demands. we also show that the complexity of computing a maximum multicommodity flow is o*(1/εlog2(1/ε)). in contrast, previous algorithms required ω(ε-2) iterations.
on the number of additions to compute specific polynomials (preliminary version) it is well known from the work of motzkin [55], belaga [58] and pan [66], that &ldquo;most&rdquo; nth degree polynomials p &egr; r[x] require about n/2 &times;, &divide; ops and n &plusmn; ops and that these bounds can always be achieved within the framework of preconditioned evaluation (1). more precisely, if p can be computed using less than [equation] &times;, &divide; or less than n &plusmn; ops, then the coefficients of p are algebraically dependent. the situation when counting &plusmn; ops with the potential of unlimited * ops, is not as clear. while the arguments based on algebraic dependence provide us with our best lower bounds thus far, a different approach of independent interest is taken in section iv. namely, we are able to show that the number of &plusmn; ops required to compute any p &egr; r[x] is bounded below by a function of the number of distinct real zeros of p. the potential (e.g., for producing non linear lower bounds) and limitations of this approach will be discussed.
a time-space tradeoff for sorting on a general sequential model of computation in a general sequential model of computation, no restrictions are placed on the way in which the computation may proceed, except parallel operations are not allowed. we show that in such an unrestricted environment time&bull;space&equil;&ohgr;(n2/log n) in order to sort n elements, each in the range [1,n2].
bounds for width two branching programs branching programs for the computation of boolean functions were first studied in the master's thesis of masek.7 in a rather straightforward manner they generalize the concept of a decision tree to a decision graph. let p be a branching program with edges labelled by the boolean variables, x1,...,xn and their complements. given an input a&equil;(a1,...,an) &egr; {0,1}n, program p computes a function value fp(a) in the following way. the nodes of p play the role of states or configurations. in particular, sinks play the role of final states or stopping configurations. the length of program p is the length of the longest path in p. following cobham,2capacity of the program is defined to be the logarithm to the base 2 of the number of nodes in p. length and capacity are lower bounds on time and space requirements for any reasonable model of sequential computation. clearly, any n-variable boolean function can be computed by a branching program of length n if the capacity is not constrained. since space lower bounds in excess of log n remain a fundamental challenge, we consider restricted branching programs in the hope of gaining insight into this problem and the closely related problem of time-space trade-offs.
size-time complexity of boolean networks for prefix computations the prefix problem consists of computing all the products x0x1 &hellip; xj (j = 0, &hellip; , n - 1), given a sequence x = (x0, x1, &hellip; , xn-1) of elements in a semigroup. in this paper we completely characterize the size-time complexity of computing prefixes with boolean networks, which are synchronized interconnections of boolean gates and one-bit storage devices. this complexity crucially depends upon two properties of the underlying semigroup, which we call cycle-freedom (no cycle of length greater than one in the cayley graph of the semigroup), and memory-induciveness (arbitrarily long products of semigroup elements are true functions of all their factors). a nontrivial characterization is given of non-memory-inducive semigroups as those whose recurrent subsemigroup (formed by the elements with self-loops in the cayley graph) is the direct product of a left-zero semigroup and a right-zero semigroup. denoting by s and t size and computation time, respectively, we have s = &thgr;((n/t)log(n/t)) for memory-inducive non-cycle-free semigroups, and s = &thgr;(n/t) for all other semigroups. we have t &egr; [&ohgr;(log n), &ogr;(n)] for all semigroups, with the exception of those whose recurrent subsemigroup is a right-zero semigroup, for which t &egr; [&ohgr;(1), &ogr;(n)]. the preceding results are also extended to the vlsi model of computation. area-time optimal circuits are obtained for both boundary and nonboundary i/o protocols.
proof of a conjecture of r. kannan r. kannan conjectured that every non-deterministic two-way finite automaton can be positionally simulated by a deterministic two-way finite automaton. the conjecture is proved here by reduction to a similar problem about finite semigroups. the method and the result are then generalized to alternating two-way finite automata.
adversarial queueing theory. we consider packet routing when packets are injected continuously into a network. we develop an adversarial theory of queuing aimed at addressing some of the restrictions inherent in probabilistic analysis and queuing theory based on time-invariant stochastic generation. we examine the stability of queuing networks and policies when the arrival process is adversarial, and provide some preliminary results in this direction. our approach sheds light on various queuing policies in simple networks, and paves the way for a systematic study of queuing with few or no probabilistic assumptions.
an optimal online algorithm for metrical task systems in practice, almost all dynamic systems require decisions to be made online, without full knowledge of their future impact on the system. we introduce a general model for the processing of sequences of tasks and develop a general online decision algorithm. we show that, for an important class of special cases, this algorithm is optimal among all online algorithms. specifically, a task system (s, d) for processing sequences of tasks consists of a set s of states and a cost matrix d where d(i, j) is the cost of changing from state i to state j (we assume that d satisfies the triangle inequality and all diagonal entries are o.) the cost of processing a given task depends on the state of the system. a schedule for a sequence t1, t2 &hellip; tk of tasks is a sequence s1, s2 &hellip; sk of states where si is the state in which ti is processed; the cost of a schedule is the sum of all task processing costs and state transition costs incurred. an online scheduling algorithm is one that chooses si only knowing t1 t2 &hellip; ti. such an algorithm operates within waste factor w if, on any input task sequence, its costs is within an additive constant of w times the optimal offline schedule cost. the online waste factor w(s, d) is the infirm waste factor of any online scheduling algorithm for (s, d). we show that w(s, d) = 2|s| - 1 for every task system in which d symmetric, and w(s, d) = &ogr;(|s|2) for every task system.
subquadratic approximation algorithms for clustering problems in high dimensional spaces. one of the central problems in information retrieval, data mining, computational biology, statistical analysis, computer vision, geographic analysis, pattern recognition, distributed protocols is the question of classification of data according to some clustering rule. often the data is noisy and even approximate classification is of extreme importance. the difficulty of such classification stems from the fact that usually the data has many incomparable attributes, and often results in the question of clustering problems in high dimensional spaces. since they require measuring distance between every pair of data points, standard algorithms for computing the exact clustering solutions use quadratic or &ldquo;nearly quadratic&rdquo; running time&semi; i.e., o(dn2&minus;&alpha;(d)) time where n is the number of data points, d is the dimension of the space and &alpha;(d) approaches 0 as d grows. in this paper, we show (for three fairly natural clustering rules) that computing an approximate solution can be done much more efficiently. more specifically, for agglomerative clustering (used, for example, in the alta vista&trade; search engine), for the clustering defined by sparse partitions, and for a clustering based on minimum spanning trees we derive randomized (1 + &epsi;) approximation algorithms with running times &otilde;(d2 n2&minus;&gamma;) where &gamma; > 0 depends only on the approximation parameter &epsi; and is independent of the dimension d.
how much can hardware help routing? we study the extent to which complex hardware can speed up routing. specifically, we consider the following questions. how much does adaptive routing improve over oblivious routing? how much does randomness help? how does it help if each node can have a large number of neighbors? what benefit is available if a node can send packets to several neighbors within a single time step? some of these features require complex networking hardware, and thus it is important to investigate whether the performance justifies the investment. by varying these hardware parameters, we obtain a hierarchy of time bounds for worst-case permutation routing. we develop a nearly complete taxonomy of the complexity of routing.
finding extremal polygons given n points in the plane, we present algorithms for finding maximum perimeter or area convex k-gons with vertices k of the given n points. our algorithms work in linear space and time o(knlg n + n lg 2n). for the special case k -&-equil; 3 we give o (nlgn) algorithms for these problems. several related issues are discussed.
the chip complexity of binary arithmetic the chip complexity of a computation is concerned with the chip area, a, and the time, t, required to perform the computation when implemented on a chip. an area-time product at&agr;,for &agr; &ge; 0, is used as a complexity measure. a particular value of &agr;, which is chosen by the user, reflects the relative importance between a and t. this paper derives lower and upper bounds on the area-time complexity for chips that implement binary arithmetic, assuming a model of computation which is intended to approximate, current and anticipated lsi or vlsi technology.
approximation techniques for utilitarian mechanism design. this paper deals with the design of efficiently computable incentive compatible, or truthful, mechanisms for combinatorial optimization problems with multi-parameter agents. we focus on approximation algorithms for np-hard mechanism design problems. these algorithms need to satisfy certain monotonicity properties to ensure truthfulness. since most of the known approximation techniques do not fulfill these properties, we study alternative techniques.our first contribution is a quite general method to transform a pseudopolynomial algorithm into a monotone fptas. this can be applied to various problems like, e.g., knapsack, constrained shortest path, or job scheduling with deadlines. for example, the monotone fptas for the knapsack problem gives a very efficient, truthful mechanism for single-minded multi-unit auctions. the best previous result for such auctions was a 2-approximation. in addition, we present a monotone ptas for the generalized assignment problem with any bounded number of parameters per agent.the most efficient way to solve packing integer programs (pips) is lp-based randomized rounding, which also is in general not monotone. we show that primal-dual greedy algorithms achieve almost the same approximation ratios for pips as randomized rounding. the advantage is that these algorithms are inherently monotone. this way, we can significantly improve the approximation ratios of truthful mechanisms for various fundamental mechanism design problems like single-minded combinatorial auctions (cas), unsplittable flow routing and multicast routing. our approximation algorithms can also be used for the winner determination in cas with general bidders specifying their bids through an oracle.
target shooting with programmed random variables letx1,...,xn be pairwise independent random variables of known (but not necessarily identical) distribution; we wish to select a subset of these whose sum will be as close as possible to some known target value t. conditions described below force the selections to be made by a primitive distributed system (similar to one considered by papadimitriou and yannakakis [2] in podc '91); here we are able to obtain a surprising amount of information about optimal solutions. the conditions are that each variable must be &ldquo;programmed&rdquo; in advance, joining the selected set according to its own value. thus, for example, one variable might be programmed to join just if its value lies between &agr; and &bgr;, while another is told to join regardless of its value. our object is to find a strategy, that is, a collection of programs, which minimizes the mean square error in approximating t. typical applications involve producing a steady flow of some commodity when supply is controlled at a multiplicity of random sources. it turns out that there is always an optimal strategy in which each xi is programmed to join if its value is between 0 and &thgr;i, for appropriate choice of thresholds &thgr;i. when the variables are identically distributed, we examine conditions under which the &thgr;i's must be equal. the case of uniform distributions on [0,1], for which the above conditions are not satisfied, is analyzed in detail, showing the rather bizarre behavior of the &thgr;i's which may take place in general as the target value is gradually changed. next, we analyze the problem in which the variables are permitted to contribute any part of themselves to the sum; here it turns out that in an optimal strategy each program will be of the form &ldquo;contribute the minimum of xi and &eegr;i&rdquo; with all the &eegr;i's equal in the i.i.d. case. finally, we show how the original target shooting problem can be generalized to a kind of load balancing, where variables are assigned to different buckets, each with its own target, and the penalty is a weighted sum of squared errors. the surprising result here is that when the weights are equal, an optimal solution assigns variables only according to their signs.
on the optimal evaluation of a set of bilinear forms although general theories are beginning to emerge in the area of automata based complexity theory, there are very few general methods or even general problem formulations in the area of arithmetic complexity. in this paper we propose and defend a general model for studying bilinear multiplication in order to provide a common framework for discussing a wide class of problems. at the heart of a number of problems in minimizing the number of multiplications required to perform a calculation is a problem in matrix algebra relating to the expansion of a given set of matrices as linear combinations of rank one matrices. in this paper we make a systematic attack on this problem and derive some general results which unify and extend numerous known results. among the new results given here to illustrate the strength of this approach is a new lower bound on the number of multiplications required for n by n matrix multiplication of 3n2-3n+1 which is independent of the subset of the reals with respect to which multiplication is regarded as free. an even sharper bound is obtained if this set is restricted to the integers.