Nicola Galesi
Dipartimento d i Ingegneria Informatica, Automatica e Gestionale "Antonio Ruberti"Via Ariosto 25, 00185 Roma, Italy
room: A202tel:email: lastname[TA]diag[TOD]uniroma[TOD]itoffice hours: app by email.
Embedded Files
bio
bio
Nicola is an associate professor since 2001. He holds a PhD (00) from Universitat Politecnica de Catalunya, advised by Maria Luisa Bonet and Italian habilitations as full professor in Mathematical Logic and Computer Science.
From 2005 Nicola is in Sapienza, now a t DIAG (Dept. of Computer, Control and Management Engineering "A. Ruberti" ) in Rome. He teaches: Calculus, Mathematical Logic and Computational Complexity.
From 2001 to 2005 Nicola was associate professor at Universitat Politecnica de Catalunya, in Barcelona. Before 2001 he was a researcher at School of Mathematics of the Institute for Advanced Studies in Princeton and Postdoc at University of Toronto (2002-2003).
In 2015 and 2021 Nicola was visiting scientist at Simons Institute for Theory of Computing. UC-Berkeley and in 2015 at Tokyo Institute for Technology.
research
research
Interests: Computational Complexity and Logic in Computer Science. Proof Complexity, SAT-Solving, Optimization. Group testing and network tomography.
PhD Advising: Massimo Lauria (09), Ilario Bonacina (15), Fariba Ranjbar (21)
Postdocs: Alan Skelley, Olaf Beyersdorff, Massimo Lauria, Valentino Delle Rose.
Citation: DBLP, Google scholar
news
news
Sep 28-Oct 6: Off at Clay Mathematics Institute (Oxford) workshop: "P vs NP and Complexity Lower Bounds"
Sep 25. Paper with Leszek Kołodziejczyk and Neil Thapen: "Polynomial Calculus Space and Resolution Width". Accepted to Theory of Computing.
Sep 25. Paper with Tony Huynh and Fariba Ranjbar: "Cluster deletion and clique partitioning in graphs with bounded clique number". On Arxiv.
Sep 25: Paper with Fariba Ranjbar: "The complexity of Boolean Failure Identification", accepted to Theoretical Computer Science.
Aug 10-14, 25.Off at Oxford Workshop "Proof Complexity"
July 17, 2025 LoC3 Seminar Giovanni Varricchione: Logic, Automata and Reinforcement Learning
12 Jun 25, LoC3 Seminar: Gabriele Buriola: Ordinal analysis of Well-Ordering Principles and Well Quasi-Orders Closure Properties
27 March 25, LoC3 Seminar: Jacobo Toràn: The Complexity of Graph Isomorphism Formula.
04 Mar 25: Computational Complexity course. Master in Engineering in Computer Science. Starting date : Tue 4 March. A4 -DIAG
31 Jan 25: PhD Course: Foundations of SAT-Solving (Info and Enroll)
selected papers
selected papers
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.
Josh Buresh-Oppenheim, Nicola Galesi, Avner Magen, Toni Pitassi. Shlomo Hoory. Rank Bounds and Integrality Gaps for Cutting Planes Procedures. Theory of Computing. 2(1) pp. 65–90, 2006.
Ilario Bonacina, Nicola Galesi. A framework for space
complexity in algebraic proof systems. Journal of the ACM. 62(3),pp. 1–20. 2015
activities
activities
Organizer of the Seminar series in Sapienza. Sapienza LOC3 (Logic, Complexity, Combinatorics, Computability)
Editor for Logical Methods in Computer Science (LMCS)
Founder/Organizer of RaTLoCC workshops "Ramsey Theory in Logic, Combinatorics and Complexity" (11,12,18,24).
Recent Program Committee: CIAC23, IJCAI22, IJCAI21, FSTTCS17.
Page updated
Report abuse