Contacts

Nicola Galesi Dipartimento di Ingegneria Informatica, Automatica e Gestionale "Antonio Ruberti"Via Ariosto 25, 00185 Roma, Italy
room: A202tel:email: lastname[AT]diag.uniroma1.itoffice hours: app by email/thu 11-13.

bio

Nicola is an associate professor since 2001. He holds a PhD (00) from Universitat Politecnica de Catalunya, advised by Maria Luisa Bonet and holds an Italian habilitation as full professor in Mathematical Logic since 2012.

Since 22 he is with DIAG (Dept. of Computer, Control and Management Engineering "A. Ruberti" ) in Sapienza, in Rome.

From 05 to 21 he was with the Department of Computer Science, always in Sapienza.

From 01 to 05 Nicola was associate professor at Universitat Politecnica de Catalunya, in Barcelona. Before (01) he was a researcher at School of Mathematics of the Institute for Advanced Studies in Princeton and Postdoc at University of Toronto (02-03).

In 15 and 21 Nicola was visiting scientist at Simons Institute for Theory of Computing. UC-Berkeley and in 15 at Tokyo Institute for Technology.

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.

Citation: DBLP, Google scholar

news

Sep 22. Paper accepted to Mathematical Foundations of Computer Science (MFCS 22). On Vanishing Sums of Roots of Unity in Polynomial Calculus and Sum-Of-Squares. With I. Bonacina and M.Lauria

Jul 22. Paper accepted to Annals of Pure and Applied Logic. Bounded-depth Frege complexity of Tseitin formulas for all graphs. With D. Itsykson, A.Riazanov, A Sofronova.

Jun-Jul 22. Logic Colloquium 2022. I co-organized the special session in Computer Science Logic.

Jul 22: Workshop Mathematical Approaches to Lower Bounds: Complexity of Proofs and Computation. (International Centre for Mathematical Sciences, Edinburgh)

Jun-Jul 22: Workshop Complexity Theory with a human face (Czech Academy of Sciences, Prague)


Mar22. Paper published on Theoretical Computer Science: Tight bounds to localize failure nodes on trees, grids and through embeddings under boolean network tomography. With Fariba Ranjbar
Jan22. Paper accepted to STACS 22. Depth lower bounds in Stabbing Planes for combinatorial principles. With S. Dantchev, A. Ghani, B. Martin.

selected papers

  1. 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.

  2. 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.

  3. Ilario Bonacina, Nicola Galesi. A framework for space complexity in algebraic proof systems. Journal of the ACM. 62(3),pp. 1–20. 2015

activities

Editor for Logical Methods in Computer Science (LMCS)

Founder/Organizer of RaTLoCC workshops "Ramsey Theory in Logic, Combinatorics and Complexity" (11,12,18).

Recent Program Committee: IJCAI22, IJCAI21, FSTTCS17.