Arrow Research search

Author name cluster

Alok Aggarwal

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.

23 papers
2 author rows

Possible papers

23

AAAI Conference 2019 Conference Paper

Regularized Evolution for Image Classifier Architecture Search

  • Esteban Real
  • Alok Aggarwal
  • Yanping Huang
  • Quoc V. Le

The effort devoted to hand-crafting neural network image classifiers has motivated the use of architecture search to discover them automatically. Although evolutionary algorithms have been repeatedly applied to neural network topologies, the image classifiers thus discovered have remained inferior to human-crafted ones. Here, we evolve an image classifier— AmoebaNet-A—that surpasses hand-designs for the first time. To do this, we modify the tournament selection evolutionary algorithm by introducing an age property to favor the younger genotypes. Matching size, AmoebaNet-A has comparable accuracy to current state-of-the-art ImageNet models discovered with more complex architecture-search methods. Scaled to larger size, AmoebaNet-A sets a new state-of-theart 83. 9% top-1 / 96. 6% top-5 ImageNet accuracy. In a controlled comparison against a well known reinforcement learning algorithm, we give evidence that evolution can obtain results faster with the same hardware, especially at the earlier stages of the search. This is relevant when fewer compute resources are available. Evolution is, thus, a simple method to effectively discover high-quality architectures.

ICRA Conference 2011 Conference Paper

Efficient, generalized indoor WiFi GraphSLAM

  • Joseph Huang
  • David Millman
  • Morgan Quigley
  • David Stavens
  • Sebastian Thrun
  • Alok Aggarwal

The widespread deployment of wireless networks presents an opportunity for localization and mapping using only signal-strength measurements. The current state of the art is to use Gaussian process latent variable models (GP-LVM). This method works well, but relies on a signature uniqueness assumption which limits its applicability to only signal-rich environments. Moreover, it does not scale computationally to large sets of data, requiring O (N 3 ) operations per iteration. We present a GraphSLAM-like algorithm for signal strength SLAM. Our algorithm shares many of the benefits of Gaussian processes, yet is viable for a broader range of environments since it makes no signature uniqueness assumptions. It is also more tractable to larger map sizes, requiring O (N 2 ) operations per iteration. We compare our algorithm to a laser-SLAM ground truth, showing it produces excellent results in practice.

FOCS Conference 1992 Conference Paper

Efficient Minimum Cost Matching Using Quadrangle Inequality

  • Alok Aggarwal
  • Amotz Bar-Noy
  • Samir Khuller
  • Dina Kravets
  • Baruch Schieber

The authors present efficient algorithms for finding a minimum cost perfect matching, and for solving the transportation problem in bipartite graphs, G = (Red union Blue, Red * Blue), where mod Red mod = n, mod Blue mod = m, n >

TCS Journal 1990 Journal Article

Communication complexity of PRAMs

  • Alok Aggarwal
  • Ashok K. Chandra
  • Marc Snir

We propose a model, LPRAM, for parallel random access machines with local memory that captures both the communication and computational requirements in parallel computation. For this model, we present several interesting results, including the following: Two n × n matrices can be multiplied in 0(n 3/p) computation time and 0(n2/p 2 3 ) communication steps using p processors (for p = 0(n3/log 3 2 n)). Furthermore, these bounds are optimal for arithmetic on semirings (using +, × only). It is shown that any algorithm that uses comparisons only and that sorts n words requires Ω(n log n/(p log(n/p))) communication steps for 1 < p < n. We also provide an algorithm that sorts n words and uses (-)(n log n/p) computation time and (-)(n log n/p log(n/p))) communication steps. These bounds also apply for computing an n-point FFT graph. It is shown that computing any binary tree τ with n nodes and height h requires Ω(n/p + log n + √h) communication steps, and can always be computed in 0(n/p + min(√n, h)) steps. We also present a simple linear-time algorithm that generates a schedule for computing τ in at most 2D opt(τ) steps, where D opt(τ) represents the minimum communication delay for computing τ. It is also shown that various problems that are expressed as DAGs exhibit a communication-delay/computation-time trade-off.

I&C Journal 1989 Journal Article

Finding minimal convex nested polygons

  • Alok Aggarwal
  • Heather Booth
  • Joseph O'Rourke
  • Subhash Suri
  • Chee K. Yap

We consider the problem of finding a polygon nested between two given convex polygons that has a minimal number of vertices. Our main result is an O(n log k) algorithm for solving the problem, where n is the total number of vertices of the given polygons, and k is the number of vertices of a minimal nested polygon. We also present an O(n) sub-optimal algorithm, and a simple O(nk) optimal algorithm.

FOCS Conference 1988 Conference Paper

Notes on Searching in Multidimensional Monotone Arrays (Preliminary Version)

  • Alok Aggarwal
  • James K. Park

A two-dimensional array A=(a/sub i, j/) is called monotone if the maximum entry in its ith row lies below or to the right of the maximum entry in its (i- 1)-st row. An array A is called totally monotone if every 2*2 subarray (i. e. , every 2*2 minor) is monotone. The notion of two-dimensional totally monotone arrays is generalized to multidimensional arrays, and a wide variety of problems are exhibited involving computational geometry, dynamic programming, VLSI river routing, and finding certain kinds of shortest paths that can be solved efficiently by finding maxima in totally monotone arrays. >

STOC Conference 1987 Conference Paper

A Linear Time Algorithm for Computing the Voronoi Diagram of a Convex Polygon

  • Alok Aggarwal
  • Leonidas J. Guibas
  • James B. Saxe
  • Peter W. Shor

We present an algorithm for computing certain kinds of three-dimensional convex hulls in linear time. Using this algorithm, we show that the Voronoi diagram of n points in the plane can be computed in Θ( n ) time when these points form the vertices of a convex polygon in, say, counterclockwise order. This settles an outstanding open problem in computational geometry. Our techniques can also be used to obtain linear time algorithms for computing the farthest-point Voronoi diagram and the medial axis of a convex polygon and for deleting a vertex from a general planar Voronoi diagram.

STOC Conference 1987 Conference Paper

A Model for Hierarchical Memory

  • Alok Aggarwal
  • Bowen Alpern
  • Ashok K. Chandra
  • Marc Snir

In this paper we introduce the Hierarchical Memory Model (HMM) of computation. It is intended to model computers with multiple levels in the memory hierarchy. Access to memory location x is assumed to take time ⌈ log x ⌉. Tight lower and upper bounds are given in this model for the time complexity of searching, sorting, matrix multiplication and FFT. Efficient algorithms in this model utilize locality of reference by bringing data into fast memory and using them several times before returning them to slower memory. It is shown that the circuit simulation problem has inherently poor locality of reference. The results are extended to HMM's where memory access time is given by an arbitrary (nondecreasing) function. Tight upper and lower bounds are obtained for HMM's with polynomial memory access time; the algorithms for searching, FFT and matrix multiplication are shown to be optimal for arbitrary memory access time. On-line memory management algorithms for the HMM model are also considered. An algorithm that uses LRU policy at the successive “levels” of the memory hierarchy is shown to be optimal.

FOCS Conference 1987 Conference Paper

Hierarchical Memory with Block Transfer

  • Alok Aggarwal
  • Ashok K. Chandra
  • Marc Snir

In this paper we introduce a model of Hierarchical Memory with Block Transfer (BT for short). It is like a random access machine, except that access to location x takes time f(x), and a block of consecutive locations can be copied from memory to memory, taking one unit of time per element after the initial access time. We first study the model with f(x) = xα for 0 ≪ α ≪ 1. A tight bound of θ(n log log n) is shown for many simple problems: reading each input, dot product, shuffle exchange, and merging two sorted lists. The same bound holds for transposing a √n × √n matrix; we use this to compute an FFT graph in optimal θ(n log n) time. An optimal θ(n log n) sorting algorithm is also shown. Some additional issues considered are: maintaining data structures such as dictionaries, DAG simulation, and connections with PRAMs. Next we study the model f(x) = x. Using techniques similar to those developed for the previous model, we show tight bounds of θ(n log n) for the simple problems mentioned above, and provide a new technique that yields optimal lower bounds of Ω(n log2n) for sorting, computing an FFT graph, and for matrix transposition. We also obtain optimal bounds for the model f(x)= xα with α ≫ 1. Finally, we study the model f(x) = log x and obtain optimal bounds of θ(n log*n) for simple problems mentioned above and of θ(n log n) for sorting, computing an FFT graph, and for some permutations.

FOCS Conference 1985 Conference Paper

Multi-Layer Grid Embeddings

  • Alok Aggarwal
  • Maria M. Klawe
  • David Lichtenstein
  • Nati Linial
  • Avi Wigderson

In this paper we propose two new multi-layer grid models for VLSI layout, both of which take into account the number of contact cuts used. For the first model in which nodes "exist" only on one layer, we prove a tight area x (number of contact cuts) = Θ(n2) trade-off for embedding any degree 4 n-node planar graph in two layers. For the second model in which nodes "exist" simultaneously on all layers, we prove a number of bounds on the area needed to embed graphs using no contact cuts. For example we prove that any n-node graph which is the union of two planar subgraphs can be embedded on two layers in O(n2) area without contact cuts. This bound is tight even if more layers and an unbounded number of contact cuts are allowed. We also show that planar graphs of bounded degree can be embedded on two layers in O(n1. 6) area without contact cuts. These results use some interesting new results on embedding graphs in a single layer. In particular we give an O(n2) area embedding of planar graphs such that each edge makes a constant number of turns, and each exterior vertex has a path to the perimeter of the grid making a constant number of turns. We also prove a tight Ω(n3) lower bound on the area of grid n-permutation networks.

FOCS Conference 1984 Conference Paper

A Comparative Study of X-Tree, Pyramid and Related Machines

  • Alok Aggarwal

The intent of this paper was to investigate data movement techniques for some special networks which are derived from the binary tree and the mesh machines. We presented optimal bounds for some problems and close bounds for others. A new lower bound technique which incorporates the entire network topdogy was introduced. We believe that this technique is quite powerful and can be exploited to yield good lower bounds for conservative flow algorithms on other networks. However, it seems to be diacult to generalize it for nonconservative flow algorithms. Though we have obtained close bounds, several problems that remain open are noted.

v2026.09.13