default search action
Mihai Patrascu
Person information
- unicode name: Mihai Pătrașcu
- affiliation: University of Copenhagen, Denmark
- affiliation: University of Washington, Seattle, WA, USA
- affiliation: AT&T Labs - Research, Florham Park, NJ, USA
- affiliation: IBM Research, Almaden, San Jose, CA, USA
- affiliation (PhD 2008): Massachusetts Institute of Technology, CSAIL, Cambridge, MA, USA
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
2010 – 2019
- 2016
- [j14]Mihai Patrascu, Mikkel Thorup
:
On the k-Independence Required by Linear Probing and Minwise Independence. ACM Trans. Algorithms 12(1): 8:1-8:27 (2016) - [r4]Mihai Patrascu:
Lower Bounds for Dynamic Connectivity. Encyclopedia of Algorithms 2016: 1162-1167 - [r3]Mihai Patrascu:
Predecessor Search. Encyclopedia of Algorithms 2016: 1601-1605 - 2015
- [c48]Paul Beame, Vincent Liew, Mihai Patrascu:
Finding the Median (Obliviously) with Bounded Space. ICALP (1) 2015: 103-115 - [c47]Anupama Kulkarni, Mihai Patrascu, Yuri van de Vijver, Jaap van Wensveen, Robert Pijnenburg, Stoyan Nihtianov:
Investigation of long-term drift of NTC temperature sensors with less than 1 mK uncertainty. ISIE 2015: 150-155 - [i17]Paul Beame, Vincent Liew, Mihai Patrascu:
Finding the Median (Obliviously) with Bounded Space. CoRR abs/1505.00090 (2015) - 2014
- [j13]David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono
Necklaces, Convolutions, and X+Y. Algorithmica 69(2): 294-314 (2014) - [j12]Erik D. Demaine, Martin L. Demaine, Yair N. Minsky, Joseph S. B. Mitchell, Ronald L. Rivest, Mihai Patrascu:
Picture-Hanging Puzzles. Theory Comput. Syst. 54(4): 531-550 (2014) - [j11]Mihai Patrascu, Liam Roditty:
Distance Oracles beyond the Thorup-Zwick Bound. SIAM J. Comput. 43(1): 300-311 (2014) - [c46]Mihai Patrascu, Mikkel Thorup
Dynamic Integer Sets with Optimal Rank, Select, and Predecessor Search. FOCS 2014: 166-175 - [i16]Mihai Patrascu, Mikkel Thorup:
Dynamic Integer Sets with Optimal Rank, Select, and Predecessor Search. CoRR abs/1408.3045 (2014) - 2013
- [c45]Mihai Patrascu, Mikkel Thorup
Twisted Tabulation Hashing. SODA 2013: 209-228 - 2012
- [j10]Mihai Patrascu, Mikkel Thorup
The Power of Simple Tabulation Hashing. J. ACM 59(3): 14:1-14:50 (2012) - [c44]Mihai Patrascu, Liam Roditty, Mikkel Thorup
A New Infinity of Distance Oracles for Sparse Graphs. FOCS 2012: 738-747 - [c43]Erik D. Demaine, Martin L. Demaine, Yair N. Minsky, Joseph S. B. Mitchell, Ronald L. Rivest, Mihai Patrascu:
Picture-Hanging Puzzles. FUN 2012: 81-93 - [c42]John Iacono, Mihai Patrascu:
Using hashing to solve the dictionary problem. SODA 2012: 570-582 - [i15]Erik D. Demaine, Martin L. Demaine, Yair N. Minsky, Joseph S. B. Mitchell, Ronald L. Rivest, Mihai Patrascu:
Picture-Hanging Puzzles. CoRR abs/1203.3602 (2012) - [i14]David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono
Necklaces, Convolutions, and X+Y. CoRR abs/1212.4771 (2012) - 2011
- [j9]Timothy M. Chan, Mihai Patrascu, Liam Roditty:
Dynamic Connectivity: Connecting to Networks and Geometry. SIAM J. Comput. 40(2): 333-349 (2011) - [j8]Mihai Patrascu:
Unifying the Landscape of Cell-Probe Lower Bounds. SIAM J. Comput. 40(3): 827-847 (2011) - [c41]Timothy M. Chan, Kasper Green Larsen, Mihai Patrascu:
Orthogonal range searching on the RAM, revisited. SCG 2011: 1-10 - [c40]Mihai Patrascu, Mikkel Thorup
The power of simple tabulation hashing. STOC 2011: 1-10 - [c39]Mihai Patrascu, Mikkel Thorup
Don't rush into a union: take time to find your roots. STOC 2011: 559-568 - [i13]Mihai Patrascu, Mikkel Thorup:
Don't Rush into a Union: Take Time to Find Your Roots. CoRR abs/1102.1783 (2011) - [i12]Timothy M. Chan, Kasper Green Larsen, Mihai Patrascu:
Orthogonal Range Searching on the RAM, Revisited. CoRR abs/1103.5510 (2011) - [i11]John Iacono, Mihai Patrascu:
Using Hashing to Solve the Dictionary Problem (In External Memory). CoRR abs/1104.2799 (2011) - 2010
- [c38]Mihai Patrascu, Liam Roditty:
Distance Oracles beyond the Thorup-Zwick Bound. FOCS 2010: 815-823 - [c37]Mihai Patrascu, Mikkel Thorup
On the k-Independence Required by Linear Probing and Minwise Independence. ICALP (1) 2010: 715-726 - [c36]Mihai Patrascu, Emanuele Viola:
Cell-Probe Lower Bounds for Succinct Partial Sums. SODA 2010: 117-122 - [c35]Timothy M. Chan, Mihai Patrascu:
Counting Inversions, Offline Orthogonal Range Counting, and Related Problems. SODA 2010: 161-173 - [c34]Alexandr Andoni, T. S. Jayram, Mihai Patrascu:
Lower Bounds for Edit Distance and Product Metrics via Poincaré-Type Inequalities. SODA 2010: 184-192 - [c33]Mihai Patrascu, Ryan Williams
On the Possibility of Faster SAT Algorithms. SODA 2010: 1065-1075 - [c32]Yevgeniy Dodis, Mihai Patrascu, Mikkel Thorup:
Changing base without losing space. STOC 2010: 593-602 - [c31]Mihai Patrascu:
Towards polynomial lower bounds for dynamic problems. STOC 2010: 603-610 - [i10]Timothy M. Chan, Mihai Patrascu:
Transdichotomous Results in Computational Geometry, II: Offline Search. CoRR abs/1010.1948 (2010) - [i9]Mihai Patrascu:
Unifying the Landscape of Cell-Probe Lower Bounds. CoRR abs/1010.3783 (2010) - [i8]Mihai Patrascu, Mikkel Thorup:
The Power of Simple Tabulation Hashing. CoRR abs/1011.5200 (2010)
2000 – 2009
- 2009
- [j7]Jakub Pawlewicz
Order Statistics in the Farey Sequences in Sublinear Time and Counting Primitive Lattice Points in Polygons. Algorithmica 55(2): 271-282 (2009) - [j6]Timothy M. Chan, Mihai Patrascu:
Transdichotomous Results in Computational Geometry, I: Point Location in Sublogarithmic Time. SIAM J. Comput. 39(2): 703-729 (2009) - [j5]Mihai Patrascu, Mikkel Thorup:
Higher Lower Bounds for Near-Neighbor and Further Rich Problems. SIAM J. Comput. 39(2): 730-741 (2009) - [c30]Erik D. Demaine, Dion Harmon, John Iacono, Daniel Kane, Mihai Patrascu:
The geometry of binary search trees. SODA 2009: 496-505 - [i7]Mihai Patrascu:
A Lower Bound for Succinct Rank Queries. CoRR abs/0907.1103 (2009) - 2008
- [b1]Mihai Patrascu:
Lower bound techniques for data structures. Massachusetts Institute of Technology, Cambridge, MA, USA, 2008 - [j4]Ilya Baran, Erik D. Demaine, Mihai Patrascu:
Subquadratic Algorithms for 3SUM. Algorithmica 50(4): 584-596 (2008) - [c29]Timothy M. Chan, Mihai Patrascu, Liam Roditty:
Dynamic Connectivity: Connecting to Networks and Geometry. FOCS 2008: 95-104 - [c28]Mihai Patrascu:
Succincter. FOCS 2008: 305-313 - [c27]Alexandr Andoni, Dorian Croitoru, Mihai Patrascu:
Hardness of Nearest Neighbor under L-infinity. FOCS 2008: 424-433 - [c26]Mihai Patrascu:
(Data) STRUCTURES. FOCS 2008: 434-443 - [c25]Alexandr Andoni, Ronald Fagin, Ravi Kumar, Mihai Patrascu, D. Sivakumar:
Corrigendum to "efficient similarity search and classification via rank aggregation" by Ronald Fagin, Ravi Kumar and D. Sivakumar (proc. SIGMOD'03). SIGMOD Conference 2008: 1375-1376 - [c24]Amit Chakrabarti, T. S. Jayram, Mihai Patrascu:
Tight lower bounds for selection in randomly ordered streams. SODA 2008: 720-729 - [r2]Mihai Patrascu:
Lower Bounds for Dynamic Connectivity. Encyclopedia of Algorithms 2008 - [r1]Mihai Patrascu:
Predecessor Search. Encyclopedia of Algorithms 2008 - [i6]Timothy M. Chan, Mihai Patrascu, Liam Roditty:
Dynamic Connectivity: Connecting to Networks and Geometry. CoRR abs/0808.1128 (2008) - 2007
- [j3]Erik D. Demaine, Dion Harmon, John Iacono, Mihai Patrascu:
Dynamic Optimality - Almost. SIAM J. Comput. 37(1): 240-251 (2007) - [j2]Mihai Patrascu, Corina E. Tarnita
On dynamic bit-probe complexity. Theor. Comput. Sci. 380(1-2): 127-142 (2007) - [c23]Erik D. Demaine, Mihai Patrascu:
Tight bounds for dynamic convex hull queries (again). SCG 2007: 354-363 - [c22]Gianni Franceschini, S. Muthukrishnan, Mihai Patrascu:
Radix Sorting with No Extra Space. ESA 2007: 194-205 - [c21]Mihai Patrascu, Mikkel Thorup:
Planning for Fast Connectivity Updates. FOCS 2007: 263-271 - [c20]Nicholas J. A. Harvey, Mihai Patrascu, Yonggang Wen, Sergey Yekhanin, Vincent W. S. Chan:
Non-Adaptive Fault Diagnosis for All-Optical Networks via Combinatorial Group Testing on Graphs. INFOCOM 2007: 697-705 - [c19]Mihai Patrascu, Mikkel Thorup:
Randomization does not help searching predecessors. SODA 2007: 555-564 - [c18]Timothy M. Chan, Mihai Patrascu:
Voronoi diagrams in n·2osqrt(lg lg n) time. STOC 2007: 31-39 - [c17]Mihai Patrascu:
Lower bounds for 2-dimensional range counting. STOC 2007: 40-46 - [i5]Gianni Franceschini, S. Muthukrishnan, Mihai Patrascu:
Radix Sorting With No Extra Space. CoRR abs/0706.4107 (2007) - 2006
- [j1]Mihai Patrascu, Erik D. Demaine:
Logarithmic Lower Bounds in the Cell-Probe Model. SIAM J. Comput. 35(4): 932-963 (2006) - [c16]Mihai Patrascu:
Planar Point Location in Sublogarithmic Time. FOCS 2006: 325-332 - [c15]Alexandr Andoni, Piotr Indyk, Mihai Patrascu:
On the Optimality of the Dimensionality Reduction Method. FOCS 2006: 449-458 - [c14]Mihai Patrascu, Mikkel Thorup:
Higher Lower Bounds for Near-Neighbor and Further Rich Problems. FOCS 2006: 646-654 - [c13]Erik D. Demaine, Friedhelm Meyer auf der Heide, Rasmus Pagh, Mihai Patrascu:
De Dictionariis Dynamicis Pauco Spatio Utentibus (lat. On Dynamic Dictionaries Using Little Space). LATIN 2006: 349-361 - [c12]Micah Adler, Erik D. Demaine, Nicholas J. A. Harvey, Mihai Patrascu:
Lower bounds for asymmetric communication channels and distributed source coding. SODA 2006: 251-260 - [c11]Mette Berger, Esben Rune Hansen, Rasmus Pagh, Mihai Patrascu, Milan Ruzic, Peter Tiedemann:
Deterministic load balancing and dictionaries in the parallel disk model. SPAA 2006: 299-307 - [c10]Mihai Patrascu, Mikkel Thorup:
Time-space trade-offs for predecessor search. STOC 2006: 232-240 - [i4]Mihai Patrascu, Mikkel Thorup:
Time-Space Trade-Offs for Predecessor Search. CoRR abs/cs/0603043 (2006) - 2005
- [c9]Corina E. Patrascu, Mihai Patrascu:
On Dynamic Bit-Probe Complexity. ICALP 2005: 969-981 - [c8]Mihai Patrascu, Stefano Stramigioli
Stick-slip Actuation of Electrostatic Stepper Micropositioners for Data Storage - the µWalker. ICMENS 2005: 81-86 - [c7]Christian Worm Mortensen, Rasmus Pagh, Mihai Patrascu:
On dynamic range reporting in one dimension. STOC 2005: 104-111 - [c6]Ilya Baran, Erik D. Demaine, Mihai Patrascu:
Subquadratic Algorithms for 3SUM. WADS 2005: 409-421 - [i3]Christian Worm Mortensen, Rasmus Pagh, Mihai Patrascu:
On Dynamic Range Reporting in One Dimension. CoRR abs/cs/0502032 (2005) - [i2]Mihai Patrascu, Erik D. Demaine:
Logarithmic Lower Bounds in the Cell-Probe Model. CoRR abs/cs/0502041 (2005) - [i1]Erik D. Demaine, Friedhelm Meyer auf der Heide, Rasmus Pagh, Mihai Patrascu:
De Dictionariis Dynamicis Pauco Spatio Utentibus. CoRR abs/cs/0512081 (2005) - 2004
- [c5]Corina E. Patrascu, Mihai Patrascu:
Computing Order Statistics in the Farey Sequence. ANTS 2004: 358-366 - [c4]Erik D. Demaine, Dion Harmon, John Iacono, Mihai Patrascu:
Dynamic Optimality - Almost. FOCS 2004: 484-490 - [c3]Mihai Patrascu, Erik D. Demaine:
Tight bounds for the partial-sums problem. SODA 2004: 20-29 - [c2]Erik D. Demaine, Thouis R. Jones, Mihai Patrascu:
Interpolation search for non-independent data. SODA 2004: 529-530 - [c1]Mihai Patrascu, Erik D. Demaine:
Lower bounds for dynamic connectivity. STOC 2004: 546-553
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-11-07 21:36 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: