Nicola Galesi
Nicola is an associate professor since 2001. He got a PhD at Universitat Politecnica de Catalunya, advised by Maria Luisa Bonet and holds an Italian habilitation as full professor in Mathematical Logic since 2012. Since March 22 he is with DIAG (Dept. of Computer, Control and Management Engineering ) in Sapienza, Rome, Italy. From 2005 to 2021 he was with the Department of Computer Science in Sapienza, and from 2001 to 2005 at Universitat Politecnica de Catalunya, in Barcelona. Before, he was researcher at Institute for Advanced Studies in Princeton (IAS) (00-01) and Postdoc at University of Toronto (02-03) in the theory group led by Stephen Cook and Toni Pitassi. In 2015 and 2021 visiting scientist at the Simons Institute for Theory of Computing UC-Berkeley and in 2015 at Tokyo Institute for Technology.
Computational Complexity and Logic in Computer Science.
Proof Complexity, SAT-Solving, Optimization.
Group testing and network tomography.
Selected publications
- Nicola Galesi, Leszek A. Kolodziejczyk, Neil Thapen. Polynomial Calculus Space and Resolution width. IEEE Foundations of Computer Science (FOCS) 2019, pp. 1325-1337
- Ilario Bonacina, Nicola Galesi. A framework for space complexity in algebraic proof systems. Journal of the ACM. 62(3),pp. 1–20. 2015
- Olaf Beyersdorff, Nicola Galesi, Massimo Lauria, Alexander Razborov. Parameterized Bounded-depth Frege is not optimal. ACM Transactions on Computation Theory (TOCT). 4(3), pp. 1–16 2012.
- Josh Buresh-Oppenheim, Nicola Galesi, Shlomo Hoory, Avner Magen, Toni Pitassi. Rank Bounds and Integrality Gaps for Cutting Planes Procedures. Theory of Computing. 2(1) pp. 65–90, 2006.
- Maria Luisa Bonet, Juan Luis Esteban, Nicola Galesi, Jan Johannsen. On the Relative Complexity of the Resolution Refinements and Cutting Planes Proof Systems. SIAM Journal on Computing. 30(5), pp. 1462–1484. 2000.
ACM Computing Review Most Notable paper in Theory of Computing for 2012, for the paper
Olaf Beyersdorff, Nicola Galesi, Massimo Lauria, Alezander Razborov. Parameterized Bounded-depth Frege is not optimal. ACM Transactions on Computation Theory (TOCT). 4(3), pp. 1–16 2012.