BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Mihai Patrascu

Mihai Patrascu appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Data Structures and AlgorithmsComputational GeometryComputational Complexitymath.GNmath.GRmath.NT

Catalog footprint

What is connected

9works
6topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

9 published item(s)

preprint2014arXiv

Dynamic Integer Sets with Optimal Rank, Select, and Predecessor Search

We present a data structure representing a dynamic set S of w-bit integers on a w-bit word RAM. With |S|=n and w > log n and space O(n), we support the following standard operations in O(log n / log w) time: - insert(x) sets S = S + {x}. - delete(x) sets S = S - {x}. - predecessor(x) returns max{y in S | y< x}. - successor(x) returns min{y in S | y >= x}. - rank(x) returns #{y in S | y< x}. - select(i) returns y in S with rank(y)=i, if any. Our O(log n/log w) bound is optimal for dynamic rank and select, matching a lower bound of Fredman and Saks [STOC'89]. When the word length is large, our time bound is also optimal for dynamic predecessor, matching a static lower bound of Beame and Fich [STOC'99] whenever log n/log w=O(log w/loglog w). Technically, the most interesting aspect of our data structure is that it supports all the above operations in constant time for sets of size n=w^{O(1)}. This resolves a main open problem of Ajtai, Komlos, and Fredman [FOCS'83]. Ajtai et al. presented such a data structure in Yao's abstract cell-probe model with w-bit cells/words, but pointed out that the functions used could not be implemented. As a partial solution to the problem, Fredman and Willard [STOC'90] introduced a fusion node that could handle queries in constant time, but used polynomial time on the updates. We call our small set data structure a dynamic fusion node as it does both queries and updates in constant time.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Picture-Hanging Puzzles

We show how to hang a picture by wrapping rope around n nails, making a polynomial number of twists, such that the picture falls whenever any k out of the n nails get removed, and the picture remains hanging when fewer than k nails get removed. This construction makes for some fun mathematical magic performances. More generally, we characterize the possible Boolean functions characterizing when the picture falls in terms of which nails get removed as all monotone Boolean functions. This construction requires an exponential number of twists in the worst case, but exponential complexity is almost always necessary for general functions.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Necklaces, Convolutions, and X+Y

We give subquadratic algorithms that, given two necklaces each with n beads at arbitrary positions, compute the optimal rotation of the necklaces to best align the beads. Here alignment is measured according to the p norm of the vector of distances between pairs of beads from opposite necklaces in the best perfect matching. We show surprisingly different results for p = 1, p even, and p = \infty. For p even, we reduce the problem to standard convolution, while for p = \infty and p = 1, we reduce the problem to (min, +) convolution and (median, +) convolution. Then we solve the latter two convolution problems in subquadratic time, which are interesting results in their own right. These results shed some light on the classic sorting X + Y problem, because the convolutions can be viewed as computing order statistics on the antidiagonals of the X + Y matrix. All of our algorithms run in o(n^2) time, whereas the obvious algorithms for these problems run in Θ(n^2) time.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Don't Rush into a Union: Take Time to Find Your Roots

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 union-find problem: InsertEdge(s,t) can be implemented by Union(Find(s), Find(t)). This gives worst-case time t_u = t_q = O(lg n / lglg n) and amortized t_u = t_q = O(alpha(n)). By contrast, we show that if t_u = o(lg n / lglg n), the query time explodes to t_q >= 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 * poly(lglg n)) upper bound.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Orthogonal Range Searching on the RAM, Revisited

We present several 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 for points in rank space: ** We present two data structures for 2-d orthogonal range emptiness. The first achieves O(n lglg n) space and O(lglg n) query time. This improves the previous results by Alstrup, Brodal, and Rauhe(FOCS'00), with O(n lg^eps n) space and O(lglg n) query time, or with O(nlglg 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/lglg n) time. ** For 3-d orthogonal range reporting, we obtain space O(n lg^{1+eps} n) and query time O(lglg n + k), for any constant eps>0. This improves previous results by Afshani (ESA'08), Karpinski and Nekrich (COCOON'09), and Chan (SODA'11), with O(n lg^3 n) space and O(lglg n + k) query time, or with O(n lg^{1+eps} n) space and O(lg^2 lg n + k) query time. This implies improved bounds for orthogonal range reporting in all constant dimensions above 3. ** We give a randomized algorithm for 4-d offline dominance range reporting/emptiness with running time O(n lg n + k). This resolves two open problems from Preparata and Shamos' seminal book: **** given n axis-aligned rectangles in the plane, we can report all k enclosure pairs in O(n lg n + k) expected time. The best known result was an O([n lg n + k] lglg n) algorithm from SoCG'95 by Gupta, Janardan, Smid, and Dasgupta. **** given n points in 4-d, we can find all maximal points in O(n lg n) expected time. The best previous result was an O(n lg n lglg n) algorithm due to Gabow, Bentley, and Tarjan (STOC'84). This implies record time bounds for the maxima problem in all constant dimensions above 4.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

The Power of Simple Tabulation Hashing

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, ..., T_c mapping characters to random hash codes. A key x=(x_1, ..., x_q) is hashed to T_1[x_1] xor ... xor T_c[x_c]. 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.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Transdichotomous Results in Computational Geometry, II: Offline Search

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 2^O(sqrt{lglg 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 online point location, which implied a bound of O(n lg n/lglg n) for three-dimensional convex hulls 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).

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Unifying the Landscape of Cell-Probe Lower Bounds

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(n polylog n). * 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 lglg n factor.) Our reductions also imply the following new results: * an Omega(lg n / lglg n) bound for 4-dimensional range reporting, given space O(n polylog n). This is quite timely, since a recent result solved 3D reporting in O(lglg n) 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.

0 citations0 reviewsNo code linkedOpen access