waashk/dblp huggingface dataset:
the two-processor scheduling problem is in r-nc the two-processor scheduling problem is perhaps the most basic problem in scheduling theory, and several efficient algorithms have been discovered for it. however, these algorithms are inherently sequential in nature. we give a fast parallel (r-nc) algorithm for this problem. interestingly enough, our algorithm for this purely combinatoric-looking problem draws on some powerful algebraic methods.
approximation schemes for clustering problems. let k be a fixed integer. we consider the problem of partitioning an input set of points endowed with a distance function into k clusters. we give polynomial time approximation schemes for the following three clustering problems: metric k-clustering, l 22 k-clustering, and l22 k-median. in the k-clustering problem, the objective is to minimize the sum of all intra-cluster distances. in the k-median problem, the goal is to minimize the sum of distances from points in a cluster to the (best choice of) cluster center. in metric instances, the input distance function is a metric. in l 22 instances, the points are in r d and the distance between two points x,y is measured by x&minus;y 22 (notice that (r d, &sdot; 22 is not a metric space). for the first two problems, our results are the first polynomial time approximation schemes. for the third problem, the running time of our algorithms is a vast improvement over previous work.
tensor decomposition and approximation schemes for constraint satisfaction problems. the only general class of max-rcsp problems for which polynomial time approximation schemes (ptas) are known are the dense problems. in this paper, we give ptas's for a much larger class of weighted max-rcsp problems which includes as special cases the dense problems and, for r = 2, all metric instances (where the weights satisfy the triangle inequality) and quasimetric instances; for r > 2, our class includes a generalization of metrics. our algorithms are based on low-rank approximations with two novel features: (1) a method of approximating a tensor by the sum of a small number of "rank-1" tensors, akin to the traditional singular value decomposition (this might be of independent interest) and (2) a simple way of scaling the weights. besides max-rcsp problems, we also give ptas's for problems with a constant number of global constraints such as maximum weighted graph bisection and some generalizations.
random instances of a graph coloring problem are hard np-complete problems should be hard on some (may be extremely rare) instances. but on generic instances many such problems (especially related to random graphs) have been proven easy. we show the intractability of random instances of a graph coloring problem by modifying the np-completeness theorem.
properties that characterize logcfl two properties, called semi-unboundedness, and polynomial proof-size, are identified as key properties shared by the definitions of logcfl on several models of computations. the semi-unboundedness property leads to the definition of new models of computation based on unbounded fan-in circuits. these are circuits obtained from unbounded fan-in circuits by restricting the fan-in of gates of one type. a new characterization of logcfl is obtained on such a model in which the fan-in of the and gates are bounded by a constant. this property also suggests new characterizations of logcfl on the following models: alternating turing machines [cks81], nondeterministic auxiliary pushdown automata [co71], and bounded fan-in boolean circuits [co85].
randomized speed-ups in parallel computation the following problem is considered: given a linked list of length n, compute the distance of each element of the linked list from the end of the list. the problem has two standard deterministic algorithms: a linear time serial algorithm, and an o((nlog n)/p + log n) time parallel algorithm using p processors. a known conjecture states that it is impossible to design an o(log n) time deterministic parallel algorithm that uses only n/log n processors. we present three randomized parallel algorithms for the problem. one of these algorithms runs almost-surely in time of o(n/p + log nlog*n) using p processors on an exclusive-read exclusive-write parallel ram.
almost optimal permutation routing on hypercubes. this paper deals with permutation routing on hypercube networks in the store-and-forward model. we introduce the first (on-line and off-line) algorithms routing any permutation on the d-dimensional hypercube in d+o(d) steps. the best previously known results were 2d+o(d) (oblivious on-line) and 2d-3 (off-line). in particular, we presenta randomized, oblivious on-line algorithm with routing time d + o(d/log d),a matching lower bound of d + &ohgr;(d/log d) for (randomized) oblivious on-line routing, anda deterministic, off-line algorithm with routing time d+o(\sqrt{d\log d}).previous algorithms lose a factor of two mainly because packets are first sent to intermediate destinations in order to resolve congestion. as a consequence, the maximum path length becomes 2d - o(d). our algorithms use intermediate destinations as well, but we introduce a simple, elegant trick ensuring that the routing paths are not stretched too much. in fact, we achieve small congestion using paths of length at most d.the main focus of our work, however, lies on the scheduling aspect. on one hand, we investigate well-known and practical scheduling policies for on-line routing, namely farthest-to-go and nearest-to-origin. on the other hand, we present a new off-line scheduling scheme that is based on frugal colorings of multigraphs. this scheme might be of interest for other sparse scheduling problems, too.
some structural properties of polynomial reducibilities and sets in np in this abstract and discussion of forthcoming papers, we will be concerned with variations on a common theme: without assuming a solution to p vs np, what can one say of a general nature that relates structural properties of general classes of sets in np to reducibilities among these sets? by &ldquo;structural&rdquo; we mean, in ways that will become clearer as we proceed, properties which arise from general definitions rather than properties which may arise from a perhaps more &ldquo;natural&rdquo; computational point of view. although quite a bit is known about such questions relative to oracles or relative to the assumption that p @@@@ np, in so far as possible we wish to obtain absolute results; that is results which are about sets in np (not relativized) and which can be obtained without assuming a solution to p vs np. in a final section summarizing our results we will make some general comments about the historical antecedents and possible future significance of this approach.
speed-ups by changing the order in which sets are enumerated (preliminary version) in a suitably general context, the following analogue of the blum speed-up theorem is proven: there are some infinite sets which are so difficult to enumerate that, given any order for enumerating the set, there is some other order, and some one method of enumerating the set in this second order which is much faster than any method of enumerating the set in the first ordering. it may be possible to interpret this result as a statement about the relative merits of &ldquo;hardware&rdquo; vs. &ldquo;programming&rdquo; speed-ups. the proof itself is one of the first nontrivial applications of priority methods to questions of computational complexity. as such, it perhaps represents an advance in bringing the results and techniques of contemporary &ldquo;pure&rdquo; recursion theory to bear on questions of computational complexity. in this paper we shall prove, in a suitably general context, the following analogue of the blum speed-up theorem, [b1]: there are some infinite sets which are so difficult to enumerate that, given any order for enumerating the set, there is some other order, and some one method of enumerating the set in this second order which is much faster than any method of enumerating the set in the first ordering.
an algebraic theory of recursive definitions and recursive languages this is the introductory paper in a series devoted to a general algebraic theory of &ldquo;recursive definitions&rdquo; and &ldquo;recursive languages&rdquo;. in this paper we present the fundamental concepts and theorems concerning the basic structure (basic syntax), the semantics and the combination and manipulation of &ldquo;recursive definitions&rdquo; and the closure properties of &ldquo;recursive languages&rdquo;. the development is carried out within the framework of category theory and lattice theory. to illustrate the generality of the approach and our results we show how they apply directly to the specific examples of &ldquo;recursive languages&rdquo; of (generalized) context-free grammars, turing machines, and flowcharts.
formal models for some features of programming languages in this paper we attempt to tighten the connections between classical mathematics, automata theory, and the theory of programming languages. formal linguistic objects corresponding to programs are defined via sets of functional equations; two interpretations of such an object are given, one in classical mathematics, and one in terms of an abstract machine that executes the program. within this framework we examine flow charts, recursion, parameterization, and declaration.
from algebras to programming languages this paper gives an informal presentation of constructions which, when combined, enable one to construct high level programming languages from algebras or, equivalently, from collections of primitive operations on some set (e.g. from the arithmetic, vector and logical operations on the set of integers, integer vectors, and truth values). using this approach one can construct languages with block structure, procedures, procedure calls by both name and value, plus essentially simpler concepts such as assignment statements and conditional transfers. the constructions are algebraic in the sense that they are constructions on algebras which yield new algebras. however, for the sake of comprehensibility, we present them in this paper in a more informal manner as constructions on &ldquo;black boxes&rdquo;. this paper is a continuation of work presented earlier in [3] and [4] and owes much to the joint work to be reported in [5].
new upper and lower bounds for randomized and quantum local search. local search problem, which finds a local minimum of a black-box function on a given graph, is of both practical and theoretical importance to combinatorial optimization, complexity theory and many other areas in theoretical computer science. in this paper, we study the problem in the randomized and quantum query models and give new lower and upper bound techniques in both models.the lower bound technique works for any graph that contains a product graph as a subgraph. applying it to the boolean hypercube (0, 1)n and the constant dimensional grids [n]d, two particular product graphs that recently drew much attention, we get the following tight results: rls((0, 1)n) = θ(2n/2n1/2), qls((0, 1)n) = θ(2n/3n1/6); rls([n]d) = θ(nd/2), ∀ d ≥ 4, qls([n]d) = θ(nd/3), ∀ d ≥ 6. here rls(g) and qls(g) are the randomized and quantum query complexities of local search on g, respectively. these improve the previous results by aaronson [2], ambainis (unpublished) and santha and szegedy [20].our new algorithms work well when the underlying graph expands slowly. as an application to [n]2, a new quantum algorithm using o(☂n(log log n)1.5) queries is given. this improves the previous best known upper bound of o(n2/3) (aaronson, [2]), and implies that local search on grids exhibits different properties in low dimensions.
on the complexity of the extended string-to-string correction problem the extended string-to-string correction problem [esscp] is defined as the problem of determining, for given strings a and b over alphabet v, a minimum-cost sequence s of edit operations such that s(a) &equil; b. the sequence s may make use of the operations: change, insert, delete and swaps, each of constant cost wc, wi, wd, and ws respectively. swap permits any pair of adjacent characters to be interchanged. the principal results of this paper are: (1) a brief presentation of an algorithm (the cellar algorithm) which solves esscp in time &oslash;(&brvbar;a&brvbar;* &brvbar;b&brvbar;* &brvbar;v&brvbar;s*s), where s &equil; min(4wc, wi+wd)/ws + 1; (2) presentation of polynomial time algorithms for the cases (a) ws &equil; 0, (b) ws > 0, wc&equil; wi&equil; wd&equil; @@@@; (3) proof that esscp, with wi < wc &equil; wd &equil; @@@@, 0 < ws < @@@@, suitably encoded, is np-complete. (the remaining case, ws&equil; @@@@, reduces esscp to the string-to-string correction problem of [1], where an &oslash;( &brvbar;a&brvbar;* &brvbar;b&brvbar;) algorithm is given.) thus, &ldquo;almost all&rdquo; esscp's can be solved in deterministic polynomial time, but the general problem is np-complete.
linear degree extractors and the inapproximability of max clique and chromatic number. a randomness extractor is an algorithm which extracts randomness from a low-quality random source, using some additional truly random bits. we construct new extractors which require only log n + o(1) additional random bits for sources with constant entropy rate. we further construct dispersers, which are similar to one-sided extractors, which use an arbitrarily small constant times log n additional random bits for sources with constant entropy rate. our extractors and dispersers output 1-α fraction of the randomness, for any α>0.we use our dispersers to derandomize results of hastad [23] and feige-kilian [19] and show that for all ε>0, approximating max clique and chromatic number to within n1-ε are np-hard. we also derandomize the results of khot [29] and show that for some γ > 0, no quasi-polynomial time algorithm approximates max clique or chromatic number to within n/2(log n)1-γ, unless np = p.our constructions rely on recent results in additive number theory and extractors by bourgain-katz-tao [11], barak-impagliazzo-wigderson [5], barak-kindler-shaltiel-sudakov-wigderson [6], and raz [36]. we also simplify and slightly strengthen key theorems in the second and third of these papers, and strengthen a related theorem by bourgain [10].
characterization of flowchartable recursions (short version) in this paper we give new characterizations for the flowchartability of recursive functionals. the general question of flowchartability is recursively undecidable. we present here an effective map from recursions to representatives for which the question is decidable. the decision provides a good approximation to a characterization for general flowchartability in the following senses: (1) if a representative is flowchartable then the recursions it represents are, and (2) there is a straightforward method of flowcharting, depending only on recursion structure, such that a recursion is flowchartable by this method if and only if its representative is flowchartable. the main results of the paper are (1) that such a representative is flowchartable if, and only if, it is simple or linear, and (2) that, when the context is restricted so that only invertible operations are considered, such a representative is flowchartable if, and only if, it is nested. the terms &ldquo;simple&rdquo; and &ldquo;linear&rdquo; have been defined in previous papers in the area, although they are extended slightly in this one. the term nested is introduced here. simple, linear, and nested recursions are very easy to identify by inspection.
an unusual application of program-proving an inductive proof in mathematics may often be expressed as an algorithm and a proof that the algorithm is correct. especially when the proof proceeds by cases, a recursive pattern-matching language, such as hewitt's matchless, is a felicitous language for writing the algorithm. we use this idea to prove a new mathematical result, which itself is of interest in computer science. we define objects called k-models. our main theorem is a necessary and sufficient condition for a k-model to be the restriction of a k+1-model.
a new incompleteness result for hoare's system a structure a is presented for which hoare's formal system for partial correctness is incomplete, even if the entire first-order theory of a is included among the axioms. it follows that the language of first-order logic is insufficient to express all loop invariants. the implications of this result for program-proving are discussed.
estimating true evolutionary distances between genomes. evolution operates on whole genomes by operations that change the order and strandedness of genes within the genomes. this type of data presents new opportunities for discoveries about deep evolutionary rearrangement events, provided that sufficiently accurate methods can be developed to reconstruct evolutionary trees in these models [3, 6, 7, 15, 17]. a necessary component of any such method is the ability to accurately estimate true evolutionary distances between two genomes, which is the number of rearrangement events that took place in the evolutionary history between them. we present a new technique called iebp, for estimating the true evolutionary distance between two genomes, whether signed or unsigned, circular or linear, and for any relative probabilities of rearrangement event classes. the method is highly accurate, as our simulation study shows. this simulation study also shows that the distance estimation technique improves the accuracy of the phylogenetic trees reconstructed by the popular distance-based method, neighbor joining [1, 20].
predecessor machines and regressing functions a predecessor machine is a random-access machine with a predecessor operation (i.e., an instruction which subtracts 1 from the contents of a memory cell), but with no operation which can increase the contents of a cell. a regressing function is a total function which never yields an output larger than the maximum of its inputs and a constant. unlike the situation for random-access machines with a successor operation, it does not matter whether or not predecessor machines with loop control also have conditional transfer instructions. furthermore, the class of functions computable by predecessor loop machines consists of exactly those regressing functions which are computable by a deterministic linear-bounded automaton. some generalized predecessor machines are also considered.
lower bounds for 2-dimensional range counting. proving lower bounds for range queries has been an active topic of research since the late 70s, but so far nearly all results have been limited to the (rather restrictive) semigroup model. we consider one of the most basic range problem, orthogonal range counting in two dimensions, and show almost optimal bounds in the group model and the (holy grail) cell-probe model. specifically, we show the following bounds, which were known in the semigroup model, but are major improvements in the more general models:* in the group and cell-probe models, a static data structure of size n lgo(1) n requires omega(lg n lglg n) time per query. this is an exponential improvement over previous bounds, and matches known upper bounds.* in the group model, a dynamic data structure takes time omega((lg n lglg n)2) per operation. this is close to the o(lg2 n) upper bound, where as the previous lower bound was omega(lg n). proving such (static and dynamic) bounds in the group model has been regarded as an important challenge at least since [fredman, jacm 1982] and [chazelle, focs 1986].
quantum algorithms for solvable groups. in this paper we give a polynomial-time quantum algorithm for computing orders of solvable groups. several other problems, such as testing membership in solvable groups, testing equality of subgroups in a given solvable group, and testing normality of a subgroup in a given solvable group, reduce to computing orders of solvable groups and therefore admit polynomial-time quantum algorithms as well. our algorithm works in the setting of black-box groups, wherein none of these problems have polynomial-time classical algorithms. as an important byproduct, our algorithm is able to produce a pure quantum state that is uniform over the elements in any chosen subgroup of a solvable group, which yields a natural way to apply existing quantum algorithms to factor groups of solvable groups.
some new results on node-capacitated packing of a-paths. in this paper we propose a (semi-strongly) polynomial time algorithm to find a maximum packing subject to node-capacities, and thus we obtain a generalization of keijsper, pendavingh and stougie algorithm concerning edge-capacities. our method is based on gerards' strongly polynomial time algorithm to find a maximum b-matching in a graph, which is based on a so-called proximity lemma. our node-capacitated a-path packing algorithm first constructs a maximum fractional packing by using an ellipsoid method subroutine, then takes its integer part to obtain a near-optimal integral packing, and finally we construct a maximum integer packing by a short sequence of augmentations. this short sequence of augmentations is constructed by applying the version of gerards' proximity lemma, specially formulated for the node-capacitated a-path packing problem. in addition, we also state some related results on the fractional packing problem. we prove the primal- and dual integrality of the corresponding linear program. we mention that the fractional packing problem reduces to the matroid fractional matching problem.
zero-knowledge against quantum attacks. this paper proves that several interactive proof systems are zero-knowledge against general quantum attacks. this includes the well-known goldreich-micali-wigderson classical zero-knowledge protocols for graph isomorphism and graph 3-coloring (assuming the existence of quantum computationally concealing commitment schemes in the second case). also included is a quantum interactive proof system for a complete problem for the complexity class of problems having honest verifier quantum statistical zero-knowledge proofs, which therefore establishes that honest verifier and general quantum statistical zero-knowledge are equal: $\mathrm{qszk}= \mathrm{qszk}_{\mathrm{hv}}$. previously no nontrivial interactive proof systems were known to be zero-knowledge against quantum attacks, except in restricted settings such as the honest verifier and common reference string models. this paper therefore establishes for the first time that true zero-knowledge is indeed possible in the presence of quantum information and computation.