A cycle basis of a graph is a minimal set of cycles from which every cycle in the graph can be generated by symmetric difference. We study the problem of constructing cycle bases of graphs with low maximum edge participation, defined as the maximum number of cycles in the basis that share any single edge. This quantity, though less studied than total weight or length, plays a critical role in quantum fault tolerance, as it directly impacts the overhead of lattice surgery procedures used to implement an almost universal quantum gate set. Building on a recursive algorithm by Freedman and Hastings, we introduce a family of load-aware heuristics that adaptively select vertices and edges to minimize edge participation throughout the cycle basis construction. Our approach improves empirical performance on random regular graphs and on graphs derived from small quantum codes. We further analyze a simplified balls-into-bins process to establish lower bounds on edge participation. While the model differs from the cycle basis algorithm on real graphs, it captures what can be proven for our heuristics without using more complex graph theoretic properties related to the distribution of cycles in the graph. Our analysis suggests that the maximum load of all of our heuristics will be Ω(log² n). Our results indicate that careful cycle basis construction can yield significant practical benefits in the design of fault-tolerant quantum systems. Maximum edge participation has been studied in the graph theory literature under the name basis number, which is the minimum possible maximum edge participation over all cycle bases in a graph.

We introduce a quantum algorithm design paradigm called combine and conquer, which is a quantum version of the "marriage-before-conquest" technique of Kirkpatrick and Seidel. In a quantum combine-and-conquer algorithm, one performs the essential computation of the combine step of a quantum divide-and-conquer algorithm prior to the conquer step while avoiding recursion. This model is better suited for the quantum setting, due to its non-recursive nature. We show the utility of this approach by providing quantum algorithms for 2D maxima set and convex hull problems for sorted point sets running in Õ(√{nh}) time, w.h.p., where h is the size of the output.

Despite immense progress in quantum Hamiltonian complexity in the past decade, little is known about the computational complexity of quantum physics at the thermodynamic limit. In fact, even defining the problem properly is not straight forward. We study the complexity of estimating the ground energy of a fixed, translationally-invariant (TI) Hamiltonian in the thermodynamic limit, to within a given precision; this precision (given by n the number of bits of the approximation) is the sole input to the problem. Understanding the complexity of this problem captures how difficult it is for a physicist to measure or compute another digit in the approximation of a physical quantity in the thermodynamic limit. We show that this problem is contained in FEXP QMA-EXP and is hard for FEXP NEXP . This means that the problem is doubly exponentially hard in the size of the input. As an ingredient in our construction, we study the problem of computing the ground energy of translationally invariant finite 1D chains. A single Hamiltonian term, which is a fixed parameter of the problem, is applied to every pair of particles in a finite chain. In the finite case, the length of the chain is the sole input to the problem and the task is to compute an approximation of the ground energy. No thresholds are provided as in the standard formulation of the local Hamiltonian problem. We show that this problem is contained in FP QMA-EXP and is hard for FP NEXP . Our techniques employ a circular clock structure in which the ground energy is calibrated by the length of the cycle. This requires more precise expressions for the ground energies of the resulting matrices than were required for previous QMA-completeness constructions and even exact analytical bounds for the infinite case which we derive using techniques from spectral graph theory. To our knowledge, this is the first use of the circuit-to-Hamiltonian construction that shows hardness for a function class.

In this work, we provide the first QFT-free algorithm for Quantum Amplitude Estimation (QAE) that is asymptotically optimal while maintaining the leading numerical performance. QAE algorithms appear as a subroutine in many applications for quantum computers. The optimal query complexity achievable by a quantum algorithm for QAE is log queries, providing a speedup of a factor of 1/ε over any other classical algorithm for the same problem. The original algorithm for QAE utilizes the quantum Fourier transform (QFT) which is expected to be a challenge for near-term quantum hardware. To solve this problem, there has been interest in designing a QAE algorithm that avoids using QFT. Recently, the iterative QAE algorithm (IQAE) [1] was introduced with a near-optimal query complexity and small constant factors. In this work, we combine ideas from the preceding line of work to introduce a QFT-free QAE algorithm that maintains the asymptotically optimal query complexity while retaining small constant factors. We supplement our analysis with numerical experiments comparing our performance with IQAE where we find that our modifications retain the high performance, and in some cases even improve the numerical results.

We study the complexity of classical constraint satisfaction problems on a 2D grid. Specifically, we consider the complexity of function versions of such problems, with the additional restriction that the constraints are translationally invariant, namely, the variables are located at the vertices of a 2D grid and the constraint between every pair of adjacent variables is the same in each dimension. The only input to the problem is thus the size of the grid. This problem is equivalent to one of the most interesting problems in classical physics, namely, computing the lowest energy of a classical system of particles on the grid. We provide a tight characterization of the complexity of this problem, and show that it is complete for the class $FP^{NEXP}$. Gottesman and Irani (FOCS 2009) also studied classical translationally-invariant constraint satisfaction problems; they show that the problem of deciding whether the cost of the optimal solution is below a given threshold is NEXP-complete. Our result is thus a strengthening of their result from the decision version to the function version of the problem. Our result can also be viewed as a generalization to the translationally invariant setting, of Krentel's famous result from 1988, showing that the function version of SAT is complete for the class $FP^{NP}$. An essential ingredient in the proof is a study of the complexity of a gapped variant of the problem. We show that it is NEXP-hard to approximate the cost of the optimal assignment to within an additive error of $Ω(N^{1/4})$, for an $N \times N$ grid. To the best of our knowledge, no gapped result is known for CSPs on the grid, even in the non-translationally invariant case. As a byproduct of our results, we also show that a decision version of the optimization problem which asks whether the cost of the optimal assignment is odd or even is also complete for $P^{NEXP}$.

It is a useful fact in classical computer science that many search problems are reducible to decision problems; this has led to decision problems being regarded as the $\textit{de facto}$ computational task to study in complexity theory. In this work, we explore search-to-decision reductions for quantum search problems, wherein a quantum algorithm makes queries to a classical decision oracle to output a desired quantum state. In particular, we focus on search-to-decision reductions for $\mathsf{QMA}$, and show that there exists a quantum polynomial-time algorithm that can generate a witness for a $\mathsf{QMA}$ problem up to inverse polynomial precision by making one query to a $\mathsf{PP}$ decision oracle. We complement this result by showing that $\mathsf{QMA}$-search does $\textit{not}$ reduce to $\mathsf{QMA}$-decision in polynomial-time, relative to a quantum oracle. We also explore the more general $\textit{state synthesis problem}$, in which the goal is to efficiently synthesize a target state by making queries to a classical oracle encoding the state. We prove that there exists a classical oracle with which any quantum state can be synthesized to inverse polynomial precision using only one oracle query and to inverse exponential precision using two oracle queries. This answers an open question of Aaronson from 2016, who presented a state synthesis algorithm that makes $O(n)$ queries to a classical oracle to prepare an $n$-qubit state, and asked if the query complexity could be made sublinear.

Despite immense progress in quantum Hamiltonian complexity in the past decade, little is known about the computational complexity of quantum physics at the thermodynamic limit. In fact, even defining the problem properly is not straight forward. We study the complexity of estimating the ground energy of a fixed, translationally-invariant (TI) Hamiltonian in the thermodynamic limit, to within a given precision; this precision (given by n the number of bits of the approximation) is the sole input to the problem. Understanding the complexity of this problem captures how difficult it is for a physicist to measure or compute another digit in the approximation of a physical quantity in the thermodynamic limit. We show that this problem is contained in FEXPQMA-EXP and is hard for FEXPNEXP. This means that the problem is doubly exponentially hard in the size of the input.

Online education offers an attractive alternative to face-to-face classes by providing flexibility to students and efficiencies for educational institutions. Leveraging online technology has the potential to help computer science departments offer a quality educational experience in the face of burgeoning enrollments. However, effective online course design is critical to student satisfaction and learning outcomes. In this paper, we describe the experience of converting a large face-to-face course in Discrete Mathematics to an online format. Particular care was taken to incorporate active learning strategies, such as clicker questions and interactive discussions, in order to enhance student engagement. We describe ways in which we cultivated an active instructor presence in the course through carefully designed pre-recorded videos, online video conferencing, and participation in Piazza, an online social learning platform. In-class tests were specifically designed to provide a meaningful comparison of learning outcomes between a face-to-face and online offering of the course taught by the same instructor. The results indicate that there is no loss in student performance in the online course, even after accounting for demographic and academic differences between the students enrolled in the two courses. There is also no significant difference in performance for "at-risk" students. End-of-quarter student evaluations show a high level of student satisfaction with the online format, especially in regards to the opportunities to have questions answered and the positive presence of the instructor in the course.

Advances in storage technology have introduced Non-Volatile Memory, NVM, as a new storage medium. NVM, along with DRAM and Disk present a system designer with a wide array of options in designing caching middleware. Moreover, design decisions to replicate a data item in more than one level of a caching memory hierarchy may enhance the overall system performance with a faster recovery time in the event of a memory failure. Given a fixed budget, the key configuration questions are: Which storage media should constitute the memory hierarchy? What is the storage capacity of each hierarchy? Should data be replicated or partitioned across the different levels of the hierarchy? We study a model of these cache configuration questions and present results from a simple algorithm to evaluate design tradeoffs in the context of a memory hierarchy for a Key-Value Store, e.g., memcached. The results show selective replication is appropriate with certain failure rates and workload characteristics. With a slim failure rate and frequent data updates, tiering of data across the different storage media that constitute the cache is superior to replication.

We introduce the subset assignment problem in which items of varying sizes are placed in a set of bins with limited capacity. Items can be replicated and placed in any subset of the bins. Each (item, subset) pair has an associated cost. Not assigning an item to any of the bins is not free in general and can potentially be the most expensive option. The goal is to minimize the total cost of assigning items to subsets without exceeding the bin capacities. The subset assignment problem models the problem of managing a cache composed of banks of memory with varying cost/performance specifications. The ability to replicate a data item in more than one memory bank can benefit the overall performance of the system with a faster recovery time in the event of a memory failure. For this setting, the number n of data objects (items) is very large and the number d of memory banks (bins) is a small constant (on the order of 3 or 4). Therefore, the goal is to determine an optimal assignment in time that minimizes dependence on n. The integral version of this problem is NP-hard since it is a generalization of the knapsack problem. We focus on an efficient solution to the LP relaxation as the number of fractionally assigned items will be at most d. If the data objects are small with respect to the size of the memory banks, the effect of excluding the fractionally assigned data items from the cache will be small. We give an algorithm that solves the LP relaxation and runs in time $$O(\left( {\begin{array}{c}3^d\\ d+1\end{array}}\right) {\text {poly}}(d) n \log (n) \log (nC) \log (Z))$$ , where Z is the maximum item size and C the maximum storage cost.

This section of SICOMP contains 11 specially selected papers from the Forty-seventh Annual ACM Symposium on Theory of Computing, otherwise known as STOC 2015, held June 15 to 17 in Portland, Oregon. The papers here were chosen to represent both the excellence and the broad range of the STOC program. The papers have been revised and extended by the authors and subjected to the standard thorough reviewing process of SICOMP. The program committee consisted of Ronitt Rubinfeld (chair), Benny Applebaum, Niv Buchbinder, Edith Cohen, Costis Daskalakis, Ilias Diakonikolas, Shaddin Dughmi, Michael Forbes, Michel Goemans, Elena Grigorescu, Venkatesan Guruswami, Bernhard Haeupler, Sandy Irani, Yael Kalai, Sanjeev Khanna, Swastik Kopparty, Krzysztof Onak, Anup Rao, Ben Reichardt, Yaron Singer, Nikhil Srivastava, Chris Umans, Ola Svensson, Jonathan Ullman, Udi Wieder, and Mary Wootters. We briefly describe the papers that appear here. Sketching and Embedding Are Equivalent for Norms, by Alexandr Andoni, Robert Krauthgamer, and Ilya Razenshteyn, provides an almost complete characterization of sketching in terms of embeddings for normed spaces. Inapproximability of Nash Equilibrium, by Aviad Rubinstein, proves that finding an $\epsilon$-approximate Nash equilibrium is PPAD-complete for some constant value of $\epsilon$ in multiplayer games with binary strategies and sparse player interactions, where each player's payoff depends on the strategy of at most three other players; this resolves an open problem of about a decade on the complexity of approximate Nash equilibrium. Approximating Nash Equilibria and Dense Subgraphs via an Approximate Version of Carathéodory's Theorem, by Siddharth Barman, provides a self-contained proof of an approximate version of Carathéodory's theorem for $p$-norm approximating vectors in a polytope of bounded $p$-norm vectors via a convex combination of a dimension-independent number of polytope vertices, along with algorithmic applications of this theorem, including a polynomial-time approximation scheme for Nash equilibrium in two-player games with fixed column sparsity, and an additive approximation algorithm for the normalized densest $k$-subgraph problem. Forrelation: A Problem That Optimally Separates Quantum from Classical Computing, by Scott Aaronson and Andris Ambainis, achieves essentially the largest possible separation between quantum and classical query complexities using a property-testing problem called Forrelation. On the Lovász Theta Function for Independent Sets in Sparse Graphs, by Nikhil Bansal, Anupam Gupta and Guru Prashanth Guruganesh, shows that the integrality gap of the Lovász $\vartheta$-function is $\tilde{O}(d/\log^2 d)$. Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order, by Nitish Korula, Vahab Mirrokni, and Morteza Zadimoghaddam, considers an online version of the Submodular Welfare Maximization problem and shows that the greedy algorithm obtains a competitive ratio of at least .505 in the random order model. Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH Is False), by Arturs Backurs and Piotr Indyk, shows that if the edit distance between two strings can be computed in time $O(n^{2-\delta})$ for some constant $\delta > 0$, then the strong exponential time hypothesis would be violated. Matching Triangles and Basing Hardness on an Extremely Popular Conjecture, by Amir Abboud, Virginia Vassilevska Williams, and Huacheng Yu, obtains novel lower bounds under the assumption that at least one of the 3-SUM, APSP, and CNF-SAT hypotheses are true. Indistinguishability Obfuscation for RAM Programs and Succinct Randomized Encodings, by Nir Bitansky, Ran Canetti, Sanjam Garg, Justin Holmgren, Abhishek Jain, Huijia Lin, Rafael Pass, Sidharth Telang, and Vinod Vaikuntanathan, shows a novel use of an indistinguishability obfuscation (iO) for circuits to construct a succinct randomized encoding scheme, and an iO for RAM programs; prior to this work, there were no candidates for either of these two primitives. Approximating the Nash Social Welfare with Indivisible Items, by Richard Cole and Vasilis Gkatzelis, provides the first efficient constant-factor approximation algorithm for the problem of allocating a set of indivisible items among agents with additive valuations, with the goal of maximizing the geometric mean of the agents’ valuations, also called the Nash social welfare. Gaussian Cooling and $O^*(n^3)$ Algorithms for Volume and Gaussian Volume, by Ben Cousins and Santosh Vempala, gives a $O^*(n^3)$ randomized algorithm for estimating the volume of a well-rounded convex body given by a membership oracle, improving on the previous best complexity of $O^*(n^4)$, as well as an $O^*(n^3)$ algorithm for computing the Gaussian volume of a convex set that contains the unit ball. The following paper was also invited to the special section but remains in review at this writing. If accepted, it will appear in a later SICOMP issue. Randomized Composable Core-Sets for Distributed Submodular Maximization, by Vahab Mirrokni and Morteza Zadimoghaddam, shows how a randomized version of composable core-sets can beat impossibility results for the deterministic version on coverage, monotone, and non-monotone submodular maximization problems. We thank the authors and the program committee for their hard work, and we especially thank the reviewers for their work in evaluating and improving the submitted papers.

In the generalized caching problem, items can have varying costs and sizes. We consider a variant of this problem in which the cache management policy must not only specify which items to evict to make room for an incoming item (cache replacement), but must also specify a location in memory where each object can be placed contiguously (memory allocation). The problem is motivated by current implementations of key-value stores in large commercial databases with high read-to-write ratio such as those maintained by Facebook and Twitter. We propose a simple algorithm and show that if the algorithm is given some additional memory to account for fragmentation, it is competitive against an offline optimal algorithm that does not specify memory layout. (The optimal algorithm needs only to ensure that the sum of the sizes of the items in the cache does not exceed the total capacity of the cache). On the benchmark traces in the experiments presented here, our algorithm requires approximately 10–15– additional space to be k-competitive against the optimal offline algorithm. Through trace-driven simulations, we demonstrate that the caching performance of our algorithm for cache replacement with memory allocation is close to that of competitive strategies that are not required to manage memory layout within the cache.

Cost Adaptive Multi-queue eviction Policy (CAMP) is an algorithm for a general purpose key-value store (KVS) that manages key-value pairs computed by applications with different access patterns, key-value sizes, and varying costs for each key-value pair. CAMP is an approximation of the Greedy Dual Size (GDS) algorithm in that its eviction policy is as effective as GDS. At the same time, its implementation is as efficient at LRU. Similar to an implementation of LRU using queues, it adapts to changing workload patterns based on the history of requests for different key-value pairs. It is superior to LRU because it considers both the size and cost of key-value pairs to maximize the utility of the available memory across competing applications. We compare CAMP with both LRU and an alternative that requires human intervention to partition memory into pools and assign grouping of key-value pairs to different pools. The results demonstrate CAMP is as fast as LRU while outperforming both LRU and the pooled alternative. We also present results from an implementation of CAMP using Twitter's version of memcached.

We study the complexity of a class of problems involving satisfying constraints which remain the same under translations in one or more spatial directions. In this paper, we show hardness of a classical tiling problem on an (N x N) 2-dimensional grid and a quantum problem involving finding the ground state energy of a 1-dimensional quantum system of N particles. In both cases, the only input is N, provided in binary. We show that the classical problem is NEXP-complete and the quantum problem is QMAEXP-complete. Thus, an algorithm for these problems that runs in time polynomial in N (exponential in the input size) would imply EXP = NEXP or BQEXP = QMAEXP, respectively. Although tiling in general is already known to be NEXP-complete, to our knowledge, all previous reductions require that either the set of tiles and their constraints or some varying boundary conditions be given as part of the input. In the problem considered here, these are fixed, constant-sized parameters of the problem. Instead, the problem instance is encoded solely in the size of the system.

We consider the problem of selecting threshold times to transition a device to low-power sleep states during an idle period. The two-state case, in which there is a single active and a single sleep state, is a continuous version of the ski-rental problem. We consider a generalized version in which there is more than one sleep state, each with its own power-consumption rate and transition costs. We give an algorithm that, given a system, produces a deterministic strategy whose competitive ratio is arbitrarily close to optimal. We also give an algorithm to produce the optimal online strategy given a system and a probability distribution that generates the length of the idle period. We also give a simple algorithm that achieves a competitive ratio of $3 + 2\sqrt{2} \approx 5.828$ for any system.

We study the computational strength of quantum particles (each of finite dimensionality) arranged on a line. First, we prove that it is possible to perform universal adiabatic quantum computation using a one-dimensional quantum system (with 9 states per particle). Building on the same construction, but with some additional technical effort and 12 states per particle, we show that the problem of approximating the ground state energy of a system composed of a line of quantum' particles is QMA-complete; QMA is a quantum analogue of NP. This is in striking contrast to the analogous classical problem, one dimensional MAX-2-SAT with nearest neighbor constraints, which is in P.The proof of the QMA-completeness result requires an additional idea beyond the usual techniques in the area: Some illegal configurations cannot be ruled out by local checks, and are instead ruled out because they would, in the future, evolve into a state which can be seen locally to be illegal. Assuming BQP ne QMA, our construction gives a one-dimensional system which takes an exponential time to relax to its ground state at any temperature. This makes it a candidate for a one-dimensional spin glass.

This article examines two different mechanisms for saving power in battery-operated embedded systems. The first strategy is that the system can be placed in a sleep state if it is idle. However, a fixed amount of energy is required to bring the system back into an active state in which it can resume work. The second way in which power savings can be achieved is by varying the speed at which jobs are run. We utilize a power consumption curve P ( s ) which indicates the power consumption level given a particular speed. We assume that P ( s ) is convex, nondecreasing, and nonnegative for s ≥ 0. The problem is to schedule arriving jobs in a way that minimizes total energy use and so that each job is completed after its release time and before its deadline. We assume that all jobs can be preempted and resumed at no cost. Although each problem has been considered separately, this is the first theoretical analysis of systems that can use both mechanisms. We give an offline algorithm that is within a factor of 2 of the optimal algorithm. We also give an online algorithm with a constant competitive ratio.

Study of contrast sensitivity of the human eye shows that our suprathreshold contrast sensitivity follows the Weber Law and, hence, increases proportionally with the increase in the mean local luminance. In this paper, we effectively apply this fact to design a contrast-enhancement method for images that improves the local image contrast by controlling the local image gradient with a single parameter. Unlike previous methods, we achieve this without explicit segmentation of the image, either in the spatial (multiscale) or frequency (multiresolution) domain. We pose the contrast enhancement as an optimization problem that maximizes the average local contrast of an image strictly constrained by a perceptual constraint derived directly from the Weber Law. We then propose a greedy heuristic, controlled by a single parameter, to approximate this optimization problem.

This paper examines two variants of strip packing: when the rectangles to be placed have precedence constraints and when the rectangles have release times. Strip packing can be used to model scheduling problems in which tasks require a contiguous subset of identical resources that are arranged in a linear topology. The particular variants studied here are motivated by scheduling tasks for dynamically reconfigurable Field-Programmable Gate Arrays (FPGAs) comprised of an array of computing columns. Each column is a computing resource and the array of columns forms the linear topology of resources. We assume that the given FPGA has K columns, where K is a fixed positive integer, and each task occupies a contiguous subset of these columns. For the case in which tasks have precedence constraints, we give an O(log n) approximation, where n is the number of tasks. We then consider the special case in which all the rectangles have uniform height and reduce it to the resource constrained scheduling studied by Garey, Graham, Johnson and Yao, thereby extending their asymptotic results to our special case problem. We also give an absolute 3-approximation for this special case problem. For strip packing with release times, we provide an asymptotic polynomial time (1 + e)- approximation scheme. We make the standard assumption that the rectangles have height at most 1. In addition, we also require widths to be in [1K, 1], i.e., the rectangles are at least as wide as a column in the FPGA. Our running time is polynomial in n and 1/e, but exponential in K.

Dynamic power management (DPM) refers to the problem of judicious application of various low-power techniques based on runtime conditions in an embedded system to minimize the total energy consumption. To be effective, often such decisions take into account the operating conditions and the system-level design goals. DPM has been a subject of intense research in the past decade driven by the need for low power consumption in modern embedded devices. We present a comprehensive overview of two closely related approaches to designing DPM strategies, namely, competitive analysis approach and model checking approach based on adversarial modeling. Although many other approaches exist for solving the system-level DPM problem, these two approaches are closely related and are based on a common theme. This commonality is in the fact that the underlying model is that of a competition between the system and an adversary. The environment that puts service demands on devices is viewed as an adversary, or to be in competition with the system to make it burn more energy, and the DPM strategy is employed by the system to counter that.

We consider the problem of selecting threshold times to transition a device to low-power sleep states during an idle period. The two-state case in which there is a single active and a single sleep state is a continuous version of the ski-rental problem. We consider a generalized version in which there is more than one sleep state, each with its own power consumption rate and transition costs. We give an algorithm that, given a system, produces a deterministic strategy whose competitive ratio is arbitrarily close to optimal. We also give an algorithm to produce the optimal online strategy given a system and a probability distribution that generates the length of the idle period. We also give a simple algorithm that achieves a competitive ratio of 3 + 2/spl radic/2 /spl ap/ 5.828 for any system.

Summary form only given. Many distributed applications in the real world now require real time services in which aggregate queries need to be computed over a set of values. These applications can often tolerate varying degrees of inaccuracy in the results. System designers, on the other hand, would like to provide services with low inaccuracy and minimal management overhead. We focus on addressing the tradeoffs between timeliness, accuracy and cost for data aggregation in distributed environments. Specifically, we address the problem of time-sensitive computation of aggregate queries (count, sum and min) over a set of values represented by intervals with lower and upper bounds. These intervals are approximations based on most recent values about distributed sources. In order to meet the precision constraints from users, a subset of sources needs to be probed for exact values. We first propose algorithms for batch selection of the probing set, where selection is done before probing without the knowledge of the actual values. In addition, we propose an iterative selection approach where the selection of the next probing source depends on the previous returned value.

Online dynamic power management (DPM) strategies refer to strategies that attempt to make power-mode-related decisions based on information available at runtime. In making such decisions, these strategies do not depend upon information of future behavior of the system, or any a priori knowledge of the input characteristics. In this paper, we present online strategies, and evaluate them based on a measure called the competitive ratio that enables a quantitative analysis of the performance of online strategies. All earlier approaches (online or predictive) have been limited to systems with two power-saving states (e.g., idle and shutdown). The only earlier approaches that handled multiple power-saving states were based on stochastic optimization. This paper provides a theoretical basis for the analysis of DPM strategies for systems with multiple power-down states, without resorting to such complex approaches. We show how a relatively simple "online learning" scheme can be used to improve the competitive ratio over deterministic strategies using the notion of "probability-based" online DPM strategies. Experimental results show that the algorithm presented here attains the best competitive ratio in comparison with other known predictive DPM algorithms. The other algorithms that come close to matching its performance in power suffer at least an additional 40% wake-up latency on average. Meanwhile, the algorithms that have comparable latency to our methods use at least 25% more power on average.

We present strategies for "online" dynamic power management (DPM) based on the notion of the competitive ratio that allows us to compare the effectiveness of algorithms against an optimal strategy. This paper makes two contributions: it provides a theoretical basis for the analysis of DPM strategies for systems with multiple power down states; and provides a competitive algorithm based on probabilistically generated inputs that improves the competitive ratio over deterministic strategies. Experimental results show that our probability-based DPM strategy improves the efficiency of power management over the deterministic DPM strategy by 25%, bringing the strategy to within 23% of the optimal offline DPM.

The problem of power management for an embedded system is to reduce system level power dissipation by shutting off parts of the system when they are not being used and turning them back on when requests have to be serviced. Algorithms for this problem are online in nature; the algorithm must operate only with access to data that it has seen so far and without access to the complete data set or its characteristics. We present online algorithms to manage power for embedded systems and discuss their effects on system latency. We introduce competitive analysis as a formal framework for the evaluation of various power management algorithms. Competitive analysis does not depend on the distribution of interarrival times of requests. We present a nonadaptive online algorithm, analyze its behavior, and show that it is optimal. We also present a lower bound on the competitiveness of any adaptive algorithm. We show that no adaptive online algorithm can dissipate less than about 1.6 times the power dissipated by the optimal offline algorithm in the worst case. We also show that in order for any online algorithm to achieve this lower bound, it may have to maintain a complete history of the interarrival. times of the requests in the input sequence. Since this is not practical, we present a simple algorithm that uses only the last interarrival time to predict the arrival of the next request.

With advances in storage technology, the ability to provide client end storage for continuous media applications has become a possibility. Transmission of data in cluster based multimedia environments can be semi-continuous in conjunction with client side buffering and staging. Experiments indicate that a client buffer size (staging degree) of 20 percent (of object size) is near optimal for most objects. The work presented in this paper also addresses the implications of semi-continuous transmission to placement and admission control mechanisms in a cluster-based multimedia server. We improve admission control by introducing a technique called dynamic request migration in clusterbased multimedia servers that is enabled by client staging. Simulation studies demonstrate that close to maximum utilization can be achieved even if at most one migration within the server cluster is performed for each request arrival and each request is migrated at most once during its lifetime. Furthermore, our performance results reveal that with client staging and dynamic request migration, even naive placement techniques are tolerant to extreme variations in request patterns. In fact, our results indicate that under most circumstances one can be oblivious to request pattern variations during placement, eliminating the need to predict relative popularities of objects. 1.

A power management algorithm for an embedded system reduces system level power dissipation by shutting off parts of the system when they are not being used and turning them back on when they are required. Algorithms for this problem are online in nature since they must operate without knowledge of the arrival time or service requirements of future requests. In this paper, we present online algorithms to manage power for embedded systems. We perform an empirical analysis of these algorithms and give theoretical justification for the empirical results. Effective power management strategies have an adverse impact on the latency of the system for which the strategy is designed. Typically, the more aggressive the power management scheme, the greater the increase in the latency of the system. In this paper, we prove an upper bound on the additional latency of the system introduced by power management strategies. Moreover, we show that this upper bound occurs each time the system is shutdown and hence is an important system design parameter. In addition, service time and latencies have an effect on power management strategies since they alter the length and occurrences of idle periods which. We study this phenomenon experimentally, by modeling the disk drive of a laptop computer as an embedded system. The results show that if service times of arriving requests are modeled, the relative performance of algorithms can change leading to non-adaptive algorithms performing better than adaptive ones. We compare the performance of adaptive and non-adaptive power management algorithms. In particular, our experimental results show that an "immediate" shutdown strategy that shuts down the system whenever it encounters an idle period performs surprising better than sophisticated adaptive algorithms suggested in the literature. We provide an analytical explanation for the effectiveness of power management strategies.

The goal of this paper is to identify the most efficient algorithms for the optimum mean cycle and optimum cost to time ratio problems and compare them with the popular ones in the CAD community.These problems have numerous important applications in CAD, graph theory, discrete event system theory, and manufacturing systems.In particular, they are fundamental to the performance analysis of digital systems such as synchronous, asynchronous, dataflow, and embedded real-time systems.For instance, algorithms for these problems are used to compute the cycle period of any cyclic digital system.Without loss of generality, we discuss these algorithms in the context of the minimum mean cycle problem (MCMP).We performed a comprehensive experimental study of ten leading algorithms for MCMP.We programmed these algorithms uniformly and efficiently.We systematically compared them on a test suite composed of random graphs as well as benchmark circuits.Above all, our results provide important insight into the performance of these algorithms in practice.One of the most surprising results of this paper is that Howard's algorithm, known primarily in the stochastic control community, is by far the fastest algorithm on our test suite although the only known bound on its running time is exponential.We provide two stronger bounds on its running time.

We study on-line scheduling in overloaded systems. Requests for jobs arrive one by one as time proceeds; the serving agents have limited capacity and not all requests can be served. Still, we want to serve the "best" set of requests according to some criterion. In this situation, the ability to preempt (i.e., abort) jobs in service in order to make room for better jobs that would otherwise be rejected has proven to be of great help in some scenarios. We show that, surprisingly, in many other scenarios this is not the case. In a simple, generic model, we prove a polylogarithmic lower bound on the competitiveness of randomized and preemptive on-line scheduling algorithms. Our bound applies to several recently studied problems. In fact, in certain scenarios our bound is quite close to the competitiveness achieved by known deterministic, nonpreemptive algorithms.

We consider the paging problem where the pages have varying size.This problem has applications to page replacement policies for caches containing World Wide Web documents.We consider two models for the cost of an algorithm on a request sequence.In this first, (the FAULT model) the goal is to minimize the number of page faults.In the second, (the BIT model) the goal is to minimize the total number of bits which have to be read into the cache.We show offline algorithms for both cost models which obtain approximation factors of O(log k), where k is the ratio of the size of the cache to the size of the smallest page.We show randomized online algorithms for both cost models which are O(log2 k)-competitive.In addition, if the input sequence is generated by a known distribution, we show algorithms for both cost models whose expected cost is within a factor of O(log k) of any other online algorithm.

Abstract The subject of this paper is the design and analysis of Monte Carlo algorithms for two basic matching techniques used in model-based recognition: alignment, and geometric hashing. We first give analyses of our Monte Carlo algorithms, showing that they are asymptotically faster than their deterministic counterparts while allowing failure probabilities that are provably very small. We then describe experimental results that bear out this speed-up, suggesting that randomization results in significant improvements in running time. Our theoretical analyses are not the best possible; as a step to remedying this we define a combinatorial measure of self-similarity for point sets, and give an example of its power.

What is the best paging algorithm if one has partial information about the possible sequences of page requests? We give a partial answer to this question by presenting the analysis of strongly competitive paging algorithms in the access graph model. This model restricts page requests so that they conform to a notion of locality of reference given by an arbitrary access graph We first consider optimal algorithms for undirected access graphs. Borodin et al. [Proc. 23rd ACM Symposium on Theory of Computing, 1991, pp. 249–259] define an algorithm, called FAR, and prove that it is within a logarithmic factor of the optimal online algorithm. We prove that FAR is in fact strongly competitive, i.e, within a constant factor of the optimum. For directed access graphs, we present an algorithm that is strongly competitive on structured program graphs—graphs that model a subset of the request sequences of structured programs.

We discuss settings where several “agents” combine efforts to solve problems. This is a well-known setting in distributed artificial intelligence. Our work addresses theoretical questions in this model which are motivated by the work of Deng and Papadimitriou [Proc. 12th IFIPS Congress, Madrid, 1992; Proc. World Economic Congress, Moscow, 1992]. We consider optimization problems, in particular load balancing and virtual circuit routing, in which the input is divided among the agents. An underlying directed graph, whose nodes are the agents, defines the constraints on the information each agent may have about the portion of the input held by other agents. The questions we discuss are as follows: Given a bound on the maximum out-degree in this graph, which is the best graph? What is the quality of the solution obtained as a function of the maximum out-degree?

We study on-line scheduling in overloaded systems.Requests for jobs arrive one by one as time proceeds; the serving agents have limited capacity and not all requests can be served, Still, we want to serve the 'best' set of requests according to some criterion.In this situation, the ability to preempt (i.e., abort) jobs in service in order to make room for better jobs that would otherwise be rejected has proven to be of great help in some scenarios.We show that, surprisingly, in many other scenarios this is not the case.In a simple, generic model, we prove a polylogarithmic lower bound on the competitiveness of randomized and preemptive on-line scheduling algorithms.Our bound applies to several recently studied problems.In fact, in certain scenarios our bound is quite close to the competitiveness achieved by known deterministic, non-preemptive algorithms.

We discuss settings where several "agents" combine efforts to solve problems. This is a well-known setting in distributed artificial intelligence. Our work addresses theoretical questions in this model which are motivated by the work of X. Deng and C.H. Papadimitriou (1992). We consider optimization problems, in particular load balancing and virtual circuit routing, in which the input is divided among the agents. An underlying directed graph, whose nodes are the agents, defines the constraints on the information each agent may have about the portion of the input held by other agents. The questions we discuss are: Given a bound on the maximum out-degree in this graph, which is the best graph? What is the quality of the solution obtained as a function of the maximum out-degree?.>

The Sleator-Tarjan competitive analysis of paging [19] gives us the ability to make strong theoretical statements about the performance of paging algorithms without making probabilistic assumptions on the input.Nevertheless practitioners voice reservations about the model, citing its inability to discern between is that it is more robust than probabilistic analysis, while more practical than worst-case analysis.With these definitions, Sleator and Tarjan showed that no deterministic on-line paging algorithm can achieve a competitiveness less than k, and that a number of algorithms used in practice (including Least Recently Used or LRU and First-In First-Out or FIFO) are kcompetitive and thus optimal by this measure.

Online graph coloring, in which the vertices are presented one at a time, is considered. Each vertex must be assigned a color, different from the colors of its neighbors, before the next vertex is given. The class of d-inductive graphs is treated. A graph G is said to be d-inductive if the vertices of G can be numbered so that each vertex has at most d edges to higher numbered vertices. First Fit (FF) is the algorithm that assigns each vertex the lowest numbered color possible. It is shown that if G is d-inductive, then FF uses O(d log n) colors on G. This yields an upper bound of O(log n) on the performance ratio of FF on chordal and planar graphs. FF does as well as any online algorithm for d-inductive graphs; it is shown that for any d and any online graph-coloring algorithm A, there is a d-inductive graph that forces A to use Omega (d log n) colors to color G. Online graph coloring with lookahead is also investigated.>