Arrow Research search

Author name cluster

John Iacono

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.

22 papers
2 author rows

Possible papers

22

TCS Journal 2024 Journal Article

How fast can we play Tetris greedily with rectangular pieces?

  • Justin Dallant
  • John Iacono

Consider a variant of Tetris played on a board of width w and infinite height, where the pieces are axis-aligned rectangles of arbitrary integer dimensions, the pieces can only be moved before letting them drop, and a row does not disappear once it is full. Suppose we want to follow a greedy strategy: let each rectangle fall where it will end up the lowest given the current state of the board. To do so, we want a data structure which can always suggest a greedy move. In other words, we want a data structure which maintains a set of O ( n ) rectangles, supports queries which return where to drop the rectangle, and updates which insert a rectangle dropped at a certain position and return the height of the highest point in the updated set of rectangles. We show via a reduction from the Multiphase problem [Pătraşcu, 2010] that on a board of width w = Θ ( n ), if the OMv conjecture [Henzinger et al. , 2015] is true, then both operations cannot be supported in time O ( n 1 / 2 − ϵ ) simultaneously. The reduction also implies polynomial bounds from the 3-SUM conjecture and the APSP conjecture. On the other hand, we show that there is a data structure supporting both operations in O ( n 1 / 2 log 3 / 2 ⁡ n ) time on boards of width n O ( 1 ), matching the lower bound up to an n o ( 1 ) factor.

Details DOI

TCS Journal 2022 Journal Article

Fragile complexity of adaptive algorithms

  • Prosenjit Bose
  • Pilar Cano
  • Rolf Fagerberg
  • John Iacono
  • Riko Jacob
  • Stefan Langerman

The fragile complexity of a comparison-based algorithm is f ( n ) if each input element participates in O ( f ( n ) ) comparisons. In this paper, we explore the fragile complexity of algorithms adaptive to various restrictions on the input, i. e. , algorithms with a fragile complexity parameterized by a quantity other than the input size n. We show that searching for the predecessor in a sorted array has fragile complexity Θ ( log ⁡ k ), where k is the rank of the query element, both in a randomized and a deterministic setting. For predecessor searches, we also show how to optimally reduce the amortized fragile complexity of the elements in the array. We also prove the following results: Selecting the kth smallest element has expected fragile complexity O ( log ⁡ log ⁡ k ) for the element selected. Deterministically finding the minimum element has fragile complexity Θ ( log ⁡ ( Inv ) ) and Θ ( log ⁡ ( Runs ) ), where Inv is the number of inversions in a sequence and Runs is the number of increasing runs in a sequence. Deterministically finding the median has fragile complexity O ( log ⁡ ( Runs ) + log ⁡ log ⁡ n ) and Θ ( log ⁡ ( Inv ) ). Deterministic sorting has fragile complexity Θ ( log ⁡ ( Inv ) ) but it has fragile complexity Θ ( log ⁡ n ) regardless of the number of runs.

Details DOI

SODA Conference 2020 Conference Paper

Competitive Online Search Trees on Trees

  • Prosenjit Bose
  • Jean Cardinal
  • John Iacono
  • Grigorios Koumoutsos
  • Stefan Langerman

We consider the design of adaptive data structures for searching elements of a tree-structured space. We use a natural generalization of the rotation-based online binary search tree model in which the underlying search space is the set of vertices of a tree. This model is based on a simple structure for decomposing graphs, previously known under several names including elimination trees, vertex rankings, and tubings. The model is equivalent to the classical binary search tree model exactly when the underlying tree is a path. We describe an online O (log log n )-competitive search tree data structure in this model, matching the best known competitive ratio of binary search trees. Our method is inspired by Tango trees, an online binary search tree algorithm, but critically needs several new notions including one which we call Steiner-closed search trees, which may be of independent interest. Moreover our technique is based on a novel use of two levels of decomposition, first from search space to a set of Steiner-closed trees, and secondly from these trees into paths.

Details

TCS Journal 2018 Journal Article

Encoding nearest larger values

  • Michael Hoffmann
  • John Iacono
  • Patrick K. Nicholson
  • Rajeev Raman

In nearest larger value (NLV) problems, we are given an array A [ 1. . n ] of distinct numbers, and need to preprocess A to answer queries of the following form: given any index i ∈ [ 1, n ], return a “nearest” index j such that A [ j ] > A [ i ]. We consider the variant where the values in A are distinct, and we wish to return an index j such that A [ j ] > A [ i ] and | j − i | is minimized, the nondirectional NLV (NNLV) problem. We consider NNLV in the encoding model, where the array A is deleted after preprocessing. The NNLV encoding problem turns out to have an unexpectedly rich structure: the effective entropy (optimal space usage) of the problem depends crucially on details in the definition of the problem. Of particular interest is the tiebreaking rule: if there exist two nearest indices j 1, j 2 such that A [ j 1 ] > A [ i ] and A [ j 2 ] > A [ i ] and | j 1 − i | = | j 2 − i |, then which index should be returned? For the tiebreaking rule where the rightmost (i. e. , largest) index is returned, we encode a path-compressed representation of the Cartesian tree that can answer all NNLV queries in 1. 89997 n + o ( n ) bits, and can answer queries in O ( 1 ) time. An alternative approach, based on forbidden patterns, achieves a very similar space bound for two tiebreaking rules (including the one where ties are broken to the right), and (for a more flexible tiebreaking rule) achieves 1. 81211 n + o ( n ) bits. Finally, we develop a fast method of counting distinguishable configurations for NNLV queries. Using this method, we prove a lower bound of 1. 62309 n − Θ ( 1 ) bits of space for NNLV encodings for the tiebreaking rule where the rightmost index is returned.

Details DOI

TCS Journal 2016 Journal Article

Encoding 2D range maximum queries

  • Mordecai Golin
  • John Iacono
  • Danny Krizanc
  • Rajeev Raman
  • Srinivasa Rao Satti
  • Sunil Shende

We consider the two-dimensional range maximum query (2D-RMQ) problem: given an array containing elements from an ordered set, encode the array so that the position of the maximum element in any specified range of rows and range of columns can be found efficiently. We focus on determining the effective entropy of 2D-RMQ, i. e. , how many bits are needed to encode an array so that 2D-RMQ queries can be answered without accessing the array. We give tight upper and lower bounds on the expected effective entropy for the case when A contains independent identically-distributed random values, and give new upper and lower bounds for the case when the array contains few rows. The latter results improve upon the upper and lower bounds by Brodal et al. [4]. We also give some efficient data structures for 2D-RMQ whose space usage is close to the effective entropy.

Details DOI

SODA Conference 2016 Conference Paper

Weighted dynamic finger in binary search trees

  • John Iacono
  • Stefan Langerman

It is shown that the online binary search tree data structure GreedyASS performs asymptotically as well on a sufficiently long sequence of searches as any static binary search tree where each search begins from the previous search (rather than the root). This bound is known to be equivalent to assigning each item i in the search tree a positive weight w i and bounding the search cost of an item in the search sequence s 1, …, s m This result is the strongest finger-type bound to be proven for binary search trees. By setting the weights to be equal, one observes that our bound implies the dynamic finger bound. Compared to the previous proof of the dynamic finger bound for Splay trees, our result is significantly shorter, stronger, simpler, and has reasonable constants.

Details

SODA Conference 2014 Conference Paper

The Complexity of Order Type Isomorphism

  • Greg Aloupis
  • John Iacono
  • Stefan Langerman
  • Özgür Özkan
  • Stefanie Wuhrer

The order type of a point set in ℝ d maps each ( d +1)-tuple of points to its orientation (e. g. , clockwise or counterclockwise in ℝ 2 ). Two point sets X and Y have the same order type if there exists a mapping f from X to Y for which every ( d +1)-tuple ( a 1, a 2, …, a d +1 ) of X and the corresponding tuple ( f ( a 1 ), f ( a 2 ), …, f ( a d +1 )) in Y have the same orientation. In this paper we investigate the complexity of determining whether two point sets have the same order type. We provide an O ( n d ) algorithm for this task, thereby improving upon the O ( n ⌊3 d /2⌋ ) algorithm of Goodman and Pollack (1983). The algorithm uses only order type queries and also works for abstract order types (or acyclic oriented matroids). Our algorithm is optimal, both in the abstract setting and for realizable points sets if the algorithm only uses order type queries.

Details

SODA Conference 2009 Conference Paper

The geometry of binary search trees

  • Erik D. Demaine
  • Dion Harmon
  • John Iacono
  • Daniel M. Kane
  • Mihai Patrascu

We present a novel connection between binary search trees (BSTs) and points in the plane satisfying a simple property. Using this correspondence, we achieve the following results: 1. 1. A surprisingly clean restatement in geometric terms of many results and conjectures relating to BSTs and dynamic optimality. 2. 2. A new lower bound for searching in the BST model, which subsumes the previous two known bounds of Wilber [FOCS'86]. 3. 3. The first proposal for dynamic optimality not based on splay trees. A natural greedy but offline algorithm was presented by Lucas [1988], and independently by Munro [2000], and was conjectured to be an (additive) approximation of the best binary search tree. We show that there exists an equal-cost online algorithm, transforming the conjecture of Lucas and Munro into the conjecture that the greedy algorithm is dynamically optimal.

Details

TCS Journal 2007 Journal Article

A unified access bound on comparison-based dynamic dictionaries

  • Mihai Bădoiu
  • Richard Cole
  • Erik D. Demaine
  • John Iacono

We present a dynamic comparison-based search structure that supports insertions, deletions, and searches within the unified bound. The unified bound specifies that it is quick to access an element that is near a recently accessed element. More precisely, if w ( y ) distinct elements have been accessed since the last access to element y, and d ( x, y ) denotes the rank distance between x and y among the current set of elements, then the amortized cost to access element x is O ( min y log [ w ( y ) + d ( x, y ) + 2 ] ). This property generalizes the working-set and dynamic-finger properties of splay trees.

Details DOI

FOCS Conference 2004 Conference Paper

Dynamic Optimality - Almost

  • Erik D. Demaine
  • Dion Harmon
  • John Iacono
  • Mihai Patrascu

We present an O(lg lg n)-competitive online binary search tree, improving upon the best previous (trivial) competitive ratio of O(lg n). This is the first major progress on Sleator and Tarjan's dynamic optimality conjecture of 1985 that O(1)-competitive binary search trees exist.

Details

FOCS Conference 2003 Conference Paper

The Cost of Cache-Oblivious Searching

  • Michael A. Bender
  • Gerth Stølting Brodal
  • Rolf Fagerberg
  • Dongdong Ge
  • Simai He
  • Haodong Hu
  • John Iacono
  • Alejandro López-Ortiz

Tight bounds on the cost of cache-oblivious searching are proved. It is shown that no cache-oblivious search structure can guarantee that a search performs fewer than lg e log/sub B/N block transfers between any two levels of the memory hierarchy. This lower bound holds even if all of the block sizes are limited to be powers of 2. A modified version of the van Emde Boas layout is proposed, whose expected block transfers between any two levels of the memory hierarchy arbitrarily close to [lg e + O(lg lg B/ lgB)] logB N + O(1). This factor approaches lg e /spl ap/ 1. 443 as B increases. The expectation is taken over the random placement of the first element of the structure in memory. As searching in the disk access model (DAM) can be performed in log/sub B/N + 1 block transfers, this result shows a separation between the 2-level DAM and cache-oblivious memory-hierarchy models. By extending the DAM model to k levels, multilevel memory hierarchies can be modeled. It is shown that as k grows, the search costs of the optimal k-level DAM search structure and of the optimal cache-oblivious search structure rapidly converge. This demonstrates that for a multilevel memory hierarchy, a simple cache-oblivious structure almost replicates the performance of an optimal parameterized k-level DAM structure.

Details