Mihai Patrascu (home)

Mihai Pătraşcu: Publications

You can also see the DBLP listing. Click on a title to see the abstract.

[38]   Towards Polynomial Lower Bounds for Dynamic Problems   Mihai Pătraşcu Submitted. Unavailable due to release procedures; email for a copy. We consider a number of dynamic problems with no known poly-logarithmic upper bounds, and show that they require nΩ(1) time per operation, unless 3SUM has strongly subquadratic algorithms. Our result is modular: 1. We describe a carefully-chosen dynamic version of set disjointness (the multiphase problem), and conjecture that it requires nΩ(1) time per operation. All our lower bounds follow by easy reduction. 2. We reduce 3SUM to the multiphase problem. Ours is the first nonalgebraic reduction from 3SUM, and allows 3SUM-hardness results for combinatorial problems. For instance, it implies hardness of reporting all triangles in a graph. 3. It is possible that an unconditional lower bound for the multiphase problem can be established via a number-on-forehead communication game.
[37]   The Power of Simple Tabulation-Based Hashing   Mihai Pătraşcu and Mikkel Thorup Submitted. Unavailable due to release procedures; email for a copy. We show that the simplest possible tabulation hashing provides as good load balancing as 5-independent hash functions, even though it is only 3-independent. This implies that simple tabulation can be used with linear probing, replacing more complicated schemes which guaranteed 5-independence. Our scheme suggests an extremely efficient pseudorandom generator, which has guaranteed 4-th moment bounds, and thus can be used in applications like quicksort. The generator also has strong min-wise independent properties, making it useful in other applications.
[36]   An Alternative to Arithmetic Coding with Local Decodability   Yevgeniy Dodis, Mihai Pătraşcu, and Mikkel Thorup Submitted. Unavailable due to release procedures; email for a copy. We describe a simple, but powerful local encoding technique, implying two surprising results: 1. We show how to represent a vector of n values from Σ using ⌈nlog 2Σ⌉ 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 nlog 2Σ + n∕lg O(1)n bits for constant access. 2. Given a stream of n bits arriving online (for any n, not known in advance), we can output a prefix-free encoding that uses n + log 2n + 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ödin 2005] on the hardness of online prefix-free encodings.
[35]   Faster Primal-Dual Algorithms for the Economic Lot-Sizing Problem   Mihai Pătraşcu and Dan Stratila In preparation. Talk in 20th International Symposium of Mathematical Programming (ISMP 2009). 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(nlg 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(nlg lg n).
[34]   Cell-Probe Lower Bounds for Succinct Partial Sums   Mihai Pătraşcu and Emanuele Viola 21st ACM/SIAM Symposium on Discrete Algorithms (SODA 2010). The partial sums problem in succinct data structures asks to preprocess an array A[1..n] of bits into a data structure using as close to n bits as possible, and answer queries of the form rank(k) = ∑ i=1kA[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∕wO(t) bits. This redundancy/probe trade-off is essentially optimal: Patrascu [FOCS’08] showed how to achieve n + n∕(w∕t)Ω(t) bits. We also extend our lower bound to the closely related select queries, and to the case of sparse arrays.
[33]   On the Possibility of Faster SAT Algorithms   Mihai Pătraşcu and Ryan Williams 21st ACM/SIAM Symposium on Discrete Algorithms (SODA 2010). 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: an O(nk-ε) algorithm for k-Dominating Set, for any k ≥ 3, a (computationally efficient) protocol for 3-party set disjointness with o(m) bits of communication, an no(d) algorithm for d-SUM, an O(n2-ε) algorithm for 2-SAT with m = n1+o(1) clauses, where two clauses may have unrestricted length, and an O((n+m)k-ε) algorithm for HornSat with k unrestricted length clauses. One may interpret our reductions as new attacks on the complexity of SAT, or sharp lower bounds conditional on exponential hardness of SAT.
[32]   Counting Inversions, Offline Orthogonal Range Counting, and Related Problems   Timothy Chan and Mihai Pătraşcu 21st ACM/SIAM Symposium on Discrete Algorithms (SODA 2010). We give an O(n)-time algorithm for counting the number of inversions in a permutation on n elements. This improves a long-standing previous bound of O(nlg 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 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 in d dimensions, an algorithm to answer n offline orthogonal range counting queries in time O(nlg d-2+1∕dn); an improved construction time for online data structures for orthogonal range counting; an improved update time for the partial sums problem; faster Word RAM algorithms for finding the maximum depth in an arrangement of axis-aligned rectangles, and for the slope selection problem. As a bonus, we also give a simple (1 + ε)-approximation algorithm for counting inversions that runs in linear time, improving the previous O(nlg lg n) bound by Andersson and Petersson.
[31]   Lower Bounds for Edit Distance and Product Metrics via Poincaré-Type Inequalities   Alex Andoni, T.S. Jayram, and Mihai Pătraşcu 21st ACM/SIAM Symposium on Discrete Algorithms (SODA 2010). 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 ℓ∞d(X) requires Ω(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é inequalities and suggests an intimate connection between non-embeddability, sketching and communication complexity.
[30]   The Geometry of Binary Search Trees   Erik Demaine, Dion Harmon, John Iacono, Daniel Kane, and Mihai Pătraşcu 20th ACM/SIAM Symposium on Discrete Algorithms (SODA 2009). 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: A surprisingly clean restatement in geometric terms of many results and conjectures relating to BSTs and dynamic optimality. A new lower bound for searching in the BST model, which subsumes the previous two known bounds of Wilber [FOCS’86]. 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.
[29]   Unifying the Landscape of Cell-Probe Lower Bounds   Mihai Pătraşcu SIAM Journal on Computing (SICOMP), submitted. Special issue. 49th IEEE Symposium on Foundations of Computer Science (FOCS 2008). 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: high-dimensional problems, where the goal is to show large space lower bounds. constant-dimensional geometric problems, where the goal is to bound the query time for space O(npolylogn). 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.) Our reductions also imply the following new results: an Ω(lg n∕lg lg n) bound for 4-dimensional range reporting, given space O(npolylogn). 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. a tight space lower bound for the partial match problem, for constant query time. the first lower bound for reachability oracles. In the process, we prove optimal randomized lower bounds for lopsided set disjointness.
[28]   Succincter   Mihai Pătraşcu 49th IEEE Symposium on Foundations of Computer Science (FOCS 2008). Best Student Paper (the Machtey Award) We can represent an array of n values from {0,1,2} using bits (arithmetic coding), but then we cannot retrieve a single element efficiently. Instead, we can encode every block of t elements using 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.
[27]   Hardness of Nearest Neighbor under L-infinity   Alex Andoni, Dorian Croitoru, and Mihai Pătraşcu 49th IEEE Symposium on Foundations of Computer Science (FOCS 2008). Parental advisory:  The conference version contains some typos and some less than coherent explanations. This chapter of my PhD thesis contains a polished version of the material. Recent years have seen a significant increase in our understanding of high-dimensional nearest neighbor search (NNS) for distances like the ℓ1 and ℓ2 norms. By contrast, our understanding of the ℓ∞ 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ρ), for any ρ > 1, which achieves approximation O(log ρ log d) for NNS in the d-dimensional ℓ∞ 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 ℓ∞, which proves that this space/approximation trade-off is optimal for decision trees and for data structures with constant cell-probe complexity.
[26]   Dynamic Connectivity: Connecting to Networks and Geometry   Timothy Chan, Mihai Pătraşcu, and Liam Roditty 49th IEEE Symposium on Foundations of Computer Science (FOCS 2008). Full version: arXiv:0808.1128. 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: 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 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 amortized time, where m denotes the number of edges in the graph. This greatly improves over the previous result [Chan, STOC’02], which required fast matrix multiplication and had an update time of O(m0.94). The new data structure is also simpler. 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, , for these special cases. Moreover, we show how to obtain sublinear update bounds for virtually all families of geometric objects which allow sublinear-time range queries. In particular, we obtain the first sublinear update time for arbitrary 2D line segments: ; for d-dimensional simplices: ; and for d-dimensional balls: .
[25]   Order Statistics in the Farey Sequences in Sublinear Time and Counting Primitive Lattice Points in Polygons   Jakub Pawlewicz and Mihai Pătraşcu Algorithmica, to appear. Based on a paper by Pawlewicz in ESA'07, and my subsequent: arXiv:0708.0080. 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(n2∕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 D6∕7, where D is the diameter of the polygon.
[24]   Tight Lower Bounds for Selection in Randomly Ordered Streams   Amit Chakrabarti, T.S. Jayram, and Mihai Pătraşcu 19th ACM/SIAM Symposium on Discrete Algorithms (SODA 2008). We show that any algorithm computing the median of a stream presented in random order, using O(polylogn) space, requires an optimal Ω(log log n) passes, resolving an open question from the seminal paper on streaming by Munro and Paterson, from FOCS 1978.
[23]   Planning for Fast Connectivity Updates   Mihai Pătraşcu and Mikkel Thorup 48th IEEE Symposium on Foundations of Computer Science (FOCS 2007). 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(dpolylogn) 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.
[22]   Radix Sorting With No Extra Space   Gianni Franceschini, S. Muthukrishnan, and Mihai Pătraşcu 15th European Symposium on Algorithms (ESA 2007). Full version: arXiv:0706.4107. It is well known that n integers in the range [1,nc] 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 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.
[21]   Lower Bounds for 2-Dimensional Range Counting   Mihai Pătraşcu 39th ACM Symposium on Theory of Computing (STOC 2007). 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: In the group and cell-probe models, a static data structure of size nlg O(1)n requires Ω(lg n∕lg lg n) time per query. This is an exponential improvement over previous bounds, and matches known upper bounds. In the group model, a dynamic data structure takes time per operation. This is close to the O(lg 2n) upper bound, whereas the previous lower bound was Ω(lg n). 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].
[20]   Transdichotomous Results in Computational Geometry, II: Offline Search   Timothy Chan and Mihai Pătraşcu Journal version in preparation. Conference version: Sorry, abstract not available.
»	Voronoi Diagrams in n•2O(√lglg n) Time   39th ACM Symposium on Theory of Computing (STOC 2007). 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 Voronoi diagram of n points in the plane can be constructed in (randomized) time . Similar bounds hold for numerous other geometric problems, such as three-dimensional convex hulls, planar Euclidean minimum spanning trees, line segment intersection, and triangulation of non-simple polygons. In FOCS’06, we developed a data structure for online point location, which implied a bound of for Voronoi diagrams and the other problems. Our current bounds are dramatically better, and a convincing improvement over the classic O(nlg 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).
[19]   Tight Bounds for Dynamic Convex Hull Queries (Again)   Erik Demaine and Mihai Pătraşcu 23rd ACM Symposium on Computational Geometry (SoCG 2007). 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, , 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.
[18]   Non-Adaptive Fault Diagnosis for All-Optical Networks via Combinatorial Group Testing on Graphs   Nick Harvey, Mihai Pătraşcu, Yonggang Wen, Sergey Yekhanin, and Vincent Chan 26th IEEE Conference on Computer Communications (INFOCOM 2007). 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.
[17]   Randomization Does Not Help Searching Predecessors   Mihai Pătraşcu and Mikkel Thorup 18th ACM/SIAM Symposium on Discrete Algorithms (SODA 2007). 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 ℓ-bit word. Our trade-off lower bounds are tight for any combination of parameters. For small space, i.e. n1+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 ℓ) 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 ℓ∕lg lg ℓ) using quadratic space. We also show a tight Ω(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.
[16]   Transdichotomous Results in Computational Geometry, I: Point Location in Sublogarithmic Time   Timothy Chan and Mihai Pătraşcu SIAM Journal on Computing (SICOMP), to appear. Special issue. Based on two independent papers by each author, achieving similar results. Given a planar subdivision whose coordinates are integers bounded by U ≤ 2w, we present a linear-space data structure that can answer point location queries in time on the unit-cost RAM with word size w. This is the first result to beat the standard Θ(lg n) bound for infinite precision models. As a consequence, we obtain the first o(nlg 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).
»	Planar Point Location in Sublogarithmic Time   Mihai Pătraşcu 47th IEEE Symposium on Foundations of Computer Science (FOCS 2006). We consider the static planar point location problem in an arbitrary polygonal subdivision given by n segments. We assume points come from the [u]2 grid, and consider algorithms for the RAM with words of O(lg u) bits. We give the first solution to the problem which can surpass the traditional query time of O(lg n). Specifically, we can obtain a query time of . Though computational geometry on a grid has been investigated for a long time (including for this problem), it is generally not known how to make good use of a bounded universe in problems of such nonorthogonal flavor. Our result shows this limitation can be surpassed, at least for planar point location. A result by Timothy Chan, appearing independently in FOCS’06, also achieves sublogarithmic query times. Combining the two results, we obtain the following bound. For any S ≥ 2, the exists a data structure using space O(n ⋅ S) which supports queries in time:
[15]   Higher Lower Bounds for Near-Neighbor and Further Rich Problems   Mihai Pătraşcu and Mikkel Thorup SIAM Journal on Computing (SICOMP), to appear. Special issue. 47th IEEE Symposium on Foundations of Computer Science (FOCS 2006). 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 Ω(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 nlg O(1)n, we now obtain bounds of Ω(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 = Θ(lg n), we have the first superconstant lower bound. From a complexity theoretic perspective, our lower bounds are the highest known for any static data structure problem, significantly improving on previous records.
[14]   On the Optimality of the Dimensionality Reduction Method   Alex Andoni, Piotr Indyk, and Mihai Pătraşcu 47th IEEE Symposium on Foundations of Computer Science (FOCS 2006). We investigate the optimality of (1 + ε)-approximation algorithms obtained via the dimensionality reduction method. We show that: Any data structure for the (1 + ε)-approximate nearest neighbor problem in Hamming space, which uses constant number of probes to answer each query, must use space. Any algorithm for the (1+ε)-approximate closest substring problem must run in time exponential in 1∕ε2-γ for any γ > 0 (unless 3SAT can be solved in sub-exponential time) Both lower bounds are (essentially) tight.
[13]   Deterministic Load Balancing and Dictionaries in the Parallel Disk Model   Mette Berger, Esben Rune Hansen, Rasmus Pagh, Mihai Pătraşcu, Milan Ružić, and Peter Tiedemann 18th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2006). 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.
[12]   Time-Space Trade-Offs for Predecessor Search   Mihai Pătraşcu and Mikkel Thorup 38th ACM Symposium on Theory of Computing (STOC 2006). Full version (very preliminary): arXiv:cs/0603043. 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 ℓ bits each, the goal is to efficiently find predecessor(x) = . For this purpose, we represent Y on a RAM with word length w using S ≥ nℓ bits of space. Defining , we show that the optimal search time is, up to constant factors: In external memory (w > ℓ), 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 = ℓ = γ lg n, for γ > 1 (i.e. polynomial universes), and near linear space (such as S = n ⋅ lg O(1)n), the optimal search time is Θ(lg ℓ). 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 , a running time of O(lg ℓ∕lg lg ℓ) was given by Beame and Fich [STOC’99].
[11]   De Dictionariis Dynamicis Pauco Spatio Utentibus   (On Dynamic Dictionaries Using Little Space)   Erik Demaine, Friedhelm Meyer auf der Heide, Rasmus Pagh, and Mihai Pătraşcu 7th Latin American Theoretical Informatics (LATIN 2006). Full version (rather unpolished): arXiv:0512081. 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 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,…,n + t} of hashcodes allowed as output. We prove that the optimal space bound is bits when supporting only perfect-hashing queries, and it is bits when also supporting membership queries. All upper bounds are new, as is the lower bound.
[10]   Lower Bounds for Asymmetric Communication Channels and Distributed Source Coding   Micah Adler, Erik Demaine, Nick Harvey, and Mihai Pătraşcu 17th ACM/SIAM Symposium on Discrete Algorithms (SODA 2006). 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∕2O(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 Ω(1), any efficient protocol can be forced to use Ω(lg k∕lg lg k) rounds. Along the way, we develop new techniques of independent interest for proving lower bounds in communication complexity.
[9]   Subquadratic Algorithms for 3SUM   Ilya Baran, Erik Demaine, and Mihai Pătraşcu Algorithmica, vol. 50(4), 2008. Special issue. 9th Workshop on Algorithms and Data Structures (WADS 2005). 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 . In the circuit RAM with one nonstandard AC0 operation, we obtain . In external memory, we achieve O(n2∕(MB)), even under the standard assumption of data indivisibility. Cache-obliviously, we obtain a running time of . 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.
[8]   On Dynamic Bit-Probe Complexity   Mihai Pătraşcu and Corina Tarniţă Theoretical Computer Science (TCS), vol. 380, 2007. Special issue. 32nd International Colloquium on Automata, Languages and Programming (ICALP 2005). Best Student Paper Award (Track A). This work present several advances in the understanding of dynamic data structures in the bit-probe model: We improve the lower bound record for dynamic language membership problems to . Surpassing Ω(lg n) was listed as the first open problem in a survey by Miltersen. We prove a bound of for maintaining partial sums in ℤ∕2ℤ. Previously, the known bounds were and O(lg n). We prove a surprising and tight upper bound of 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. 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ătraşcu and Demaine [2004], this was the only known technique for dynamic lower bounds, and surpassing was a central open problem in cell-probe complexity.
[7]   On Dynamic Range Reporting in One Dimension   Christian Worm Mortensen, Rasmus Pagh, and Mihai Pătraşcu 37th ACM Symposium on Theory of Computing (STOC 2005). Full version (unpolished; conference version recommended): arXiv:0502032. 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.
[6]   Dynamic Optimality -- Almost   Erik Demaine, Dion Harmon, John Iacono, and Mihai Pătraşcu SIAM Journal on Computing (SICOMP), vol. 37(1), 2007. Special issue. 45th IEEE Symposium on Foundations of Computer Science (FOCS 2004). 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.
[5]   Finding a Divisible Pair and a Good Wooden Fence   Stelian Ciurea, Erik Demaine, Corina Tarniţă, and Mihai Pătraşcu 3rd International Conference on Fun with Algorithms (FUN 2004). The divisible-pair problem was covered in a poster presentation at ANTS'04, and an invited 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,…,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 and an almost matching upper bound of 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.
»	Finding a Divisible Pair   ACM SIGSAM Bulletin, vol. 38(3), 2004. This is superseded by a follow-up paper of Adrian Dumitrescu and Guangwu Xu, which also corrects a technical error in our upper bound. Sorry, abstract not available.
[4]   Computing Order Statistics in the Farey Sequence   Corina Tarniţă and Mihai Pătraşcu 6th Algorithmic Number Theory Symposium (ANTS 2004). This is superseded by a more recent paper. 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 Θ(n2) elements. For the problem of finding the k-th element, we obtain an algorithm that runs in time O(nlg n) and uses space . 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(n1∕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(polylogn) is unlikely to exist, since that would give a polynomial-time algorithm for integer factorization.
[3]   Logarithmic Lower Bounds in the Cell-Probe Model   Mihai Pătraşcu and Erik Demaine SIAM Journal on Computing (SICOMP), vol. 35(4), 2006. Special issue. This chapter of my PhD thesis contains a gentler and cleaner exposition of the technique. This journal version is a merging of [1] and: We develop a new technique for proving cell-probe lower bounds on dynamic data structures. This technique enables us to prove an amortized randomized Ω(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 Ω(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 Ω(log Bn) 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.
»	Lower Bounds for Dynamic Connectivity   36th ACM Symposium on Theory of Computing (STOC 2004). We prove an Ω(lg n) cell-probe lower bound on maintaining connectivity in dynamic graphs, as well as a more general trade-off between updates and queries. Our bound holds even if the graph is formed by disjoint paths, and thus also applies to trees and plane graphs. The bound is known to be tight for these restricted cases, proving optimality of these data structures (e.g., Sleator and Tarjan’s dynamic trees). Our trade-off is known to be tight for trees, and the best two data structures for dynamic connectivity in general graphs are points on our trade-off curve. In this sense these two data structures are optimal, and this tightness serves as strong evidence that our lower bounds are the best possible. From a more theoretical perspective, our result is the first logarithmic cell-probe lower bound for any problem in the natural class of dynamic language membership problems, breaking the long standing record of Ω(lg n∕lg lg n). In this sense, our result is the first data-structure lower bound that is “truly” logarithmic, i.e., logarithmic in the problem size counted in bits. Obtaining such a bound is listed as one of three major challenges for future research by Miltersen [1999] (the other two remain unsolved). Our techniques form a general framework for proving cell-probe lower bounds on dynamic data structures. We show how our framework also applies to the partial-sums problem to obtain a nearly complete understanding of the problem in cell-probe and algebraic models, solving several previously posed open problems.
[2]   Interpolation Search for Non-Independent Data   Erik Demaine, Thouis "Ray" Jones, and Mihai Pătraşcu 15th ACM/SIAM Symposium on Discrete Algorithms (SODA 2004). Errata: There is an error in Lemma 2.1, regarding the behavior on the uniform distribution. The behavior as stated is correct, but the justification is not. We define a deterministic metric of “well-behaved data” that enables searching along the lines of interpolation search. Specifically, define Δ 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 Δ) 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.
[1]   Tight Bounds for the Partial-Sums Problem   15th ACM/SIAM Symposium on Discrete Algorithms (SODA 2004). Invited to special issue of ACM Transactions on Algorithms (declined). Merged with [3] for the journal version. 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 Ω(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 δ-bit integers. We give a RAM algorithm that achieves a running time of Θ(1 + lg n∕lg(b∕δ)) 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 δ. The best previous lower bound was Ω(lg n∕(lg lg n + lg b)), and the best previous upper bound matched only in the special case b = Θ(lg n) and δ = O(lg lg n).