Nicola Galesi

Nicola Galesi serves as an Associate Professor in the Department of Computer, Control and Management Engineering (DIAG) at Sapienza University of Rome since 2022, following 17 years in Sapienza's Department of Computer Science (2005-2022). His academic journey began with an Associate Professorship at Universitat Politecnica de Catalunya (2001-2005) after postdoctoral positions at the Institute for Advanced Studies in Princeton (2000-2001) and University of Toronto (2002-2003) under Stephen Cook and Toni Pitassi.

His educational background features a PhD from Universitat Politecnica de Catalunya supervised by Maria Luisa Bonet, complemented by dual Italian habilitations as full professor in Mathematical Logic (2012) and Computer Science. These qualifications underpin his rigorous theoretical approach across research domains.

Galesi's research program centers on Computational Complexity and Logic in Computer Science, with specialized expertise in Proof Complexity (investigating resolution refinements and algebraic proof systems), SAT-Solving, Optimization, and applied domains like Group Testing and Network Tomography. His seminal work on space complexity in algebraic proof systems (JACM 2015) established foundational frameworks, while recent network tomography research develops mathematical models for node failure identification in communication networks using Boolean algebra and graph connectivity principles.

Analysis of his 15 most recent publications (2022-2025) reveals a cohesive research trajectory bridging theoretical proof complexity and practical network analysis. Key trends include depth lower bounds in stabbing planes for combinatorial principles, vertex-connectivity metrics for failure localization, and algebraic investigations of vanishing sums in polynomial calculus. His work consistently applies combinatorial principles to derive tight bounds across graph structures while advancing the theoretical understanding of proof systems through tensor isomorphism and roots of unity analyses.

His scientific recognition includes:

• ACM Computing Review Most Notable paper in Theory of Computing for 2012

Galesi mentors the next generation through PhD supervision of Massimo Lauria (2009), Ilario Bonacina (2015), and Fariba Ranjbar (2021), while hosting postdocs including Alan Skelley, Olaf Beyersdorff, and Massimo Lauria. His research is amplified through prestigious visiting positions at the Simons Institute for Theory of Computing (2015, 2021) and Tokyo Institute for Technology (2015), building on his foundational work at IAS Princeton and Toronto.

He actively shapes the theoretical CS landscape as organizer of the Sapienza LOC3 (Logic, Complexity, Combinatorics, Computability) seminar series and founder of the RaTLoCC workshops (Ramsey Theory in Logic, Complexity and Combinatorics). His editorial role for Logical Methods in Computer Science (LMCS) and program committee service for CIAC, IJCAI, and FSTTCS conferences demonstrate sustained community leadership beyond his core research and teaching responsibilities in Calculus, Mathematical Logic, and Computational Complexity.