Mihai Pătraşcu: Publications

[Advanced GUI]

You can also see the DBLP listing.

[43]   PDF | PS | BibTeX 
Using Hashing to Solve the Dictionary Problem (In External Memory)
John Iacono and Mihai Pătraşcu
23rd ACM/SIAM Symposium on Discrete Algorithms (SODA 2012).
Also available as: arXiv:1104.2799.
[42]   PDF | PS | BibTeX 
Orthogonal Range Searching on the RAM, Revisited
Timothy M. Chan, Kasper Larsen, and Mihai Pătraşcu
27th ACM Symposium on Computational Geometry (SoCG 2011).
Full version: arXiv:1011.5200. Invited to special issue of Computational Geometry: Theory and Applications (CGTA); declined.
[41]   PDF | PS | Talk (PDF) | BibTeX 
The Power of Simple Tabulation Hashing
Mihai Pătraşcu and Mikkel Thorup
43rd ACM Symposium on Theory of Computing (STOC 2011).
In submission to J. ACM. Full version:: arXiv:1011.5200.
[40]   PDF | PS | Talk (PPSX) | Talk (PDF) | BibTeX 
Don't Rush into a Union: Take Time to Find Your Roots
Mihai Pătraşcu and Mikkel Thorup
43rd ACM Symposium on Theory of Computing (STOC 2011).
Also: arXiv:1102.1783.
[39]   PDF | PS | Talk (PPSX) | Talk (PDF) | BibTeX 
Distance Oracles Beyond the Thorup--Zwick Bound
Mihai Pătraşcu and Liam Roditty
51st IEEE Symposium on Foundations of Computer Science (FOCS 2010).
[38]   PDF | PS | Talk (PPSX) | Talk (PDF) | BibTeX 
On the k-Independence Required by Linear Probing and Minwise Independence
Mihai Pătraşcu and Mikkel Thorup
37th International Colloquium on Automata, Languages and Programming (ICALP 2010).
[37]   PDF | PS | Talk (PPSX) | Talk (PDF) | BibTeX 
Towards Polynomial Lower Bounds for Dynamic Problems
Mihai Pătraşcu
42nd ACM Symposium on Theory of Computing (STOC 2010).
[36]   PDF | PS | Talk (PPSX) | Talk (PDF) | BibTeX 
Changing Base without Losing Space
Yevgeniy Dodis, Mihai Pătraşcu, and Mikkel Thorup
42nd ACM Symposium on Theory of Computing (STOC 2010).
[35]   Talk (PPSX) | Talk (PDF) | BibTeX 
Faster Primal-Dual Algorithms for the Economic Lot-Sizing Problem
Mihai Pătraşcu and Dan Strătilă
In preparation. Talk in 20th International Symposium of Mathematical Programming (ISMP 2009).
[34]   PDF | PS | Talk (PPSX) | Talk (PDF) | BibTeX 
Cell-Probe Lower Bounds for Succinct Partial Sums
Mihai Pătraşcu and Emanuele Viola
21st ACM/SIAM Symposium on Discrete Algorithms (SODA 2010).
[33]   PDF | PS | Talk (PDF) | BibTeX 
On the Possibility of Faster SAT Algorithms
Mihai Pătraşcu and Ryan Williams
21st ACM/SIAM Symposium on Discrete Algorithms (SODA 2010).
[32]   PDF | PS | Talk (PDF) | BibTeX 
Counting Inversions, Offline Orthogonal Range Counting, and Related Problems
Timothy M. Chan and Mihai Pătraşcu
21st ACM/SIAM Symposium on Discrete Algorithms (SODA 2010).
[31]   PDF | PS | Talk (PDF) | BibTeX 
Lower Bounds for Edit Distance and Product Metrics via Poincaré-Type Inequalities
Alexandr Andoni, T.S. Jayram, and Mihai Pătraşcu
21st ACM/SIAM Symposium on Discrete Algorithms (SODA 2010).
[30]   PDF | PS | Talk (PPSX) | Talk (PDF) | BibTeX 
The Geometry of Binary Search Trees
Erik Demaine, Dion Harmon, John Iacono, Daniel Kane, and Mihai Pătraşcu
20th ACM/SIAM Symposium on Discrete Algorithms (SODA 2009).
[29]   PDF | PS | Talk (PPSX) | Talk (PDF) | BibTeX 
Unifying the Landscape of Cell-Probe Lower Bounds
Mihai Pătraşcu
SIAM Journal on Computing (SICOMP), vol. 40(3), 2011. Special issue.
49th IEEE Symposium on Foundations of Computer Science (FOCS 2008).
Also available as: arXiv:1010.3783.
[28]   PDF | PS | Talk (PPSX) | Talk (PDF) | BibTeX 
Succincter
Mihai Pătraşcu
49th IEEE Symposium on Foundations of Computer Science (FOCS 2008).
Best Student Paper (the Machtey Award)
[27]   PDF | PS | BibTeX 
Hardness of Nearest Neighbor under L-infinity
Alexandr Andoni, Dorian Croitoru, and Mihai Pătraşcu
49th IEEE Symposium on Foundations of Computer Science (FOCS 2008).
This chapter of my PhD thesis contains a polished version of the material.
[26]   PDF | PS | Talk (PPSX) | Talk (PDF) | BibTeX 
Dynamic Connectivity: Connecting to Networks and Geometry
Timothy M. Chan, Mihai Pătraşcu, and Liam Roditty
SIAM Journal on Computing (SICOMP), vol. 40(2), 2011.
49th IEEE Symposium on Foundations of Computer Science (FOCS 2008).
Full version: arXiv:0808.1128.
[25]   PDF | PS | BibTeX 
Order Statistics in the Farey Sequences in Sublinear Time and Counting Primitive Lattice Points in Polygons
Jakub Pawlewicz and Mihai Pătraşcu
Algorithmica, vol. 55(2), 2009.
Based on a paper by Pawlewicz in ESA'07, and my subsequent: arXiv:0708.0080.
[24]   PDF | PS | BibTeX 
Tight Lower Bounds for Selection in Randomly Ordered Streams
Amit Chakrabarti, T.S. Jayram, and Mihai Pătraşcu
19th ACM/SIAM Symposium on Discrete Algorithms (SODA 2008).
[23]   PDF | PS | Talk (PPSX) | Talk (PDF) | BibTeX 
Planning for Fast Connectivity Updates
Mihai Pătraşcu and Mikkel Thorup
48th IEEE Symposium on Foundations of Computer Science (FOCS 2007).
[22]   PDF | PS | BibTeX 
Radix Sorting With No Extra Space
Gianni Franceschini, S. Muthukrishnan, and Mihai Pătraşcu
15th European Symposium on Algorithms (ESA 2007).
Full version: arXiv:0706.4107.
[21]   PDF | PS | Talk (PPSX) | Talk (PDF) | BibTeX 
Lower Bounds for 2-Dimensional Range Counting
Mihai Pătraşcu
39th ACM Symposium on Theory of Computing (STOC 2007).
[20]   PDF | PS | Talk (PPSX) | Talk (PDF) | BibTeX 
Transdichotomous Results in Computational Geometry, II: Offline Search
Timothy M. Chan and Mihai Pătraşcu
39th ACM Symposium on Theory of Computing (STOC 2007).
Journal version (submitted): arXiv:1010.1948. The conference title was "Voronoi Diagrams in n•2O(√lglg n) Time"
[19]   PDF | PS | Talk (PPSX) | BibTeX 
Tight Bounds for Dynamic Convex Hull Queries (Again)
Erik Demaine and Mihai Pătraşcu
23rd ACM Symposium on Computational Geometry (SoCG 2007).
[18]   PDF | Talk (PPSX) | Talk (PDF) | BibTeX 
Non-Adaptive Fault Diagnosis for All-Optical Networks via Combinatorial Group Testing on Graphs
Nick Harvey, Mihai Pătraşcu, Yonggang Wen, Sergey Yekhanin, and Vincent Chan
26th IEEE Conference on Computer Communications (INFOCOM 2007).
[17]   PDF | PS | BibTeX 
Randomization Does Not Help Searching Predecessors
Mihai Pătraşcu and Mikkel Thorup
18th ACM/SIAM Symposium on Discrete Algorithms (SODA 2007).
[16]   PDF | PS | Talk (PDF) | BibTeX 
Transdichotomous Results in Computational Geometry, I: Point Location in Sublogarithmic Time
Timothy M. Chan and Mihai Pătraşcu
SIAM Journal on Computing (SICOMP), vol. 39(2), 2010. Special issue.
47th IEEE Symposium on Foundations of Computer Science (FOCS 2006).
Based on two FOCS'06 papers by each author, achieving similar results. My conference paper was entitled: Planar Point Location in Sublogarithmic Time
[15]   PDF | PS | Talk (PDF) | BibTeX 
Higher Lower Bounds for Near-Neighbor and Further Rich Problems
Mihai Pătraşcu and Mikkel Thorup
SIAM Journal on Computing (SICOMP), vol. 39(2), 2010. Special issue.
47th IEEE Symposium on Foundations of Computer Science (FOCS 2006).
[14]   PDF | PS | BibTeX 
On the Optimality of the Dimensionality Reduction Method
Alexandr Andoni, Piotr Indyk, and Mihai Pătraşcu
47th IEEE Symposium on Foundations of Computer Science (FOCS 2006).
[13]   PDF | PS | BibTeX 
Deterministic Load Balancing and Dictionaries in the Parallel Disk Model
Mette Berger, Esben Rune Hansen, Rasmus Pagh, Mihai Pătraşcu, Milan Ružić, and Peter Tiedemann
18th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2006).
[12]   PDF | PS | BibTeX 
Time-Space Trade-Offs for Predecessor Search
Mihai Pătraşcu and Mikkel Thorup
38th ACM Symposium on Theory of Computing (STOC 2006).
Full version (very preliminary): arXiv:cs/0603043.
[11]   PDF | PS | Talk (PDF) | BibTeX 
De Dictionariis Dynamicis Pauco Spatio Utentibus   (On Dynamic Dictionaries Using Little Space)
Erik Demaine, Friedhelm Meyer auf der Heide, Rasmus Pagh, and Mihai Pătraşcu
7th Latin American Theoretical Informatics (LATIN 2006).
Full version (rather unpolished): arXiv:cs/0512081.
[10]   PDF | PS | Talk (PDF) | BibTeX 
Lower Bounds for Asymmetric Communication Channels and Distributed Source Coding
Micah Adler, Erik Demaine, Nick Harvey, and Mihai Pătraşcu
17th ACM/SIAM Symposium on Discrete Algorithms (SODA 2006).
[9]   PDF | PS | BibTeX 
Subquadratic Algorithms for 3SUM
Ilya Baran, Erik Demaine, and Mihai Pătraşcu
Algorithmica, vol. 50(4), 2008. Special issue.
9th Workshop on Algorithms and Data Structures (WADS 2005).
[8]   PDF | PS | Talk (PDF) | BibTeX 
On Dynamic Bit-Probe Complexity
Mihai Pătraşcu and Corina Tarniţă
Theoretical Computer Science (TCS), vol. 380, 2007. Special issue.
32nd International Colloquium on Automata, Languages and Programming (ICALP 2005).
Best Student Paper Award (Track A).
[7]   PDF | PS | Talk (PDF) | BibTeX 
On Dynamic Range Reporting in One Dimension
Christian Worm Mortensen, Rasmus Pagh, and Mihai Pătraşcu
37th ACM Symposium on Theory of Computing (STOC 2005).
Full version (unpolished; conference version recommended): arXiv:cs/0502032.
[6]   PDF | PS | BibTeX 
Dynamic Optimality -- Almost
Erik Demaine, Dion Harmon, John Iacono, and Mihai Pătraşcu
SIAM Journal on Computing (SICOMP), vol. 37(1), 2007. Special issue.
45th IEEE Symposium on Foundations of Computer Science (FOCS 2004).
[5]   PDF | PS | Talk (PPSX) | Talk (PDF) | BibTeX 
Finding a Divisible Pair and a Good Wooden Fence
Stelian Ciurea, Erik Demaine, Corina Tarniţă, and Mihai Pătraşcu
3rd International Conference on Fun with Algorithms (FUN 2004).
The divisible-pair problem was also covered in a poster at ANTS'04, and an invited abstract in ACM SIGSAM Bulletin, vol. 38(3), 2004. A follow-up paper of Adrian Dumitrescu and Guangwu Xu corrects an error in our divisible-pair upper bound.
[4]   PDF | PS | Talk (PDF) | BibTeX 
Computing Order Statistics in the Farey Sequence
Corina Tarniţă and Mihai Pătraşcu
6th Algorithmic Number Theory Symposium (ANTS 2004).
This is superseded by [25].
[3]   PDF | PS | Talk (PDF) | BibTeX 
Logarithmic Lower Bounds in the Cell-Probe Model
Mihai Pătraşcu and Erik Demaine
SIAM Journal on Computing (SICOMP), vol. 35(4), 2006. Special issue
36th ACM Symposium on Theory of Computing (STOC 2004).
This chapter of my PhD thesis contains a better exposition. The conference title was: Lower Bounds for Dynamic Connectivity.
[2]   PDF | PS | BibTeX 
Interpolation Search for Non-Independent Data
Erik Demaine, Thouis Jones, and Mihai Pătraşcu
15th ACM/SIAM Symposium on Discrete Algorithms (SODA 2004).
Errata: There is an error in Lemma 2.1, regarding the behavior on the uniform distribution. The behavior as stated is correct, but the justification is not.
[1]   PDF | PS | Talk (PPSX) | Talk (PDF) | BibTeX 
Tight Bounds for the Partial-Sums Problem
Mihai Pătraşcu and Erik Demaine
15th ACM/SIAM Symposium on Discrete Algorithms (SODA 2004).
Invited to special issue of ACM Transactions on Algorithms (declined). Merged with [3] for the journal version.