Mihai Patrascu

84 papers A* 35A 1B 3Misc 1Journal 31Unranked 8

Year	Rank	Type	Title / Venue / Authors
2016	—	`ch.`	Lower Bounds for Dynamic Connectivity. Encyclopedia of Algorithms Mihai Patrascu
2016	J	`jnl`	On the ACM Trans. Algorithms Mihai Patrascu, Mikkel Thorup
2016	—	`ch.`	Predecessor Search. Encyclopedia of Algorithms Mihai Patrascu
2015	—	`conf`	Finding the Median (Obliviously) with Bounded Space. ICALP (1) Paul Beame, Vincent Liew, Mihai Patrascu
2015	J	`jnl`	Finding the Median (Obliviously) with Bounded Space. CoRR Paul Beame, Vincent Liew, Mihai Patrascu
2015	—	`conf`	Investigation of long-term drift of NTC temperature sensors with less than 1 mK uncertainty. ISIE Anupama Kulkarni, Mihai Patrascu, Yuri van de Vijver, Jaap van Wensveen, Robert Pijnenburg, Stoyan Nihtianov
2014	J	`jnl`	Distance Oracles beyond the Thorup-Zwick Bound. SIAM J. Comput. Mihai Patrascu, Liam Roditty
2014	A*	`conf`	Dynamic Integer Sets with Optimal Rank, Select, and Predecessor Search. FOCS Mihai Patrascu, Mikkel Thorup
2014	J	`jnl`	Dynamic Integer Sets with Optimal Rank, Select, and Predecessor Search. CoRR Mihai Patrascu, Mikkel Thorup
2014	J	`jnl`	Necklaces, Convolutions, and X+Y. Algorithmica David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Mihai Patrascu, Perouz Taslakian
2014	J	`jnl`	Picture-Hanging Puzzles. Theory Comput. Syst. Erik D. Demaine, Martin L. Demaine, Yair N. Minsky, Joseph S. B. Mitchell, Ronald L. Rivest, Mihai Patrascu
2013	A*	`conf`	Twisted Tabulation Hashing. SODA Mihai Patrascu, Mikkel Thorup
2012	A*	`conf`	A New Infinity of Distance Oracles for Sparse Graphs. FOCS Mihai Patrascu, Liam Roditty, Mikkel Thorup
2012	J	`jnl`	Necklaces, Convolutions, and X+Y CoRR David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Mihai Patrascu, Perouz Taslakian
2012	J	`jnl`	Picture-Hanging Puzzles CoRR Erik D. Demaine, Martin L. Demaine, Yair N. Minsky, Joseph S. B. Mitchell, Ronald L. Rivest, Mihai Patrascu
2012	Misc	`conf`	Picture-Hanging Puzzles. FUN Erik D. Demaine, Martin L. Demaine, Yair N. Minsky, Joseph S. B. Mitchell, Ronald L. Rivest, Mihai Patrascu
2012	J	`jnl`	The Power of Simple Tabulation Hashing. J. ACM Mihai Patrascu, Mikkel Thorup
2012	A*	`conf`	Using hashing to solve the dictionary problem. SODA John Iacono, Mihai Patrascu
2011	J	`jnl`	Don't Rush into a Union: Take Time to Find Your Roots CoRR Mihai Patrascu, Mikkel Thorup
2011	A*	`conf`	Don't rush into a union: take time to find your roots. STOC Mihai Patrascu, Mikkel Thorup
2011	J	`jnl`	Dynamic Connectivity: Connecting to Networks and Geometry. SIAM J. Comput. Timothy M. Chan, Mihai Patrascu, Liam Roditty
2011	J	`jnl`	Orthogonal Range Searching on the RAM, Revisited CoRR Timothy M. Chan, Kasper Green Larsen, Mihai Patrascu
2011	—	`conf`	Orthogonal range searching on the RAM, revisited. SCG Timothy M. Chan, Kasper Green Larsen, Mihai Patrascu
2011	A*	`conf`	The power of simple tabulation hashing. STOC Mihai Patrascu, Mikkel Thorup
2011	J	`jnl`	Unifying the Landscape of Cell-Probe Lower Bounds. SIAM J. Comput. Mihai Patrascu
2011	J	`jnl`	Using Hashing to Solve the Dictionary Problem (In External Memory) CoRR John Iacono, Mihai Patrascu
2010	A*	`conf`	Cell-Probe Lower Bounds for Succinct Partial Sums. SODA Mihai Patrascu, Emanuele Viola
2010	A*	`conf`	Changing base without losing space. STOC Yevgeniy Dodis, Mihai Patrascu, Mikkel Thorup
2010	A*	`conf`	Counting Inversions, Offline Orthogonal Range Counting, and Related Problems. SODA Timothy M. Chan, Mihai Patrascu
2010	A*	`conf`	Distance Oracles beyond the Thorup-Zwick Bound. FOCS Mihai Patrascu, Liam Roditty
2010	A*	`conf`	Lower Bounds for Edit Distance and Product Metrics via Poincaré-Type Inequalities. SODA Alexandr Andoni, T. S. Jayram, Mihai Patrascu
2010	—	`conf`	On the ICALP (1) Mihai Patrascu, Mikkel Thorup
2010	A*	`conf`	On the Possibility of Faster SAT Algorithms. SODA Mihai Patrascu, Ryan Williams
2010	J	`jnl`	The Power of Simple Tabulation Hashing CoRR Mihai Patrascu, Mikkel Thorup
2010	A*	`conf`	Towards polynomial lower bounds for dynamic problems. STOC Mihai Patrascu
2010	J	`jnl`	Transdichotomous Results in Computational Geometry, II: Offline Search CoRR Timothy M. Chan, Mihai Patrascu
2010	J	`jnl`	Unifying the Landscape of Cell-Probe Lower Bounds CoRR Mihai Patrascu
2009	J	`jnl`	A Lower Bound for Succinct Rank Queries CoRR Mihai Patrascu
2009	J	`jnl`	Higher Lower Bounds for Near-Neighbor and Further Rich Problems. SIAM J. Comput. Mihai Patrascu, Mikkel Thorup
2009	J	`jnl`	Order Statistics in the Farey Sequences in Sublinear Time and Counting Primitive Lattice Points in Polygons. Algorithmica Jakub Pawlewicz, Mihai Patrascu
2009	A*	`conf`	The geometry of binary search trees. SODA Erik D. Demaine, Dion Harmon, John Iacono, Daniel Kane, Mihai Patrascu
2009	J	`jnl`	Transdichotomous Results in Computational Geometry, I: Point Location in Sublogarithmic Time. SIAM J. Comput. Timothy M. Chan, Mihai Patrascu
2008	A*	`conf`	(Data) STRUCTURES. FOCS Mihai Patrascu
2008	—	`conf`	Corrigendum to "efficient similarity search and classification via rank aggregation" by Ronald Fagin, Ravi Kumar and D. Sivakumar (proc. SIGMOD'03). SIGMOD Conference Alexandr Andoni, Ronald Fagin, Ravi Kumar, Mihai Patrascu, D. Sivakumar
2008	J	`jnl`	Dynamic Connectivity: Connecting to Networks and Geometry CoRR Timothy M. Chan, Mihai Patrascu, Liam Roditty
2008	A*	`conf`	Dynamic Connectivity: Connecting to Networks and Geometry. FOCS Timothy M. Chan, Mihai Patrascu, Liam Roditty
2008	A*	`conf`	Hardness of Nearest Neighbor under L-infinity. FOCS Alexandr Andoni, Dorian Croitoru, Mihai Patrascu
2008	—	`ch.`	Lower Bounds for Dynamic Connectivity. Encyclopedia of Algorithms Mihai Patrascu
2008	—	`—`	Lower bound techniques for data structures. Mihai Patrascu
2008	—	`ch.`	Predecessor Search. Encyclopedia of Algorithms Mihai Patrascu
2008	J	`jnl`	Subquadratic Algorithms for 3SUM. Algorithmica Ilya Baran, Erik D. Demaine, Mihai Patrascu
2008	A*	`conf`	Succincter. FOCS Mihai Patrascu
2008	A*	`conf`	Tight lower bounds for selection in randomly ordered streams. SODA Amit Chakrabarti, T. S. Jayram, Mihai Patrascu
2007	J	`jnl`	Dynamic Optimality - Almost. SIAM J. Comput. Erik D. Demaine, Dion Harmon, John Iacono, Mihai Patrascu
2007	A*	`conf`	Lower bounds for 2-dimensional range counting. STOC Mihai Patrascu
2007	A*	`conf`	Non-Adaptive Fault Diagnosis for All-Optical Networks via Combinatorial Group Testing on Graphs. INFOCOM Nicholas J. A. Harvey, Mihai Patrascu, Yonggang Wen, Sergey Yekhanin, Vincent W. S. Chan
2007	J	`jnl`	On dynamic bit-probe complexity. Theor. Comput. Sci. Mihai Patrascu, Corina E. Tarnita
2007	A*	`conf`	Planning for Fast Connectivity Updates. FOCS Mihai Patrascu, Mikkel Thorup
2007	J	`jnl`	Radix Sorting With No Extra Space CoRR Gianni Franceschini, S. Muthukrishnan, Mihai Patrascu
2007	A	`conf`	Radix Sorting with No Extra Space. ESA Gianni Franceschini, S. Muthukrishnan, Mihai Patrascu
2007	A*	`conf`	Randomization does not help searching predecessors. SODA Mihai Patrascu, Mikkel Thorup
2007	—	`conf`	Tight bounds for dynamic convex hull queries (again). SCG Erik D. Demaine, Mihai Patrascu
2007	A*	`conf`	Voronoi diagrams in n·2 STOC Timothy M. Chan, Mihai Patrascu
2006	B	`conf`	De Dictionariis Dynamicis Pauco Spatio Utentibus ( LATIN Erik D. Demaine, Friedhelm Meyer auf der Heide, Rasmus Pagh, Mihai Patrascu
2006	B	`conf`	Deterministic load balancing and dictionaries in the parallel disk model. SPAA Mette Berger, Esben Rune Hansen, Rasmus Pagh, Mihai Patrascu, Milan Ruzic, Peter Tiedemann
2006	A*	`conf`	Higher Lower Bounds for Near-Neighbor and Further Rich Problems. FOCS Mihai Patrascu, Mikkel Thorup
2006	J	`jnl`	Logarithmic Lower Bounds in the Cell-Probe Model. SIAM J. Comput. Mihai Patrascu, Erik D. Demaine
2006	A*	`conf`	Lower bounds for asymmetric communication channels and distributed source coding. SODA Micah Adler, Erik D. Demaine, Nicholas J. A. Harvey, Mihai Patrascu
2006	A*	`conf`	On the Optimality of the Dimensionality Reduction Method. FOCS Alexandr Andoni, Piotr Indyk, Mihai Patrascu
2006	A*	`conf`	Planar Point Location in Sublogarithmic Time. FOCS Mihai Patrascu
2006	J	`jnl`	Time-Space Trade-Offs for Predecessor Search CoRR Mihai Patrascu, Mikkel Thorup
2006	A*	`conf`	Time-space trade-offs for predecessor search. STOC Mihai Patrascu, Mikkel Thorup
2005	J	`jnl`	De Dictionariis Dynamicis Pauco Spatio Utentibus CoRR Erik D. Demaine, Friedhelm Meyer auf der Heide, Rasmus Pagh, Mihai Patrascu
2005	J	`jnl`	Logarithmic Lower Bounds in the Cell-Probe Model CoRR Mihai Patrascu, Erik D. Demaine
2005	A*	`conf`	On Dynamic Bit-Probe Complexity. ICALP Corina E. Patrascu, Mihai Patrascu
2005	J	`jnl`	On Dynamic Range Reporting in One Dimension CoRR Christian Worm Mortensen, Rasmus Pagh, Mihai Patrascu
2005	A*	`conf`	On dynamic range reporting in one dimension. STOC Christian Worm Mortensen, Rasmus Pagh, Mihai Patrascu
2005	—	`conf`	Stick-slip Actuation of Electrostatic Stepper Micropositioners for Data Storage - the µWalker. ICMENS Mihai Patrascu, Stefano Stramigioli
2005	B	`conf`	Subquadratic Algorithms for 3SUM. WADS Ilya Baran, Erik D. Demaine, Mihai Patrascu
2004	—	`conf`	Computing Order Statistics in the Farey Sequence. ANTS Corina E. Patrascu, Mihai Patrascu
2004	A*	`conf`	Dynamic Optimality - Almost. FOCS Erik D. Demaine, Dion Harmon, John Iacono, Mihai Patrascu
2004	A*	`conf`	Interpolation search for non-independent data. SODA Erik D. Demaine, Thouis R. Jones, Mihai Patrascu
2004	A*	`conf`	Lower bounds for dynamic connectivity. STOC Mihai Patrascu, Erik D. Demaine
2004	A*	`conf`	Tight bounds for the partial-sums problem. SODA Mihai Patrascu, Erik D. Demaine