Mihai Patrascu (home)

Mihai Pătraşcu: Publications

[Basic HTML]

You can also see the DBLP listing. Click on a title to see the abstract.

 
John Iacono and Mihai Pătraşcu
23rd ACM/SIAM Symposium on Discrete Algorithms (SODA 2012).
Also available as: arXiv:1104.2799.
 
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.
 
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.
 
Mihai Pătraşcu and Mikkel Thorup
43rd ACM Symposium on Theory of Computing (STOC 2011).
Also: arXiv:1102.1783.
 
Mihai Pătraşcu and Liam Roditty
51st IEEE Symposium on Foundations of Computer Science (FOCS 2010).
 
Mihai Pătraşcu and Mikkel Thorup
37th International Colloquium on Automata, Languages and Programming (ICALP 2010).
 
Mihai Pătraşcu
42nd ACM Symposium on Theory of Computing (STOC 2010).
 
Yevgeniy Dodis, Mihai Pătraşcu, and Mikkel Thorup
42nd ACM Symposium on Theory of Computing (STOC 2010).
 
Mihai Pătraşcu and Dan Strătilă
In preparation. Talk in 20th International Symposium of Mathematical Programming (ISMP 2009).
 
Mihai Pătraşcu and Emanuele Viola
21st ACM/SIAM Symposium on Discrete Algorithms (SODA 2010).
 
Mihai Pătraşcu and Ryan Williams
21st ACM/SIAM Symposium on Discrete Algorithms (SODA 2010).
 
Timothy M. Chan and Mihai Pătraşcu
21st ACM/SIAM Symposium on Discrete Algorithms (SODA 2010).
 
Alexandr Andoni, T.S. Jayram, and Mihai Pătraşcu
21st ACM/SIAM Symposium on Discrete Algorithms (SODA 2010).
 
Erik Demaine, Dion Harmon, John Iacono, Daniel Kane, and Mihai Pătraşcu
20th ACM/SIAM Symposium on Discrete Algorithms (SODA 2009).
 
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.
 
Mihai Pătraşcu
49th IEEE Symposium on Foundations of Computer Science (FOCS 2008).
Best Student Paper (the Machtey Award)
 
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.
 
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.
 
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.
 
Amit Chakrabarti, T.S. Jayram, and Mihai Pătraşcu
19th ACM/SIAM Symposium on Discrete Algorithms (SODA 2008).
 
Mihai Pătraşcu and Mikkel Thorup
48th IEEE Symposium on Foundations of Computer Science (FOCS 2007).
 
Gianni Franceschini, S. Muthukrishnan, and Mihai Pătraşcu
15th European Symposium on Algorithms (ESA 2007).
Full version: arXiv:0706.4107.
 
Mihai Pătraşcu
39th ACM Symposium on Theory of Computing (STOC 2007).
 
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"
 
Erik Demaine and Mihai Pătraşcu
23rd ACM Symposium on Computational Geometry (SoCG 2007).
 
 
Mihai Pătraşcu and Mikkel Thorup
18th ACM/SIAM Symposium on Discrete Algorithms (SODA 2007).
 
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
 
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).
 
Alexandr Andoni, Piotr Indyk, and Mihai Pătraşcu
47th IEEE Symposium on Foundations of Computer Science (FOCS 2006).
 
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).
 
Mihai Pătraşcu and Mikkel Thorup
38th ACM Symposium on Theory of Computing (STOC 2006).
Full version (very preliminary): arXiv:cs/0603043.
 
[11]   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.
 
Micah Adler, Erik Demaine, Nick Harvey, and Mihai Pătraşcu
17th ACM/SIAM Symposium on Discrete Algorithms (SODA 2006).
 
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).
 
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).
 
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.
 
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).
 
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.
 
Corina Tarniţă and Mihai Pătraşcu
6th Algorithmic Number Theory Symposium (ANTS 2004).
This is superseded by [25].
 
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.
 
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.
 
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.
 
      [link]

d.s. lower bound (15)
integers (9)
geometry (8)
hashing (7)
succinctness (5)
hardness (5)
graphs (4)
high dimensions (3)
fun (3)

SICOMP (6)
Algorithmica (2)
TCS (1)

SODA (11)
FOCS (10)
STOC (9)
SoCG (2)
ICALP (2)

Erik Demaine (10)
Mikkel Thorup (8)
Timothy M. Chan (5)
Rasmus Pagh (3)
John Iacono (3)
Corina Tarniţă (3)
Alexandr Andoni (3)
T.S. Jayram (2)
Nick Harvey (2)
Liam Roditty (2)
Dion Harmon (2)