Mihai Patrascu

According to our database1, Mihai Patrascu authored at least 61 papers between 2004 and 2016.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2016
Predecessor Search.
Encyclopedia of Algorithms, 2016

Lower Bounds for Dynamic Connectivity.
Encyclopedia of Algorithms, 2016

On the k-Independence Required by Linear Probing and Minwise Independence.
ACM Trans. Algorithms, 2016

2015
Finding the Median (Obliviously) with Bounded Space.
Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2014
Distance Oracles beyond the Thorup-Zwick Bound.
SIAM J. Comput., 2014

Picture-Hanging Puzzles.
Theory Comput. Syst., 2014

Necklaces, Convolutions, and X+Y.
Algorithmica, 2014

Dynamic Integer Sets with Optimal Rank, Select, and Predecessor Search.
Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013
Twisted Tabulation Hashing.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

2012
The Power of Simple Tabulation Hashing.
J. ACM, 2012

Using hashing to solve the dictionary problem.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

A New Infinity of Distance Oracles for Sparse Graphs.
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

2011
Unifying the Landscape of Cell-Probe Lower Bounds.
SIAM J. Comput., 2011

Dynamic Connectivity: Connecting to Networks and Geometry.
SIAM J. Comput., 2011

Using Hashing to Solve the Dictionary Problem (In External Memory)
CoRR, 2011

Don't rush into a union: take time to find your roots.
Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Orthogonal range searching on the RAM, revisited.
Proceedings of the 27th ACM Symposium on Computational Geometry, 2011

2010
Transdichotomous Results in Computational Geometry, II: Offline Search
CoRR, 2010

Towards polynomial lower bounds for dynamic problems.
Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Changing base without losing space.
Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

On the Possibility of Faster SAT Algorithms.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Cell-Probe Lower Bounds for Succinct Partial Sums.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Counting Inversions, Offline Orthogonal Range Counting, and Related Problems.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Lower Bounds for Edit Distance and Product Metrics via Poincaré-Type Inequalities.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

2009
Higher Lower Bounds for Near-Neighbor and Further Rich Problems.
SIAM J. Comput., 2009

Transdichotomous Results in Computational Geometry, I: Point Location in Sublogarithmic Time.
SIAM J. Comput., 2009

A Lower Bound for Succinct Rank Queries
CoRR, 2009

Order Statistics in the Farey Sequences in Sublinear Time and Counting Primitive Lattice Points in Polygons.
Algorithmica, 2009

The geometry of binary search trees.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

2008
Predecessor Search.
Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Lower Bounds for Dynamic Connectivity.
Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Lower bound techniques for data structures.
PhD thesis, 2008

Subquadratic Algorithms for 3SUM.
Algorithmica, 2008

Tight lower bounds for selection in randomly ordered streams.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Corrigendum to "efficient similarity search and classification via rank aggregation" by Ronald Fagin, Ravi Kumar and D. Sivakumar (proc. SIGMOD'03).
Proceedings of the ACM SIGMOD International Conference on Management of Data, 2008

(Data) STRUCTURES.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

Succincter.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

Hardness of Nearest Neighbor under L-infinity.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007
On dynamic bit-probe complexity.
Theor. Comput. Sci., 2007

Dynamic Optimality - Almost.
SIAM J. Comput., 2007

Lower bounds for 2-dimensional range counting.
Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

Voronoi diagrams in n·2osqrt(lg lg n) time.
Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

Randomization does not help searching predecessors.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Non-Adaptive Fault Diagnosis for All-Optical Networks via Combinatorial Group Testing on Graphs.
Proceedings of the INFOCOM 2007. 26th IEEE International Conference on Computer Communications, 2007

Planning for Fast Connectivity Updates.
Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

Radix Sorting with No Extra Space.
Proceedings of the Algorithms, 2007

Tight bounds for dynamic convex hull queries (again).
Proceedings of the 23rd ACM Symposium on Computational Geometry, Gyeongju, 2007

2006
Logarithmic Lower Bounds in the Cell-Probe Model.
SIAM J. Comput., 2006

Time-space trade-offs for predecessor search.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Deterministic load balancing and dictionaries in the parallel disk model.
Proceedings of the SPAA 2006: Proceedings of the 18th Annual ACM Symposium on Parallelism in Algorithms and Architectures, Cambridge, Massachusetts, USA, July 30, 2006

Lower bounds for asymmetric communication channels and distributed source coding.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

De Dictionariis Dynamicis Pauco Spatio Utentibus (lat. On Dynamic Dictionaries Using Little Space).
Proceedings of the LATIN 2006: Theoretical Informatics, 2006

Planar Point Location in Sublogarithmic Time.
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

On the Optimality of the Dimensionality Reduction Method.
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

2005
De Dictionariis Dynamicis Pauco Spatio Utentibus
CoRR, 2005

On dynamic range reporting in one dimension.
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Stick-slip Actuation of Electrostatic Stepper Micropositioners for Data Storage - the µWalker.
Proceedings of the 2005 International Conference on MEMS, 2005

2004
Lower bounds for dynamic connectivity.
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Tight bounds for the partial-sums problem.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Interpolation search for non-independent data.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Computing Order Statistics in the Farey Sequence.
Proceedings of the Algorithmic Number Theory, 6th International Symposium, 2004


  Loading...