waashk/dblp huggingface dataset:
new lower bounds for parallel computation lower bounds are proven on the parallel-time complexity of several basic functions on the most powerful concurrent-read concurrent-write pram with unlimited shared memory and unlimited power of individual processors (denoted by priority(&infin;)): it is proved that with a number of processors polynomial in n, &ohgr; (log n) time is needed for addition, multiplication or bitwise or of n numbers, when each number has n' bits. hence even the bit complexity (i.e., the time complexity as a function of the total number of bits in the input) is logarithmic in this case. this improves a beautiful result of meyer auf der heide and wigderson [22]. they proved a log n lower bound using ramsey-type techniques. using ramsey theory, it is possible to get an upper bound on the number of bits in the inputs used. however, for the case of polynomially many processors, this upper bound is more than a polynomial in n. an &ohgr; (log n) lower bound is given for priority(&infin;) with no(1) processors on a function with inputs from {0, 1}, namely for the function &fnof;(x1, &hellip; , xn,) = &sgr; nl- 1 xlai where a is fixed and xi &egr; {0, 1}. finally, by a new efficient simulation of priority(&infin;) by unbounded fan-in circuits, that with less than exponential number of processors, it is proven a priority(&infin;) cannot compute parity in constant time, and with no(1) processors &ohgr;(@@@@log n) time is needed. the simulation technique is of independent interest since it can serve as a general tool to translate circuit lower bounds into pram lower bounds. further, the lower bounds in (1) and (2) remain valid for probabilistic or nondeterministic concurrent-read concurrent-write prams.
randomness-efficient low degree tests and short pcps via epsilon-biased sets. we present the first explicit construction of probabilistically checkable proofs (pcps) and locally testable codes (ltcs) of fixed constant query complexity which have almost-linear (= n * 2õ(√log n)) size. such objects were recently shown to exist (nonconstructively) by goldreich and sudan[17]. previous explicit constructions required size n1 + ω(ε) with 1/ε queries. the key to these constructions is a nearly optimal randomness-efficient version of the low degree test[32]. in a similar way we give a randomness-efficient version of the blr linearity test[13] (which is used, for instance, in locally testing the hadamard code). the derandomizations are obtained through ε-biased sets for vector spaces over finite fields. the analysis of the derandomized tests rely on alternative views of ε-biased sets --- as generating sets of cayley expander graphs for the low degree test, and as defining linear error-correcting codes for the linearity test.
short proofs are narrow - resolution made simple. the width of a resolution proof is defined to be the maximal number of literals in any clause of the proof. in this paper we relate proof width to proof size, in both general resolution, and its tree-like variant. specifically, the main observation of this paper is a relation between these two fundamental resources
building a complete inverted file for a set of text files in linear time given a finite set of texts s &equil; {&ohgr;1, ..., &ohgr;k} over some fixed finite alphabet &sgr;, a complete inverted file for s is an abstract data type that provides the functions find(&ohgr;), which returns the longest prefix of &ohgr; which occurs in s; freq(&ohgr;), which returns the number of times &ohgr; occurs in s; and locations(&ohgr;) which returns the set of positions at which &ohgr; occurs. we give a data structure to implement a complete inverted file for s which occupies linear space and can be built in linear time, using the uniform cost ram model. using this data structure, the time for each of the above query functions is optimal. to accomplish this, we use techniques from the theory of finite automata to build a deterministic finite automaton which recognizes the set of all sub words of the set s. this automaton is then annotated with additional information and compacted to facilitate the desired query functions.
space-efficient scheduling of multithreaded computations. this paper considers the problem of scheduling dynamic parallel computations to achieve linear speedup without using significantly more space per processor than that required for a single-processor execution. utilizing a new graph-theoretic model of multithreaded computation, execution efficiency is quantified by three important measures: t1 is the time required for executing the computation on a 1 processor, $t_\infty$ is the time required by an infinite number of processors, and s1 is the space required to execute the computation on a 1 processor. a computation executed on p processors is time-efficient if the time is $o(t_1/p + t_\infty)$, that is, it achieves linear speedup when $p=o(t_1/t_\infty)$, and it is space-efficient if it uses o(s1p) total space, that is, the space per processor is within a constant factor of that required for a 1-processor execution.the first result derived from this model shows that there exist multithreaded computations such that no execution schedule can simultaneously achieve efficient time and efficient space. but by restricting attention to "strict" computations---those in which all arguments to a procedure must be available before the procedure can be invoked---much more positive results are obtainable. specifically, for any strict multithreaded computation, a simple online algorithm can compute a schedule that is both time-efficient and space-efficient. unfortunately, because the algorithm uses a global queue, the overhead of computing the schedule can be substantial. this problem is overcome by a decentralized algorithm that can compute and execute a p-processor schedule online in expected time $o(t_1/p + t_\infty\lg p)$ and worst-case space $o(s_1p\lg p)$, including overhead costs.
the power of a pebble: exploring and mapping directed graphs. exploring and mapping an unknown environment is a fundamental problem that is studied in a variety of contexts. many results have focused on finding efficient solutions to restricted versions of the problem. in this paper, we consider a model that makes very limited assumptions about the environment and solve the mapping problem in this general setting. we model the environment by an unknown directed graph g, and consider the problem of a robot exploring and mapping g. the edges emanating from each vertex are numbered from '1' to 'd', but we do not assume that the vertices of g are labeled. since the robot has no way of distinguishing between vertices, it has no hope of succeeding unless it is given some means of distinguishing between vertices. for this reason we provide the robot with a "pebble'--a device that it can place on a vertex and use to identify the vertex later. in this paper we show: (1) if the robot knows an upper bound on the number of vertices then it can learn the graph efficiently with only one pebble. (2) if the robot does not know an upper bound on the number of vertices n, then θ(log log n) pebbles are both necessary and sufficient. in both cases our algorithms are deterministic.
balanced boolean functions that can be evaluated so that every input bit is unlikely to be read. a boolean function of n bits is balanced if it takes the value 1 with probability 1⁄2. we exhibit a balanced boolean function with a randomized evaluation procedure (with probability 0 of making a mistake) so that on uniformly random inputs, no input bit is read with probability more than θ(n-1/2√ log n). we construct a balanced monotone boolean function and a randomized algorithm computing it for which each bit is read with probability θ(n-1⁄3 log n). we then show that for any randomized algorithm for evaluating a balanced boolean function, when the input bits are uniformly random, there is some input bit that is read with probability at least θ(n-1䊪). for balanced monotone boolean functions, there is some input bit that is read with probability at least θ(n-1䊫).
an iteration theorem for one-counter languages we give a definition of one-counter languages. we show that the smallest full afl containing this family is principal with full generator d'@@@@ @@@@, the semi-dyck language on two letters. we then give without the proof, which shall be published elsewhere, our main result: an iteration theorem for one-counter languages that yields several corollaries.
modified log-sobolev inequalities, mixing and hypercontractivity. motivated by (the rate of information loss or) the rate at which the entropy of an ergodic markov chain relative to its stationary distribution decays to zero, we study modified versions of the standard logarithmic sobolev inequality in the discrete setting of finite markov chains and graphs. these inequalities turn out to be weaker than the standard log-sobolev inequality, but stronger than the poincare' (spectral gap) inequality. we also derive a hypercontractivity formulation equivalent to our main modified log-sobolev inequality which might be of independent interest. finally we show that, in contrast with the spectral gap, for bounded degree expander graphs various log-sobolev-type constants go to zero with the size of the graph.
a linear time algorithm for finding tree-decompositions of small treewidth. in this paper, we give for constant $k$ a linear-time algorithm that, given a graph $g=(v,e)$, determines whether the treewidth of $g$ is at most $k$ and, if so, finds a tree-decomposition of $g$ with treewidth at most $k$. a consequence is that every minor-closed class of graphs that does not contain all planar graphs has a linear-time recognition algorithm. another consequence is that a similar result holds when we look instead for path-decompositions with pathwidth at most some constant $k$.
some unexpected expected behavior results for bin packing we study the asymptotic expected behavior of the first fit and first fit decreasing bin packing algorithms applied to items chosen uniformly from the interval (0,u], u &le; 1. our results indicate that the algorithms perform even better than previously expected.
pseudorandom generators for low degree polynomials. we investigate constructions of pseudorandom generators that fool polynomial tests of degree d in m variables over finite fields f. our main construction gives a generator with seed length o(d4 log m (1 + log(d ⁄ ε) ⁄ log log m) + log |f|) bits that achieves arbitrarily small bias ε and works whenever |f| is at least polynomial in d, log m, and 1⁄ε. we also present an alternate construction that uses a seed that can be described by o(c2d8m6⁄(c-2) log(d⁄ε) + log |f|) bits (more precisely, o(c2d8m6⁄(c-2)) field elements, each chosen from a set of size poly(cd⁄ε), plus two field elements ranging over all of f), works whenever |f| is at least polynomial in c, d, and 1⁄ε, and has the property that every element of the output is a function of at most c field elements in the input. both generators are computable by small arithmetic circuits. the main tool used in the construction is a reduction that allows us to transform any "dense" hitting set generator for polynomials into a pseudorandom generator.
divide-and-conquer in multidimensional space we investigate a divide-and-conquer technique in multidimensional space which decomposes a geometric problem on n points in k dimensions into two problems on n/2 points in k dimensions plus a single problem on n points in k&minus;1 dimension. special structure of the subproblems is exploited to obtain an algorithm for finding the two closest of n points in 0(n log n) time in any dimension. related results are discussed, along with some conjectures and unsolved geometric problems.
an area-maximum edge length tradeoff for vlsi layout we construct an n-node graph g which has (i) a layout with area o(n) and maximum edge length o(n1/2), (ii) a layout with area o(n5/4) and maximum edge length o(n1/4). we prove for 1 &le; f(n) &le; o(n1/8) that any layout for g with area nf(n) has an edge of length &ohgr;(n1/2/f (n) &bull;log n). hence g has no layout which is optimal with respect to both measures.
balanced allocations: the heavily loaded case. we investigate balls-into-bins processes allocating $m$ balls into $n$ bins based on the multiple-choice paradigm. in the classical single-choice variant each ball is placed into a bin selected uniformly at random. in a multiple-choice process each ball can be placed into one out of $d \ge 2$ randomly selected bins. it is known that in many scenarios having more than one choice for each ball can improve the load balance significantly. formal analyses of this phenomenon prior to this work considered mostly the lightly loaded case, that is, when $m \approx n$. in this paper we present the first tight analysis in the heavily loaded case, that is, when $m \gg n$ rather than $m \approx n$.the best previously known results for the multiple-choice processes in the heavily loaded case were obtained using majorization by the single-choice process. this yields an upper bound of the maximum load of bins of $m/n + {\mbox{$\cal o$}}(\sqrt{m \ln n \,/\, n})$ with high probability. we show, however, that the multiple-choice processes are fundamentally different from the single-choice variant in that they have "short memory." the great consequence of this property is that the deviation of the multiple-choice processes from the optimal allocation (that is, the allocation in which each bin has either $\lfloor m/n \rfloor$ or $\lceil m/n \rceil$ balls) does not increase with the number of balls as in the case of the single-choice process. in particular, we investigate the allocation obtained by two different multiple-choice allocation schemes, the greedy scheme due to azar et al. and the always-go-left scheme due to vöcking. we show that these schemes result in a maximum load of only $m/n + {\mbox{$\cal o$}}(\ln \ln n)$ with high probability. all our detailed bounds on the maximum load are tight up to an additive constant.furthermore, we investigate the two multiple-choice algorithms in a comparative study. we present a majorization result showing that the always-go-left scheme obtains a better load balancing than the greedy scheme for any choice of $n$, $m$, and $d$.
isotopic implicit surface meshing. this paper addresses the problem of piecewise linear approximation of implicit surfaces. we first give a criterion ensuring that the zero-set of a smooth function and the one of a piecewise linear approximation of it are isotopic. then, we deduce from this criterion an implicit surface meshing algorithm certifying that the output mesh is isotopic to the actual implicit surface. this is the first algorithm achieving this goal in a provably correct way.
tree-walking automata do not recognize all regular languages. tree-walking automata are a natural sequential model for recognizing tree languages. every tree language recognized by a tree-walking automaton is regular. in this paper, we present a tree language which is regular but not recognized by any (nondeterministic) tree-walking automaton. this settles a conjecture of engelfriet, hoogeboom and van best. moreover, the separating tree language is definable already in first-order logic over a signature containing the left-son, right-son and ancestor relations.
reconstructing a three-dimensional model with arbitrary errors. a number of current technologies allow for the determination of interatomic distance information in structures such as proteins and rna. thus, the reconstruction of a three-dimensional set of points using information about its interpoint distances has become a task of basic importance in determining molecular structure. the distance measurements one obtains from techniques such as nmr are typically sparse and error-prone, greatly complicating the reconstruction task. many of these errors result in distance measurements that can be safely assumed to lie within certain fixed tolerances. but a number of sources of systematic error in these experiments lead to inaccuracies in the data that are very hard to quantify; in effect, one must treat certain entries of the measured distance matrix as being arbitrarily &ldquo;corrupted.&rdquo;the existence of arbitrary errors leads to an interesting sort of error-correction problem&mdash;how many corrupted entries in a distance matrix can be efficiently corrected to produce a consistent three-dimensional structure? for the case of an n &times; n matrix in which every entry is specified, we provide a randomized algorithm running in time o(n log n) that enumerates all structures consistent with at most (1/2-&egr;)n errors per row, with high probability. in the case of randomly located errors, we can correct errors of the same density in a sparse matrix-one in which only a &bgr; fraction of the entries in each row are given, for any constant &bgr;gt;0.
on the expected behaviour of disjoint set union algorithms we show that the expected time of the weighted quickfind (qfw) disjoint set union and find algorithm to perform (n - 1) randomly chosen unions is cn + o(n/log n), where c = 2.0847 &hellip;. this implies, through an observation of tarjan and van leeuwen, linear expected time bounds to perform o(n) unions and finds for a class of other union -find algorithms. we also prove that the expected time of the unweighted quickfind (qf) algorithm is n2/8 + o(n(log n)2), and set the several related open questions of knuth and sch&ouml;nhage.
finding smooth integers in short intervals using crt decoding. we present a new algorithm for crt list decoding. an instance of the, crt list decoding problem consists of integers b, 〈p1, ..., pn〉 and 〈r1, ..., rn〉, where p1 < p2 < ... < pn is a sequence of relatively prime integers. the crt list decoding problem is to find all positive integers x < b such that x = ri mod pi for all but e values of i ∈ {1, ..., n}. suppose b = πi=1r pi for some integer k. goldreich, ron, and sudan (in "proc. of stoc'99", pp. 225-234, 1999) recently gave several applications for this problem and presented the first efficient algorithm that works whenever e (approximately) satisfies e < n - √2kn log pn/log p1. our new algorithm achieves the stronger bound e < n - √kn log pn/log p1 (approximately). the improvement is significant when k is relatively close to n, e.g. k > n/3. the bounds we obtain are similar to the bounds obtained by guruswami and sudan for reed-solomon list decoding. hence, our algorithm reduces the gap between crt list decoding and list decoding of reed-solomon codes. in addition, we give a new application for crt list decoding: finding smooth integers in short intervals. problems of this type come up in several algorithms for factoring large integers. we define and solve a generalized crt list decoding problem and discuss how it might be used within the quadratic sieve factoring method.
a completeness technique for d-axiomatizable semantics in this paper, we show that by dropping the restrictions on interpretations of arbitrary programs and requiring only that very natural deductive systems are sound, we get classes of semantics which give good representations of program behavior and are more well-suited for applications involving an axiomatic approach (for example program verification). in addition, by tying the restrictions on the behavior of arbitrary programs or specified axiom schema, we get both a powerful formal tool and properties more widely used specifications lack such as compactness and completeness. completeness is a very desirable property. it is fairly straightforward to show given any reasonable deductive system d for a class of models a that pr(d) @@@@ th(a) . but given an application such as program verification, if it is not true that th(a) @@@@ pr(d) , we may be able to find correct programs which we cannot verify. in this paper we show that by using the &ldquo;axiomatizability&rdquo; of programming constructs, we can obtain a technique for showing completeness results for some of the more widely used variations of pdl. we begin with some definitions.
constructing evolutionary trees in the presence of polymorphic characters. most phylogenetics literature and construction methods based upon characters presume monomorphism (one state per character per species), yet polymorphism (multiple states per character per species) is well documented in both biology and historical linguistics. in this paper we consider the problem of inferring evolutionary trees for polymorphic characters. we show efficient algorithms for the construction of perfect phylogenies from polymorphic data. these methods have been used to help construct the evolutionary tree proposed by warnow, ringe, and taylor for the indo-european family of languages and presented by invitation at the national academy of sciences in november 1995.
quasi-realtime languages-extended abstract quasi-realtime languages are the languages accepted by nondeterministic multitape turing machines in real time. the family of quasi-realtime languages forms an abstract family of languages closed under intersection, linear erasing, and reversal. it is identical with the family of languages accepted by nondeterministic multitape turing machines in linear time. every quasi-realtime language can be accepted in real time by a non-deterministic one stack, one pushdown store machine, and can be expressed as the length-preserving homomorphic image of the intersection of three context-free languages.
tape- and time-bounded turing acceptors and afls: extended abstract complexity classes of formal languages defined by time- and tape-bounded turing acceptors are studied with the aim of showing sufficient conditions for these classes to be afls and to be principal afls.
intersections of linear context-free languages and reversal-bounded multipushdown machines (extended abstract) the purpose of this paper is to establish the following result. theorem 3.1. let l be a language. the following are equivalent: (i) l is accepted by a nondeterministic multipushdown acceptor which operates in such a way that in every accepting computation each pushdown store makes at most a bounded number of reversals and which runs in linear time; (ii) l is accepted by a nondeterministic multipushdown acceptor which operates in such a way that in every accepting computation each pushdown store makes at most one reversal and which runs in real time; (iii) l is the length-preservlng homomorphie image of the intersection of some finite number of linear context-free languages; (iv) l is accepted by a nondeterministlc acceptro with three pushdown stores which operates in such a way that in every computation each pushdown store makes at most one reversal and which rmls in real time; (v) l is the length-preservlng homomorphic image of the intersection of three linear context-free languages.
linear algorithms to recognize interval graphs and test for the consecutive ones property a matrix of zeroes and ones is said to have the consecutive ones property if there is a permutation of its rows such that the ones in each column appear consecutively. this paper develops a data structure which may be used to test a matrix for the consecutive ones property, and produce the desired permutation of the rows, in linear time. one application of the consecutive ones property is in recognizing interval graphs. a graph is an interval graph if there exists a 1-1 correspondence between its vertices and a set of intervals on the real line such that two vertices are adjacent if and only if the corresponding intervals have a nonempty intersection. fulkerson and gross have characterized interval graphs as those for which the clique versus vertex incidence matrix has the consecutive ones property. in testing this particular matrix for the consecutive ones property we may process the columns in a special order to simplify the algorithm. this yields the interval graph recognition algorithm which is presented in section 2; section 3 indicates how this algorithm may be extended to the general consecutive ones problem.