A Ihara-Bass Formula for Non-Boolean Matrices and Strong Refutations of Random CSPs
- LecturerProf. Luca Trevisan (Department of Computing Sciences, Bocconi University)
Host: Kai-Min Chung - Time2023-01-11 (Wed.) 15:00 ~ 16:00
- LocationAuditorium 101 at IIS new Building
Abstract
We define a notion of non-backtracking operator for general weighted graphs, including graphs with negative weights, and prove a Ihara-Bass formula for it. Previously these notions were known only for unweighted graphs.
We use this theory to prove new results on strong refutations of random instances of 3SAT and of other constraint satisfaction problems with an odd number of variables per constraint.
(Joint work with Tommaso D'Orsi)
We use this theory to prove new results on strong refutations of random instances of 3SAT and of other constraint satisfaction problems with an odd number of variables per constraint.
(Joint work with Tommaso D'Orsi)
BIO
Luca Trevisan is a Professor of Computer Science at Bocconi University, where he holds the Invernizzi Foundation Chair in Computer Science. Luca received his Dottorato (PhD) in 1997, from the Sapienza University of Rome, working with Pierluigi Crescenzi. After graduating, Luca was a post-doc at MIT and at DIMACS, and he was on the faculty of Columbia University, U.C. Berkeley, and Stanford, before returning to Berkeley in 2014 and, at long last, returning to Italy in 2019.
Luca's research is in theoretical computer science, with a focus on computational complexity, on the analysis of algorithms, on the foundations of cryptography, and on topics at the intersection of theoretical computer science and pure mathematics.
Luca is a Fellow of the ACM and a member of the Accademia Nazionale delle Scienze Detta dei XL, the Italian National Academy of Science. He received the 2000 Oberwolfach Prize, the 2000 Sloan Fellowship and an NSF CAREER Award. He was an invited speaker at the 2006 International Congress of Mathematicians. In 2019, he received an ERC Advanced Grant. He is currently serving a five-year term on the committee that assigns the Turing Award.
https://lucatrevisan.github.io/
Luca's research is in theoretical computer science, with a focus on computational complexity, on the analysis of algorithms, on the foundations of cryptography, and on topics at the intersection of theoretical computer science and pure mathematics.
Luca is a Fellow of the ACM and a member of the Accademia Nazionale delle Scienze Detta dei XL, the Italian National Academy of Science. He received the 2000 Oberwolfach Prize, the 2000 Sloan Fellowship and an NSF CAREER Award. He was an invited speaker at the 2006 International Congress of Mathematicians. In 2019, he received an ERC Advanced Grant. He is currently serving a five-year term on the committee that assigns the Turing Award.
https://lucatrevisan.github.io/