An Efficient Algorithm for approximating 1D Ground States (2009)
Aharonov, Dorit, Arad, Itai, Irani, Sandy
The most commonly used algorithm for approximating ground states of 1D quantum systems is the Density Matrix Renormalization Group approach (DMRG). DMRG works very well in practice, but there is no...
Gottesman, Daniel, Irani, Sandy
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...
Sandy Irani, John Augustine, Chaitanya Swamy
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...
Ground State Entanglement in One Dimensional Translationally Invariant Quantum Systems (2009)
We examine whether it is possible for one-dimensional translationally-invariant Hamiltonians to have ground states with a high degree of entanglement. We present a family of translationally invariant...
Sandy Irani, John Augustine, Chaitanya Swamy
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...
Online Strategies for Dynamic Power Management in Systems with Multiple (2008)
Power-saving States, Sandy Irani, Sandeep Shukla, Rajesh Gupta
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...
A Comparison of Performance Measures for Online Algorithms (2008)
Boyar, Joan, Irani, Sandy, Larsen, Kim S.
This paper provides a systematic study of several recently suggested measures for online algorithms in the context of a specific problem, namely, the two server problem on three colinear points. We...
Perception-Based Contrast Enhancement of Images (2008)
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...
Optimal Power-Down Strategies (2008)
Augustine, John, Irani, Sandy, Swamy, Chaitanya
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...
The Problem of Renting versus Buying (2007)
Sandy Irani, Dinesh Ramanathan
The problem studied here is a member of a large class of on-line decision problems. The basic question is to choose from two possible alternatives at a given instance, for the use of an item. This...
The Complexity of Quantum Systems on a One-dimensional Chain (2007)
We prove that adiabatic computation is equivalent to standard quantum computation even when the adiabatic quantum system is restricted to be a set of particles on a one-dimensional chain. We give a...
The power of quantum systems on a line (2007)
Aharonov, Dorit, Gottesman, Daniel, Irani, Sandy, Kempe, Julia
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...
Algorithmic problems in power management (2005)
We survey recent research that has appeared in the theoretical computer science literature on algorithmic
Optimal power-down strategies (2004)
Sandy Irani, John Augustine, Chaitanya Swamy Y
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...
Formal Methods for Dynamic Power Management (2003)
Sandeep K. Shukla, Rajesh K. Gupta, Rajesh K. Gupta, Sandy Irani, Sandy Irani, Sandeep Kumar Shukla
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...
Sandy Irani, Sandeep Shukla, Rajesh Gupta
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...
Sandy Irani, Sandeep Shukla, Rajesh Gupta
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...
Randomized weighted caching with two page weights (2002)
We consider a special case of the weighted caching problem where the weight ofevery page is either 1 or some xed number M>1. We present a randomized algorithm which achieves a competitive ratio...
On-line algorithms for the dynamic traveling repair problem (2002)
We consider the dynamic traveling repair problem (DTRP) in which requests with deadlines arrive through time on points in a metric space. Servers move from point topoint at constant speed. The goal...
Latency effects of system level power management algorithms (2000)
Dinesh Ramanathan, Sandy Irani, Rajesh Gupta
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...
The Problem of Renting versus Buying (1998)
Sandy Irani, Dinesh Ramanathan
The problem studied here is a member of a large class of on-line decision problems. The basic question is to choose from two possible alternatives at a given instance, for the use of an item. This...
Bounding The Power Of Preemption In Randomized Scheduling (1998)
.<F3.796e+05> 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...
Cost-Aware WWW Proxy Caching Algorithms (1997)
Web caches can not only reduce network traffic and downloading latency, but can also affect the distribution of web traffic over the network through costaware caching. This paper introduces...
Scheduling with Conflicts (1997)
Sandy Irani, Vitus Leung, S. Irani, V. Leung
In this paper, we consider the scheduling of jobs that may be competing for mutually exclusive resources. We model the conflicts between jobs with a conflict graph, so that the set of all...
Logo Detection in Document Images (1997)
Steve Seiden, Michael Dillencourt, Sandy Irani, Roland Borrey, Timothy Murphy
This paper focuses on the problem of classifying segments of bitonal document images according to whether or not they are likely to contain a logo. A simple set of features is extracted from each...
Logo Detection in Document Images (1997)
Steve Seiden, Michael Dillencourt, Sandy Irani, Roland Borrey, Timothy Murphy
This paper focuses on the problem of classifying segments of bitonal document images according to whether or not they are likely to contain a logo. A simple set of features is extracted from each...
Simulation Results for Traffic Signal Control (1997)
Vitus Leung, Sandy Irani, V. Leung, S. Irani
In this paper, we discuss simulation results for the traffic signal control problem. Our algorithms are motivated by theoretical results from Supported in part by Caltrans Contract 65Q090. Email:...
Probabilistic Analysis for Scheduling with Conflicts (1997)
Sandy Irani, Vitus Leung, S. Irani, V. Leung
In this paper, we consider the scheduling of jobs that may be competing for mutually exclusive resources. We model the conflicts between Supported in part by NSF Grant CCR-9309456. Email:...
GreedyDual-Size: A Cost-Aware WWW Proxy Caching Algorithm (1997)
this paper, we introduce a new algorithm, called GreedyDual-Size, which combines locality, size and latency/cost concerns effectively to achieve the best overall performance. GreedyDual-Size is a...
This chapter presents an introduction to the competitive analysis of online algorithms. In an online problem...
Page replacement with multi-size pages and applications to Web caching (1997)
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...
Competitive Analysis of Paging: A Survey (1996)
. This paper is a survey of competitive analysis of paging. We present proofs showing tight bounds for the competitive ratio achievable by any deterministic or randomized online algorithm. We then go...
On the Value of Coordination in Distributed Decision Making (1996)
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...
Randomized Algorithms for Metrical Task Systems (1995)
Borodin, Linial, and Saks introduce a general model for online systems in [BLS92] called task systems and show a deterministic algorithm which achieves a competitive ratio of 2n \Gamma 1 for any...
Competitive Paging With Locality of Reference (1991)
Allan Borodin, Prabhakar Raghavan, Sandy Irani, Baruch Schieber
Abstract The Sleator-Tarjan competitive analysis of paging [Comm. of the ACM; 28:202- 208, 1985] gives us the ability to make strong theoretical statements about the performance of paging algorithms...