In this work, we study time/space trade-offs for function composition. We prove asymptotically optimal lower bounds for function composition in the setting of nondeterministic read once branching programs, for the syntactic model as well as the stronger semantic model of read-once nondeterministic computation. We prove that such branching programs for solving the tree evaluation problem over an alphabet of size k requires size roughly k^{Omega(h)}, i.e space Omega(h log k). Our lower bound nearly matches the natural upper bound which follows the best strategy for black-white pebbling the underlying tree. While previous super-polynomial lower bounds have been proven for read-once nondeterministic branching programs (for both the syntactic as well as the semantic models), we give the first lower bounds for iterated function composition, and in these models our lower bounds are near optimal.

We prove exponential lower bounds on the size of semantic read-once 3-ary nondeterministic branching programs. Prior to our result the best that was known was for D-ary branching programs with |D| >= 2^{13}.

Proving superpolylogarithmic lower bounds for dynamic data structures has remained an open problem despite years of research. Pǎtraşcu proposed an exciting approach for breaking this barrier via a two-player communication model in which one player gets private advice at the beginning of the protocol. He gave reductions from the problem of solving an asymmetric version of set-disjointness in his model to a diverse collection of natural dynamic data structure problems in the cell probe model. He also conjectured that, for any hard problem in the standard two-party communication model, the asymmetric version of the problem is hard in his model, provided not too much advice is given. In this paper, we prove several surprising results about his model. We show that there exist Boolean functions requiring linear randomized communication complexity in the two-party model, for which the asymmetric versions in his model have deterministic protocols with exponentially smaller complexity. For set-disjointness, which also requires linear randomized communication complexity in the two-party model, we give a deterministic protocol for the asymmetric version in his model with a quadratic improvement in complexity. These results demonstrate that Pǎtraşcu's conjecture, as stated, is false. In addition, we show that the randomized and deterministic communication complexities of problems in his model differ by no more than a logarithmic multiplicative factor. We also prove lower bounds in some restricted versions of this model for natural functions such as set-disjointness and inner product. All of our upper bounds conform to these restrictions. Moreover, a special case of one of these lower bounds implies a new proof of a strong lower bound on the tradeoff between the query time and the amortized update time of dynamic data structures with nonadaptive query algorithms.

Proving superpolylogarithmic lower bounds for dynamic data structures has remained an open problem despite years of research. Recently Pătraşcu proposed an exciting new approach for breaking this barrier via a two player communication model in which one player gets private advice at the beginning of the protocol. He gave reductions from the problem of solving an asymmetric version of set-disjointness in his model to a diverse collection of natural dynamic data structure problems in the cell probe model. He also conjectured that, for any hard problem in the standard two-party communication model, the asymmetric version of the problem is hard in his model, provided not too much advice is given. In this paper, we prove several surprising results about his model. We show that there exist Boolean functions requiring linear randomized communication complexity in the two-party model, for which the asymmetric versions in his model have deterministic protocols with exponentially smaller complexity. For set-disjointness, which also requires linear randomized communication complexity in the two-party model, we give a deterministic protocol for the asymmetric version in his model with a quadratic improvement in complexity. These results demonstrate that Pătraşcu's conjecture, as stated, is false. In addition, we show that the randomized and deterministic communication complexities of problems in his model differ by no more than a logarithmic multiplicative factor. We also prove lower bounds in some restricted versions of this model for natural functions such as set-disjointness and inner product. All of our upper bounds conform to these restrictions.

We give a scalable ((1+ϵ)-speed O (1)-competitive) nonclairvoyant algorithm for scheduling jobs with sublinear nondecreasing speedup curves on multiple processors with the objective of average response time.

We address the scheduling model of arbitrary speed-up curves and the broadcast scheduling model. The former occurs when jobs are scheduled in a multi-core system or on a cloud of machines. Here jobs can be sped up when given more processors or machines. However, the parallelizability of the jobs may vary and the algorithm is required to be oblivious of the parallelizability of a job. The latter model is natural in wireless and LAN networks where requests (or jobs) can be simultaneously satisfied together. Both settings are similar in that two schedules can do different amounts of work to satisfy all the jobs. We focus on optimizing the ℓk- norms of flow time. Recently, Gupta et al. [24] gave a (k + ε)-speed O(1)-competitive algorithm for the ℓk norms of flow time in both scheduling settings for fixed k. Inspired by this work, we give the first analysis of a scalable algorithm, i.e. (1 + ε)-speed O(1)-competitive, for all ℓk-norms of flow time in both settings for fixed k and 0 < ε ≤ 1. Both problems have a strong lower bound without resource augmentation, so this is the best result that can be shown in the worst case setting up to a constant factor in the competitive ratio.

We give three results related to online nonclairvoyant speed scaling to minimize total flow time plus energy. We give a nonclairvoyant algorithm LAPS, and show that for every power function of the form P(s)=s α , LAPS is O(1)-competitive; more precisely, the competitive ratio is 8 for α=2, 13 for α=3, and $\frac{2\alpha^{2}}{\ln\alpha}$ for α>3. We then show that there is no constant c, and no deterministic nonclairvoyant algorithm A, such that A is c-competitive for every power function of the form P(s)=s α . So necessarily the achievable competitive ratio increases as the steepness of the power function increases. Finally we show that there is a fixed, very steep, power function for which no nonclairvoyant algorithm can be O(1)-competitive.

We consider the well-known cake cutting problem in which a protocol wants to divide a cake among n ≥ 2 players in such a way that each player believes that they got a fair share. The standard Robertson-Webb model allows the protocol to make two types of queries, Evaluation and Cut, to the players. A deterministic divide-and-conquer protocol with complexity O ( n log n ) is known. We provide the first a Ω( n log n ) lower bound on the complexity of any deterministic protocol in the standard model. This improves previous lower bounds, in that the protocol is allowed to assign to a player a piece that is a union of intervals and only guarantee approximate fairness. We accomplish this by lower bounding the complexity to find, for a single player, a piece of cake that is both rich in value, and thin in width. We then introduce a version of cake cutting in which the players are able to cut with only finite precision. In this case, we can extend the Ω( n log n ) lower bound to include randomized protocols.

We consider the problem of computing bounds on the variance and expectation of the longest path length in a DAG from knowledge of variance and expectation of edge lengths. We focus primarily on the case where all edge lengths are non-negative and the DAG has a single source and sink node. We present analytic bounds for various simple DAG structures, and present a new algorithm to compute bounds for more general DAG structures. Our algorithm is motivated by an analogy with balance of forces in a network of “strange” springs.

We consider the problem of computing a minimum-distortion bijection between two point-sets in ℝ2. We prove the first non-trivial inapproximability result for this problem, for the case when the distortion is constant. More precisely, we show that there exist constants 0 < α < β, such that it is NP-hard to distinguish between spaces for which the distortion is either at most α, or at least β, under the Euclidean norm. This addresses a question of Kenyon, Rabani and Sinclair [KRS04], and extends a result due to Papadimitriou and Safra [PS05], who gave inapproximability for point-sets in ℝ3. We also apply similar ideas to the problem of computing a minimum-distortion embedding of a finite metric space into ℝ2. We obtain an analogous inapproximability result under the ℓ∞ norm for this problem. Inapproximability for the case of constant distortion was previously known only for dimension at least 3 [MS08].

We give a scalable ((1+∊)-speed O(1)-competitive) non-clairvoyant algorithm for scheduling jobs with sublinear nondecreasing speed-up curves on multiple processors with the objective of average response time.

We consider the setting of a multiprocessor where the speeds of the m processors can be individually scaled. Jobs arrive over time and have varying degrees of parallelizability. A nonclairvoyant scheduler must assign the jobs to processors, and scale the speeds of the processors. We consider the objective of energy plus flow time. For jobs that may have side effects or that are not checkpointable, we show an Ωm((α-1)/α2) bound on the competitive ratio of any deterministic algorithm. Here m is the number of processors and α is the exponent of the power function. For checkpointable jobs without side effects, we give an O(log m)-competitive algorithm. Thus for jobs that may have side effects or that are not checkpointable, the achievable competitive ratio grows quickly with the number of processors, but for checkpointable jobs without side effects, the achievable competitive ratio grows slowly with the number of processors. We then show a lower bound of Ω(log1/α m) on the competitive ratio of any algorithm for checkpointable jobs without side effects. Finally we slightly improve the upper bound on the competitive ratio for the single processor case, which is equivalent to the case that all jobs are fully parallelizable, by giving an improved analysis of a previously proposed algorithm. Copyright 2009 ACM.

We study online nonclairvoyant speed scaling to minimize total flow time plus energy. We first consider the traditional model where the power function is $P(s)=s^\alpha$. We give a nonclairvoyant algorithm that is shown to be $O(\alpha^3)$-competitive. We then show an $\Omega( \alpha^{1/3-\epsilon} )$ lower bound on the competitive ratio of any nonclairvoyant algorithm. We also show that there are power functions for which no nonclairvoyant algorithm can be $O(1)$-competitive.

We give a randomized algorithm for the well known caking cutting problem that achieves approximate fairness, and has complexity O(n), when all players are honest. The heart of this result involves extending the standard offline multiple-choice balls and bins analysis to the case where the underlying resources/bins/machines have different utilities to different players/balls/jobs

There has been considerable recent interest in probabilistic packet marking schemes for sending information from nodes (routers) along one or more paths traveled by a stream of packets to the end-host receiving that stream. A central consideration for such schemes is the tradeoff between the number B of possible states of the marking bits in a packet, the number of bits n of information being sent by the nodes, and the expected number of packets T required to reconstruct this information. For the case where the packets all travel along the same path, we prove a lower bound of T ≥ Ω(B22n/(B-1)), roughly the square of an earlier lower bound of Adler.For an upper bound, we consider a model where each of m nodes along a single path must send one of s possible messages (thus n = m log2 s total bits are sent). We prove that T ≤ O(m • 22m(log2 s)/(B-1)) suffices (the implicit constant depends on B and s); this almost matches the lower bound, and is roughly the square root of an earlier upper bound of Adler. The new bound holds for all B and s in two slightly relaxed models, while under the strictest requirements we prove it only for some special values of B and s. This is related to a challenging geometric problem: the existence of an s-reptile (B-1)-dimensional simplex, i.e. a simplex S that can be tiled by s congruent simplices similar to S.We also consider the case where the packets travel along multiple paths to the same destination. In this case, we present a new protocol and analysis technique that together allow us to significantly generalize over previous work the scenarios where the protocol is effective.

We consider server scheduling strategies to minimize average flow time in a multicast pull system where data items have uniform size. The algorithm Longest Wait First (LWF) always services the page where the aggregate waiting times of the outstanding requests for that page is maximized. We provide the first non-trivial analysis of the worst case performance of LWF. On the negative side, we show that LWF is nots-speedO(1)-competitive fors< 1+√5/2. On the positive side, we show that LWF is 6-speedO(1)-competitive.

The well-known Transport Control Protocol (TCP) is a crucial component of the TCP/IP architecture on which the Internet is built, and is a de facto standard for reliable communication on the Internet. At the heart of the TCP protocol is its congestion control algorithm. While most practitioners believe that TCP congestion control algorithm performs very well, a complete analysis of the congestion control algorithm is yet to be done. A lot of effort has, therefore, gone into the evaluation of different performance metrics like throughput and average latency under TCP. In this paper, we approach the problem from a different perspective and use the the competitive analysis framework to provide some answers to the question “how good is the TCP/IP congestion control algorithm? ” First, we prove that for networks with a single bottleneck (or point of congestion), TCP is competitive to the optimal centralized (global) algorithm in minimizing the user-perceived latency or flow time of the sessions, provided we limit the adversary by giving it strictly less resources than TCP. Specifically, we show that with O(1) times as much bandwidth and O(1) extra time per job, TCP is O(1)-competitive against an optimal global algorithm. We motivate the need for allowing TCP to have extra resources by observing that existing lower bounds for nonclairvoyant scheduling algorithms imply that no online, distributed, non-clairvoyant algorithm can be competitive with an optimal offline algorithm if both algorithms were given the same resources. Second, we show that TCP is fair by proving that it converges quickly to allocations where every session gets its fair share of network bandwidth. 1

We considered non-clairvoyant multiprocessor scheduling of jobs with arbitrary arrival times and changing execution characteristics.The problem has been studied extensively when either the jobs all arrive at time zero, or when all the jobs are fully parallelizable, or when the scheduler has considerable knowledge about the jobs.This paper considers for the first time this problem without any of these three restrictions yet when our algorithm is given more resources than the adversary.We provide new upper and lower bound techniques applicable in this more difficult scenario.The results axe of both theoretical and practical interest.In our model, a job can arrive at any arbitrary time and its execution characteristics can change through the life of the job from being anywhere from fully parallelizable to completely sequential.We assume that the scheduler has no knowledge about the jobs except for knowing when a job arrives and knowing when it completes.(This is why we say that the scheduler is completely in the dark.)Given all this, we prove that the scheduler algorithm Equi-partition, though simple, performs within a constant factor as well as the optimal scheduler as long as it is given at least twice a8 many proceesors.More over, we prove that if none of the jobs are "strictly" fully parallelizahle, then Equi-partition performs competitively with no extra processors.We also consider other variations: faster procesors; fewer preemp tions; and a wider range of execution characteristics.

Directed st-connectivity is the problem of deciding whether or not there exists a path from a distinguished node s to a distinguished node t in a directed graph. We prove a time--space lower bound on the probabilistic NNJAG model of Poon [ Proc. 34th Annual Symposium on Foundations of Computer Science, Palo Alto, CA, 1993, pp. 218--227]. Let n be the number of nodes in the input graph and S and T be the space and time used by the NNJAG, respectively. We show that, for any $\delta > 0$, if an NNJAG uses space $S \in O(n^{1-\delta})$, then $T \in 2^{ \Omega(\log^2 (n/S)) }$; otherwise $T \in 2^{ \Omega( \log^2({n\log n \over S}) / \log\log n )} \times (nS / \log n)^{1/2}$. (In a preliminary version of this paper by Edmonds and Poon [Proc. 27th Annual ACM Symposium on Theory of Computing, Las Vegas, NV, 1995, pp. 147--156.], a lower bound of $T \in 2^{ \Omega( \log^2({n\log n \over S}) / \log\log n )} \times (nS/\log n)^{1/2}$ was proved.) Our result greatly improves the previous lower bound of $ST \in \Omega(n^2/\log n)$ on the JAG model by Barnes and Edmonds [ Proc. 34th Annual Symposium on Foundations of Computer Science, Palo Alto, CA, 1993, pp. 228--237] and that of $S^{1/3}T \in \Omega(n^{4/3})$ on the NNJAG model by Edmonds [ Time-Space Lower Bounds for Undirected and Directed ST-Connectivity on JAG Models, Ph.D. thesis, University of Toronto, Toronto, ON, Canada, 1993]. Our lower bound is tight for $S \in O(n^{1-\delta})$, for any $\delta > 0$, matching the upper bound of Barnes \etal [ Proc. 7th Annual IEEE Conference on Structure in Complexity Theory, Boston, MA, 1992, pp. 27--33]. As a corollary of this improved lower bound, we obtain the first tight space lower bound of $\Omega( \log^2 n )$ on the NNJAG model. No tight space lower bound was previously known even for the more restricted JAG model.

Directed st-connectivity is the problem of detecting whether there is a path from a distinguished vertex s to a distinguished vertex t in a directed graph. We prove time--space lower bounds of $ST = \Omega({n^{2} \log n \over \log (n \log n/S)})$ and $S^{1 \over 2}T = \Omega(m (n \log n)^{1 \over 2})$ for directed st-connectivity on Cook and Rackoff's jumping automaton for graphs (JAG) model [SIAM J. Comput., 9(1980), pp. 636--652], where n is the number of vertices and m the number of edges in the input graph, S is the space, and T the time used by the JAG. These lower bounds are simple and elegant, they approach the known upper bound of T = O(m) when S approaches $\Theta(n \log n)$, and they are the first time--space tradeoffs for JAGs with an unrestricted number of jumping pebbles.

Undirected st-connectivity is an important problem in computing. There are algorithms for this problem that use O(n) time and ones that use O(log n) space. The main result of this paper is that, in a very natural structured model, these upper bounds are not simultaneously achievable. Any probabilistic jumping automaton for graphs (JAG) requires either space $\Omega( \log^2 n / \log log n )$ or time $n^{(1 + \Omega ( 1 / \log \log n )) }$ to solve undirected st-connectivity.

A multiprocessor system is unlikely to have access to information about the execution characteristics of the jobs it is to schedule. In this work, we are interested in scheduling algorithms for batch jobs that require no such knowledge (such algorithms are called nonclairvoyant) . Preemptive scheduling (i.e., redistribution of processors) is important to reduce mean response time in multiprocessor systems, especially in the widely available network of workstations. Preemption is a method to adapt to the uncertain and changing nature of jobs and workloads. Unfortunately, preemption may incur large overheads if it is applied frequently. To account for the cost preemptions, we consider a number of simple scheduling algorithms classified by the number of preemptions they are allowed, ranging from none to an infinite number. The Equi-part...

A propositionalproof system can be viewed as a non-deterministic algorithm for the (co-NP complete) unsatisfiabilit y problem.Many such proof systems, such as resolution, are rdso used as the basis for heuristics which deterministicrdly search for short proofs in the system.We discuss a propositional proof system baaed on algebraic rea soning, which we call the Groebner proof system because of a tight connection to the Groebner basis algorithm.For an appropriate measure of proof size, we show that (a degree-limited implement =ation of ) the Groebner basis algorithm finds a Groebner proof of a tautology in time polynomial in the size of the smallest such proof, In other words, urdike most proof systems, the non-deterministic algorithm can be converted to a deterministic one without loss in power.We then compare the power of the Groebner proof system to more studied systems.We show that the Groebner system polynomially simulates Horn clause resolution, quasi-polynomially simulates tree-like resolution, and weakly exponentially simulates resolution.Thus, Groebnerproofs will have better than worst-case behaviour on the same classes of inputs that resolution does.On the other hand, there are simple tautologies which have polynomialsize Groebner proofs but which require exponential-size resolution proofs.We also compare the Groebner proof system to the similar Nullstellensatz proof system introduced in [BIK+94].We show a family of tautologies that have degree 3 (and hence polynomirdsize) Groebner refutations, but which require @(W degree Nullst ellensat z refutations.Thus, there is an exponential separation between the two systems.These results suggest that the Groebner basis algorithm might replace mmlutian M s bseie far hem.ieticsfar NP.emnple&e pmh

We introduce a new method, called priority encoding transmission, for sending messages over lossy packet-based networks. When a message is to be transmitted, the user specifies a priority value for each part of the message. Based on the priorities, the system encodes the message into packets for transmission and sends them to (possibly multiple) receivers. The priority value of each part of the message determines the fraction of encoding packets sufficient to recover that part. Thus even if some of the encoding packets are lost en-route, each receiver is still able to recover the parts of the message for which a sufficient fraction of the encoding packets are received. For any set of priorities for a message, we define a natural quantity called the girth of the priorities. We develop systems for implementing any given set of priorities such that the total length of the encoding packets is equal to the girth. On the other hand, we give an information-theoretic lower bound that shows that for any set of priorities the total length of the encoding packets must be at least the girth. Thus the system we introduce is optimal in terms of the total encoding length. This work has immediate applications to multimedia and high-speed networks applications, especially in those with bursty sources and multiple receivers with heterogeneous capabilities. Implementations of the system show promise of being practical.

An (n,c,l,r) erasure code consists of an encoding algorithm and a decoding algorithm with the following properties. The encoding algorithm produces a set of l-bit packets of total length cn from an n-bit message. The decoding algorithm is able to recover the message from any set of packets whose total length is r, i.e., from any set of r/l packets. We describe erasure codes where both the encoding and decoding algorithms run in linear time and where r is only slightly larger than n.

Papadimitriou introduced several classes of NP search problems based on combinatorial principles which guarantee the existence of solutions to the problems.Many interesting search problems not known to be solvable in polynomial time are contained in these classes, and a number of them are complete problems.We consider the question of the relative complexity of these search problem classes.We prove several separations which show that in a generic relativized world, the search classes are distinct and there is a standard search problem in each of them that is not computationally equivalent to any decision problem.(Naturally, absolute separations would imply that P 6 = NP.)Our separation proofs have interesting combinatorial content and go to the heart of the combinatorial principles on which the classes are based.We derive one result via new lower bounds on the degrees of polynomials asserted to exist by Hilbert's Nullstellensatz over nite elds.

Article A nearly optimal time-space lower bound for directed st-connectivity on the NNJAG model Share on Authors: Jeff Edmonds International Computer Science Institute, Berkeley, California International Computer Science Institute, Berkeley, CaliforniaView Profile , Chung-Keung Poon Department of Computer Science, University of Toronto, Toronto, Ontario M5S 1A4 Department of Computer Science, University of Toronto, Toronto, Ontario M5S 1A4View Profile Authors Info & Claims STOC '95: Proceedings of the twenty-seventh annual ACM symposium on Theory of computingMay 1995 Pages 147–156https://doi.org/10.1145/225058.225103Online:29 May 1995Publication History 6citation270DownloadsMetricsTotal Citations6Total Downloads270Last 12 Months3Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We introduce a novel approach for sending messages over lossy packet-based networks. The new method, called Priority Encoding Transmission, allows a user to specify a different priority on each segment of the message. Based on the priorities, the sender uses the system to encode the segments into packets for transmission. The system ensures recovery of the segments in order of their priority. The priority of a segment determines the minimum number of packets sufficient to recover the segment. We define a measure for a set of priorities, called the rate, which dictates how much information about the message must be contained in each bit of the encoding. We develop systems for implementing any set of priorities with rate equal to one. We also give an information-theoretic proof that there is no system that implements a set of priorities with rate greater than one. This work has applications to multi-media and high speed networks applications, especially in those with bursty sources and multiple receivers with heterogeneous capabilities.>

Directed s-t connectivity is the problem of detecting whether there is a path from a distinguished vertex s to a distinguished vertex t in a directed graph. We prove time-space lower bounds of ST=/spl Omega/(n/sup 2//log n) and S/sup 1/2/T /spl Omega/(mn/sup 1/2/) for Cook and Rackoff's JAG model (1980), where n is the number of vertices and m the number of edges in the input graph, and S is the space and T the time used by the JAG. We also prove a time-space lower bound of S/sup 1/3/T=/spl Omega/(m/sup 2/3/n(2/3)) on the more powerful node-named JAG model of Poon (1993). These bounds approach the known upper bound of T=O(m) when S=/spl Theta/(n log n).>

Article Free Access Share on Time-space trade-offs for undirected st-connectivity on a JAG Author: Jeff Edmonds View Profile Authors Info & Claims STOC '93: Proceedings of the twenty-fifth annual ACM symposium on Theory of ComputingJune 1993 Pages 718–727https://doi.org/10.1145/167088.167272Published:01 June 1993Publication History 11citation205DownloadsMetricsTotal Citations11Total Downloads205Last 12 Months8Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

M. Karchmer et al. (1991) considered the circuit depth complexity of n-bit Boolean function constructed by composing up to d=log n/log log n levels of k=log-n-bit Boolean functions. Any such function is in AC/sup 1/. They conjecture that circuit depth is additive under composition, which would imply that any (bounded fan-in) circuit for this problem requires dk in Omega (log/sup 2/ n/log log n) depth. This would separate AC/sup 1/ from NC/sup 1/. They recommend using the communication game characterization of circuit depth. They suggest an intermediate problem which they call the universal composition relation. An almost optimal lower bound of dk-O(d/sup 2/(k log k)/sup 1/2/) is given for this problem. In addition, a proof, directly in terms of communication complexity, that there is a function on k bits requiring Omega (k) circuit depth is presented.>