O Programa de Pós-graduação em Ciência da Computação (PPGCC) da UFMG irá promover, nesta sexta-feira, 19, na sala 2077 do Instituto de Ciências Exatas (ICEx), mais uma palestra como parte da série de seminários avançados. A palestra será proferida pelo professor das Universidades de Copenhague e de Lund, Jakob Nordström, que tratará o tema “Complexity Theory for Real-World Computation”. O evento é aberto ao público interessado e não há necessidade de inscrição prévia. Abaixo, em inglês, mais informações sobre a palestra e sobre o professor:
ABSTRACT
Boolean satisfiability (SAT) and other NP-complete problems have been intensely studied for over 50 years, and a rich and mathematically sophisticated body of work has been developed exploring the consequences of the hypothesis that these problems are not solvable in polynomial time or are even exponentially hard. However, practitioners mostly think of SAT as an easy problem, and there are very efficient applied algorithms that can often solve formulas with even millions of variables in close to linear time. It is hard to think of a starker disconnect between theory and practice.
In this talk, we will discuss how computational complexity tools can be used to analyse algorithms that are widely used in practice. In addition to proving unconditional exponential lower bounds on running time, this study can also lead to ideas for how to improve such algorithms, and how to enhance them to produce machine-verifiable certificates of correctness for their computations.
Biographic Sketch
Jakob Nordström obtained his Master of Science degree in Computer Science and Mathematics at Stockholm University in 2001, and his PhD degree in Computer Science at KTH Royal Institute of Technology in 2008. During 2008-2010 he was a postdoctoral researcher at the Massachusetts Institute of Technology (MIT), after which he returned to KTH in 2011, where he became an associate professor and received his Docent degree (habilitation) in 2015. In 2019 he moved to the University of Copenhagen, where he is now a full professor, and since 2020 he also has a part-time affiliation with Lund University.
In 2006 Jakob Nordström received the best student paper award at 38th ACM Symposium on Theory of Computing (STOC ’06), and his PhD thesis received the Ackermann Award 2009 for “outstanding dissertations in Logic in Computer Science” from the European Association for Computer Science Logic. More recently, in 2022 he received a distinguished paper award at the 36th AAAI Conference on Artificial Intelligence (AAAI ’22) and a best paper award at the 25th International Conference on Theory and Applications of Satisfiability Testing (SAT ’22). During the years 2018-2023 Jakob Nordström was a member of the Young Academy of Sweden, where he served on the board 2020-2023. His current research is mainly funded by grants from the Independent Research Fund Denmark, the Swedish Research Council, and the Wallenberg AI, Autonomous Systems and Software Program (WASP).
In 1997-1998, Jakob Nordström served as a military interpreter at the Swedish Armed Forces Language Institute (Försvarets tolkskola), graduating as the best student of the 1998 class. In parallel with his studies and later his research, he worked for a number of years as a Russian interpreter, engaged among others for His Majesty the King of Sweden and the Swedish Prime Minister. He also has a Diploma in Choir Conducting with extended Music Theory from the Tallinn Music Upper Secondary School, Estonia. During the period 1994-1999, he was the artistic director of Collegium Vocale Stockholm, a vocal ensemble performing mainly Renaissance and Baroque music.
