waashk/dblp huggingface dataset:
a new polynomial-time algorithm for linear programming we present a new polynomial-time algorithm for linear programming. the running-time of this algorithm is o(n3-5l2), as compared to o(n6l2) for the ellipsoid algorithm. we prove that given a polytope p and a strictly interior point a &egr; p, there is a projective transformation of the space that maps p, a to p', a' having the following property. the ratio of the radius of the smallest sphere with center a', containing p' to the radius of the largest sphere with center a' contained in p' is o (n). the algorithm consists of repeated application of such projective transformations each followed by optimization over an inscribed sphere to create a sequence of points which converges to the optimal solution in polynomial-time.
some connections between nonuniform and uniform complexity classes it is well known that every set in p has small circuits [13]. adleman [1] has recently proved the stronger result that every set accepted in polynomial time by a randomized turing machine has small circuits. both these results are typical of the known relationships between uniform and nonuniform complexity bounds. they obtain a nonuniform upper bound as a consequence of a uniform upper bound. the central theme here is an attempt to explore the converse direction. that is, we wish to understand when nonuniform upper bounds can be used to obtain uniform upper bounds. in this section we will define our basic notion of nonuniform complexity. then we will show how to relate it to more common notions.
efficient pram simulation on a distributed memory machine we present a randomized simulation of a nlog log (n) log (n)-processor shared memory machine (dmm) with optimal expected delay o(log log (n)) per step of simulation. the time bound for the delay is guaranteed with overwhelming probability. the algorithm is based on hashing and uses a novel simulation scheme. the best previous simulations use a simpler scheme based on hashing and have much larger expected delay: &thgr;(log(n)/log log (n)) for the simulation of an n-processor pram on an n processor dmm, and &thgr;(log(n)) in the case where the simulation preserves the processor-time product.
a probabilistic analysis of multidimensional bin packing problems this paper gives probabilistic analyses of two kinds of multidimensional bin packing problems: vector packing and rectangle packing. in the vector packing problem each of the d dimensions can be interpreted as a resource. a given object i consumes aij units of the jth resource, and the objects packed in any given bin may not collectively consume more than one unit of any resource. subject to this constraint, the objects are to be packed into a minimum number of bins. the rectangle packing problem is more geometric in character. the ith object is a d-dimensional box whose jth side is of length aij, and the goal is to pack the objects into a minimum number of cubical boxes of side 1. we study these problems on the assumption that the aij are drawn independently from the uniform distribution over [0,1]. we study a vector packing heuristic called vpack that tries to place two objects in each bin and a rectangle packing heuristic called rpack that tries to pack one object into each of the 2d corners of each bin. we show that each of these heuristics tends to produce packings in which very little of the capacity of the bins is wasted. in the case of rectangle packing, we show that the results can be extended to a wide class of distributions of the piece sizes.
rapid identification of repeated patterns in strings, trees and arrays in this paper we look at a number of matching problems and devise general techniques for attacking such problems. in particular, we describe a strategy for constructing efficient algorithms for solving two types of matching problems. we use this strategy to develop explicit algorithms for these two problems applied to strings (where the patterns are substrings) and arrays (where the patterns are subarrays or blocks). we also develop algorithms for these and related problems for trees, where the patterns are subtrees. certain special cases of these algorithms are also discussed. although we do not claim that these algorithms are optimal, we analyze each algorithm to estimate its computational cost. this provides some basis for choosing which algorithm is most desirable in any given situation.
linear expected-time algorithms for connectivity problems (extended abstract) researchers in recent years have developed many graph algorithms that are fast in the worst case, but little work has been done on graph algorithms that are fast on the average. (exceptions include the work of angluin and valiant [1], karp [7], and schnorr [9].) in this paper we analyze the expected running time of four algorithms for solving graph connectivity problems. our goal is to exhibit algorithms whose expected time is within a constant factor of optimum and to shed light on the properties of random graphs. in section 2 we develop and analyze a simple algorithm that finds the connected components of an undirected graph with n vertices in o(n) expected time. in sections 3 and 4 we describe algorithms for finding the strong components of a directed graph and the blocks of an undirected graph in o(n) expected time. the time required for these three problems is &ohgr;(m) in the worst case, where m is the number of edges in the graph, since all edges must be examined; but our results show that only o(n) edges must be examined on the average.*@@@@ in section 5 we present an algorithm for finding a minimum weight spanning forest in an undirected graph with edge weights in o(m) expected time.
constructing a perfect matching is in random nc we show that the problem of constructing a perfect matching in a graph is in the complexity class random nc: i.e., the problem is solvable in polylog time by a randomized parallel algorithm using a polynomial-bounded number of processors. we also show that several related problems lie in random nc. these include: (i) constructing a perfect matching of maximum weight in a graph whose edge weights are given in unary notation; (ii) constructing a maximum-cardinality matching; (iii) constructing a matching covering a set of vertices of maximum weight in a graph whose vertex weights are given in binary; (iv) constructing a maximum s-t flow in a directed graph whose edge weights are given in unary.
are search and decision problems computationally equivalent? from the point of view of sequential polynomial time computation, the answer to the question in the title is 'yes'. the process of self-reducibility is a linear time turing (oracle) reduction from a given combinatorial search problem to an appropriately defined decision problem. however, from the point of view of fast parallel computation, the answer is not so clear. many of the sequential algorithms that were 'marked off' as being &ldquo;inherently sequential&rdquo; embed within them the self-reducibility process. can this inherently sequential process be parallelized? to study this problem, we define an abstract setting (namely that of an independence system) in which one, universal search problem captures all combinatorial search problems. we consider several natural decision and function oracles to which this search problem may be reduced. on the positive side, we give efficient probabilistic parallel reductions to these oracles. these reductions constitute a scheme for parallelizing search problems in case the oracles for these problems are themselves efficiently computable in parallel. we give examples of problems that did not yield to parallelism before, but can be parallelized using this scheme. on the negative side, we prove lower bounds on any determininistic parallel reductions to the same oracles. if p processors are used, the sequential (linear) running time cannot be enhanced by more than a factor of &ogr;(log p) and hence for any polynomial number of processors the problem remains inherently sequential. this proves that randomization can be exponentially more powerful than determinism in our model, and suggests that nc &ne; random nc. finally, we state some intriguing conjectures and suggest new directions of research in complexity theory that arise from this work.
a fast parallel algorithm for the maximal independent set problem a parallel algorithm is presented that accepts as input a graph g and produces a maximal independent set of vertices in g. on a p-ram without the concurrent write or concurrent read features, the algorithm executes in o((log n)4) time and uses o((n/(log n))3) processors, where n is the number of vertices in g. the algorithm has several novel features that may find other applications. these include the use of balanced incomplete block designs to replace random sampling by deterministic sampling, and the use of a &ldquo;dynamic pigeonhole principle&rdquo; that generalizes the conventional pigeonhole principle.
a randomized parallel branch-and-bound procedure we present a universal randomized method called local best-first search for parallelizing sequential branch-and-bound algorithms. the method executes on a message-passing multiprocessor system, and requires no global data structures or complex communication protocols. we show that, uniformly on all instances, the execution time of the method is unlikely to exceed a certain inherent lower bound by more than a constant factor.
polynomial bounds for vc dimension of sigmoidal neural networks. we introduce a new method for proving explicit upper bounds on the vc dimension of general functional basis networks, and prove as an application, for the first time, the vc dimension of analog neural networks with the sigmoid activation function $\sigma(y)=1/1+e^{-y}$ to be bounded by a quadratic polynomial in the number of programmable parameters.
a new solution to the critical section problem a classical problem in concurrent program control is to provide a mechanism whereby several processes running concurrently can gain exclusive control of a resource. for each process, the section of its program in which it accesses the resource is called its critical section, and the problem is called the critical section problem. a solution to the critical section problem guarantees that no more than one process can be in its critical section at any time. the solution presented here improves on previous solutions by allowing processes to enter their critical sections on a first-come first-served basis.
efficient noise-tolerant learning from statistical queries. in this paper, we study the problem of learning in the presence of classification noise in the probabilistic learning model of valiant and its variants. in order to identify the class of &ldquo;robust&rdquo; learning algorithms in the most general way, we formalize a new but related model of learning from statistical queries. intuitively, in this model a learning algorithm is forbidden to examine individual examples of the unknown target function, but is given acess to an oracle providing estimates of probabilities over the sample space of random examples.one of our main results shows that any class of functions learnable from statistical queries is in fact learnable with classification noise in valiant's model, with a noise rate approaching the information-theoretic barrier of 1/2. we then demonstrate the generality of the statistical query model, showing that practically every class learnable in valiant's model and its variants can also be learned in the new model (and thus can be learned in the presence of noise). a notable exception to this statement is the class of parity functions, which we prove is not learnable from statistical queries, and for which no noise-tolerant algorithm is known.
combining dimensionality and rate of growth arguments for establishing lower bounds on the number of multiplications in this paper we describe a new method for establishing lower bounds for the number of multiplications and divisions required to compute rational functions. we shall start by reminding the reader of some standard notations.
efficient program transformations for resilient parallel computation via randomization (preliminary version) in this paper, we address the problem of automatically transforming arbitrary programs written for an ideal parallel machine to run on a completely asynchronous machine. we present a transformation which can be applied to an ideal program such that the resulting program's execution on an asynchronous machine is work and space efficient, relative to the ideal program from which it is derived. above all, the transformation will guarantee that the ideal program will execute in a continually progressive manner on the asynchronous machine; these instructions are not universal. furthermore, the individual processors can get delayed for arbitrary amounts of time while executing any instruction. in contrast, previous work relied either on the asynchronous machine having universal read-modify-write instructions as primitives, or on limited asynchrony by restricting the relative speeds of the processors.
approximability and nonapproximability results for minimizing total flow time on a single machine. we consider the problem of scheduling n jobs that are released over time on a single machine in order to minimize the total flow time. this problem is well known to be np-complete, and the best polynomial-time approximation algorithms constructed so far had (more or less trivial) worst-case performance guarantees of o(n). in this paper, we present one positive and one negative result on polynomial-time approximations for the minimum total flow time problem: the positive result is the first approximation algorithm with a sublinear worst-case performance guarantee of $o(\sqrt{n})$. this algorithm is based on resolving the preemptions of the corresponding optimum preemptive schedule. the performance guarantee of our approximation algorithm is not far from best possible, as our second, negative result demonstrates: unless p=np, no polynomial-time approximation algorithm for minimum total flow time can have a worst-case performance guarantee of $o(n^{1/2-\eps})$ for any $\eps>0$.
spectral partitioning, eigenvalue bounds, and circle packings for graphs of bounded genus. in this paper, we address two long-standing questions about finding good separators in graphs of bounded genus and degree: 1. it is a classical result of gilbert, hutchinson, and tarjan [j. algorithms, 5 (1984), pp. 391-407] that one can find asymptotically optimal separators on these graphs if given both the graph and an embedding of it onto a low genus surface. does there exist a simple, efficient algorithm to find these separators, given only the graph and not the embedding? 2. in practice, spectral partitioning heuristics work extremely well on these graphs. is there a theoretical reason why this should be the case? we resolve these two questions by showing that a simple spectral algorithm finds separators of cut ratio $o(\sqrt{\smash[b]{g/n}})$ and vertex bisectors of size $o(\sqrt{gn})$ in these graphs, both of which are optimal. as our main technical lemma, we prove an $o(g/n)$ bound on the second smallest eigenvalue of the laplacian of such graphs and show that this is tight, thereby resolving a conjecture of spielman and teng. while this lemma is essentially combinatorial in nature, its proof comes from continuous mathematics, drawing on the theory of circle packings and the geometry of compact riemann surfaces.
a randomized polynomial-time simplex algorithm for linear programming. we present the first randomized polynomial-time simplex algorithm for linear programming. like the other known polynomial-time algorithms for linear programming, its running time depends polynomially on the number of bits used to represent its input.we begin by reducing the input linear program to a special form in which we merely need to certify boundedness. as boundedness does not depend upon the right-hand-side vector, we run the shadow-vertex simplex method with a random right-hand-side vector. thus, we do not need to bound the diameter of the original polytope.our analysis rests on a geometric statement of independent interest: given a polytope a x ≤ b in isotropic position, if one makes a polynomially small perturbation to b then the number of edges of the projection of the perturbed polytope onto a random 2-dimensional subspace is expected to be polynomial.
on the parallel complexity of computing a maximal independent set in a hypergraph a maximal independent set in a hypergraph is a subset of vertices that is maximal with respect to the property of not containing any edge of the hypergraph. we show that an algorithm proposed by beame and luby is in randomized nc for hypergraphs in which the maximum edge size is bounded by a constant. to prove this, we bound the upper tail of sums of dependent random variables defined on the edges of a hypergraph. these bounds may be viewed as extensions of bounds on the tail of the binomial distribution. we derandomize this algorithm to obtain the first sublinear time deterministic algorithm for hypergraphs with edges of size o(1). the algorithm exhibits the following time-processor tradeoff: it can be made to run in time o(n&egr;) with no(1/&egr;) processors for a hypergraph on n vertices, for any &egr; &ge; 2d+1&bull; (log log n)/(log n); here d = o(1) denotes the maximum size of an edge in h. in particular, for any constant &egr; > o, we have an algorithm running in time o(n&egr;) on a polynomial number of processors, and we have an algorithm running in time (log n)o(1) on no(log n/log log n) processors.
spatial gossip and resource location protocols. the dynamic behavior of a network in which information is changing continuously over time requires robust and efficient mechanisms for keeping nodes updated about new information. gossip protocols are mechanisms for this task in which nodes communicate with one another according to some underlying deterministic or randomized algorithm, exchanging information in each communication step. in a variety of contexts, the use of randomization to propagate information has been found to provide better reliability and scalability than more regimented deterministic approaches.in many settings --- consider a network of sensors, or a cluster of distributed computing hosts --- new information is generated at individual nodes, and is most &ldquo;interesting&rdquo; to nodes that are nearby. thus, we propose distance-based propagation bounds as a performance measure for gossip algorithms: a node at distance d from the origin of a new piece of information should be able to learn about this information with a delay that grows slowly with d, and is independent of the size of the network.for nodes arranged with uniform density in euclidean space, we present natural gossip algorithms that satisfy such a guarantee: new information is spread to nodes at distance \dist, with high probability, in o(\log^{1 + \ve} \dist) time steps. such a bound combines the desirable qualitative features of uniform gossip, in which information is spread with a delay that is logarithmic in the full network size, and deterministic flooding, in which information is spread with a delay that is linear in the distance and independent of the network size. our algorithms and their analysis resolve a conjecture of demers et al. we show an application of our gossip algorithms to a basic resource location problem, in which nodes seek to rapidly
connectivity and inference problems for temporal networks. many network problems are based on fundamental relationships involving time. consider, for example, the problems of modeling the flow of information through a distributed network, studying the spread of a disease through a population, or analyzing the reachability properties of an airline timetable. in such settings, a natural model is that of a graph in which each edge is annotated with a time label specifying the time at which its endpoints "communicated." we will call such a graph a temporal network. to model the notion that information in such a network "flows" only on paths whose labels respect the ordering of time, we call a path time-respecting if the time labels on its edges are non-decreasing. the central motivation for our work is the following question: how do the basic combinatorial and algorithmic properties of graphs change when we impose this additional temporal condition? the notion of a path is intrinsic to many of the most fundamental algorithmic problems on graphs; spanning trees, connectivity, flows, and cuts are some examples. when we focus on time-respecting paths in place of arbitrary paths, many of these problems acquire a character that is different from the traditional setting, but very rich in its own right. we provide results on two types of problems for temporal networks. first, we consider connectivity problems, in which we seek disjoint time-respecting paths between pairs of nodes. the natural analogue of menger's theorem for node-disjoint paths fails in general for time-respecting paths; we give a non-trivial characterization of those graphs for which the theorem does hold in terms of an excluded subdivision theorem, and provide a polynomial-time algorithm for connectivity on this class of graphs. (the problem on general graphs is np-complete.) we then define and study the class of inference problems, in which we seek to reconstruct a partially specified time labeling of a network in a manner consistent with an observed history of information flow.
a decentralized algorithm for spectral analysis. in many large network settings, such as computer networks, social networks, or hyperlinked text documents, much information can be obtained from the network's spectral properties. however, traditional centralized approaches for computing eigenvectors struggle with at least two obstacles: the data may be difficult to obtain (both due to technical reasons and because of privacy concerns), and the sheer size of the networks makes the computation expensive. a decentralized, distributed algorithm addresses both of these obstacles: it utilizes the computational power of all nodes in the network and their ability to communicate, thus speeding up the computation with the network size. and as each node knows its incident edges, the data collection problem is avoided as well.our main result is a simple decentralized algorithm for computing the top k eigenvectors of a symmetric weighted adjacency matrix, and a proof that it converges essentially in o(τmixlog2 n) rounds of communication and computation, where τmix is the mixing time of a random walk on the network. an additional contribution of our work is a decentralized way of actually detecting convergence, and diagnosing the current error. our protocol scales well, in that the amount of computation performed at any node in any one round, and the sizes of messages sent, depend polynomially on k, but not on the (typically much larger) number n of nodes.
verifying partial orders we present a randomized algorithm which uses o(n(log n)1/3) expected comparisons to verify that a given partial order holds on n elements from an unknown total order.
low distortion maps between point sets. we initiate the study of the minimum distortion problem: given as input two n-point metric spaces, find a bijection between them with minimum distortion. this is an abstraction of certain geometric problems in shape and image matching, and is also a natural variation and extension of the fundamental problems of graph isomorphism and bandwidth. our focus is on algorithms that find an optimal (or near-optimal) bijection when the distortion is fairly small. we present a polynomial time algorithm that finds an optimal bijection between two line metrics, provided the distortion is less than 3+2√2. we also give a parameterized polynomial time algorithm that finds an optimal bijection between an arbitrary unweighted graph metric and a bounded-degree tree metric.