Gianni Franceschini's homepage

Current Position

I am an Assistant Professor at the Department of Computer Science, University of Rome "La Sapienza".

Contact

e-mail:	francesc "at" di.uniroma1.it


address:	Dipartimento di Informatica - Universita' "La Sapienza" di Roma
	Via Salaria 113
	00198 Roma - Italy

My Curriculum vitae

My Research Activity

Implicit and space efficient data structures
Sorting and searching algorithms
Cache-oblivious algorithms and data structures
String algorithms and data structures
Graph Theory

Papers

Unpublished papers

[27]	Gianni Franceschini and Torben Hagerup. Computing Maximum Suffixes with Fewer Comparisons. 2007. [ bib ]
[26]	Gianni Franceschini and Jyrki Katajainen. Generic Algorithm for 0/1-Sorting. 2006. [ bib ]
[25]	Gianni Franceschini and Roberto Grossi. Stable Sorting of Multisets in the Cache-Oblivious Model (and its application to Google's MapReduce). 2006. [ bib ]

Conferences

[24]	Gianni Franceschini, Roberto Grossi and S. Muthukrishnan. Optimal Cache-Aware Suffix Selection. In Proceedings of the 26th Symposium on Theoretical Aspects of Computer Science (STACS), to appear, 2009. [ bib ]
[23]	Gianni Franceschini, S. Muthukrishnan and Mihai Pătraşcu. Radix Sorting With No Extra Space. In Proceedings of the 15th European Symposium on Algorithms (ESA), to appear, 2007. [ bib ]
[22]	Gianni Franceschini and S. Muthukrishnan. In-Place Suffix Sorting. In Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP), to appear, 2007. [ bib ]
[21]	Gianni Franceschini and S. Muthukrishnan. Optimal Suffix Selection. In Proceedings of the 39th ACM Symposium on Theory of Computing (STOC), to appear, 2007. [ bib ]
[20]	Gianni Franceschini. Sorting by Merging or Merging by Sorting?. In Proceedings of the 10th Scandinavian Workshop on Algorithm Theory (SWAT), pages 77--89, 2006. [ bib ]
[19]	Gianni Franceschini and J. Ian Munro. Implicit Dictionaries with O(1) Modifications per Update and Fast Search. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 404--413, 2006. [ bib ]
[18]	Arash Farzan, Paolo Ferragina, Gianni Franceschini and Ian Munro. Cache-oblivious comparison-based algorithms on multisets. In Proceedings of the 13th European Symposium on Algorithms (ESA), pages 305--316, 2005. [ bib ]
[17]	Gianni Franceschini and Roberto Grossi. Optimal In-Place Sorting of Vectors and Records. In Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP), pages 90--102, 2005. [ bib ]
[16]	Gianni Franceschini. Sorting Stably, In-Place, with O(nlog n) Comparisons and O(n) Moves. In Proceedings of the 22nd Symposium on Theoretical Aspects of Computer Science (STACS), pages 629--640, 2005. [ bib ]
[15]	Gianni Franceschini and Roberto Grossi. No Sorting? Better Searching!. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 491--498, 2004. [ bib ]
[14]	Gianni Franceschini and Roberto Grossi. A General Technique for Managing Strings in Comparison-Driven Data Structures. In Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP), pages 606--617, 2004. [ bib ]
[13]	Gianni Franceschini. Proximity Mergesort: Optimal In-Place Sorting in the Cache-Oblivious Model. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 291--299, 2004. [ bib ]
[12]	Gianni Franceschini and Viliam Geffert. An In-Place Sorting with O(nlog n) Comparisons and O(n) Moves. In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 242--250, 2003. [ bib ]
[11]	Gianni Franceschini and Roberto Grossi. Optimal worst-case operations for implicit cache-oblivious search trees. In Proceedings of the 8th International Workshop on Algorithms and Data Structures (WADS), pages 114--126, 2003. [ bib ]
[10]	Gianni Franceschini and Roberto Grossi. Optimal cache-oblivious implicit dictionaries. In Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP), pages 316--331, 2003. [ bib ]
[9]	Gianni Franceschini and Roberto Grossi. Implicit dictionaries supporting searches and amortized updates in O(log n loglog n). In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 670-678. SIAM, 2003. [ bib ]
[8]	Gianni Franceschini, Roberto Grossi, J. Ian Munro, and Linda Pagli. Implicit B-trees: New results for the dictionary problem. In Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 145--154, 2002. [ bib ]
[7]	Lino Flores Pacheco, Gianni Franceschini, Fabrizio Luccio, and Linda Pagli. Decomposition of k-Dense Trees. In Proceedings of 3rd Symposium on Distributed Data and Structures, 2001. [ bib ]

Journals

[6]	Gianni Franceschini and Roberto Grossi. No Sorting? Better Searching!. ACM Transactions on Algorithms, to appear, 2007. [ bib ]
[5]	Gianni Franceschini, Roberto Grossi. Optimal Implicit Dictionaries over Unbounded Universes. Theory of Computing Systems, volume 39, number 2, pages 321--345, 2006. [ bib ]
[4]	Gianni Franceschini. Sorting Stably, In-Place, with O(nlog n) Comparisons and O(n) Moves. Theory of Computing Systems, to appear, 2006. Special issue of the 22nd Symposium on Theoretical Aspects of Computer Science (STACS), 2005. [ bib ]
[3]	Gianni Franceschini and Viliam Geffert. An In-Place Sorting with O(nlog n) Comparisons and O(n) Moves. Journal of the ACM , volume 52, number 4, pages 515--537, 2005. [ bib ]
[2]	Gianni Franceschini, Fabrizio Luccio and Linda Pagli. Dense trees: a new look at degenerate graphs. Journal of Discrete Algorithms, 2005. To appear. [ bib ]
[1]	Gianni Franceschini, Roberto Grossi, J. Ian Munro, and Linda Pagli. Implicit B-trees: A New Data Structure for the Dictionary Problem. Journal of Computer and System Sciences, volume 68, issue 4, pages 788--807, 2004. Special issue of the 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS). [ bib ]