Arrow Research search

Author name cluster

Sandy Irani

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

21 papers
2 author rows

Possible papers

21

STOC Conference 2022 Conference Paper

Hamiltonian complexity in the thermodynamic limit

  • Dorit Aharonov
  • Sandy Irani

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 states of the resulting matrices than was 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 which shows hardness for a function class.

Details

TCS Journal 2009 Journal Article

Strip packing with precedence constraints and strip packing with release times

  • John Augustine
  • Sudarshan Banerjee
  • Sandy Irani

The strip packing problem seeks to tightly pack a set of n rectangles into a strip of fixed width and arbitrary height. The rectangles model tasks and the height models time. 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 is used to model scheduling problems in which tasks require a contiguous subset of identical resources that are arranged in a linear topology. The variants studied here are motivated by scheduling tasks for dynamically reconfigurable Field-Programmable Gate Arrays (FPGAs) comprised of a linear arrangement of K homogeneous computing resources, where K is a fixed positive integer, and each task occupies a contiguous subset of these resources. For the case in which tasks have precedence constraints, we give an O ( log n ) approximation algorithm. 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 approximation scheme. We make the standard assumption that the rectangles have height at most 1. In addition, we also require widths to be in [ 1 K, 1 ]. For the FPGA application, this would imply that the rectangles are at least as wide as a column. Our running time is polynomial in n and 1 / ϵ, but exponential in K.

Details DOI

FOCS Conference 2009 Conference Paper

The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems

  • Daniel Gottesman
  • Sandy Irani

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.

Details

TCS Journal 2008 Journal Article

Probabilistic analysis for scheduling with conflicts

  • Sandy Irani
  • Vitus Leung

In this paper, we consider scheduling jobs that may be competing for mutually exclusive resources. We model the conflicts between jobs with a conflict graph, so that all concurrently running jobs must form an independent set in the graph. Our goal is to bound the maximum response time of any job in the system. We adopt a discrete model of time and assume that each job requires one time unit to be completed once it is started. It has been previously shown [S. Irani, V. Leung, Scheduling with conflicts, and applications to traffic signal control, in: Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 1996] that the best competitive ratio achievable by any online algorithm is Ω ( n ), where n is the number of nodes in the graph. As a result, we study scheduling with conflicts under probabilistic assumptions about the input. Each node i has a value p i such that a job arrives at node i in any given time unit with probability p i. Arrivals at different nodes and during different time periods are independent. Under reasonable assumptions on the value for the p i ’s, we are able to obtain a bounded competitive ratio for an arbitrary conflict graph. In addition, if the conflict graph is a perfect graph, we give an algorithm whose competitive ratio converges to 1.

Details DOI

FOCS Conference 2007 Conference Paper

The Power of Quantum Systems on a Line

  • Dorit Aharonov
  • Daniel Gottesman
  • Sandy Irani
  • Julia Kempe

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.

Details

FOCS Conference 2004 Conference Paper

Optimal Power-Down Strategies

  • John Augustine 0001
  • Sandy Irani
  • 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 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.

Details

TCS Journal 2004 Journal Article

WITHDRAWN: Foreword

  • Sandy Irani
  • Amos Fiat

This article has been withdrawn at the request of the author(s) and/or editor. The Publisher apologizes for any inconvenience this may cause. The full Elsevier Policy on Article Withdrawal can be found at http: //www. elsevier. com/locate/withdrawalpolicy

Details DOI

TCS Journal 1998 Journal Article

Randomized algorithms for metrical task systems

  • Sandy Irani
  • Steve Seiden

Borodin et al. (1992) introduce a general model for online systems in [3] called task systems and show a deterministic algorithm which achieves a competitive ratio of 2n − 1 for any metrical task system with n states. We present a randomized algorithm which achieves a competitive ratio of e/(e − 1)n − 1/(e − 1) ≈ 1. 5820n − 0. 5820 for this same problem. For the uniform metric space, Borodin et al. present an algorithm which achieves a competitive ratio of 2H n, and they show a lower bound of H n, for any randomized algorithm. We improve their upper bound for the uniform metric space by showing a randomized algorithm which is (H n + O(√log n))-competitive.

Details DOI

FOCS Conference 1993 Conference Paper

On the Value of Information in Coordination Games (preliminary version)

  • Sandy Irani
  • Yuval Rabani

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? . >

Details

FOCS Conference 1990 Conference Paper

Coloring Inductive Graphs On-Line

  • Sandy Irani

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. >

Details
v2026.09.13