waashk/dblp huggingface dataset:
measuring energy consumption in vlsi circuits: a foundation energy conservation is a key question in today' s society and the proliferation of vlsi circuits encourages an energy conscious approach to their design. although a single chip at current densities may consume less than one watt of power, assembling larger and larger systems with these chips results in significant energy costs [me 80]. moreover, energy consumed by a circuit is dissipated, typically by convection, as heat. the heat dissipated is proportional to the energy consumed. increased densities in planar technologies and the possibility of 3-dimensional technologies, therefore, increase the need to reduce the amount of heal. produced. the intent of this paper is to lay the ground work for measuring the switching energy consumed in vlsi circuits. intuitively, switching energy measures the area -&-ldquo;used-&-rdquo; to effect a computation. a wire or gate consumes switching energy when it changes staie from 0 to 1 or from 1 to 0. some technologies consume more than switching energy. for example, nmos dissipates dc power [mc 80]. cmos, however, consumes only switching energy [mc 80]. switching energy is thus a lower bound on total energy, and is alternately termed -&-ldquo;energy-&-rdquo; throughout this paper. in this paper, two energy models are developed, model 1, the uniswitch model (usm), assumes that a wire or gate in an acyclic circuit can switch at most once. in particular, wire delays are neglected, the affects of different path lengths are neglected (ie. circuits are synchronous [sa 76]), and all inputs are assumed to arrive together. model 2, the multiswitch model (msm), is more sensitive to timing issues that can cause wires and gates in an acyclic circuit to switch more than once. the rest of this paper is organized as follows. section 2 defines the energy models. in section 3, a class of restricted acyclic circuits is defined. lower and upper bounds for worst case energy are obtained for these circuits. an -&-ohgr;(area) lower bound is obtained for acyclic monotone circuits. in section 4, average energy bounds are obtained for the restricted circuits.
quantum time-space tradeoffs for sorting. we investigate the complexity of sorting in the model of sequential quantum circuits. while it is known that in general a quantum algorithm based on comparisons alone cannot outperform classical sorting algorithms by more than a constant factor in time complexity, this is wrong in a space bounded setting. we observe that for all storage bounds n/log ≥ s ≥ log3n, one can devise a quantum algorithm that sorts n numbers (using comparisons only) in time t=o(n3/2 log3/2 n/√s). we then show the following lower bound on the time-space tradeoff for sorting n numbers from a polynomial size range in a general sorting algorithm (not necessarily based on comparisons): ts=ω(n3/2). hence for small values of s the upper bound is almost tight. classically the time-space tradeoff for sorting is ts=θ(n2).
interaction in quantum communication and the complexity of set disjointness. one of the most intriguing facts about communication using quantum states is that these states cannot be used to transmit more classical bits than the number of qubits used, yet in some scenarios there are ways of conveying information with exponentially fewer qubits than possible classically [3, 26]. moreover, these methods have a very simple structure---they involve only few message exchanges between the communicating parties.we consider the question as to whether every classical protocol may be transformed to a &ldquo;simpler&rdquo; quantum protocol---one that has similar efficiency, but uses fewer message exchanges. we show that for any constant k, there is a problem such that its k+1 message classical communication complexity is exponentially smaller than its k message quantum communication complexity, thus answering the above question in the negative. this in particular proves a round hierarchy theorem for quantum communication complexity, and implies via a simple reduction, an \omega(n^{1/k}) lower bound for k message protocols for set disjointness for constant~k.our result builds on two primitives, local transitions in bi-partite states (based on previous work) and average encoding which may be of significance in other contexts as well.
a subset spanner for planar graphs, : with application to subset tsp. let ε>0 be a constant. for any edge-weighted planar graph g and a subset s of nodes of g, there is a subgraph h of g of weight a constant times that of the minimum steiner tree for s such that distances in h between nodes in s are at most 1+ε times the corresponding distances in g. as a consequence, there is an o(n log n)-time approximation scheme for finding a tsp among a given subset of nodes of a planar graph. this is the first ptas for the problem.
efficient approximation algorithms for semidefinite programs arising from max cut and coloring. the best known approximation algorithm for graph max cut, due to goemans and williamson, first finds the optimal solution a semidefinite program and then derives a graph cut from that solution. building on this result, karger, motwani, and sudan gave an approximation algorithm for graph coloring that also involves solving a semidefinite program. solving these semidefinite programs using known methods (ellipsoid, interior-point), though polynomial-time, is quite expensive. we show how they can be approximately solved in $\tilde o(nm)$ time for graphs with $n$ nodes and $m$ edges.
faster shortest-path algorithms for planar graphs. we give a linear-time algorithm for single-source shortest paths in planar graphs with nonnegative edge-lengths. our algorithm also yields a linear-time algorithm for maximum flow in a planar graph with the source and sink on the same face. the previous best algorithms for these problems required $\omega(n \sqrt{\log n})$ time where $n$ is the number of nodes in the input graph. for the case where negative edge-lengths are allowed, we give an algorithm requiring $o(n^{4/3} \log nl)$ time, where $l$ is the absolute value of the most negative length. previous algorithms for shortest paths with negative edge-lengths required $\omega(n^{3/2})$ time. our shortest-path algorithm yields an $o(n^{4/3} \log n)$-time algorithm for finding a perfect matching in a planar bipartite graph. a similar improvement is obtained for maximum flow in a directed planar graph.
a parallel randomized approximation scheme for shortest paths we give a randomized parallel algorithm for approximate shortest path computation in an undirected weighted graph. the algorithm is based on a technique used by ullman and yannakakis in a parallel algorithm for breadth-first search. it has application, e.g., in approximate solution of multicommodity flow problems with unit capacities. we also show how to adapt the algorithm to perform better for planar graphs.
a randomized linear-time algorithm for finding minimum spanning trees. we present a randomized linear-time algorithm for finding a minimum spanning tree in a connected graph with edge weights. the algorithm is a modification of one proposed by karger and uses random sampling in combination with a recently discovered linear-time algorithm for verifying a minimum spanning tree. our computational model is a unit-cost random-access machine with the restriction that the only operations allowed on edge weights are binary comparisons.
the small-world phenomenon: an algorithm perspective. long a matter of folklore, the ``small-world phenomenon'''' --the principle that we are all linked by short chains of acquaintances --was inaugurated as an area of experimental study in the social sciences through the pioneering work of stanley milgram in the 1960''s. this work was among the first to make the phenomenon quantitative, allowing people to speak of the ``six degrees of separation'''' between any two people in the united states. since then, a number of network models have been proposed as frameworks in which to study the problem analytically. one of the most refined of these models was formulated in recent work of watts and strogatz; their framework provided compelling evidence that the small-world phenomenon is pervasive in a range of networks arising in nature and technology, and a fundamental ingredient in the evolution of the world wide web. but existing models are insufficient to explain the striking algorithmic component of milgram''s original findings: that individuals using local information are collectively very effective at actually constructing short paths between two points in a social network. although recently proposed network models are rich in short paths, we prove that no decentralized algorithm, operating with local information only, can construct short paths in these networks with non-negligible probability. we then define an infinite family of network models that naturally generalizes the watts-strogatz model, and show that for one of these models, there is a decentralized algorithm capable of finding short paths with high probability. more generally, we provide a strong characterization of this family of network models, showing that there is in fact a unique model within the family for which decentralized algorithms are effective.
segmentation problems. we study a novel genre of optimization problems, which we call segmentation problems, motivated in part by certain aspects of clustering and data mining. for any classical optimization problem, the corresponding segmentation problem seeks to partition a set of cost vectors into several segments, so that the overall cost is optimized. we focus on two natural and interesting (but maxsnp-complete) problems in this class, the hypercube segmentation problem and the catalog segmentation problem, and present approximation algorithms for them. we also present a general greedy scheme, which can be specialized to approximate any segmentation problem.
allocating bandwidth for bursty connections. in this paper, we undertake the first study of statistical multiplexing from the perspective of approximation algorithms. the basic issue underlying statistical multiplexing is the following: in high-speed networks, individual connections (i.e., communication sessions) are very bursty, with transmission rates that vary greatly over time. as such, the problem of packing multiple connections together on a link becomes more subtle than in the case when each connection is assumed to have a fixed demand.we consider one of the most commonly studied models in this domain: that of two communicating nodes connected by a set of parallel edges, where the rate of each connection between them is a random variable. we consider three related problems: (1) stochastic load balancing, (2) stochastic bin-packing, and (3) stochastic knapsack. in the first problem the number of links is given and we want to minimize the expected value of the maximum load. in the other two problems the link capacity and an allowed overflow probability p are given, and the objective is to assign connections to links, so that the probability that the load of a link exceeds the link capacity is at most $p$. in bin-packing we need to assign each connection to a link using as few links as possible. in the knapsack problem each connection has a value, and we have only one link. the problem is to accept as many connections as possible.for the stochastic load balancing problem we give an o(1)-approximation algorithm for arbitrary random variables. for the other two problems we have algorithms restricted to on-off sources (the most common special case studied in the statistical multiplexing literature), with a somewhat weaker range of performance guarantees.a standard approach that has emerged for dealing with probabilistic resource requirements is the notion of effective bandwidth---this is a means of associating a fixed demand with a bursty connection that "represents" its distribution as closely as possible. our approximation algorithms make use of the standard definition of effective bandwidth and also a new one that we introduce; the performance guarantees are based on new results showing that a combination of these measures can be used to provide bounds on the optimal solution.
using mixture models for collaborative filtering. a collaborative filtering system at an e-commerce site or similar service uses data about aggregate user behavior to make recommendations tailored to specific user interests. we develop recommendation algorithms with provable performance guarantees in a probabilistic mixture model for collaborative filtering proposed by hoffman and puzicha. we identify certain novel parameters of mixture models that are closely connected with the best achievable performance of a recommendation algorithm; we show that for any system in which these parameters are bounded, it is possible to give recommendations whose quality converges to optimal as the amount of data grows.all our bounds depend on a new measure of independence that can be viewed as an l1-analogue of the smallest singular value of a matrix. using this, we introduce a technique based on generalized pseudoinverse matrices and linear programming for handling sets of high-dimensional vectors. we also show that standard approaches based on l2-spectral methods are not strong enough to yield comparable results, thereby suggesting some inherent limitations of spectral analysis.
new layouts for the shuffle-exchange graph (extended abstract) in this extended abstract, we present several new layouts for the shuffle-exchange graph, including one which requires only 0(n2/log2n) area. the optimal layout is described and analyzed in section 3. the analysis is heavily dependent on several combinatorial results which we state in section 2 and prove in the appendix. the other layouts are described in section 4. although these layouts are not asymptotically optimal (most require 0(n2/log3/2n) area), the theory behind their development is interesting and may eventually lead to good practical layouts as well as other asymptotically optimal layouts.
graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses. traditional hardness versus randomness results focus on time-efficient randomized decision procedures. we generalize these trade-offs to a much wider class of randomized processes. we work out various applications, most notably to derandomizing arthur-merlin games. we show that every language with a bounded round arthur-merlin game has subexponential size membership proofs for infinitely many input lengths unless exponential time coincides with the third level of the polynomial-time hierarchy (and hence the polynomial-time hierarchy collapses). since the graph nonisomorphism problem has a bounded round arthur-merlin game, this provides the first strong evidence that graph nonisomorphism has subexponential size proofs. we also establish hardness versus randomness trade-offs for space bounded computation.
randomness efficient identity testing of multivariate polynomials. we present a randomized polynomial time algorithm to determine if a multivariate polynomial is zero using o(\log mn&dgr;) random bits where n is the number of variables, m is the number of monomials, and &dgr; is the total degree of the unknown polynomial. all other known randomized identity tests (see for example [7, 12, 1]) use &ohgr;(n) random bits even when the polynomial is sparse and has low total degree. in such cases our algorithm has an exponential savings in randomness. in addition, we obtain the first polynomial time algorithm for interpolating sparse polynomials over finite fields of large characteristic. our approach uses an error correcting code combined with the randomness optimal isolation lemma of [8] and yields a generalized isolation lemma which works with respect to a set of linear forms over a base set.
learning dnf in time 2. using techniques from learning theory, we show that any s-term dnf over n variables can be computed by a polynomial threshold function of degree o(n1/3 log s). this upper bound matches, up to a logarithmic factor, the longstanding lower bound given by minsky and papert in their 1968 book perceptrons. as a consequence of this upper bound we obtain the fastest known algorithm for learning polynomial size dnf, one of the central problems in computational learning theory.
on structuring flowcharts (preliminary version) cooper's syntactic transformations for structuring flowcharts are studied. after exhibiting major problems with these transformations, a modified set of transformations are proposed. it is proved that a flowchart g is transformable into a d-chart if and only if for every 3 connected circuits c1, c2 and c3 in g, there exists a vertex v on c1+c2+c3 such that for every i, ci passes through v or every path from ci to the out of the flowchart passes through v.
on a multidimensional search problem (preliminary version) the problem of searching for a given k-vector among a sorted list of n k-vectors is considered. the binary search is known to be optimal when k is 1. here an almost optimal algorithm is presented for the 2-dimensional case. interesting upper and lower bounds are derived for the general problem.
the decision problem for the probabilities of higher-order properties the probability of a property on the class of all finite relational structures is the limit as n &rarr; &infin; of the fraction of structures with n elements satisfying the property, provided the limit exists. it is known that 0-1 laws hold for any property expressible in first-order logic or in fixpoint logic, i.e. the probability of any such property exists and is either 0 or 1. it is also known that the associated decision problem for the probabilities is pspace-complete and exptime-complete for first-order logic and fixpoint logic respectively. the 0-1 law fails, however, in general for second-order properties and the decision problem becomes unsolvable. we investigate here logics which on the one hand go beyond fixpoint in terms of expressive power and on the other possess the 0-1 law. we consider first iterative logic which is obtained from first order logic by adding while looping as a construct. we show that the 0-1 law holds for this logic and determine the complexity of the associated decision problem. after this we study a fragment of second order logic called strict &sgr;11. this class of properties is obtained by restricting appropriately the first-order part of existential second-order sentences. every strict &sgr;11 property is np-computable and there are strict &sgr;11 properties that are np-complete, such as 3-colorability. we show that the 0-1 law holds for strict &sgr;11 properties and establish that the associated decision problem is nexptime-complete. the proofs of the decidability and complexity results require certain combinatorial machinery, namely generalizations of ramsey's theorem.
fast parallel processing array algorithms for some graph problems (preliminary version) the parallel processing array consists of an n&times;n array of processors to which a cn2 node directed graph can be input by placing c nodes at every point of the array. it is shown that every one of the following properties of the graph can be computed in order of n steps: (1) to test whether the graph is strongly connected, (2) to mark a node in every strongly connected component, (3) to mark a strong connected component that contains a given node, (4) to mark a simple directed path between a given pair of nodes, and (5) to compute the interconnectivity of the c nodes within every point. as a consequence, several open problems can be solved. for example, any language recognized by a 2-dimensional finite state automaton with 1 pebble can be recognized in order of n steps by a parallel processing array. (it was not even known whether the languages recognized by 2-dimensional finite state automata without pebbles can be recognized in order of n steps by a parallel processing array). note that a 1 pebble automaton can run for order of n4 steps before accepting an input.
constructing small sample spaces satisfying given constraints. the subject of this paper is finding small sample spaces for joint distributions of n discrete random variables. such distributions are often only required to obey a certain limited set of constraints of the form pr (event) = $\pi$. it is shown that the problem of deciding whether there exists any distribution satisfying a given set of constraints is np-hard. however, if the constraints are consistent, then there exists a distribution satisfying them, which is supported by a "small" sample space (one whose cardinality is equal to the number of constraints). for the important case of independence constraints, where the constraints have a certain form and are consistent with a joint distribution of independent random variables, a small sample space can be constructed in polynomial time. this last result can be used to derandomize algorithms; this is demonstrated by an application to the problem of finding large independent sets in sparse hypergraphs.
real-time simulation of concatenable double-ended queues by double-ended queues (preliminary version) it is shown that concatenable double-ended queues can be simulated in real-time by double-ended queues without concatenation. consequently, every multihead turing machine with head-to-head jumps can be simulated in real-time by multitape turing machines.
localized search in sorted lists it is well known that every one of the set operations insert, delete and member can be performed in o(log n) steps, where n is the number of elements currently in the set. here we implement these operations and a move operation for a sorted list with f fingers (points of reference) established on the list. it is shown that these operations can be performed in o(log d) steps, where d is the distance between the corresponding finger and the key involved.
a matter of degree: improved approximation algorithms for degree-bounded minimum spanning trees. in this paper, we present a new bicriteria approximation algorithm for the degree-bounded minimum spanning tree problem. in this problem, we are given an undirected graph, a nonnegative cost function on the edges, and a positive integer b*, and the goal is to find a minimum-cost spanning tree t with maximum degree at most b*. in an n-node graph, our algorithm finds a spanning tree with maximum degree o(b*+logn) and cost o(optb*), where optb* is the minimum cost of any spanning tree whose maximum degree is at most b*. our algorithm uses ideas from lagrangean duality. we show how a set of optimum lagrangean multipliers yields bounds on both the degree and the cost of the computed solution.
decidability of reachability in vector addition systems (preliminary version) a convincing proof of the decidability of reachability in vector addition systems is presented. no drastically new ideas beyond those in sacerdote and tenney, and mayr are made use of. the complicated tree constructions in the earlier proofs are completely eliminated.
primal-dual meets local search: approximating mst's with nonuniform degree bounds. we present a new bicriteria approximation algorithm for the degree-bounded minimum-cost spanning tree problem: given an undirected graph with nonnegative edge weights and degree bounds bv > 1 for all vertices v, find a spanning tree t of minimum total edge-cost such that the maximum degree of each node v in t is at most bv. our algorithm finds a tree in which the degree of each node v is o(bv + log n) and the total edge-cost is at most a constant times the cost of any tree that obeys all degree constraints.our previous algorithm[9] with similar guarantees worked only in the case of uniform degree bounds (i.e. bv=b for all vertices v). while the new algorithm is based on ideas from lagrangean relaxation as is our previous work, it does not rely on computing a solution to a linear program. instead it uses a repeated application of kruskal's mst algorithm interleaved with a combinatorial update of approximate lagrangean node-multipliers maintained by the algorithm. these updates cause subsequent repetitions of the spanning tree algorithm to run for longer and longer times, leading to overall progress and a proof of the performance guarantee.