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.

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 (N3) 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 (N2) operations per iteration. We compare our algorithm to a laser-SLAM ground truth, showing it produces excellent results in practice.

The primary disadvantage of orthogonal frequency-division multiplexing (OFDM) is the high time-domain peak-to-average power ratio (PAR) that severely limits the transmitter power efficiency. The PAR can be globally minimized by distorting the OFDM constellation subject to a constraint on the error vector magnitude (EVM). In this paper, we demonstrate that an optimal amount of EVM exists for minimizing the transmitter power consumption while maintaining a constant bit error rate (BER) at the receiver. Alternatively, the EVM value may be chosen to maximize the channel capacity while maintaining a constant power consumption at the transmitter. Both EVM levels are only a function of the required signal-to-noise ratio at the OFDM receiver.

Recent work has used convex optimization to minimize the peak-to-average power ratio (PAR) of OFDM signals subject to a constraint on the constellation error vector magnitude (EVM). This paper extends the PAR optimization technique to multiple-input multiple-output (MIMO) OFDM systems with channel precoding. In MIMO systems with a large OFDM symbol size, it is infeasible to solve the optimization problem by direct methods such as Cholesky factorization. Instead, we propose an iterative conjugate-gradient (CG) method to find an approximate solution with far lower memory and latency requirements. Simulation results are presented for a MIMO-OFDM system with 4 antennas and 1024 carriers. The PAR can be reduced from 11.5 dB to 4.3 dB for QPSK with -20 dB EVM, and from 11.5 dB to 5.5 dB for 16-QAM with -30 dB EVM. The tradeoff between PAR reduction and computational complexity is also examined to determine the number of CG iterations needed to reach within 1 dB of the globally optimal solution.

The main disadvantage of OFDM is the high time-domain peak-to-average power ratio (PAR) that limits transmitter power efficiency. This paper presents a convex optimization algorithm for minimizing the PAR of an OFDM signal subject to constraints on the constellation error vector magnitude (EVM). The derivation reduces computational complexity by exploiting known features of the optimization problem, such as OFDM's FFT structure. Simulation results are given for the 802.11 a/g WLAN standard. The customized algorithm is approximately 100 times faster than a general-purpose optimizer. The algorithm achieves PAR within 1 dB of the globally optimal solution after two iterations, where the main complexity per iteration is four FFTs plus the solution of a linear system of equations.

Efficient OFDM transmission has been limited by power amplifier (PA) non-linearity combined with OFDM's high peak-to-average power ratio (PAPR). We show that minimization of the PAPR of an OFDM signal, subject to constraints on allowable constellation error and out-of-band noise, can be formulated as a convex optimization problem. The globally optimal solution can be calculated with low complexity using known algorithms. A system model is proposed for transmitting OFDM signals with maximum power-efficiency regardless of PA linearity. No change in receiver structure is required. Simulation results are presented for the 802.11a WLAN standard.

Digital watermarking is seen as a viable solution to authentication of multimedia data and hence its security, especially in a networked environment. We present a new watermarking technique to add a code to digital images in the spatial domain. This technique is further shown to be robust under common compression schemes, including lossy compression schemes. Watermark embedding is done keeping in mind the limitations of the human visual system. We have used a procedure for error diffusion so as to minimize the chances of image tampering. For the verification of the image, the original uncorrupted image is not required. Experimental results show that the watermark is robust to JPEG compression.

A number of basic models for VLSI layout are based on the construction of node-disjoint paths between terminals on a multilayer grid. In this setting, one is interested in minimizing both the number of layers required and the area of the underlying grid. Building on work of Cutler and Shiloach [ Networks, 8 (1978), pp. 253--278], Aggarwal et al. [ Proc. 26th IEEE Symposium on Foundations of Computer Science , Portland, OR, 1985; Algorithmica, 6 (1991), pp. 241--255], and Aggarwal, Klawe, and Shor [ Algorithmica}, 6 (1991), pp. 129--151], we prove an upper-bound trade-off between these two quantities in a general multilayer grid model. As a special case of our main result, we obtain significantly improved bounds for the problem of routing a full permutation on the mesh using node-disjoint paths; our new bound here is within polylogarithmic factors of the bisection bound. Our algorithms involve some new techniques for analyzing the structure of node-disjoint paths in planar graphs and indicate some respects in which this problem, at least in the planar case, is fundamentally different from its edge-disjoint counterpart.

Motivated by applications in robotics, we formulate the problem of minimizing the total angle cost of a TSP tour for a set of points in Euclidean space, where the angle cost of a tour is the sum of the direction changes at the points. We establish the NP-hardness of both this problem and its relaxation to the cycle cover problem. We then consider the issue of designing approximation algorithms for these problems and show that both problems can be approximated to within a ratio of O(log n) in polynomial time. We also consider the problem of simultaneously approximating both the angle and the length measure for a TSP tour. In studying the resulting tradeoff, we choose to focus on the sum of the two performance ratios and provide tight bounds on the sum. Finally, we consider the extremal value of the angle measure and obtain essentially tight bounds for it. In this paper we restrict our attention to the planar setting, but all our results are easily extended to higher dimensions.

A number of basic models for VLSI layout are based on the construction of nodedisjoint paths between terminals on a multi-layer grid. In this setting, one is interested in minimizing both the number of layers required and the area of the underlying grid. Building on work of Cutler and Shiloach, and Aggarwal, Klawe, et al., we prove an upper-bound trade-off between these two quantities in a general multi-layer grid model. As a special case of our main result, we obtain significantly improved bounds for the problem of routing a full permutation on the mesh using node-disjoint paths; our new bound here is within polylogarithmic factors of the bisection bound. Our algorithms involve some new techniques for analyzing the structure of node-disjoint paths in planar graphs, and indicate some respects in which this problem, at least in the planar case, is fundamentally different from its edge-disjoint counterpart. 1 Introduction The basic node--disjoint paths problem is as follows. We are give...

This paper studies the problem of dedicating routes to connections in optical networks. In optical networks, the vast bandwidth available in an optical fiber is utilized by partitioning it into several channels, each at a different optical wavelength. A connection between two nodes is assigned a specific wavelength, with the constraint that no two connections sharing a link in the network can be assigned the same wavelength. This paper considers optical networks with and without switches, and different types of routing in these networks. It presents optimal or near-optimal constructions of optical networks in these cases and algorithms for routing connections, specifically permutation routing for the networks constructed here.

Let G be a weighted, complete, directed acyclic graph (DAG), whose edge weights obey the Monge condition.We give an efficient algorithm for finding the minimum weight K-link path between a given pair of vertices for any given K.The time complexity of our algorithm is O(n~=) for the concave case and O (ncr (n) log3 n) for the convex case.Our algorithm uses some properties of DAGs withMonge property together with a refined parametric search technique.We apply our algorithm (for the concave case) to get efficient solutions for the following problems, improving on previous results:(1) Finding the largest K-gon contained in a given polygon.(2) Finding the smallest K-gon that is the intersection of K halfplanes out of of given set of halfplanes defining an n-gon.(3) Computing maximum K-cliques of an interval graph.(4) Computing length limited Huffman codes.(5) Computing optimal discrete quantization.

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>

Let P be (the boundary of) a simple polygon with n vertices. For a vertex p of P, let ϕ(p) be the set of points on P that are farthest from p, where the distance between two points is the length of the (Euclidean) shortest path that connects them without intersecting the interior of P. In this paper, we present an O(n log n) algorithm to compute a member of ϕ(p) for every vertex p of P. As a corollary, the external diameter of P can also be computed in the same time.

Article Parallel searching in generalized Monge arrays with applications Share on Authors: A. Aggarwal IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NY IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NYView Profile , D. Kravets Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MAView Profile , J. Park Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MAView Profile , S. Sen Department of Computer Science, Duke University, Durham, NC Department of Computer Science, Duke University, Durham, NCView Profile Authors Info & Claims SPAA '90: Proceedings of the second annual ACM symposium on Parallel algorithms and architecturesMay 1990 Pages 259–268https://doi.org/10.1145/97444.97693Online:01 May 1990Publication History 11citation348DownloadsMetricsTotal Citations11Total Downloads348Last 12 Months4Last 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

In this paper, we describe a new technique for solving a variety of query-retrieval problems in optimal time with optimal or near-optimal space.In particular, we use the technique to construct algorithms and data structures for circular range searching, half-space range searching, and computing k-nearest neighbors in a variety of metrics.For each problem and each query, the response to the query is provided in O(k) or O(k + log n) time where k is the size of the response and n is the size of the problem.(E.g., for the n-point k-nearest neighbors problem, the k-nearest neighbors of any query point are provided in O(k -4log n) steps.)Depending on the problem being solved, the space required for the data structure is either linear or O(n log n).Hence, the time bounds are optimal and the space bounds are optimal or near-optimal.Previously known data structures for these problems required a factor of ~(log n(log log n) 2) or ~(log n log log n) more space and/or more time to answer each query.Our compaction technique incorporates planar separators, filtering search, and the probabilistic method for discrepancy problems.The fundamental idea is that k'h-order Voronoi diagrams (and other suitable proximity diagrams) can be compacted from k°(1)n space to O(n) space and still retain all the information that is essential for solving query problems.This result is of independent interest and may be useful in improving the memory space requirement or the query-time bound for other query-retrieval problems.

A directed cycle separator of an n-vertex directed graph is a vertex-simple directed cycle such that when the vertices of the cycle are deleted, the resulting graph has no strongly connected component with more than ${n / 2}$ vertices. It is shown that the problem of finding a directed cycle separator is in randomized NC. It is also proved that computing cycle separators and conducting depth-first search in directed graphs are deterministically NC-equivalent. These two results together yield the first randomized NC algorithm for depth-first search in general directed graphs.

Article Free Access Share on Fining k points with minimum spanning trees and related problems Authors: A. Aggarwal IBM T. J. Watson Research Center IBM T. J. Watson Research CenterView Profile , H. Imai Kyushu University, Japan Kyushu University, JapanView Profile , N. Katoh Kobe University of Commerce, Japan Kobe University of Commerce, JapanView Profile , S. Suri Bell Communications Research Bell Communications ResearchView Profile Authors Info & Claims SCG '89: Proceedings of the fifth annual symposium on Computational geometryJune 1989 Pages 283–291https://doi.org/10.1145/73833.73865Published:05 June 1989Publication History 7citation660DownloadsMetricsTotal Citations7Total Downloads660Last 12 Months14Last 6 weeks4 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 Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A directed cycle separator of an n-vertex directed graph is a simple directed cycle such that when the vertices of the cycle are deleted, the resulting graph has no strongly connected component with more than n/2 vertices. This paper shows that the problem of finding a directed cycle separator is in randomized NC. The paper also proves that computing cycle separators and conducting depth-first search in directed graphs are deterministic NC-equivalent. These two results together yield the first RNC algorithm for depth-first search in directed graphs.

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

Article Free Access Share on Virtual memory algorithms Authors: Alok Aggarwal IBM Research Division, Thomas J. Watson Center, P. O. Box 218, Yorktown Heights, New York IBM Research Division, Thomas J. Watson Center, P. O. Box 218, Yorktown Heights, New YorkView Profile , Ashok Chandra IBM Research Division, Thomas J. Watson Center, P. O. Box 218, Yorktown Heights, New York IBM Research Division, Thomas J. Watson Center, P. O. Box 218, Yorktown Heights, New YorkView Profile Authors Info & Claims STOC '88: Proceedings of the twentieth annual ACM symposium on Theory of computingJanuary 1988 Pages 173–185https://doi.org/10.1145/62212.62227Published:01 January 1988Publication History 16citation543DownloadsMetricsTotal Citations16Total Downloads543Last 12 Months33Last 6 weeks13 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

We study energy consumption in CMOS-style VLSI circuits, where a wire of length / consumes energy Θ(l)when switching. Three model are considered: the uniswitch model where a wire is assumed to switch at most once if the input changes, the multiswitch model which allows the possibility of multiple switches caused by uncontrolled delays, and the clock model which also takes clock distribution energy into account. Previous lower bound results for the uniswitch model applied only to circuits where intermediate data were not encoded (for example, in unary) by using additional wires and area to reduce the energy. We show that such encodings can be useful for adding two n-bit numbers using synchronous Boolean circuits (energy reduction from Θ(n log n) to Ο(n log n/(log log n)), but not for transitive functions such as the cyclic shift of n bits (energy Θ(n2)). For the multiswitch model, we develop layouts that achieve energy close to the uniswitch case for these problems, and show a separation result between the uniswitch and multiswitch models. Finally, some energy-period tradeoffs are shown for the clock model.

We provide two algorithms for solving the following problem: Given a rectangle containing n points, compute the largest-area and the largest-perimeter subrectangles with sides parallel to the given rectangle that lie within this rectangle and that do not contain any points in their interior. For finding the largest-area empty rectangle, the first algorithm takes Ο(n log3 n) time and Ο(n) memory space and it simplifies the algorithm given by Chazelle, Drysdale and Lee which takes Ο(n log3 n) time but Ο(n log n) storage. The second algorithm for computing the largest-area empty rectangle is more complicated but it only takes Ο(n log2 n) time and Ο(n) memory space. The two algorithms for computing the largest-area rectangle can be modified to compute the largest-perimeter rectangle in Ο(n log2 n) and Ο(n log n) time, respectively. Since Ω(n log n) is a lower bound on time for computing the largest-perimeter empty rectangle, the second algorithm for computing such a rectangle is optimal within a multiplicative constant.

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.

In this paper we present a fast parallel algorithm for constructing a depth first search tree for an undirected graph. The algorithm is an RNC algorithm, meaning that it is a probabilistic algorithm that runs in polylog time using a polynomial number of processors on a P-RAM. The run time of the algorithm is O(TMM(n)log3n), and the number of processors used is PMM(n) where TMM(n) and PMM(n) are the time and number of processors needed to find a minimum weight perfect matching on an n vertex graph with maximum edge weight n.

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.

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.

Article Free Access Share on Geometric applications of a matrix searching algorithm Authors: A Aggarwal IBM T. J. Watson Center, Yorktown Heights IBM T. J. Watson Center, Yorktown HeightsSearch about this author , M Klawe IBM Almaden Research Center, San Jose IBM Almaden Research Center, San JoseView Profile , S Moran IBM T. J. Watson Center, Yorktown Heights IBM T. J. Watson Center, Yorktown HeightsSearch about this author , P Shor Math. Sciences Research Institute, Berkeley Math. Sciences Research Institute, BerkeleyView Profile , R Wilber IBM Almaden Research Center, San Jose IBM Almaden Research Center, San JoseView Profile Authors Info & Claims SCG '86: Proceedings of the second annual symposium on Computational geometryAugust 1986Pages 285–292https://doi.org/10.1145/10515.10546Published:01 August 1986Publication History 39citation1,255DownloadsMetricsTotal Citations39Total Downloads1,255Last 12 Months234Last 6 weeks35 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

The problem of finding the maximum of a set of values stored one per processor on a two-dimensional array of processors with a time-shared global bus is considered. The algorithm given by Bokhari is shown to be optimal, within a multiplicative constant, for this network and for other d-dimensional arrays. We generalize this model and demonstrate optimal bounds for finding the maximum of a set of values stored in a d-dimensional array with k time-shared global buses.

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 Ο(nlogκ) algorithm for solving the problem, where n is the total number of vertices of the given polygons, and κ is the number of vertices of a minimal nested polygon. We also present an Ο(n) sub-optimal algorithm, and a simple Ο(nk) optimal algorithm.

We present efficient parallel algorithms for several basic problems in computational geometry: convex hulls, Voronoi diagrams, detecting line segment intersections, triangulating simple polygons, minimizing a circumscribing triangle, and recursive data-structures for three-dimensional queries.

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.

Article Free Access Share on Tradeoffs for VLSI models with subpolynomial delay Author: A Aggarwal IBM T. J. Watson Research Center, Yorktown Heights, NY IBM T. J. Watson Research Center, Yorktown Heights, NYView Profile Authors Info & Claims STOC '85: Proceedings of the seventeenth annual ACM symposium on Theory of computingDecember 1985 Pages 59–68https://doi.org/10.1145/22145.22152Published:01 December 1985Publication History 1citation207DownloadsMetricsTotal Citations1Total Downloads207Last 12 Months11Last 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 SiteeReaderPDF

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.