waashk/dblp huggingface dataset:
computing with polynomials given by straight-line programs i: greatest common divisors we develop algorithms on multivariate polynomials represented by straight-line programs for the greatest common divisor problem and conversion to sparse representation. our algorithms are in random polynomial-time for the usual coefficient fields and output with controllably high probability the correct result which for the gcd problem is a straight-line program determining the gcd of the inputs and for the conversion algorithm is the sparse representation of the input. the algorithms only require an a priori bound for the total degrees of the inputs. over rational numbers the conversion algorithm also needs a bound on the size of the polynomial coefficients. as specializations we get, e.g., random polynomial-time algorithms for computing the sparse gcd of polynomial determinants or for computing the sparse solution of a linear system whose coefficients are given by formulas.
single-factor hensel lifting and its application to the straight-line complexity of certain polynomials three theorems are presented that establish polynomial straight-line complexity for certain operations on polynomials given by straight-line programs of unbounded input degree. the first theorem shows how to compute a higher order partial derivative in a single variable. the other two theorems impose the degree of the output polynomial as a parameter of the length of the output program. first it is shown that if a straight-line program computes an arbitrary power of a multivariate polynomial, that polynomial also admits a polynomial bounded straight-line computation. second, any factor of a multivariate polynomial given by a division-free straight-line program with relatively prime co-factor also admits a straight-line computation of length polynomial in the input length and the degree of the factor. this result is based on a new hensel lifting process, one where only one factor image is lifted back to the original factor. as an application we get that the greatest common divisor of polynomials given by a division-free straight-line program has polynomial straight-line complexity in terms of the input length and its own degree.
fault-tolerant scheduling. we study fault-tolerant multiprocessor scheduling under the realistic assumption that the occurrence of faults cannot be predicted. the goal in these problems is to minimize the delay incurred by the jobs. since this is an online problem we use competitive analysis to evaluate possible algorithms. for the problems of minimizing the makespan and minimizing the average completion time (for static release times), we give nonclairvoyant algorithms (both deterministic and randomized) that have provably asymptotically optimal competitive ratios. the main tool used by these algorithms to combat faults is redundancy. we also show that randomization has the same effect as redundancy.
deterministic extractors for small-space sources. we give polynomial-time, deterministic randomness extractors for sources generated in small space, where we model space s sources on (0,1)n as sources generated by width 2s branching programs: for every constant δ>0, we can extract .99 δ n bits that are exponentially close to uniform (in variation distance) from space s sources of min-entropy δ n, where s=ω(n). in addition, assuming an efficient deterministic algorithm for finding large primes, there is a constant η > 0 such that for any δ>n-η, we can extract m=(δ-δ)n bits that are exponentially close to uniform from space s sources with min-entropy δ n, where s=ω(β3 n). previously, nothing was known for δ ≤ 1/2, even for space 0.our results are obtained by a reduction to a new class of sources that we call independent-symbol sources, which generalize both the well-studied models of independent sources and symbol-fixing sources. these sources consist of a string of n independent symbols over a d symbol alphabet with min-entropy k. we give deterministic extractors for such sources when k is as small as polylog(n), for small enough d.
improved algorithms for integer programming and related lattice problems the integer programming problem is: given m&times;n and m&times;l matrices a and b respectively of integers, find whether, there exists an all integer n&times;l vector x satisfying the m inequalities a&times;&le;b. in settling an important open problem, lenstra (1981) showed in an elegant way that when n, the number of dimensions is fixed, there is a polynomial-time algorithm to solve this problem. his algorithm achieves a running-time of 0(cn3&bull;p(length of data)) where p is some polynomial and c a constant independent of n. since such an algorithm has several important applications - cryptography (shamir (1982)), diophantine approximations (lagarias (1982)), coding theory (conway and sloane (1982), etc. it is important to improve the running time. we present an algorithm here that has a running time of 0(n9nl log l) where l is the length of the input. whereas lenstra's algorithm in the worst case reduces an n-dimensional problem to cn2&minus;(n&minus;) dimensional problems, our algorithm effectively reduces an n-dimensional problem to at most polynomially many (n&minus;1) dimensional problems, thus achieving our time bound. the algorithm we propose, first finds a &ldquo;more orthogonal&rdquo; basis for a lattice (see the next section for the definition of a lattice) than those of lenstra (1981) and lenstra, lenstra and lovasz (1982), but in time 0(ndn poly (length of input)). it then uses an enumeration technique to solve integer programming and related problems. while this paper presents mainly the theoretical improvements that can be made in the algorithms, we discuss in section 6 why in practice our estimates of running time may be overly pessimistic. the last part of the paper discusses some complexity issues. it is an interesting open problem as to whether finding the euclidean shortest non-zero vector of a given lattice is np-hard. (see lenstra (1981), van emde boas (1981) and lagarias (1982)).
alternation and the power of nondeterminism while nondeterminism is widely beleived to be more powerful than determinism in various contexts (the most famous being the conjecture that np strictly contains p), no proof of the added power of nondeterminism is available for any significant issue. the weaker conjecture (than np strictly contains p) that there is a language accepted by a nondeterministic linear time bounded multitape turing machine that cannot be accepted by a deterministic linear time bounded multi-tape tm still seems quite hard (paul 1982). the aim of this paper is to show how the existance of the polynomial-time hierarchy of meyer and stockmeyer(1972) and the related concept of alternation (chandra, kozen and stockmeyer(1981)) can be exploited to prove the power of nondeterminism over determinism in some contexts. it is hoped that this approach may be useful in proving stronger results.
the orbit problem is decidable the &ldquo;accessibility problem&rdquo; for linear sequential machines (harrison [7]) is the problem of deciding whether there is an input x that sends such a machine from a given state q1 to a given state q2. harrison [7] showed that this problem is reducible to the &ldquo;orbit problem:&rdquo; given a&egr;qn&times;n does there exist i&egr;n such that aix &equil;y.* we will call this the &ldquo;orbit problem&rdquo; because the question can be rephrased as: does y belong to the orbit of x under a where the &ldquo;orbit of x under a&rdquo; is the set {aix: i &equil; 0,1,2,...}. (a0 is the identity matrix i.) in harrison's original problem the elements of a,x, and y were members of an arbitrary &ldquo;computable&rdquo; field. in view of the lack of structure of such fields, we study only the rationals. shank [13] proves that the orbit problem is decidable for the rational case when n&equil;2. the current paper establishes that for the general rational case, the problem is decidable - and in fact polynomial-time decidable. we wish to give a brief idea of our approach to the problem.
implicit representation of graphs how to represent a graph in memory is a fundamental data structuring question. in the usual representations of an n-node graph, the names of the nodes (i.e. integers from 1 to n) betray nothing about the graph itself. indeed, the names (or labels) on the n nodes are just logn bit place holders to allow data on the edges to code for the structure of the graph. in our scenario, there is no such waste. by assigning &ogr;(logn) bit labels to the nodes, we completely code for the structure of the graph, so that given the labels of two nodes we can test if they are adjacent in time linear in the size of the labels. furthermore, given an arbitrary original labeling of the nodes, we can find structure coding labels (as above) that are no more than a small constant factor larger than the original labels. these notions are intimately related to vertex induced universal graphs of polynomial size. for example, we can label planar graphs with structure coding labels of size < 4logn. this implies the existence of a graph with n4 nodes that contains all n-node planar graphs as vertex induced subgraphs (it was not previously known that this class had polynomial sized universal graphs). the theorems on finite graphs extend to a theorem about the constrained labeling of infinite graphs.
learning with attribute costs. we study an extension of the "standard" learning models to settings where observing the value of an attribute has an associated cost (which might be different for different attributes). our model assumes that the correct classification is given by some target function f from a class of functions cal f; most of our results discuss the ability to learn a clause (an or function of a subset of the variables) in various settings:offline: we are given both the function f and the distribution d that is used to generate an input x. the goal is to design a strategy to decide what attribute of x to observe next so as to minimize the expected evaluation cost of f(x). (in this setting there is no "learning" to be done but only an optimization problem to be solved; this problem to be np-hard and hence approximation algorithms are presented.)distributional online: we study two types of "learning" problems; one where the target function f is known to the learner but the distribution d is unknown (and the goal is to minimize the expected cost including the cost that stems from "learning" d), and the other where f is unknown (except that f∈cal f) but d is known (and the goal is to minimize the expected cost while limiting the prediction error involved in "learning" f).adversarial online: we are given f, however the inputs are selected adversarially. the goal is to compare the learner's cost to that of the best fixed evaluation order (i.e., we analyze the learner's performance by a competitive analysis).
dynamic rectangular intersection with priorities. we present efficient data structures to maintain dynamic set of rectangles, each with priority assigned to it, such that we can efficiently find the rectangle of maximum priority containing a query point. our data structures support insertions and deletions of rectangles. in one dimension, when rectangles are intervals, our most efficient data structure supports queries and insertions in o(log n) time, deletions in o(log n loglog n) time and requires linear space. when intervals are guaranteed to be nonoverlapping (but one can be nested within the other) we obtain a simpler data structure that supports all operations in o(log n) time.
meldable heaps and boolean union-find. in the classical meldable heap data type we maintain an item-disjoint collection of heaps under the operations find-min, insert, delete, decrease-key, and meld. in the usual definition decrease-key and delete get the item and the heap containing it as parameters. we consider the modified problem where decrease-key and delete get only the item but not the heap containing it. we show that for this problem one of the operations find-min, decrease-key, or meld must take non-constant time. this is in contrast with the original data type in which data structures supporting all these three operations in constant time are known (both in an amortized and a worst-case setting).to establish our results for meldable heaps we consider a weaker version of the union-find problem that is of independent interest, which we call boolean union-find. in the boolean union-find problem the find operation is a binary predicate that gets an item x and a set a and answers positively if and only if &khgr; &egr; a. we prove that the lower bounds which hold for union-find in the cell probe model hold for boolean union-find as well.we also suggest new heap data structures implementing the modified meldable heap data type that are based on redundant binary counters. our data structures have good worst-case bounds. the best of our data structures matches the worst-case lower bounds which we establish for the problem. the simplest of our data structures is an interesting generalization of binomial queues.
purely functional representations of catenable sorted lists. the power of purely functional programming in the construction of data structures has received much attention, not only because functional languages have many desirable properties, but because structures built purely functionally are automatically {\em fully persistent}: any and all versions of a structure can coexist indefinitely. recent results illustrate the surprising power of pure functionality. one such result was the development of a representation of double-ended queues with catenation that supports all operations, including catenation, in worst-case constant time~\cite{katar}. this paper is a continuation of our study of pure functionality, especially as it relates to persistence. for one purposes, a purely functional data structure is one built only with the lisp functions car, cons, cdr. we explore purely functional representations of sorted lists, implemented as finger search trees. we describe three implementations. the most efficient of these achieves logarithmic access, insertion, and deletion time, and double-logarithmic catenation time. it uses one level of structural bootstrapping to obtain its efficiency. the bounds for find, insert, and delete are the same as the best known bounds for an ephemeral implementation of these operations using finger search trees. the representations we present are the first that address the issues of persistence and pure functionality, and the first for which fast implementations of catenation and split are presented. they are simple to implement and could be efficient in practice, especially for applications that require worst-case time bounds or persistence.
monotone circuits for connectivity require super-logarithmic depth we prove that every monotone circuit which tests st-connectivity of an undirected graph on n nodes has depth &ohgr;(log2n). this implies a superpolynomial (n&ohgr;(log n)) lower bound on the size of any monotone formula for st-connectivity. the proof draws intuition from a new characterization of circuit depth in terms of communication complexity. it uses counting arguments and extremal set theory. within the same framework, we also give a very simple and intuitive proof of a depth analogue of a theorem of krapchenko concerning formula size lower bounds.
a randomized fully polynomial time approximation scheme for the all terminal network reliability problem. the classic all-terminal network reliability problem posits a graph, each of whose edges fails independently with some given probability. the goal is to determine the probability that the network becomes disconnected due to edge failures. this problem has obvious applications in the design of communication networks. since the problem is ${\sharp {\cal p}}$-complete and thus believed hard to solve exactly, a great deal of research has been devoted to estimating the failure probability. in this paper, we give a fully polynomial randomized approximation scheme that, given any n-vertex graph with specified failure probabilities, computes in time polynomial in n and $1/\epsilon$ an estimate for the failure probability that is accurate to within a relative error of $1\pm\epsilon$ with high probability. we also give a deterministic polynomial approximation scheme for the case of small failure probabilities. some extensions to evaluating probabilities of $k$-connectivity, strong connectivity in directed eulerian graphs and $r$-way disconnection, and to evaluating the tutte polynomial are also described. this version of the paper corrects several errata that appeared in the previous journal publication [d. r. karger, siam j. comput., 29 (1999), pp. 492--514].
minimum cuts in near-linear time. we significantly improve known time bounds for solving the minimum cut problem on undirected graphs. we use a "semiduality" between minimum cuts and maximum spanning tree packings combined with our previously developed random sampling techniques. we give a randomized (monte carlo) algorithm that finds a minimum cut in an m-edge, n-vertex graph with high probability in o(m log3 n) time. we also give a simpler randomized algorithm that finds all minimum cuts with high probability in o(m log3 n) time. this variant has an optimal rnc parallelization. both variants improve on the previous best time bound of o(n2 log3 n). other applications of the tree-packing approach are new, nearly tight bounds on the number of near-minimum cuts a graph may have and a new data structure for representing them in a space-efficient manner.
rounding algorithms for a geometric embedding of minimum multiway cut. given an undirected graph with edge costs and a subset ofk=3 nodes calledterminals, a multiway, ork-way, cut is a subset of the edges whose removal disconnects each terminal from the others. the multiway cut problem is to find a minimum-cost multiway cut. this problem is max-snp hard. recently, calinescu et al. (calinescu, g., h. karloff, y. rabani. 2000. an improved approximation algorithm for multiway cut.j. comput. system sci.60(3) 564--574) gave a novel geometric relaxation of the problem and a rounding scheme that produced a (3/2-1/ k)-approximation algorithm.in this paper, we study their geometric relaxation. in particular, we study the worst-case ratio between the value of the relaxation and the value of the minimum multicut (the so-called integrality gap of the relaxation). fork=3, we show the integrality gap is 12/11, giving tight upper and lower bounds. that is, we exhibit a family of graphs with integrality gaps arbitrarily close to 12/11 and give an algorithm that finds a cut of value 12/11 times the relaxation value. our lower bound shows that this is the best possible performance guarantee for any algorithm based purely on the value of the relaxation. our upper bound meets the lower bound and improves the factor of 7/6 shown by calinescu et al.for allk, we show that there exists a rounding scheme with performance ratio equal to the integrality gap, and we give explicit constructions of polynomial-time rounding schemes that lead to improved upper bounds. fork=4 and 5, our best upper bounds are based on computer-constructed rounding schemes (with computer proofs of correctness). for generalk we give an algorithm with performance ratio 1.3438-e k .our results were discovered with the help of computational experiments that we also describe here.
random sampling in residual graphs. consider an n-vertex, m-edge, undirected graph with maximum flow value v. we give a new &otilde;(m+nv)-time maximum flow algorithm based on finding augmenting paths in random samples of the edges of residual graphs. after assigning certain special sampling probabilities to edges in &otilde;(m) time, our algorithm is very simple: repeatedly find an augmenting path in a random sample of edges from the residual graph.
finding nearest neighbors in growth-restricted metrics. most research on nearest neighbor algorithms in the literature has been focused on the euclidean case. in many practical search problems however, the underlying metric is non-euclidean. nearest neighbor algorithms for general metric spaces are quite weak, which motivates a search for other classes of metric spaces that can be tractably searched.in this paper, we develop an efficient dynamic data structure for nearest neighbor queries in growth-constrained metrics. these metrics satisfy the property that for any point q and number r the ratio between numbers of points in balls of radius 2r and r is bounded by a constant. spaces of this kind may occur in networking applications, such as the internet or peer-to-peer networks, and vector quantization applications, where feature vectors fall into low-dimensional manifolds within high-dimensional vector spaces.
dynamic tcp acknowledgement and other stories about e/(e-1). we present the first optimal randomized online algorithms for the tcp acknowledgment problem [5] and the bahncard problem [7]. these problems are well-known to be generalizations of the classical online ski rental problem, however, they appeared to be harder. in this paper, we demonstrate that a number of online algorithms which have optimal competitive ratios of e/(e-1), including these, are fundamentally no more complex than ski rental. our results also suggest a clear paradigm for solving ski rental-like problems.
how good is the goemans-williamson max cut algorithm? the celebrated semidefinite programming algorithm for max cut introduced by goemans and williamson was known to have a performance ratio of at least $\alpha=\frac 2 {\pi} \min_{0
on earthmover distance, metric labeling, and 0-extension. we study the fundamental classification problems 0-extension and metric labeling. a generalization of multiway cut, 0-extension is closely related to partitioning problems in graph theory and to lipschitz extensions in banach spaces; its generalization metric labeling is motivated by applications in computer vision. researchers had proposed using earthmover metrics to get polynomial-time-solvable relaxations for these problems. a conjecture that has attracted much attention recently is that the integrality ratio for these relaxations is constant. we prove (1) that the integrality ratio of the earthmover relaxation for metric labeling is $\omega(\log k)$ (which is asymptotically tight), $k$ being the number of labels, whereas the best previous lower bound on the integrality ratio was only constant; (2) that the integrality ratio of the earthmover relaxation for 0-extension is $\omega(\sqrt{\log k})$, $k$ being the number of terminals (it was known to be $o((\log k)/\log\log k)$), whereas the best previous lower bound was only constant; (3) that for no $\epsilon>0$ is there a polynomial-time $o((\log n)^{1/4-\epsilon})$-approximation algorithm for 0-extension, $n$ being the number of vertices, unless np$\subseteq$dtime$(n^{\mathrm{poly}(\log n)})$, whereas the strongest inapproximability result known before was only max snp-hardness; and (4) that there is a polynomial-time approximation algorithm for 0-extension with performance ratio $o(\sqrt{\mathrm{diam}(d)})$, where $\mathrm{diam}(d)$ is the ratio of the largest to smallest nonzero distances in the terminal metric.
randomized algorithms and pseudorandom numbers randomized algorithms are analyzed as if unlimited amounts of perfect randomness were available, while pseudorandom number generation is usually studied from the perspective of cryptographic security. bach recently proposed studying the interaction between pseudorandom number generators and randomized algorithms. we follow bach's lead; we assume that a (small) random seed is available to start up a simple pseudorandom number generator which is then used for the randomized algorithm. we study randomized algorithms for (1) sorting; (2) selection; and (3) oblivious routing in networks.