author =    "John Iacono and Mihai P{\v a}tra{\c s}cu",
  title =     "Using Hashing to Solve the Dictionary Problem (In External Memory)",
  booktitle = "Proc. 23rd ACM/SIAM Symposium on Discrete Algorithms (SODA)",
  year =      "2012",
  note =      "To appear. See also arXiv:1104.2799"
%% Abstract:
%%  We consider the dictionary problem in external memory and improve the
%%  update time of the well-known \emph{buffer tree} by roughly a
%%  logarithmic factor. For any $\lambda \ge \max \{ \lg\lg n, \log_{M/B}
%%  (n/B) \}$, we can support updates in time $O(\frac{\lambda}{B})$ and
%%  queries in time $O(\log_\lambda n)$. We also present a lower bound in
%%  the cell-probe model showing that our data structure is optimal.
%%  In the RAM, hash tables have been use to solve the dictionary problem
%%  faster than binary search for more than half a century. By contrast,
%%  our data structure is the first to beat the comparison barrier in
%%  external memory. Ours is also the first data structure to depart
%%  convincingly from the \emph{indivisibility} paradigm.

  author =    "Timothy M. Chan and Kasper Larsen and Mihai P{\v a}tra{\c s}cu",
  title =     "Orthogonal Range Searching on the RAM, Revisited",
  booktitle = "Proc. 27th ACM Symposium on Computational Geometry (SoCG)",
  pages =     "354-363",
  year =      "2011",
  note =      "See also arXiv:1011.5200"
%% Abstract:
%%  We present a number of new results on one of the most extensively
%%  studied topics in computational geometry, orthogonal range searching.
%%  All our results are in the standard word RAM model:
%%  \begin{enumerate}
%%  \item We present two data structures for 2-d orthogonal
%%    range emptiness. The first achieves $O(n\lg\lg n)$ space and
%%    $O(\lg\lg n)$ query time, assuming that the $n$ given points are in
%%    rank space.
%%  This improves the previous results by Alstrup, Brodal, and Rauhe
%%  (FOCS'00), with $O(n\lg^\eps n)$ space and $O(\lg\lg n)$ query time,
%%  or with $O(n\lg\lg n)$ space and $O(\lg^2\lg n)$ query time. Our
%%  second data structure uses $O(n)$ space and answers queries in
%%  $O(\lg^\eps n)$ time. The best previous $O(n)$-space data structure,
%%  due to Nekrich (WADS'07),
%%  answers queries in $O(\lg n/\lg \lg n)$ time.
%%  \item We give a data structure for 3-d orthogonal range reporting
%%    with $O(n\lg^{1+\eps} n)$ space and $O(\lg\lg n + k)$ query time
%%    for points in rank space, for any constant $\eps>0$.
%%    This improves the previous results by Afshani (ESA'08),
%%    Karpinski and Nekrich (COCOON'09), and Chan (SODA'11),
%%    with $O(n\lg^3 n)$ space and $O(\lg\lg n + k)$ query time, or
%%    with $O(n\lg^{1+\eps}n)$ space and $O(\lg^2\lg n + k)$ query time.
%%    Consequently, we obtain improved upper bounds 
%%    for orthogonal range reporting in all constant dimensions above~3.
%%    Our approach also leads to a new data structure for 2-d orthogonal range 
%%    minimum queries with $O(n\lg^\eps n)$ space and $O(\lg\lg n)$ query time
%%    for points in rank space.
%%  \item We give a randomized algorithm for 4-d \emph{offline} dominance range
%%    reporting/emptiness with running time $O(n\log n)$ plus the output size.
%%    This resolves two open problems (both appeared 
%%    in Preparata and Shamos' seminal book):
%%  \begin{enumerate}
%%  \item given a set of $n$ axis-aligned rectangles in the plane,
%%     we can report all $k$ enclosure pairs (i.e., pairs $(r_1,r_2)$ where
%%     rectangle $r_1$ completely encloses rectangle $r_2$)
%%     in $O(n\lg n + k)$ expected time;
%%  \item given a set of $n$ points in 4-d, we can find all maximal points
%%     (points not dominated by any other points)
%%     in $O(n\lg n)$ expected time.
%%  \end{enumerate}
%%  The most recent previous development on (a) was reported back in SoCG'95 by
%%  Gupta, Janardan, Smid, and Dasgupta, whose main result was
%%  an $O([n\lg n + k]\lg\lg n)$ algorithm.  The best previous
%%  result on (b) was an $O(n\lg n\lg\lg n)$ algorithm
%%  due to Gabow, Bentley, and Tarjan---from STOC'84!
%%  As a consequence, we also obtain the current-record time bound for
%%  the maxima problem in all constant dimensions above~4.
%%  \end{enumerate}

  author =    "Mihai P{\v a}tra{\c s}cu and Mikkel Thorup",
  title =     "The Power of Simple Tabulation Hashing",
  booktitle = "Proc. 43rd ACM Symposium on Theory of Computing (STOC)",
  pages =     "1-10",
  year =      "2011",
  note =      "See also arXiv:1011.5200"
%% Abstract:
%%  Randomized algorithms are often enjoyed for their simplicity, but the
%%  hash functions used to yield the desired theoretical guarantees are
%%  often neither simple nor practical. Here we show that the simplest
%%  possible tabulation hashing provides unexpectedly strong guarantees.
%%  The scheme itself dates back to Carter and Wegman (STOC'77).  Keys are
%%  viewed as consisting of $c$ characters. We initialize $c$ tables $T_1,
%%  \dots, T_c$ mapping characters to random hash codes. A key
%%  $x=(x_1, \dots, x_q)$ is hashed to $T_1[x_1] \oplus \cdots \oplus
%%  T_c[x_c]$, where $\oplus$ denotes xor.
%%  While this scheme is not even 4-independent, we show that it provides
%%  many of the guarantees that are normally obtained via higher
%%  independence, e.g., Chernoff-type concentration, min-wise hashing for
%%  estimating set intersection, and cuckoo hashing.

  author =    "Mihai P{\v a}tra{\c s}cu and Mikkel Thorup",
  title =     "Don't Rush into a Union: Take Time to Find Your Roots",
  booktitle = "Proc. 43rd ACM Symposium on Theory of Computing (STOC)",
  pages =     "559-568",
  year =      "2011",
  note =      "See also arXiv:1102.1783"
%% Abstract:
%%  \newcommand{\proc}[1]{\textnormal{\scshape#1}}
%%  We present a new threshold phenomenon in data structure lower bounds
%%  where slightly reduced update times lead to exploding query
%%  times. Consider incremental connectivity, letting $t_u$ be the time to
%%  insert an edge and $t_q$ be the query time. For $t_u = \Omega(t_q)$,
%%  the problem is equivalent to the well-understood \emph{union--find}
%%  problem: $\proc{InsertEdge}(s,t)$ can be implemented by
%%  $\proc{Union}(\proc{Find}(s), \proc{Find}(t))$. This gives worst-case
%%  time $t_u = t_q = O(\lg n / \lg\lg n)$ and amortized $t_u = t_q =
%%  O(\alpha(n))$.
%%  By contrast, we show that if $t_u = o(\lg n / \lg\lg n)$, the query
%%  time explodes to $t_q \ge n^{1-o(1)}$. In other words, if the data
%%  structure doesn't have time to find the roots of each disjoint set
%%  (tree) during edge insertion, there is no effective way to organize
%%  the information!
%%  For amortized complexity, we demonstrate a new inverse-Ackermann type
%%  trade-off in the regime $t_u = o(t_q)$.
%%  A similar lower bound is given for fully dynamic connectivity, where
%%  an update time of $o(\lg n)$ forces the query time to be
%%  $n^{1-o(1)}$. This lower bound allows for amortization and Las Vegas
%%  randomization, and comes close to the known $O(\lg n \cdot (\lg\lg
%%  n)^{O(1)})$ upper bound.

  author =    "Mihai P{\v a}tra{\c s}cu and Liam Roditty",
  title =     "Distance Oracles Beyond the Thorup--Zwick Bound",
  booktitle = "Proc. 51st IEEE Symposium on Foundations of Computer Science (FOCS)",
  year =      "2010",
  note =      "To appear"
%% Abstract:
%%  We give the first improvement to the space/approximation trade-off of
%%  distance oracles since the seminal result of Thorup and Zwick [STOC'01].
%%  For unweighted graphs, our distance oracle has size $O(n^{5/3}) =
%%  O(n^{1.66\cdots})$ and, when queried about vertices at distance $d$,
%%  returns a path of length $2d+1$.
%%  For weighted graphs with $m=n^2/\alpha$ edges, our distance oracle has
%%  size $O(n^2 / \sqrt[3]{\alpha})$ and returns a factor 2 approximation.
%%  Based on a widely believed conjecture about the hardness of set
%%  intersection queries, we show that a 2-approximate distance oracle
%%  requires space $\widetilde{\Omega}(n^2 / \sqrt{\alpha})$. For
%%  unweighted graphs, this implies a $\widetilde{\Omega}(n^{1.5})$ space lower
%%  bound to achieve approximation $2d+1$.  

  author =    "Mihai P{\v a}tra{\c s}cu and Mikkel Thorup",
  title =     "On the $k$-Independence Required by Linear Probing and Minwise Independence",
  booktitle = "Proc. 37th International Colloquium on Automata, Languages and Programming (ICALP)",
  pages =     "715-726",
  year =      "2010"
%% Abstract:
%%  We show that linear probing requires 5-independent hash functions for
%%  expected constant-time performance, matching an upper bound of [Pagh
%%  et al.~STOC'07].
%%  For $(1+\eps)$-approximate minwise independence, we show that
%%  $\Omega(\lg \frac{1}{\eps})$-independent hash functions are required,
%%  matching an upper bound of [Indyk, SODA'99].
%%  We also show that the multiply-shift scheme of Dietzfelbinger, most
%%  commonly used in practice, fails badly in both applications.

  author =    "Mihai P{\v a}tra{\c s}cu",
  title =     "Towards Polynomial Lower Bounds for Dynamic Problems",
  booktitle = "Proc. 42nd ACM Symposium on Theory of Computing (STOC)",
  pages =     "603-610",
  year =      "2010"
%% Abstract:
%%  We consider a number of dynamic problems with no known
%%  poly-logarithmic upper bounds, and show that they \emph{require}
%%  $n^{\Omega(1)}$ time per operation, unless 3SUM has strongly
%%  subquadratic algorithms. Our result is modular:
%%  {\bf 1.} We describe a carefully-chosen dynamic version
%%  of set disjointness (the \emph{multiphase problem}), and conjecture
%%  that it requires $n^{\Omega(1)}$ time per operation. All our lower
%%  bounds follow by easy reduction. 
%%  {\bf 2.} We reduce 3SUM to the multiphase problem. Ours is the first
%%  \emph{nonalgebraic} reduction from 3SUM, and allows 3SUM-hardness
%%  results for combinatorial problems. For instance, it implies hardness
%%  of reporting all triangles in a graph.
%%  {\bf 3.} It is possible that an unconditional lower bound for the
%%  multiphase problem can be established via a number-on-forehead
%%  communication game.

  author =    "Yevgeniy Dodis and Mihai P{\v a}tra{\c s}cu and Mikkel Thorup",
  title =     "Changing Base without Losing Space",
  booktitle = "Proc. 42nd ACM Symposium on Theory of Computing (STOC)",
  pages =     "593-602",
  year =      "2010"
%% Abstract:
%%  We describe a simple, but powerful local encoding technique, implying
%%  two surprising results:
%%  {\bf 1.} We show how to represent a vector of $n$ values from $\Sigma$ using
%%  $\lceil n\log_2 \Sigma \rceil$ bits, such that reading or writing any
%%  entry takes $O(1)$ time. This demonstrates, for instance, an
%%  ``equivalence'' between decimal and binary computers, and has been a
%%  central toy problem in the field of succinct data structures. Previous
%%  solutions required space of $n \log_2 \Sigma + n/\lg^{O(1)} n$ bits
%%  for constant access.
%%  {\bf 2.} Given a stream of $n$ bits arriving online (for any $n$, not
%%  known in advance), we can output a \emph{prefix-free} encoding that
%%  uses $n + \log_2 n + O(\lg\lg n)$ bits. The encoding and decoding
%%  algorithms only require $O(\lg n)$ bits of memory, and run in constant
%%  time per word. This result is interesting in cryptographic
%%  applications, as prefix-free codes are the simplest counter-measure to
%%  extensions attacks on hash functions, message authentication codes and
%%  pseudorandom functions. Our result refutes a conjecture of [Maurer,
%%  Sj\"odin 2005] on the hardness of online prefix-free encodings.

  author =    "Mihai P{\v a}tra{\c s}cu and Dan Stratila",
  title =     "Faster Primal-Dual Algorithms for the Economic Lot-Sizing Problem"
%% Abstract:
%%  We consider the classical lot-sizing problem, introduced by Manne (1958), and
%%  Wagner and Whitin (1958). Since its introduction, much research has
%%  investigated the running time of this problem. Federgruen and Tzur (1991), 
%%  Wagelmans et al. (1992), and Aggarwal and Park (1993) independently obtained 
%%  $O(n \lg n)$ algorithms. Recently, Levi et al. (2006) developed a primal-dual 
%%  algorithm. Building on the work of Levi et al., we obtain a faster 
%%  algorithm with a running time of $O(n \lg\lg n)$.

  author =    "Mihai P{\v a}tra{\c s}cu and Emanuele Viola",
  title =     "Cell-Probe Lower Bounds for Succinct Partial Sums",
  booktitle = "Proc. 21st ACM/SIAM Symposium on Discrete Algorithms (SODA)",
  pages =     "117-122",
  year =      "2010"
%% Abstract:
%%  The partial sums problem in succinct data structures asks to
%%  preprocess an array $A[1\mathinner{\ldotp\ldotp} n]$ of bits into a
%%  data structure using as close to $n$ bits as possible, and answer
%%  queries of the form ${\textnormal{\scshape{rank}}}(k) = \sum_{i=1}^k
%%  A[i]$. The problem has been intensely studied, and features as a
%%  subroutine in a number of succinct data structures.
%%  We show that, if we answer rank queries by probing $t$ cells of
%%  $w$ bits, then the space of the data structure must be at least $n +
%%  n/w^{O(t)}$ bits. This redundancy/probe trade-off is essentially
%%  optimal: Patrascu [FOCS'08] showed how to achieve $n + n /
%%  (w/t)^{\Omega(t)}$ bits. We also extend our lower bound to the closely
%%  related select queries, and to the case of sparse arrays.

  author =    "Mihai P{\v a}tra{\c s}cu and Ryan Williams",
  title =     "On the Possibility of Faster SAT Algorithms",
  booktitle = "Proc. 21st ACM/SIAM Symposium on Discrete Algorithms (SODA)",
  pages =     "1065-1075",
  year =      "2010"
%% Abstract:
%%  We describe reductions from the problem of determining the
%%  satisfiability of Boolean CNF formulas (CNF-SAT) to several natural
%%  algorithmic problems. We show that attaining any of the following
%%  bounds would improve the state of the art in algorithms for SAT:
%%  \begin{itemize}
%%  \item an $O(n^{k-\eps})$ algorithm for {\sc $k$-Dominating Set}, for any
%%    $k \geq 3$,
%%  \item a (computationally efficient) protocol for 3-party set
%%    disjointness with $o(m)$ bits of communication,
%%  \item an $n^{o(d)}$ algorithm for $d$-SUM,
%%  \item an $O(n^{2-\eps})$ algorithm for 2-SAT with $m=n^{1+o(1)}$
%%    clauses, where \emph{two} clauses may have unrestricted length, and
%%  \item an $O((n+m)^{k-\eps})$ algorithm for HornSat with $k$
%%    unrestricted length clauses.
%%  \end{itemize}
%%  One may interpret our reductions as new attacks on the complexity of
%%  SAT, or sharp lower bounds conditional on exponential hardness of SAT.

  author =    "Timothy M. Chan and Mihai P{\v a}tra{\c s}cu",
  title =     "Counting Inversions, Offline Orthogonal Range Counting, and Related Problems",
  booktitle = "Proc. 21st ACM/SIAM Symposium on Discrete Algorithms (SODA)",
  pages =     "161-173",
  year =      "2010"
%% Abstract:
%%  We give an $O(n\sqrt{\lg n})$-time algorithm for counting the number
%%  of inversions in a permutation on $n$ elements.  This improves a
%%  long-standing previous bound of $O(n\lg n/\lg\lg n)$ that followed
%%  from Dietz's data structure [WADS'89], and answers a question of
%%  Andersson and Petersson [SODA'95]. As Dietz's result is known to be
%%  optimal for the related dynamic rank problem, our result demonstrates
%%  a significant improvement in the \emph{offline} setting.
%%  Our new technique is quite simple: we perform a ``vertical
%%  partitioning'' of a trie (akin to van Emde
%%  Boas trees), and use ideas from external
%%  memory. However, the technique finds numerous applications: 
%%  for example, we obtain
%%  \begin{itemize}
%%  \item in $d$ dimensions, an algorithm to answer $n$ offline orthogonal range
%%    counting queries in time $O(n\lg^{d-2+1/d}n)$;
%%  \item an improved construction time for online data structures for
%%    orthogonal range counting;
%%  \item an improved update time for the partial sums problem;
%%  \item faster Word RAM algorithms for finding the maximum depth in an
%%    arrangement of axis-aligned rectangles, and for the slope selection
%%    problem.
%%  \end{itemize}
%%  As a bonus, we also give a simple $(1+\eps)$-approximation algorithm 
%%  for counting inversions that runs in linear time, improving the
%%  previous $O(n\lg\lg n)$ bound by Andersson and Petersson. 

  author =    "Alexandr Andoni and T.S. Jayram and Mihai P{\v a}tra{\c s}cu",
  title =     "Lower Bounds for Edit Distance and Product Metrics via Poincar\'e-Type Inequalities",
  booktitle = "Proc. 21st ACM/SIAM Symposium on Discrete Algorithms (SODA)",
  pages =     "184-192",
  year =      "2010"
%% Abstract:
%%  We prove that any sketching protocol for edit distance achieving a
%%  constant approximation requires nearly logarithmic (in the strings'
%%  length) communication complexity. This is an exponential improvement
%%  over the previous, doubly-logarithmic, lower bound of
%%  [Andoni-Krauthgamer, FOCS'07]. Our lower bound also applies to the Ulam
%%  distance (edit distance over non-repetitive strings). In this special
%%  case, it is polynomially related to the recent upper bound of
%%  [Andoni-Indyk-Krauthgamer, SODA'09].
%%  From a technical perspective, we prove a direct-sum theorem for
%%  sketching product metrics that is of independent interest. We show
%%  that, for any metric $X$ that requires sketch size which is 
%%  a sufficiently large constant,
%%  sketching the max-product metric $\ell_\infty^d(X)$ requires 
%%  $\Omega(d)$ bits. The conclusion, in fact, also holds 
%%  for arbitrary two-way communication.
%%  The proof uses a novel technique for information complexity 
%%  based on Poincar\'e inequalities and suggests
%%  an intimate connection between non-embeddability, sketching
%%  and communication complexity.

  author =    "Erik D. Demaine and Dion Harmon and John Iacono and Daniel Kane and Mihai P{\v a}tra{\c s}cu",
  title =     "The Geometry of Binary Search Trees",
  booktitle = "Proc. 20th ACM/SIAM Symposium on Discrete Algorithms (SODA)",
  pages =     "496-505",
  year =      "2009"
%% Abstract:
%%  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:
%%  \begin{enumerate}
%%  \item A surprisingly clean restatement in geometric terms of many
%%    results and conjectures relating to BSTs and dynamic optimality.
%%  \item A new lower bound for searching in the BST model, which subsumes
%%    the previous two known bounds of Wilber~[FOCS'86].
%%  \item 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 \emph{online} algorithm,
%%    transforming the conjecture of Lucas and Munro into the conjecture
%%    that the greedy algorithm is dynamically optimal.
%%  \end{enumerate}

  author =    "Mihai P{\v a}tra{\c s}cu",
  title =     "Unifying the Landscape of Cell-Probe Lower Bounds",
  journal =   "SIAM Journal on Computing",
  volume =    "40",
  number =    "3",
  pages =     "827-847",
  year =      "2011",
  note =      "See also FOCS'08, arXiv:1010.3783"
%% Abstract:
%%  We show that a large fraction of the data-structure lower bounds known
%%  today in fact follow by reduction from the communication complexity of
%%  lopsided (asymmetric) set disjointness! This includes lower bounds for:
%%  \begin{itemize*}
%%  \item high-dimensional problems, where the goal is to show large space
%%    lower bounds.
%%  \item constant-dimensional geometric problems, where the goal is to
%%    bound the query time for space $O(n\, \polylog n)$.
%%  \item dynamic problems, where we are looking for a trade-off between
%%    query and update time. (In this case, our bounds are slightly weaker
%%    than the originals, losing a $\lg\lg n$ factor.)
%%  \end{itemize*}
%%  \smallskip
%%  \noindent
%%  Our reductions also imply the following \emph{new} results:
%%  \begin{itemize*}
%%  \item an $\Omega(\lg n / \lg\lg n)$ bound for 4-dimensional range
%%    reporting, given space $O(n\, \polylog n)$. This is very timely,
%%    since a recent result [Nekrich,~SoCG'07] solved 3D reporting in
%%    near-constant time, raising the prospect that higher dimensions
%%    could also be easy.
%%  \item a tight space lower bound for the partial match problem, for
%%    constant query time.
%%  \item the first lower bound for reachability oracles.
%%  \end{itemize*}
%%  \noindent
%%  In the process, we prove optimal randomized lower bounds for lopsided
%%  set disjointness.

  author =    "Mihai P{\v a}tra{\c s}cu",
  title =     "Succincter",
  booktitle = "Proc. 49th IEEE Symposium on Foundations of Computer Science (FOCS)",
  pages =     "305-313",
  year =      "2008"
%% Abstract:
%%  We can represent an array of $n$ values from $\{0,1,2\}$ using \(\lceil
%%  n \log_2 3 \rceil\) bits (arithmetic coding), but then we cannot
%%  retrieve a single element efficiently. Instead, we can encode every
%%  block of $t$ elements using \(\lceil t\log_2 3 \rceil\) bits, and bound
%%  the retrieval time by $t$. This gives a linear trade-off between the
%%  redundancy of the representation and the query time.
%%  In fact, this type of linear trade-off is ubiquitous in known succinct
%%  data structures, and in data compression. The folk wisdom is that if
%%  we want to waste one bit per block, the encoding is so constrained
%%  that it cannot help the query in any way. Thus, the only thing a query
%%  can do is to read the entire block and unpack it.
%%  We break this limitation and show how to use recursion to improve
%%  redundancy. It turns out that if a block is encoded with two (!)  bits
%%  of redundancy, we can decode a single element, and answer many other
%%  interesting queries, in time logarithmic in the block size.
%%  Our technique allows us to revisit classic problems in succinct data
%%  structures, and give surprising new upper bounds. We also construct a
%%  locally-decodable version of arithmetic coding.

  author =    "Alexandr Andoni and Dorian Croitoru and Mihai P{\v a}tra{\c s}cu",
  title =     "Hardness of Nearest Neighbor under L-infinity",
  booktitle = "Proc. 49th IEEE Symposium on Foundations of Computer Science (FOCS)",
  pages =     "424-433",
  year =      "2008"
%% Abstract:
%%  Recent years have seen a significant increase in our
%%  understanding of high-dimensional nearest neighbor search (NNS) for
%%  distances like the $\ell_1$ and $\ell_2$ norms. By contrast, our
%%  understanding of the $\ell_\infty$ norm is now where it was (exactly)
%%  10 years ago.
%%  In FOCS'98, Indyk proved the following unorthodox result: there is a data
%%  structure (in fact, a decision tree) of size $O(n^\rho)$, for any
%%  $\rho>1$, which achieves approximation $O(\log_\rho \log d)$ for NNS
%%  in the $d$-dimensional $\ell_\infty$ metric.
%%  In this paper, we provide results that indicate that Indyk's
%%  unconventional bound might in fact be optimal. Specifically, we show a
%%  lower bound for the asymmetric communication complexity of NNS under
%%  $\ell_\infty$, which proves that this space/approximation trade-off is
%%  optimal for decision trees and for data structures with constant
%%  cell-probe complexity.

  author =    "Timothy M. Chan and Mihai P{\v a}tra{\c s}cu and Liam Roditty",
  title =     "Dynamic Connectivity: Connecting to Networks and Geometry",
  journal =   "SIAM Journal on Computing",
  volume =    "40",
  number =    "2",
  pages =     "333-349",
  year =      "2011",
  note =      "See also FOCS'08, arXiv:0808.1128"
%% Abstract:
%%  Dynamic connectivity is a well-studied problem, but so far
%%  the most compelling progress has been confined to the edge-update
%%  model: maintain an understanding of connectivity in an undirected
%%  graph, subject to edge insertions and deletions. In this paper, we
%%  study two more challenging, yet equally fundamental problems:
%%  \smallskip
%%  {\bf Subgraph connectivity} asks to maintain an understanding of
%%  connectivity under vertex updates: updates can turn vertices on and off,
%%  and queries refer to the subgraph induced by \emph{on} vertices.  (For
%%  instance, this is closer to applications in networks of routers, where
%%  node faults may occur.)
%%  We describe a data structure supporting vertex updates in
%%  \( \tO(m^{2/3}) \) amortized time, where $m$ denotes the number
%%  of edges in the graph. This greatly improves over
%%  the previous result {\rm [Chan, STOC'02]}, which
%%  required fast matrix multiplication and had an update time 
%%  of $O(m^{0.94})$.  The new data structure is also simpler.
%%  \smallskip
%%  {\bf Geometric connectivity} asks to maintain a dynamic set of $n$
%%  geometric objects, and query connectivity in their intersection
%%  graph.  (For instance, the intersection graph of balls describes
%%  connectivity in a network of sensors with bounded transmission radius.)
%%  Previously, nontrivial fully dynamic results were known only
%%  for special cases like axis-parallel line segments and rectangles.
%%  We provide similarly improved
%%  update times, \( \tO(n^{2/3}) \), for these special cases.
%%  Moreover, we show how to obtain sublinear update bounds for
%%  virtually {\em all\/} families 
%%  of geometric objects which allow sublinear-time range queries. 
%%  In particular, we obtain the {\em first\/} sublinear update time
%%  for arbitrary 2D line segments: \( O^\star(n^{9/10}) \); for $d$-dimensional
%%  simplices: \( O^\star(n^{1-\frac{1}{d(2d+1)}}) \); and
%%  for $d$-dimensional balls: \( O^\star(n^{1-\frac{1}{(d+1)(2d+3)}}) \).

  author =    "Jakub Pawlewicz and Mihai P{\v a}tra{\c s}cu",
  title =     "Order Statistics in the Farey Sequences in Sublinear Time and Counting Primitive Lattice Points in Polygons",
  journal =   "Algorithmica",
  volume =    "55",
  number =    "2",
  pages =     "271-282",
  year =      "2009",
  note =      "See also ESA'07, arXiv:0708.0080"
%% Abstract:
%%  We present the first sublinear-time algorithms for computing order statistics in the Farey sequence
%%  and for the related problem of ranking.
%%  Our algorithms achieve a running times of nearly $O(n^{2/3})$, which is
%%  a significant improvement over the previous algorithms taking time $O(n)$.
%%  We also initiate the study of a more general problem: counting
%%  primitive lattice points inside planar shapes.  For rational polygons
%%  containing the origin, we obtain a running time proportional to
%%  $D^{6/7}$, where $D$ is the diameter of the polygon.

  author =    "Amit Chakrabarti and T.S. Jayram and Mihai P{\v a}tra{\c s}cu",
  title =     "Tight Lower Bounds for Selection in Randomly Ordered Streams",
  booktitle = "Proc. 19th ACM/SIAM Symposium on Discrete Algorithms (SODA)",
  pages =     "720-729",
  year =      "2008"
%% Abstract:
%%  We show that any algorithm computing the median of a stream presented in
%%  random order, using $O(\polylog n)$ space, requires an optimal
%%  $\Omega(\log\log n)$ passes, resolving an open question from the seminal
%%  paper on streaming by Munro and Paterson, from FOCS 1978.

  author =    "Mihai P{\v a}tra{\c s}cu and Mikkel Thorup",
  title =     "Planning for Fast Connectivity Updates",
  booktitle = "Proc. 48th IEEE Symposium on Foundations of Computer Science (FOCS)",
  pages =     "263-271",
  year =      "2007"
%% Abstract:
%%  Understanding how a single edge deletion can affect the connectivity
%%  of a graph amounts to finding the graph bridges. But when faced with
%%  $d>1$ deletions, can we establish as easily how the connectivity
%%  changes? When planning for an emergency, we want to understand the
%%  structure of our network ahead of time, and respond swiftly when an
%%  emergency actually happens.
%%  We describe a linear-space representation of graphs which enables us
%%  to determine how a batch of edge updates can impact the graph. Given a
%%  set of $d$ edge updates, in time $O(d\, \polylog n)$ we can obtain the
%%  number of connected components, the size of each component, and a fast
%%  oracle for answering connectivity queries in the updated graph.  The
%%  initial representation is polynomial-time constructible.

  author =    "Gianni Franceschini and S. Muthukrishnan and Mihai P{\v a}tra{\c s}cu",
  title =     "Radix Sorting With No Extra Space",
  booktitle = "Proc. 15th European Symposium on Algorithms (ESA)",
  pages =     "194-205",
  year =      "2007",
  note =      "See also arXiv:0706.4107"
%% Abstract:
%%  It is well known that $n$ integers in the range $[1,n^c]$ can be
%%  sorted in $O(n)$ time in the RAM model using radix sorting. More
%%  generally, integers in any range $[1,U]$ can be sorted in
%%  \( O(n\sqrt{\log\log n}) \) time.  However, these algorithms use
%%  $O(n)$ words of extra memory. Is this necessary?
%%  We present a simple, stable, integer sorting algorithm for words of
%%  size $O(\log n)$, which works in $O(n)$ time and uses only $O(1)$
%%  words of extra memory on a RAM model. This is the integer sorting case
%%  most useful in practice.  We extend this result with same bounds to
%%  the case when the keys are read-only, which is of theoretical
%%  interest. Another interesting question is the case of arbitrary $c$.
%%  Here we present a black-box transformation from any RAM sorting
%%  algorithm to a sorting algorithm which uses only $O(1)$ extra space
%%  and has the same running time.  This settles the complexity of
%%  in-place sorting in terms of the complexity of sorting.

  author =    "Mihai P{\v a}tra{\c s}cu",
  title =     "Lower Bounds for 2-Dimensional Range Counting",
  booktitle = "Proc. 39th ACM Symposium on Theory of Computing (STOC)",
  pages =     "40-46",
  year =      "2007"
%% Abstract:
%%  Proving lower bounds for range queries has been an active topic of
%%  research since the late 70s, but so far nearly all results have been
%%  limited to the (rather restrictive) semigroup model. We consider one
%%  of the most basic range problem, orthogonal range counting in two
%%  dimensions, and show almost optimal bounds in the group model and
%%  the (holy grail) cell-probe model.
%%  Specifically, we show the following bounds, which were known in the
%%  semigroup model, but are major improvements in the more general
%%  models:
%%  %
%%  \begin{itemize}
%%  \item In the group and cell-probe models, a static data structure of
%%    size $n\lg^{O(1)} n$ requires $\Omega(\lg n / \lg\lg n)$ time per
%%    query. This is an exponential improvement over previous bounds,
%%    and matches known upper bounds.
%%  \item In the group model, a dynamic data structure takes time
%%    \( \Omega\big( (\frac{\lg n}{\lg\lg n})^2 \big) \) per operation.
%%    This is close to the $O(\lg^2 n)$ upper bound, whereas the
%%    previous lower bound was $\Omega(\lg n)$.
%%  \end{itemize}
%%  \noindent
%%  Proving such (static and dynamic) bounds in the group model has been
%%  regarded as an important challenge at least since [Fredman, JACM
%%  1982] and [Chazelle, FOCS 1986].

  author =    "Timothy M. Chan and Mihai P{\v a}tra{\c s}cu",
  title =     "Transdichotomous Results in Computational Geometry, {II}: Offline Search",
  booktitle = "Proc. 39th ACM Symposium on Theory of Computing (STOC)",
  pages =     "31-39",
  year =      "2007",
  note =      "See also arXiv:1010.1948"
%% Abstract:
%%  We reexamine fundamental problems from computational geometry in the
%%  word RAM model, where input coordinates are integers that fit in a
%%  machine word. We develop a new algorithm for offline point location,
%%  a two-dimensional analog of sorting where one needs to order points
%%  with respect to segments. This result implies, for example, that the
%%  convex hull of $n$ points in three dimensions can be constructed in
%%  (randomized) time $n\cdot 2^{O(\sqrt{\lg\lg n})}$.  Similar bounds
%%  hold for numerous other geometric problems, such as
%%  planar Voronoi diagrams, planar off-line nearest neighbor search,
%%  line segment intersection, and triangulation of non-simple
%%  polygons.
%%  In FOCS'06, we developed a data structure for \emph{online} point
%%  location, which implied a bound of $O(n \frac{\lg n}{\lg\lg n})$ for
%%  three-dimensional convex hulls and the other problems. Our current bounds are
%%  dramatically better, and a convincing improvement over the classic
%%  $O(n\lg n)$ algorithms. As in the field of integer sorting, the main
%%  challenge is to find ways to manipulate information, while avoiding
%%  the online problem (in that case, predecessor search).

  author =    "Erik D. Demaine and Mihai P{\v a}tra{\c s}cu",
  title =     "Tight Bounds for Dynamic Convex Hull Queries (Again)",
  booktitle = "Proc. 23rd ACM Symposium on Computational Geometry (SoCG)",
  pages =     "354-363",
  year =      "2007"
%% Abstract:
%%  The dynamic convex hull problem was recently solved in $O(\lg n)$ time
%%  per operation, and this result is best possible in models of computation
%%  with bounded branching (e.g., algebraic computation trees).
%%  From a data structures point of view,
%%  however, such models are considered
%%  unrealistic because they hide intrinsic notions of information
%%  in the input.
%%  In the standard word-RAM and cell-probe models of computation, 
%%  we prove that the optimal query time for dynamic convex hulls is, in fact,
%%  \( \Theta\big(\frac{\lg n}{\lg \lg n}\big) \), for polylogarithmic update time
%%  (and word size).
%%  Our lower bound is based on a reduction from the marked-ancestor problem,
%%  and is one of the first data structural lower bounds for a nonorthogonal
%%  geometric problem.
%%  Our upper bounds follow a recent trend of attacking nonorthogonal geometric
%%  problems from an information-theoretic perspective that has proved
%%  central to advanced data structures.  Interestingly, our upper bounds are
%%  the first to successfully apply this perspective to dynamic geometric data
%%  structures, and require substantially different ideas from previous work.

  author =    "Nicholas J.A. Harvey and Mihai P{\v a}tra{\c s}cu and Yonggang Wen and Sergey Yekhanin and Vincent W.S. Chan",
  title =     "Non-Adaptive Fault Diagnosis for All-Optical Networks via Combinatorial Group Testing on Graphs",
  booktitle = "Proc. 26th IEEE Conference on Computer Communications (INFOCOM)",
  pages =     "697-705",
  year =      "2007"
%% Abstract:
%%  We consider the problem of detecting network faults. Our focus is
%%  on detection schemes that send probes both proactively and
%%  non-adaptively. Such schemes are particularly relevant to all-optical
%%  networks, due to these networks' operational characteristics and
%%  strict performance requirements. This fault diagnosis problem
%%  motivates a new technical framework that we introduce: group testing
%%  with graph-based constraints. Using this framework, we develop several
%%  new probing schemes to detect network faults. The efficiency of our
%%  schemes often depends on the network topology; in many cases we can
%%  show that our schemes are optimal or near-optimal by providing tight
%%  lower bounds.  

  author =    "Mihai P{\v a}tra{\c s}cu and Mikkel Thorup",
  title =     "Randomization Does Not Help Searching Predecessors",
  booktitle = "Proc. 18th ACM/SIAM Symposium on Discrete Algorithms (SODA)",
  pages =     "555-564",
  year =      "2007"
%% Abstract:
%%  At STOC'06, we presented a new technique for proving
%%  cell-probe lower bounds for static data structures with deterministic
%%  queries. This was the first technique which could prove a bound higher
%%  than communication complexity, and it gave the first separation
%%  between data structures with linear and polynomial space. The new
%%  technique was, however, heavily tuned for the deterministic
%%  worst-case, demonstrating long query times only for an exponentially
%%  small fraction of the input. In this paper, we extend the
%%  technique to give lower bounds for randomized query algorithms with
%%  constant error probability.
%%  Our main application is the problem of searching predecessors in
%%  a static set of $n$ integers, each contained in a $\ell$-bit word. Our
%%  trade-off lower bounds are tight for any combination of parameters.
%%  For small space, i.e.~$n^{1+o(1)}$, proving such lower bounds was
%%  inherently impossible through known techniques. An interesting new
%%  consequence is that for near linear space, the classic van Emde Boas
%%  search time of $O(\lg \ell)$ cannot be improved, even if we allow
%%  randomization. This is a separation from polynomial space, since Beame
%%  and Fich [STOC'02] give a predecessor search time of $O(\lg \ell / \lg\lg
%%  \ell)$ using quadratic space.
%%  We also show a tight $\Omega(\lg\lg n)$ lower bound for
%%  2-dimensional range queries, via a new reduction.  This holds even in
%%  rank space, where no superconstant lower bound was known, neither
%%  randomized nor worst-case.  We also slightly improve the best lower
%%  bound for the approximate nearest neighbor problem, when small space
%%  is available.

  author =    "Timothy M. Chan and Mihai P{\v a}tra{\c s}cu",
  title =     "Transdichotomous Results in Computational Geometry, {I}: {P}oint Location in Sublogarithmic Time",
  journal =   "SIAM Journal on Computing",
  volume =    "39",
  number =    "2",
  pages =     "703-729",
  year =      "2010",
  note =      "See also FOCS'06"
%% Abstract:
%%  Given a planar subdivision whose coordinates are integers bounded by
%%  $U\le 2^w$, we present a linear-space data structure that can answer
%%  point location queries in \( O(\min\{ \lg n / \lg\lg n,
%%  \sqrt{\lg U/\lg\lg U}\}) \) time
%%  on the unit-cost RAM with word size~$w$. This is the
%%  first result to beat the standard $\Theta(\lg n)$ bound for infinite
%%  precision models.
%%  As a consequence, we obtain the first $o(n\lg n)$ (randomized) algorithms
%%  for many fundamental problems in computational geometry for
%%  arbitrary integer input on the word RAM, including:
%%  constructing the convex hull of a
%%  three-dimensional point set, computing the Voronoi diagram or the Euclidean
%%  minimum spanning
%%  tree of a planar point set, triangulating a polygon with holes, and
%%  finding intersections among a set of line segments.
%%  Higher-dimensional extensions and applications are also discussed.
%%  Though computational geometry with bounded precision input has been
%%  investigated for a long time, improvements have been limited largely
%%  to problems of an orthogonal flavor. Our results surpass this
%%  long-standing limitation, answering, for example, a question of
%%  Willard (SODA'92).

  author =    "Mihai P{\v a}tra{\c s}cu and Mikkel Thorup",
  title =     "Higher Lower Bounds for Near-Neighbor and Further Rich Problems",
  journal =   "SIAM Journal on Computing",
  volume =    "39",
  number =    "2",
  pages =     "730-741",
  year =      "2010",
  note =      "See also FOCS'06"
%% Abstract:
%%  We convert cell-probe lower bounds for polynomial space into
%%  stronger lower bounds for near-linear space. Our technique applies to
%%  any lower bound proved through the richness method. For example, it
%%  applies to partial match, and to near-neighbor problems, either for
%%  randomized exact search, or for deterministic approximate search
%%  (which are thought to exhibit the curse of dimensionality). These
%%  problems are motivated by search in large data bases, so near-linear
%%  space is the most relevant regime.
%%  Typically, richness has been used to imply $\Omega(d / \lg n)$ lower
%%  bounds for polynomial-space data structures, where $d$ is the number
%%  of bits of a query. This is the highest lower bound provable through
%%  the classic reduction to communication complexity. However, for
%%  space $n \lg^{O(1)} n$, we now obtain bounds of $\Omega(d / \lg d)$.
%%  This is a significant improvement for natural values of $d$, such as
%%  $\lg^{O(1)} n$. In the most important case of $d = \Theta(\lg n)$,
%%  we have the first superconstant lower bound. From a
%%  complexity theoretic perspective, our lower bounds are the highest
%%  known for \emph{any} static data structure problem, significantly
%%  improving on previous records.

  author =    "Alexandr Andoni and Piotr Indyk and Mihai P{\v a}tra{\c s}cu",
  title =     "On the Optimality of the Dimensionality Reduction Method",
  booktitle = "Proc. 47th IEEE Symposium on Foundations of Computer Science (FOCS)",
  pages =     "449-458",
  year =      "2006"
%% Abstract:
%%  We investigate the optimality of $(1+\eps)$-approximation algorithms 
%%  obtained via the dimensionality reduction method. We show that:
%%  \begin{itemize}
%%  \item Any data structure for the $(1+\eps)$-approximate 
%%	{\em nearest neighbor} problem in Hamming space, which uses 
%%	constant number of probes to answer each query, must use 
%%	\( n^{\Omega(1/\eps^2)} \) space.
%%  \item Any algorithm for the $(1+\eps)$-approximate {\em closest 
%%	substring} problem must run in time exponential in 
%%	$1/\eps^{2-\gamma}$ for any $\gamma>0$ (unless 3SAT can be 
%%	solved in sub-exponential time)
%%  \end{itemize}
%%  Both lower bounds are (essentially) tight.

  author =    "Mette Berger and Esben Rune Hansen and Rasmus Pagh and Mihai P{\v a}tra{\c s}cu and Milan Ru\v{z}i\'{c} and Peter Tiedemann",
  title =     "Deterministic Load Balancing and Dictionaries in the Parallel Disk Model",
  booktitle = "Proc. 18th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)",
  pages =     "299-307",
  year =      "2006"
%% Abstract:
%%  We consider deterministic dictionaries in the parallel disk model, 
%%  motivated by applications such as file systems. Our main results show 
%%  that if the number of disks is moderately large (at least logarithmic
%%  in the size of the universe from which keys come), performance similar
%%  to the expected performance of randomized dictionaries can be achieved. 
%%  Thus, we may avoid randomization by extending parallelism. We give 
%%  several algorithms with different performance trade-offs. One of our 
%%  main tools is a deterministic load balancing scheme based on expander 
%%  graphs, that may be of independent interest. 
%%  Our algorithms assume access to certain expander graphs ``for free''. 
%%  While current explicit constructions of expander graphs have
%%  suboptimal parameters, we show how to get near-optimal expanders for
%%  the case where the amount of data is polynomially related to the size 
%%  of internal memory.

  author =    "Mihai P{\v a}tra{\c s}cu and Mikkel Thorup",
  title =     "Time-Space Trade-Offs for Predecessor Search",
  booktitle = "Proc. 38th ACM Symposium on Theory of Computing (STOC)",
  pages =     "232-240",
  year =      "2006",
  note =      "See also arXiv:cs/0603043"
%% Abstract:
%%  We develop a new technique for proving cell-probe lower bounds for
%%  static data structures. Previous lower bounds used a reduction to
%%  communication games, which was known not to be tight by counting
%%  arguments. We give the first lower bound for an explicit problem which
%%  breaks this communication complexity barrier. In addition, our bounds
%%  give the first separation between polynomial and near linear
%%  space. Such a separation is inherently impossible by communication
%%  complexity.
%%  Using our lower bound technique and new upper bound constructions, we
%%  obtain tight bounds for searching predecessors among a static set of
%%  integers. Given a set $Y$ of $n$ integers of $\ell$ bits each, the goal
%%  is to efficiently find \func{predecessor}(x) = \( \max~\{ y \in Y \mid y
%%  \le x \} \). For this purpose, we represent $Y$ on a RAM with word
%%  length $w$ using $S \ge n\ell$ bits of space. Defining \( a = \lg
%%  \frac{S}{n} \), we show that the optimal search time is, up to constant
%%  factors:
%%  %
%%  \begin{equation*}
%%  \min \left\{ \begin{array}{l}
%%    \log_{w} n \\[1.5ex]
%%    \lg \frac{\ell - \lg n}{a} \\[1.5ex]
%%    \frac{\lg \frac{\ell}{a}}{\lg \left( \frac{a}{\lg n} 
%%      \,\cdot\, \lg \frac{\ell}{a} \right)} \\[2.5ex]
%%    \frac{\lg \frac{\ell}{a}}{\lg \left( \lg \frac{\ell}{a} 
%%      \textrm{\large~/} \lg\frac{\lg n}{a} \right)}
%%  \end{array} \right.
%%  \end{equation*}
%%  In external memory ($w > \ell$), it follows that the optimal strategy
%%  is to use either standard B-trees, or a RAM algorithm ignoring the
%%  larger block size. In the important case of $w = \ell = \gamma \lg
%%  n$, for $\gamma > 1$ (i.e.~polynomial universes), and near linear
%%  space (such as $S = n \cdot \lg^{O(1)} n$), the optimal search time is
%%  $\Theta(\lg \ell)$. Thus, our lower bound implies the surprising
%%  conclusion that van Emde Boas' classic data structure from [FOCS'75]
%%  is optimal in this case. Note that for space \( n^{1+\eps} \), a running
%%  time of $O(\lg \ell / \lg\lg \ell)$ was given by Beame and Fich
%%  [STOC'99].

  author =    "Erik D. Demaine and Friedhelm Meyer auf der Heide and Rasmus Pagh and Mihai P{\v a}tra{\c s}cu",
  title =     "De Dictionariis Dynamicis Pauco Spatio Utentibus ",
  booktitle = "Proc. 7th Latin American Theoretical Informatics (LATIN)",
  pages =     "349-361",
  year =      "2006",
  note =      "See also arXiv:cs/0512081"
%% Abstract:
%%  We develop dynamic dictionaries on the word RAM that use
%%  asymptotically optimal space, up to constant factors, subject to
%%  insertions and deletions, and subject to supporting perfect-hashing
%%  queries and/or membership queries, each operation in constant time
%%  with high probability.  When supporting only membership queries, we
%%  attain the optimal space bound of \( \Theta(n \lg \frac{u}{n}) \) bits,
%%  where $n$ and $u$ are the sizes of the dictionary and the universe,
%%  respectively.  Previous dictionaries either did not achieve this
%%  space bound or had time bounds that were only expected and
%%  amortized.  When supporting perfect-hashing queries, the optimal
%%  space bound depends on the range $\{1, 2, \dots, n+t\}$ of hashcodes
%%  allowed as output.  We prove that the optimal space bound is
%%  \( \Theta(n \lg \lg \frac{u}{n} + n \lg \frac{n}{t+1}) \) bits when
%%  supporting only perfect-hashing queries, and it is \( \Theta(n \lg
%%  \frac{u}{n} + n \lg \frac{n}{t+1}) \) bits when also supporting
%%  membership queries.  All upper bounds are new, as is the \( \Omega(n
%%  \lg \frac{n}{t+1}) \) lower bound.

  author =    "Micah Adler and Erik D. Demaine and Nicholas J.A. Harvey and Mihai P{\v a}tra{\c s}cu",
  title =     "Lower Bounds for Asymmetric Communication Channels and Distributed Source Coding",
  booktitle = "Proc. 17th ACM/SIAM Symposium on Discrete Algorithms (SODA)",
  pages =     "251-260",
  year =      "2006"
%% Abstract:
%%  We prove nearly tight lower bounds on the number of rounds of communication
%%  required by efficient protocols over asymmetric channels between
%%  a server (with high sending capacity) and one or more clients
%%  (with low sending capacity).  This scenario captures the common
%%  asymmetric communication bandwidth between broadband Internet providers
%%  and home users, as well as sensor networks where sensors (clients)
%%  have limited capacity because of the high power requirements for
%%  long-range transmissions.
%%  An efficient protocol in this setting
%%  communicates $n$ bits from each of the $k$ clients to
%%  the server, where the clients' bits are sampled from a joint distribution $D$
%%  that is known to the server but not the clients,
%%  with the clients sending only $O(H(D)+k)$
%%  bits total, where $H(D)$ is the entropy of distribution~$D$.
%%  In the single-client case, there are efficient protocols using $O(1)$ rounds
%%  in expectation and $O(\lg n)$ rounds in the worst case.
%%  We prove that this is essentially best possible: with probability
%%  $1/2^{O(t \lg t)}$, any efficient protocol can be forced to use $t$ rounds.
%%  In the multi-client case, there are efficient protocols using $O(\lg k)$
%%  rounds in expectation.
%%  We prove that this is essentially best possible: with probability 
%%  $\Omega(1)$, any efficient protocol can be forced to use 
%%  $\Omega(\lg k / \lg \lg k)$ rounds.
%%  Along the way, we develop new techniques of independent interest
%%  for proving lower bounds in communication complexity.

  author =    "Ilya Baran and Erik D. Demaine and Mihai P{\v a}tra{\c s}cu",
  title =     "Subquadratic Algorithms for {3SUM}",
  journal =   "Algorithmica",
  volume =    "50",
  number =    "4",
  pages =     "584-596",
  year =      "2008",
  note =      "See also WADS'05"
%% Abstract:
%%  We obtain subquadratic algorithms for 3SUM on integers and rationals
%%  in several models. On a standard word RAM with $w$-bit words, we
%%  obtain a running time of \( O(n^2 / \max\{ \frac{w}{\lg^2 w},
%%  \frac{\lg^2 n}{(\lg\lg n)^2} \}) \). In the circuit RAM with one
%%  nonstandard $AC^0$ operation, we obtain \( O(n^2 / \frac{w^2}{\lg^2
%%  w}) \). In external memory, we achieve $O(n^2 / (MB))$, even under the
%%  standard assumption of data indivisibility. Cache-obliviously, we
%%  obtain a running time of \( O(n^2 / \frac{MB}{\lg^2 M}) \). In all
%%  cases, our speedup is almost quadratic in the ``parallelism'' the
%%  model can afford, which may be the best possible.  Our algorithms
%%  are Las Vegas randomized; time bounds hold in expectation, and in
%%  most cases, with high probability.

  author =    "Mihai P{\v a}tra{\c s}cu and Corina Tarni\c{t}\v{a}",
  title =     "On Dynamic Bit-Probe Complexity",
  journal =   "Theoretical Computer Science",
  volume =    "380",
  pages =     "127-142",
  year =      "2007",
  note =      "See also ICALP'05"
%% Abstract:
%%  This work present several advances in the understanding of dynamic
%%  data structures in the bit-probe model: 
%%  %
%%  \begin{itemize}
%%    \item We improve the lower bound record for dynamic language
%%      membership problems to \( \Omega( (\frac{\lg n}{\lg\lg n})^2
%%      ) \). Surpassing $\Omega(\lg n)$ was listed as the first open
%%      problem in a survey by Miltersen. 
%%    \item We prove a bound of \( \Omega(\frac{\lg n}{\lg\lg\lg n}) \)  for
%%      maintaining partial sums in $\mathbb{Z}/2\mathbb{Z}$. Previously, 
%%      the known bounds were \( \Omega(\frac{\lg n}{\lg\lg n}) \) and $O(\lg n)$.
%%    \item We prove a surprising and tight upper bound of \( O(\frac{\lg
%%      n}{\lg\lg n}) \) for the greater-than problem, and several
%%      predecessor-type problems. We use this to obtain the same upper
%%      bound for dynamic word and prefix problems in group-free
%%      monoids.
%%  \end{itemize}
%%  % 
%%  We also obtain new lower bounds for the partial-sums problem in the
%%  cell-probe and external-memory models. Our lower bounds are based on a
%%  surprising improvement of the classic chronogram technique of Fredman
%%  and Saks [1989], which makes it possible to prove logarithmic lower
%%  bounds by this approach. Before the work of P\u{a}tra\c{s}cu and
%%  Demaine [2004], this was the only known technique for dynamic lower
%%  bounds, and surpassing \( \Omega( \frac{\lg n}{\lg\lg n} ) \) was a
%%  central open problem in cell-probe complexity.

  author =    "Christian Worm Mortensen and Rasmus Pagh and Mihai P{\v a}tra{\c s}cu",
  title =     "On Dynamic Range Reporting in One Dimension",
  booktitle = "Proc. 37th ACM Symposium on Theory of Computing (STOC)",
  pages =     "104-111",
  year =      "2005",
  note =      "See also arXiv:cs/0502032"
%% Abstract:
%%  We consider the problem of maintaining a dynamic set of integers and
%%  answering queries of the form: report a point (equivalently, all
%%  points) in a given interval. Range searching is a natural and
%%  fundamental variant of integer search, and can be solved using
%%  predecessor search. However, for a RAM with $w$-bit words, we show
%%  how to perform updates in $O(\lg w)$ time and answer queries in
%%  $O(\lg\lg w)$ time. The update time is identical to the van Emde
%%  Boas structure, but the query time is exponentially faster. Existing
%%  lower bounds show that achieving our query time for predecessor
%%  search requires doubly-exponentially slower updates. We present some
%%  arguments supporting the conjecture that our solution is optimal.
%%  Our solution is based on a new and interesting recursion idea which
%%  is ``more extreme'' that the van Emde Boas recursion. Whereas van
%%  Emde Boas uses a simple recursion (repeated halving) on each path in
%%  a trie, we use a nontrivial, van Emde Boas-like recursion on every
%%  such path. Despite this, our algorithm is quite clean when seen from
%%  the right angle. To achieve linear space for our data structure, we
%%  solve a problem which is of independent interest. We develop the
%%  first scheme for dynamic perfect hashing requiring sublinear
%%  space. This gives a dynamic Bloomier filter (a storage scheme for
%%  sparse vectors) which uses low space. We strengthen previous lower
%%  bounds to show that these results are optimal.

  author =    "Erik D. Demaine and Dion Harmon and John Iacono and Mihai P{\v a}tra{\c s}cu",
  title =     "Dynamic Optimality -- Almost",
  journal =   "SIAM Journal on Computing",
  volume =    "37",
  number =    "1",
  pages =     "240-251",
  year =      "2007",
  note =      "See also FOCS'04"
%% Abstract:
%%  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.

  author =    "Stelian Ciurea and Erik D. Demaine and Corina Tarni\c{t}\v{a} and Mihai P{\v a}tra{\c s}cu",
  title =     "Finding a Divisible Pair and a Good Wooden Fence",
  booktitle = "Proc. 3rd International Conference on Fun with Algorithms (FUN)",
  pages =     "206-219",
  year =      "2004"
%% Abstract:
%%  We consider two algorithmic problems arising in the lives of Yogi Bear
%%  and Ranger Smith. The first problem is the natural algorithmic version
%%  of a classic mathematical result: any $(n+1)$-subset of $\{1, \ldots,
%%  2n\}$ contains a pair of divisible numbers.  How do we actually find
%%  such a pair?  If the subset is given in the form of a bit vector, we
%%  give a RAM algorithm with an optimal running time of $O(n / \lg n)$.
%%  If the subset is accessible only through a membership oracle, we show
%%  a lower bound of \( \frac{4}{3} n - O(1) \) and an almost matching upper
%%  bound of \( \left(\frac{4}{3} + \frac{1}{24}\right) n + O(1) \) on the
%%  number of queries necessary in the worst case.
%%  The second problem we study is a geometric optimization problem where
%%  the objective amusingly influences the constraints.  Suppose you want
%%  to surround $n$ trees at given coordinates by a wooden fence.
%%  However, you have no external wood supply, and must obtain wood by
%%  chopping down some of the trees.  The goal is to cut down a minimum
%%  number of trees that can be built into a fence that surrounds the
%%  remaining trees. We obtain efficient polynomial-time algorithms for
%%  this problem.
%%  We also describe an unusual data-structural view of the Nim game,
%%  leading to an intriguing open problem.

  author =    "Corina Tarni\c{t}\v{a} and Mihai P{\v a}tra{\c s}cu",
  title =     "Computing Order Statistics in the {F}arey Sequence",
  booktitle = "Proc. 6th Algorithmic Number Theory Symposium (ANTS)",
  pages =     "358-366",
  year =      "2004"
%% Abstract:
%%  We study the problem of computing the $k$-th term of the Farey
%%  sequence of order $n$, for given $n$ and $k$. Several methods for
%%  generating the entire Farey sequence are known. However, these
%%  algorithms require at least quadratic time, since the Farey sequence
%%  has $\Theta(n^2)$ elements. For the problem of finding the $k$-th
%%  element, we obtain an algorithm that runs in time $O(n \lg n)$ and
%%  uses space \( O(\sqrt{n}) \). The same bounds hold for the problem of
%%  determining the rank in the Farey sequence of a given fraction. A more
%%  complicated solution can reduce the space to $O(n^{1/3} (\lg\lg
%%  n)^{2/3})$, and, for the problem of determining the rank of a
%%  fraction, reduce the time to $O(n)$. We also argue that an algorithm
%%  with running time $O(\polylog n)$ is unlikely to exist, since that
%%  would give a polynomial-time algorithm for integer factorization.

  author =    "Mihai P{\v a}tra{\c s}cu and Erik D. Demaine",
  title =     "Logarithmic Lower Bounds in the Cell-Probe Model",
  journal =   "SIAM Journal on Computing",
  volume =    "35",
  number =    "4",
  pages =     "932-963",
  year =      "2006",
  note =      "See also STOC'04, SODA'04"
%% Abstract:
%%  We develop a new technique for proving cell-probe lower bounds on
%%  dynamic data structures.  This technique enables us to prove an
%%  amortized randomized $\Omega(\lg n)$ lower bound per operation for
%%  several data structural problems on $n$ elements, including partial
%%  sums, dynamic connectivity among disjoint paths (or a forest or a
%%  graph), and several other dynamic graph problems (by simple
%%  reductions).  Such a lower bound breaks a long-standing barrier of
%%  $\Omega(\lg n / \lg\lg n)$ for any dynamic language membership
%%  problem.  It also establishes the optimality of several existing
%%  data structures, such as Sleator and Tarjan's dynamic trees.  We
%%  also prove the first $\Omega(\log_B n)$ lower bound in the
%%  external-memory model without assumptions on the data structure
%%  (such as the comparison model).  Our lower bounds also give a
%%  query-update trade-off curve matched, e.g., by several data
%%  structures for dynamic connectivity in graphs.  We also prove
%%  matching upper and lower bounds for partial sums when parameterized
%%  by the word size and the maximum additive change in an update.

  author =    "Erik D. Demaine and Thouis Jones and Mihai P{\v a}tra{\c s}cu",
  title =     "Interpolation Search for Non-Independent Data",
  booktitle = "Proc. 15th ACM/SIAM Symposium on Discrete Algorithms (SODA)",
  pages =     "522-523",
  year =      "2004"
%% Abstract:
%%  We define a deterministic metric of ``well-behaved data'' that enables
%%  searching along the lines of interpolation search. Specifically, define 
%%  $\Delta$ to be the ratio of distances between the farthest and nearest 
%%  pair of adjacent elements. We develop a data structure that stores a 
%%  dynamic set of $n$ integers subject to insertions, deletions, and 
%%  predecessor/successor queries in $O(\lg \Delta)$ time per operation.
%%  This result generalizes interpolation search and interpolation search trees
%%  smoothly to nonrandom (in particular, non-independent) input data.
%%  In this sense, we capture the amount of ``pseudorandomness''
%%  required for effective interpolation search.

  author =    "Mihai P{\v a}tra{\c s}cu and Erik D. Demaine",
  title =     "Tight Bounds for the Partial-Sums Problem",
  booktitle = "Proc. 15th ACM/SIAM Symposium on Discrete Algorithms (SODA)",
  pages =     "20-29",
  year =      "2004"
%% Abstract:
%%  We close the gaps between known lower and upper bounds for the
%%  online partial-sums problem in the RAM and group models of
%%  computation.  If elements are chosen from an abstract group, we prove
%%  an $\Omega(\lg n)$ lower bound on the number of algebraic operations
%%  that must be performed, matching a well-known upper bound. In the RAM
%%  model with $b$-bit memory registers, we consider the well-studied case
%%  when the elements of the array can be changed additively by
%%  $\delta$-bit integers. We give a RAM algorithm that achieves a running time 
%%  of $\Theta(1 + \lg n / \lg(b / \delta))$ and prove a matching lower bound 
%%  in the cell-probe model. Our lower bound is for the amortized complexity, 
%%  and makes minimal assumptions about the relations between $n$, $b$, and $\delta$.
%%  The best previous lower bound was $\Omega(\lg n / (\lg \lg n + \lg b))$,
%%  and the best previous upper bound matched only in the special case
%%  $b = \Theta(\lg n)$ and $\delta = O(\lg \lg n)$.