.:. Roberto Grossi

Dipartimento di Informatica Università di Pisa Largo Bruno Pontecorvo 3 56127 Pisa, Italy grossi@di.unipi.it (email policy) 361-DN (room) +39-050-221-2793 (voice) +39-050-221-2726 (fax) robertogrossi (skype)
E poi ti dicono: "Tutti sono uguali, tutti rubano nella stessa maniera", ma è solo un modo per convincerti a restare chiuso dentro casa quando viene la sera. [...] La storia siamo noi, siamo noi che scriviamo le lettere, siamo noi che abbiamo tutto da vincere o tutto da perdere. E poi la gente [...] te la ritrovi tutta con gli occhi aperti, che sanno benissimo cosa fare: quelli che hanno letto un milione di libri e quelli che non sanno nemmeno parlare. -- La Storia (F. De Gregori)

-:- ABOUT ME

Associate Professor at the University of Pisa.
Ph.D. and Laurea in Computer Science at the University of Pisa.
Member of the Algorithms and Data Structures group at the Department of Computer Science.
Formerly, Assistant Professor at the University of Florence.
Member of the Editorial Board of Theory of Computing Systems (TOCS), Springer-Verlag.
PC member of CIAC03, CPM03, STACS03, ESA04, FUN04, IS04-TCS, SPIRE04, ICTCS05, SODA05, SPIRE05, ALENEX06, SWAT10, ESA10.
Member (treasurer) of the Scientific Council of the Italian Chapter of EATCS.
For any other (bad) rumor on me, ask me directly! Surely it's true :-)

-:- TEACHING (in Italian)

008AA - Algoritmica e Laboratorio - corso B
AA237 - Algoritmi e Strutture dei Dati (Matematica).
AA339 - Informatica II (Fisica, mutuato).
NW220 - Algoritmica 2.
Ricevimento degli studenti:
1. venerdì dalle 10 alle 13 presso la mia stanza 361-DN;
2. per appuntamento (per email o telefono).
Appelli di esami: calendario ufficiale.

-:- RESEARCH

Design and analysis of algorithms and data structures.
Dynamic and external memory algorithms; graph algorithms.
Experimental and algorithm engineering; fast lookup tables and dictionaries.
Pattern matching algorithms on strings, matrices and trees.
Text indexing and compressed data structures; compressed suffix array and suffix tree.
Proudly advised Ph.D. students (to be updated...): Gianni Franceschini (U. Waterloo, postdoc with Ian Munro), Ankur Gupta (Duke U. & Purdue U., advisor Jeff Vitter), Iwona Bialynicka-Birula (Galilei International Ph.D. school).
Ph.D. schools/seminars: Bertinoro 2000, Lyon 2003, Lipari 2003, Rennes 2004, Chennai 2004, Haifa 2005.

Please see also the old version. A random subset of my papers is here, probably useless...

-:- STRUTTURE DI DATI E ALGORITMI

Strutture di dati e algoritmi
Progettazione, analisi e visualizzazione
P. Crescenzi, G. Gambosi, R. Grossi
Addison-Wesley Pearson Education, 2006

PREFAZIONE
SOMMARIO

cap.1

cap.5

cap.6

www.algoritmica.org

-:- ON LINE PAPERS

to be updated...
Amortized Rigidness in Dynamic Cartesian Trees, with I. Bialynicka-Birula, International Symposium on Theoretical Aspects of Computer Science (STACS 2006).
Squeezing Succinct Data Structures into Entropy Bounds, with K. Sadakane, ACM-SIAM Symposium on Discrete Algorithms (SODA 2006).
Rank-Sensitive Data Structures, with I. Bialynicka-Birula, String Processing and Information Retrieval (SPIRE 2005).
Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching, with J.S. Vitter, SIAM Journal on Computing, 2005.
When Indexing Equals Compression: Experiments with Compressing Suffix Arrays and Applications, with A. Gupta and J.S. Vitter, ACM Transactions on Algorithms (special issue of ACM-SIAM SODA), 2005, accepted with revisions.
Optimal In-Place Sorting of Vectors and Records, with G. Franceschini, International Colloquium on Automata, Languages and Programming (ICALP 2005).
Distilling Router Data Analysis for Faster and Simpler Dynamic IP Lookup Algorithms, with F. Geraci, International Workshop on Efficient and Experimental Algorithms (WEA 2005).
Optimal Implicit Dictionaries over Unbounded Universes, with G. Franceschini, Theory of Computing Systems, 2005.
Bases of Motifs for Generating Repeated Patterns with Wild Cards, with N. Pisanti, M. Crochemore, and M.-F. Sagot, IEEE/ACM Transactions on Computational Biology and Bioinformatics 2(1) 40-50, 2005.
No Sorting? Better Searching!, with G. Franceschini, IEEE Symposium on Foundations of Computer Science (FOCS 2004), [full version].
A Comparative Study of Bases for Motif Inference, with N. Pisanti, M. Crochemore, M.-F. Sagot, in NATO volume on String Algorithmics, 2004.
A General Technique for Managing Strings in Comparison-Driven Data Structures, with G. Franceschini, International Colloquium on Automata, Languages and Programming (ICALP 2004).
A Trie-Based Approach for Compacting Automata, with M. Crochemore, C. Epifanio and F. Mignosi, Symposium on Combinatorial Pattern Matching (CPM 2004).
Fast Compression with a Static Model in High-Order Entropy, with L. Foschini, A. Gupta and J.S. Vitter, IEEE Data Compression Conference (DCC 2004).
Implicit B-trees: A New Data Structure for the Dictionary Problem, with G. Franceschini, J.I. Munro and L. Pagli, Journal of Computer and System Sciences 68(4) 788-807, 2004 (special issue of IEEE FOCS).
When Indexing Equals Compression: Experiments with Compressing Suffix Arrays and Applications, with A. Gupta and J.S. Vitter, ACM-SIAM Symposium on Discrete Algorithms (SODA 2004).
A basis of tiling motifs for generating repeated patterns and its complexity for higher quorum, with N. Pisanti, M. Crochemore and M.-F. Sagot, International Symposium on Mathematical Foundations of Computer Science (MFCS 2003) [TR-03-02].
Optimal worst-case operations for implicit cache-oblivious search trees, with G. Franceschini, Workshop on Algorithms and Data Structures (WADS 2003).
Optimal cache-oblivious implicit dictionaries, with G. Franceschini, International Colloquium on Automata, Languages and Programming (ICALP 2003).
Search data structures for skewed strings, with P. Crescenzi and G.F. Italiano, International Workshop on Efficient and Experimental Algorithms (WEA 2003).
High-order entropy-compressed text indexes, with A. Gupta and J.S. Vitter, ACM-SIAM Symposium on Discrete Algorithms (SODA 2003).
Implicit dictionaries supporting searches and amortized updates in O(lg n lglg n) time, with G. Franceschini, ACM-SIAM Symposium on Discrete Algorithms (SODA 2003).
Text sparsification via local maxima, with P. Crescenzi, A. Del Lungo, E. Lodi, L. Pagli and G. Rossi, Theoretical Computer Science 304(1):341-364, 2003.
Implicit B-trees: New results for the dictionary problem, with G. Franceschini, J.I. Munro and L. Pagli, IEEE Symposium on Foundations of Computer Science (FOCS 2002).
Compressed Indexes for fast search in sequencs, with J.S. Vitter, keynote address at Joint Conference on Information Sciences (JCIS 2002).
Optimal deterministic protocols for mobile robots on a grid, with A. Pietracaprina and G. Pucci, Information and Computation 173(2) 132-142, 2002.

-:- MISCELLANEA

Contact me for some interesting programming contests:
Glossary for students (in Italian).
Weather forecast and webcam for PISA.
Fabrizio Luccio believes that this piece of great literature refers to me :-)
The old version of these pages is here.

"We can be us, just for one day" -- Heroes (by David Bowie & Brian Eno)