Paolo Codenotti
Postdoctoral Associate
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
Education:
 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 MinFilters with Polygons, pdf , ps.
 B.S. in Mathematics (with honors), University of Chicago (2005)
Research Interests:
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)
Awards:
 Teaching Assistant Prize, University of Chicago CS, 2010.
 Outstanding Student Fellowship, University of Chicago CS, 2008.
Activities:
 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).
Publications:
 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 kcopwin graphs
(with William Baird,
Andrew Beveridge,
Anthony Bonato, Aaron Maurer, John McCauley, and Silviya Valeva).
Submitted for publication.
Preprint available at: http://www.ima.umn.edu/preprints/july2012/2405.pdf.
 PolynomialTime Isomorphism Test for Groups with no Abelian Normal Subgroups
(with Laszlo
Babai, and Youming Qiao).
ICALP 2012 (pp. 5162).
 Code Equivalence and Group Isomorphism
(with Laszlo
Babai, Joshua
A. Grochow, and Youming Qiao).
SODA 2011 (pp. 13951408).
 Resource Minimization Job Scheduling (with Julia Chuzhoy),
APPROX
2009 (pp. 7083).
Full version.
 Isomorphism of hypergraphs of low rank in moderately exponential
time
(with Laszlo Babai), FOCS 2008 (pp. 667676).
 2D MinFilters with Polygons (with Pedro
Felzenszwalb).
In the 17th Fall Workshop on Computational Geometry, 2007.
 AntiJamming Schedules for Wireless Data Broadcast Systems
(with
Alexander Sprintson and Jehoshua Bruck).
In
Proceedings of 2006 IEEE International Symposium on Information Theory
(ISIT), July 2006, Seattle, Washington (pp. 18561860).
Expanded version available as
Caltech
TR ETR070 July 2005.
Invited Talks:
 Dagstuhl Seminar on: Exact Complexity of NPhard Problems (seminar
10441).
Thore Husfeldt, Dieter Kratsch, Ramamohan Paturi, and Gregory
Sorkin organizers.
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.
Teaching:
 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
Mathematics
 TA, Winter 2010: CMSC 23700: Introduction to Computer
Graphics
 TA, Winter 2011: CMSC 15200: Introduction to Computer
Science 2