Mihai Patrascu

According to our database, Mihai Patrascu authored at least 62 papers between 2004 and 2016.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2016

Predecessor Search.

Mihai Patrascu

Encyclopedia of Algorithms, 2016

Lower Bounds for Dynamic Connectivity.

Mihai Patrascu

Encyclopedia of Algorithms, 2016

2015

Investigation of long-term drift of NTC temperature sensors with less than 1 mK uncertainty.

Anupama Kulkarni, Mihai Patrascu, Yuri van de Vijver, Jaap van Wensveen, Robert Pijnenburg, Stoyan Nihtianov

Proceedings of the 24th IEEE International Symposium on Industrial Electronics, 2015

Finding the Median (Obliviously) with Bounded Space.

Paul Beame, Vincent Liew, Mihai Patrascu

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2014

Necklaces, Convolutions, and X+Y.

David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Mihai Patrascu, Perouz Taslakian

Algorithmica, 2014

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

Mihai Patrascu, Mikkel Thorup

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013

Twisted Tabulation Hashing.

Mihai Patrascu, Mikkel Thorup

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

2012

Using hashing to solve the dictionary problem.

John Iacono, Mihai Patrascu

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Picture-Hanging Puzzles.

Erik D. Demaine, Martin L. Demaine, Yair N. Minsky, Joseph S. B. Mitchell, Ronald L. Rivest, Mihai Patrascu

Proceedings of the Fun with Algorithms - 6th International Conference, 2012

A New Infinity of Distance Oracles for Sparse Graphs.

Mihai Patrascu, Liam Roditty, Mikkel Thorup

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

2011

Unifying the Landscape of Cell-Probe Lower Bounds.

Mihai Patrascu

SIAM J. Comput., 2011

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

John Iacono, Mihai Patrascu

CoRR, 2011

Don't rush into a union: take time to find your roots.

Mihai Patrascu, Mikkel Thorup

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

The power of simple tabulation hashing.

Mihai Patrascu, Mikkel Thorup

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Orthogonal range searching on the RAM, revisited.

Timothy M. Chan, Kasper Green Larsen, Mihai Patrascu

Proceedings of the 27th ACM Symposium on Computational Geometry, 2011

2010

Transdichotomous Results in Computational Geometry, II: Offline Search

Timothy M. Chan, Mihai Patrascu

CoRR, 2010

Towards polynomial lower bounds for dynamic problems.

Mihai Patrascu

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Changing base without losing space.

Yevgeniy Dodis, Mihai Patrascu, Mikkel Thorup

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

On the Possibility of Faster SAT Algorithms.

Mihai Patrascu, Ryan Williams

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Cell-Probe Lower Bounds for Succinct Partial Sums.

Mihai Patrascu, Emanuele Viola

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Counting Inversions, Offline Orthogonal Range Counting, and Related Problems.

Timothy M. Chan, Mihai Patrascu

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.

Alexandr Andoni, T. S. Jayram, Mihai Patrascu

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

On the <i>k</i>-Independence Required by Linear Probing and Minwise Independence.

Mihai Patrascu, Mikkel Thorup

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

Distance Oracles beyond the Thorup-Zwick Bound.

Mihai Patrascu, Liam Roditty

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

2009

Transdichotomous Results in Computational Geometry, I: Point Location in Sublogarithmic Time.

Timothy M. Chan, Mihai Patrascu

SIAM J. Comput., 2009

A Lower Bound for Succinct Rank Queries

Mihai Patrascu

CoRR, 2009

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

Jakub Pawlewicz, Mihai Patrascu

Algorithmica, 2009

The geometry of binary search trees.

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

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

2008

Predecessor Search.

Mihai Patrascu

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Lower Bounds for Dynamic Connectivity.

Mihai Patrascu

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Lower bound techniques for data structures.

Mihai Patrascu

PhD thesis, 2008

Tight lower bounds for selection in randomly ordered streams.

Amit Chakrabarti, T. S. Jayram, Mihai Patrascu

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).

Alexandr Andoni, Ronald Fagin, Ravi Kumar, Mihai Patrascu, D. Sivakumar

Proceedings of the ACM SIGMOD International Conference on Management of Data, 2008

(Data) STRUCTURES.

Mihai Patrascu

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

Succincter.

Mihai Patrascu

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

Dynamic Connectivity: Connecting to Networks and Geometry.

Timothy M. Chan, Mihai Patrascu, Liam Roditty

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

Hardness of Nearest Neighbor under L-infinity.

Alexandr Andoni, Dorian Croitoru, Mihai Patrascu

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

2007

Lower bounds for 2-dimensional range counting.

Mihai Patrascu

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

Voronoi diagrams in n·2^{osqrt(lg lg n)} time.

Timothy M. Chan, Mihai Patrascu

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

Randomization does not help searching predecessors.

Mihai Patrascu, Mikkel Thorup

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.

Nicholas J. A. Harvey, Mihai Patrascu, Yonggang Wen, Sergey Yekhanin, Vincent W. S. Chan

Proceedings of the INFOCOM 2007. 26th IEEE International Conference on Computer Communications, 2007

Planning for Fast Connectivity Updates.

Mihai Patrascu, Mikkel Thorup

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, 2007

Radix Sorting with No Extra Space.

Gianni Franceschini, S. Muthukrishnan, Mihai Patrascu

Proceedings of the Algorithms, 2007

Tight bounds for dynamic convex hull queries (again).

Erik D. Demaine, Mihai Patrascu

Proceedings of the 23rd ACM Symposium on Computational Geometry, 2007

2006

Logarithmic Lower Bounds in the Cell-Probe Model.

Mihai Patrascu, Erik D. Demaine

SIAM J. Comput., 2006

Time-space trade-offs for predecessor search.

Mihai Patrascu, Mikkel Thorup

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Deterministic load balancing and dictionaries in the parallel disk model.

Mette Berger, Esben Rune Hansen, Rasmus Pagh, Mihai Patrascu, Milan Ruzic, Peter Tiedemann

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.

Micah Adler, Erik D. Demaine, Nicholas J. A. Harvey, Mihai Patrascu

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

De Dictionariis Dynamicis Pauco Spatio Utentibus (<i>lat.</i> On Dynamic Dictionaries Using Little Space).

Erik D. Demaine, Friedhelm Meyer auf der Heide, Rasmus Pagh, Mihai Patrascu

Proceedings of the LATIN 2006: Theoretical Informatics, 2006

Higher Lower Bounds for Near-Neighbor and Further Rich Problems.

Mihai Patrascu, Mikkel Thorup

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, 2006

Planar Point Location in Sublogarithmic Time.

Mihai Patrascu

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, 2006

On the Optimality of the Dimensionality Reduction Method.

Alexandr Andoni, Piotr Indyk, Mihai Patrascu

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, 2006

2005

De Dictionariis Dynamicis Pauco Spatio Utentibus

Erik D. Demaine, Friedhelm Meyer auf der Heide, Rasmus Pagh, Mihai Patrascu

CoRR, 2005

Subquadratic Algorithms for 3SUM.

Ilya Baran, Erik D. Demaine, Mihai Patrascu

Proceedings of the Algorithms and Data Structures, 9th International Workshop, 2005

On dynamic range reporting in one dimension.

Christian Worm Mortensen, Rasmus Pagh, Mihai Patrascu

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Stick-slip Actuation of Electrostatic Stepper Micropositioners for Data Storage - the µWalker.

Mihai Patrascu, Stefano Stramigioli

Proceedings of the 2005 International Conference on MEMS, 2005

On Dynamic Bit-Probe Complexity.

Corina E. Patrascu, Mihai Patrascu

Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

2004

Lower bounds for dynamic connectivity.

Mihai Patrascu, Erik D. Demaine

Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Tight bounds for the partial-sums problem.

Mihai Patrascu, Erik D. Demaine

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Interpolation search for non-independent data.

Erik D. Demaine, Thouis R. Jones, Mihai Patrascu

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Dynamic Optimality - Almost.

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

Proceedings of the 45th Symposium on Foundations of Computer Science, 2004

Computing Order Statistics in the Farey Sequence.

Corina E. Patrascu, Mihai Patrascu

Proceedings of the Algorithmic Number Theory, 6th International Symposium, 2004