waashk/dblp huggingface dataset:
lower bounds & competitive algorithms for online scheduling of unit-size tasks to related machines. in this paper we study the problem of assigning unit-size tasks to related machines when only limited online information is provided to each task. this is a general framework whose special cases are the classical multiple-choice games for the assignment of unit-size tasks to identical machines. the latter case was the subject of intensive research for the last decade. the problem is intriguing in the sense that the natural extensions of the greedy oblivious schedulers, which are known to achieve near-optimal performance in the case of identical machines, are proved to perform quite poorly in the case of the related machines.(math) in this work we present a rather surprising lower bound stating that any oblivious scheduler that assigns an arbitrary number of tasks to $n$ related machines would need $\omega\left(\frac{\log n}{\l2 n}\right)$ polls of machine loads per task, in order to achieve a constant competitive ratio versus the optimum offline assignment of the same input sequence to these machines. on the other hand, we prove that the missing information for an oblivious scheduler to perform almost optimally, is the amount of tasks to be inserted into the system. in particular, we provide an oblivious scheduler that only uses $\o(\l2 n)$ polls, along with the additional information of the size of the input sequence, in order to achieve a constant competitive ratio vs. the optimum offline assignment. the philosophy of this scheduler is based on an interesting exploitation of the slowfit concept ([1, 5, 3]; for a survey see [6, 9, 16]) for the assignment of the tasks to the related machines despite the restrictions on the provided online information, in combination with a layered induction argument for bounding the tails of the number of tasks passing from slower to faster machines. we finally use this oblivious scheduler as the core of an adaptive scheduler that does not demand the knowledge of the input sequence and yet achieves almost the same performance.
efficient lr(1) processor construction strings from lr(k) grammars can be recognized and parsed in linear time by a processor that is directed by a pre-computed parsing table. this paper deals with two questions of practical importance: the effort required to generate an lr(k)parsing table for a grammar and the size of the table generated. knuth has described an algorithm for checking an arbitrary context-free grammar for the lr(k) condition and producing a parsing table, if possible. the time-complexity of this algorithm and the size of the table it produces are each exponential functions of the grammar size. thus, for very large grammars &mdash; such as those defining the syntax of a programming language &mdash; it is not feasible to use this algorithm directly. this paper presents a practical method of checking large cfgs for the lr(1) condition and generating the corresponding parsing table. it significantly decreases both the computation required to produce the parsing table and the size of the resulting table. it operates as follows. the given grammar g is partitioned into a number of parts. each part is checked for lr(1)-ness and individual parsing tables are generated, using the knuth algorithm. certain conditional modifications to these tables are then made; if the conditions are satisfied, the grammar g is lr(1) and the modified tables can be combined into a single parsing table for g. because of the exponential nature of the knuth algorithm, this process of partitioning, computing and combining can greatly improve the efficiency of the table generation procedure. using this method lr(1) parsers for a number of programming languages, including algol, have been constructed. the empirical evidence obtained has verified the efficacy of this method: in one programming language example, table construction time was reduced by a factor of nine and the table size was reduced by a factor of three.
approximation algorithm for k-node connected subgraphs via critical graphs. we present two new approximation algorithms for the problem of finding a k-node connected spanning subgraph (directed or undirected) of minimum cost. the best known approximation guarantees for this problem were o(min (k,n/√n-k)) for both directed and undirected graphs, and o(ln k) for undirected graphs with n ≥ 6k2, where n is the number of nodes in the input graph. our first algorithm has approximation ratio o(k/n-kln 2 k, which is o(ln2 k) except for very large values of k, namely, k=n-o(n). this algorithm is based on a new result on l-connected p-critical graphs, which is of independent interest in the context of graph theory. our second algorithm uses the primal-dual method and has approximation ratio o(√n ln k) for all values of n,k. combining these two gives an algorithm with approximation ratio o(ln k • min (√k, k/n-k ln k)), which asymptotically improves the best known approximation guarantee for directed graphs for all values of n,k, and for undirected graphs for k> √n⁄6. moreover, this is the first algorithm that has an approximation guarantee better than θ(k) for all values of n,k. our approximation ratio also provides an upper bound on the integrality gap of the standard lp-relaxation to the problem.as a byproduct, we also get the following result which is of independent interest. to get a faster implementation of our algorithms, we consider the problem of adding a minimum-cost edge set to increase the outconnectivity of a directed graph by δ a graph is said to be l-outconnected from its node r if it contains l internally disjoint paths from r to any other node. the best known time complexity for the later problem is o(m3). for the particular case of δ=1, we give a primal-dual algorithm with running time o(m2).
euler paths in series parallel graphs. given a series-parallel graph, we consider the problem of drawing its layout in the plane (and the planar dual of the layout) such that the euler count of the layout is minimized. this problem is of considerable importance to the design of cmos circuits. even though it was believed that there cannot exist a polynomial time algorithm for this problem, we have been able to design a polynomial time algorithm. the degree of the polynomial is unrealistically large. the main interest is in the existence of a polynomial time algorithm for the problem. we are not aware of any natural problem for which a natural dynamic programming based algorithm has such a large degree.
analysis of structured programs we investigate various control structures to understand their computational complexity and limitations. it is generally felt that goto-less programs constructed from the classical primitives are very restrictive; structured programming languages like bliss, however, incorporating repeat-exit constructs appear to ease this sense of restrictiveness. in this paper we analyze this construct. we answer a conjecture of knuth and floyd as a special case of the general theory. we also investigate a general top-down programming construct, which we call the tdn-construct. we structurally characterize the class of goto-less programs. we also generalize such an analysis and solve an open problem of b&ouml;hm and jacopini.
computational complexity of computing polynomials over the fields of real and complex numbers fast computation of polynomials of 1 variable in the fields r and c of real and complex numbers is considered. the optimal schemes of computation with preconditioning (that is, the schemes involving the minimal number of arithmetic operations without counting preliminary treatment of coefficients) for evaluation in c are presented. the schemes which are close to optimal ones are presented for evaluation in r. the difference between the complexity of computation in r and in c is established. a new generalization of the problem is presented.
bounded-depth circuits: separating wires from gates. we develop a new method to analyze the flow of communication in constant-depth circuits. this point of view allows usto prove new lower bounds on the number of wires required to recognize certain languages. we are able to provide explicit languages that can be recognized by ac0 circuits with o(n) gates but not with o(n) wires, and similarly for acc0 circuits. we are also able to characterize exactly the regular languages that can be recognized with o(n) wires, both in ac0 and acc0 framework.
short path queries in planar graphs in constant time. we present a new algorithm for answering short path queries in planar graphs. for any fixed constant k and a given unweighted planar graph g=(v,e) one can build in o(|v|) time a data structure, which allows to check in o(1) time whether two given vertices are distant by at most k in g and if so a shortest path between them is returned. this significantly improves the previous result of d. eppstein [5] where after a linear preprocessing the queries are answered in o(log |v|) time. our approach can be applied to compute the girth of a planar graph and a corresponding shortest cycle in o(|v|) time provided that the constant bound on the girth is known.our results can be easily generalized to other wide classes of graphs~--~for instance we can take graphs embeddable in a surface of bounded genus or graphs of bounded tree-width.
complexity of finitely presented algebras an algebra a is finitely presented if there is a finite set g of generator symbols, a finite set o of operator symbols, and a finite set &ggr; of defining relations x&xgr;y where x and y are well-formed terms over g and o, such that a is isomorphic to the free algebra on g and o modulo the congruence induced by &ggr;. the uniform word problem, the finiteness problem, the triviality problem (whether a is the one element algebra), and the subalgebra membership problem (whether a given element of a is contained in a finitely generated subalgebra of a) for finitely presented algebras are shown to be &le;mlog-complete for p. the schema satisfiability problem and schema validity problem are shown to be &le;mlog-complete for np and co-np, respectively. finally, the problem of isomorphism of finitely presented algebras is shown to be polynomial time many-one equivalent to the problem of graph isomorphism.
indexing of subrecursive classes a theory of subrecursive indexings is developed, with emphasis on relationships between reducibilities, uniform simulation, and diagonalization.
a probabilistic pdl in this paper we give a probabilistic analog ppdl of propositional dynamic logic. we prove a small model property and give a polynomial space decision procedure for formulas involving well-structured programs. we also give a deductive calculus and illustrate its use by calculating the expected running time of a simple random walk program.
pebblings, edgings, and equational logic a lower bound of &ohgr;(n/logn) space is shown for two natural proof systems for equational logic. the method introduces an edging game, a generalization of the pebble game [p].
the intrinsic dimensionality of graphs. we resolve the following conjecture raised by levin together with linial, london, and rabinovich [combinatorica, 1995]. for a graph g, let dim(g) be the smallest d such that g occurs as a (not necessarily induced) subgraph of &#x2124;&#x221e; d , the infinite graph with vertex set &#x2124; d and an edge (u, v) whenever &#x2225;u &#x2212; v&#x2225;&#x221e; = 1. the growth rate of g, denoted &#x03c1; g , is the minimum &#x03c1; such that every ball of radius r > 1 in g contains at most r &#x03c1; vertices. by simple volume arguments, dim(g) = &#x03a9;(&#x03c1; g ). levin conjectured that this lower bound is tight, i.e., that dim(g) = o(&#x03c1; g ) for every graph g. previously, it was unknown whether dim(g) could be bounded above by any function of &#x03c1; g . we show that a weaker form of levin&#x2019;s conjecture holds by proving that dim(g) = o(&#x03c1; g log &#x03c1; g ) for any graph g. we disprove, however, the specific bound of the conjecture and show that our upper bound is tight by exhibiting graphs for which dim(g) = &#x03a9;(&#x03c1; g log &#x03c1; g ). for several special families of graphs (e.g., planar graphs), we salvage the strong form, showing that dim(g) = o(&#x03c1; g ). our results extend to a variant of the conjecture for finite-dimensional euclidean spaces posed by linial and independently by benjamini and schramm.
examples of hard tautologies in the propositional calculus we present examples of hard tautologies in propositional calculus by encoding instances of the assertions made by ramsey's theorem. we provide evidence that these tautologies are indeed hard by 1. showing that there are no short proofs for these tautologies in certain restricted classes of proof systems; 2. relating a proof of these tautologies to the problem of determining the diagonal ramsey numbers for graphs.
covering rectilinear polygons with axis-parallel rectangles. we give an $o(\sqrt{\log n})$ factor approximation algorithm for covering a rectilinear polygon with holes using axis-parallel rectangles. this is the first polynomial time approximation algorithm for this problem with an $o(\log n)$ approximation factor.
a bound on the multiplication efficiency of iteration for a convergent sequence {xi} generated by xi+1 &equil; @@@@(xi,x1,...,xi&minus;d+1), define the multiplication efficiency measure e to be p&frac1m;, where p is the order of convergence, and m is the number of multiplications or divisions (except by 2) needed to compute @@@@. then, if @@@@ is any multivariate rational function, e &le; 2. since e &equil; 2 for the sequence {xi} generated by xi+1 &equil; &frac12;(xi +&fracax; i)with the limit @@@@a, the bound on e is sharp.
the computational complexity of algebraic numbers let {xi} be a sequence approximating an algebraic number &agr; of degree r, and let [equation], for some rational function @@@@ with integral coefficients. let m denote the number of multiplications or divisions needed to compute @@@@ and let &mmarc; denote the number of multiplications or divisions, except by constants, needed to compute @@@@. define the multiplication efficiency measure of {xi} as [equation] or as [equation], where p is the order of convergence of {xi}. kung [1] showed that &emarc;({xi}) &le; 1 or equivalently, [equation]. in this paper we show that (i) [equation]; (ii) if e({xi}) &equil; 1 then &agr; is a rational number; (iii) if &emarc;({xi}) &equil; 1 then &agr; is a rational or quadratic irrational number. this settles the question of when the multiplication efficiency e({xi}) or &emarc;({xi}) achieves its optimal value of unity.
new algorithms and lower bounds for the parallel evaluation of certain rational expressions this paper presents new algorithms for the parallel evaluation of certain polynomial expression. in particular, for the parallel evaluation of xn,we introduce an algorithm which takes two steps of parallel division and [log2n] steps of parallel addition, while the usual algorithm takes [log2n] steps of parallel multiplication. hence our algorithm is faster than the usual algorithms when multiplication takes more time than addition. similar algorithm for the evaluation of other polynomial expressions are also introduced. lower bounds on the time needed for the parallel evaluation of rational expressions are given. all the algorithms presented in the paper are shown to be asymptotically optimal. moreover, we prove that by using parallelism the evaluation of any first order rational recurrence, e.g., [equation], and any non-linear polynomial recurrence can be sped up at most by a constant factor, no matter how many processors are used.
on the random oracle hypothesis we give two counterexamples to the random oracle hypothesis as formalized by bennett and gill[2]. we then discuss the future of the random oracle hypothesis in light of these examples we believe that these examples will severely test any new candidate for a formal random oracle hypothesis.
information-theoretically secure protocols and security under composition. we investigate the question of whether security of protocols in the information-theoretic setting (where the adversary is computationally unbounded) implies security under concurrent composition. this question is motivated by the folklore that all known protocols that are secure in the information-theoretic setting are indeed secure under concurrent composition. we provide answers to this question for a number of different settings (i.e., considering perfect versus statistical security, and concurrent composition with adaptive versus fixed inputs). our results enhance the understanding of what is necessary for obtaining security under composition, as well as providing tools (i.e., composition theorems) that can be used for proving the security of protocols under composition while considering only the standard stand-alone definitions of security.
lower bounds for randomized mutual exclusion. we establish, for the first time, lower bounds for randomized mutual exclusion algorithms (with a read-modify-write operation). our main result is that a constant-size shared variable cannot guarantee strong fairness, even if randomization is allowed. in fact, we prove a lower bound of $\omega (\log\log n)$ bits on the size of the shared variable, which is also tight.we investigate weaker fairness conditions and derive tight (upper and lower) bounds for them as well. surprisingly, it turns out that slightly weakening the fairness condition results in an exponential reduction in the size of the required shared variable. our lower bounds rely on an analysis of markov chains that may be of interest on its own and may have applications elsewhere.
log-space polynomial end-to-end communication. communication between processors is the essence of distributed computing: clearly, without communication, distributed computation is impossible. however, as networks become larger and larger, the frequency of link failures increases. the end-to-end communication problem asks how to efficiently carry out fault-free communication between two processors over a network, in spite of such frequent link failures. the sole minimum assumption is that the two processors that are trying to communicate are not permanently disconnected (i.e., the communication should proceed even when there does not (ever) simultaneously exist an operational path between the two processors that are trying to communicate).we present a protocol to solve the end-to-end problem with logarithmic-space and polynomial communication at the same time. this is an exponential memory improvement to all previous polynomial communication solutions. that is, all previous polynomial communication solutions needed at least linear (in n, the size of the network) amount of memory per link.our protocol transfers packets over the network, maintains a simple-to-compute o(log n)-bits potential function at each link in order to perform routing, and uses a novel technique of packet canceling which allows us to keep only one packet per link. the computations of both our potential function and our packet-canceling policy are totally local in nature.
efficient search for approximate nearest neighbor in high dimensional spaces. we address the problem of designing data structures that allow efficient search for approximate nearest neighbors. more specifically, given a database consisting of a set of vectors in some high dimensional euclidean space, we want to construct a space-efficient data structure that would allow us to search, given a query vector, for the closest or nearly closest vector in the database. we also address this problem when distances are measured by the l1 norm and in the hamming cube. significantly improving and extending recent results of kleinberg, we construct data structures whose size is polynomial in the size of the database and search algorithms that run in time nearly linear or nearly quadratic in the dimension. (depending on the case, the extra factors are polylogarithmic in the size of the database.)
explicit lower bound of for boolena circuits. we prove a lower bound of 4.5n - o(n) for the circuit complexity of an explicit boolean function (that is, a function constructible in deterministic polynomial time), over the basis u_2. that is, we obtain a lower bound of 4.5n - o(n) for the number of {and,or} gates needed to compute a certain boolean function, over the basis {and,or,not} (where the not gates are not counted). our proof is based on a new combinatorial property of boolean functions, called strongly-two-dependence, a notion that may be interesting in its own right. our lower bound applies to any strongly-two-dependent boolean function.
polynomial time reducibility several of the results that appear in [4] are stated to be true of polynominal time reducibility (&le;p) but are not proved explicitly. we shall prove several of these results with the hope of shedding some light on the &ldquo;determinism vs. nondeterminism&rdquo; problem. the ideas behind these proofs already exist in [4] but appear here in a different setting. we shall spend most of our time on two theorems: (i) if &fgr; <p &bgr; then there exists an &agr; such that &fgr; <p &agr; <p &bgr; and (ii) there exist &agr; and &bgr; neither of which is polynominal time computable but such that if c &le;p &agr; and c &le;p &bgr; then c is polynominal time computable. we show how the techniques used in the proofs of these theorems may be extended to prove other results.
the complexity of problems in systems of communicating sequential processes (extended abstract) there is a wide-spread belief among computer scientists that systems of communicating sequential processes are harder to analyze than purely sequential processes. the belief is largely based on the observation that the parallelism in such systems leads to a large number of possible interleavings of the actions of the different processes. we will show that other evidence supporting this belief is that the properties we are trying to analyze about these systems are themselves intrinsically complex. they are properties that make no sense when they are applied to purely sequential processes, or even parallel systems of sequential processes that have no ability to communicate with each other.
comparisons of polynomial-time reducibilities comparison of the polynomial-time-bounded reducibilities introduced by cook [1] and karp [4] leads naturally to the definition of several intermediate truth-table reducibilities. we give definitions and comparisons for these reducibilities; we note, in particular, that all reducibilities of this type which do not have obvious implication relationships are in fact distinct in a strong sense. proofs are by simultaneous diagonalization and encoding constructions. work of meyer and stockmeyer [7] and gill [2] then leads us to define nondeterministic versions of all of our reducibilities. although many of the definitions degenerate, comparison of the remaining nondeterministic reducibilities among themselves and with the corresponding deterministic reducibilities yields some interesting relationships.
tradeoffs between communication and space this paper initiates the study of communication complexity when the processors have limited work space. the following tradeoffs between number c of communications steps and space s are proved: for multiplying two n &times; n matrices in the arithmetic model with two-way communication, cs = &thgr;(n2). for convolution of two degree n polynomials in the arithmetic model with two-way communication, cs = &thgr;(n2). for multiplying an n &times; n matrix by an n-vector in the boolean model with one-way communication, cs = &thgr;(n2). in contrast, the discrete fourier transform and sorting can be accomplished in &ogr;(n) communication steps and &ogr;(log n) space simultaneously, and the search problems of karchmer and wigderson associated with any language in nck can be solved in &ogr;(logk n) communication steps and &ogr;(logk n) space simultaneously.