Institute for Mathematics and its Applications (IMA)
University of Minnesota
Office: Lind Hall 351
Email: paolo (at) ima (dot) umn (dot) edu
Current Teaching: MATH 1272: Calculus II
- PhD in Computer Science, University of Chicago, advisor: Laszlo Babai (2011). Thesis: "Testing Isomorphism of Combinatorial and Algebraic Structures." pdf
- M.S. in Computer Science, University of Chicago (2007).
Masters Thesis: 2D Min-Filters with Polygons, pdf , ps.
- B.S. in Mathematics (with honors), University of Chicago (2005)
I am interested in a
broad range of topics in algorithms. I have worked on isomorphism
testing, approximation algorithms, algorithms relating to vision,
combinatorial problems, and wireless sensor networks. I am
particularly interested in exploring the connection between algorithms
and the combinatorial and algebraic structure of the problems. My
recent focus has been on analyzing models for random networks.
My curriculum (pdf)
- Teaching Assistant Prize, University of Chicago CS, 2010.
- Outstanding Student Fellowship, University of Chicago CS, 2008.
- Visiting student with Prof. Sanjeev Khanna at the University of
Pennsylvania (Summer 2008).
- Visiting student at the Paradise group, Caltech (Summer 2006).
- Summer Intern supported by SURF Program, Caltech(Summer 2005).
- Computing Beyond Silicon Summer School, Caltech (Summer 2004).
- REU program, University of Chicago (Summer 2003).
- 14th International Olympiad in Informatics. Member of the Italian Team (Korea, 2002).
- Conflict Analysis and Branching Heuristics in the Search for Graph Automorphisms
(with Hadi Katebi,
Karem A. Sakallah, and
Igor L. Markov).
Accepted, ICTAI 2013.
- Distinguishing Vertices in Inhomogeneous Random Networks.
Preprint available at: http://www.ima.umn.edu/preprints/pp2013/2419.pdf.
- On the minimum order of k-cop-win graphs
(with William Baird,
Anthony Bonato, Aaron Maurer, John McCauley, and Silviya Valeva).
Submitted for publication.
Preprint available at: http://www.ima.umn.edu/preprints/july2012/2405.pdf.
- Polynomial-Time Isomorphism Test for Groups with no Abelian Normal Subgroups
Babai, and Youming Qiao).
ICALP 2012 (pp. 51-62).
- Code Equivalence and Group Isomorphism
A. Grochow, and Youming Qiao).
SODA 2011 (pp. 1395-1408).
- Resource Minimization Job Scheduling (with Julia Chuzhoy),
2009 (pp. 70-83).
- Isomorphism of hypergraphs of low rank in moderately exponential
(with Laszlo Babai), FOCS 2008 (pp. 667-676).
- 2D Min-Filters with Polygons (with Pedro
In the 17th Fall Workshop on Computational Geometry, 2007.
- Anti-Jamming Schedules for Wireless Data Broadcast Systems
Alexander Sprintson and Jehoshua Bruck).
Proceedings of 2006 IEEE International Symposium on Information Theory
(ISIT), July 2006, Seattle, Washington (pp. 1856-1860).
Expanded version available as
TR ETR070 July 2005.
- Dagstuhl Seminar on: Exact Complexity of NP-hard Problems (seminar
Thore Husfeldt, Dieter Kratsch, Ramamohan Paturi, and Gregory
November 2010, Dagstuhl, Germany.
Combinatorics, Groups, Algorithms, and Complexity.
Conference in honor of Laci Babai's 60th birthday.
March 2010, The Ohio State University, Columbus, Ohio.
- Instructor, Summer 2009: CMSC 15200, Intro to
Computer Science 2, Summer 2009.
- TA, Winter 2006 and 2007: CMSC 27200: Theory of Algorithms
- TA, Spring 2006 and 2007: CMSC 15400: Introduction to Computer Systems
- TA, Autumn 2006, 2009 and 2010: CMSC 27100: Discrete
- TA, Winter 2010: CMSC 23700: Introduction to Computer
- TA, Winter 2011: CMSC 15200: Introduction to Computer