Theory of Computing Seminar

Smoothed analysis of deterministic discounted and mean-payoff games

Sala 6.1.25, Ciências ULisboa

Por Mateusz Skomra (LAAS/CNRS).

Deterministic turn-based discounted and mean-payoff games are fundamental classes of games with an unsettled complexity. They belong to the complexity classes NP and coNP, but are not known to be polynomial-time solvable. Furthermore, they are at the bottom of a hierarchy of complexity classes that stratifies the NP search problems. Despite these properties, the problem of solving turn-based games efficiently has been open for 35 years. Nevertheless, even though we do not know how to solve these games in polynomial time in the worst case, practical experiments suggest that solving random games is easy. More precisely, the policy iteration methods, which can take exponentially many steps in the worst case, converge quickly to the solution when the weights of the game are taken at random. The aim of my talk is to give an explanation of this phenomenon using the framework of "smoothed analysis" introduced by Spielman and Teng to explain the real-world efficiency of the simplex method. We prove that if the weights of a turn-based deterministic game are perturbed by a Gaussian noise, then the resulting randomized problem can be solved efficiently by a variant of a policy iteration method. In the talk, I will give an introduction to turn-based discounted and mean-payoff games, explain the basic algorithms that are used to solve them, and finish by discussing the smoothed analysis result. This talk is based on a joint work with Bruno Loff.

14h00

Nos dias 24 e 25 de maio, o Museu Nacional de História Natural e da Ciência celebra o Dia de África com diversas atividades gratuitas.

Technovation Girls Challenge Portugal - Final

A 24 de maio, CIÊNCIAS recebe 400 participantes para o evento final do Technovation Girls Challenge Portugal. O evento desafia mais de 100 jovens raparigas, dos 8 aos 18 anos a desenvolverem soluções tecnológicas para problemas reais das suas comunidades, incentivando-as a aprender sobre ideação, programação, comunicação e empreendedorismo.

Seminário do Instituto de Astrofísica e Ciências do Espaço, por Pier-Stefano Corasaniti (Observatoire de Paris-Meudon, France).

Seminário de Lógica Matemática, por Antonio Piccolomini D'Aragona (University of Tübingen/University of Siena).

Seminário do Centro de Física Teórica e Computacional, por Hugo Terças (Departamento de Física do Instituto Superior de Engenharia de Lisboa, Instituto Politécnico de Lisboa / Instituto de Plasmas e Fusão Nuclear, Instituto Superior Técnico, Universidade de Lisboa, Portugal).

Um programa estruturado que combina discussões em grupo, exploração de carreira e workshops informativos, com inscrições até 23 de maio.

Seminário no âmbito do Doutoramento em Biologia e Ecologia das Alterações Globais, por Pierina Jocelyn Mendoza Yengle.

Logótipo do EVM 2025

O objetivo é proporcionar a estudantes de todo o país - que estejam a concluir o 2.º ou 3.º ano de licenciaturas em Matemática, Física ou áreas afins - a oportunidade de participar num projeto de investigação com a duração de duas semanas - candidaturas até 28 de maio.

Uma oportunidade para fortalecer a cultura de segurança e bem-estar em CIÊNCIAS.

Cartaz do filme "O Melhor dos Mundos"

A 29 de maio o filme "O Melhor dos Mundos” é exibido numa sessão especial em CIÊNCIAS, promovida pela FCiências.ID e o Instituto Dom Luiz. Após a projeção do filme, realiza-se uma mesa redonda com quatro especialistas em Sismologia, que responderão a perguntas do público.

Uma oportunidade única para interagir com a comunidade global de computação científica.

Logótipo Moodle

Ação de formação para docentes e investigadores de CIÊNCIAS.

Copilot Chat

Nesta sessão, serão exploradas as funcionalidades e benefícios do Microsoft 365 Copilot Chat de forma personalizada à comunidade académica de CIÊNCIAS.

Luís Saraiva (Ciências ULisboa) é o coordenador nacional do evento.

Comemoração do Dia Mundial da Segurança dos Alimentos em CIÊNCIAS.

Logótipo Mentimeter

Ação de formação para docentes e investigadores de CIÊNCIAS.

Título/data/local do evento e iconografia representativa de energias renováveis

Junta-te a esta revolução energética e faz a diferença!

Neste curso ficarás a saber como te podes tornar um permacultor eficiente, produtivo e consciente! O curso está preparado para iniciantes na prática de permacultura.

Formação - Cultivar em Permacultura.

Pessoas a interagirem em frente a um computador portátil

As inscrições para a edição de 2025 da formação decorrem até às 17h do dia 23 de maio.

Químico a escrever fórmulas num quadro

Curso acreditado para efeitos de progressão na carreira dos professores do Ensino Básico e Secundário do Grupo 510 (CCPFC/ACC-118288/22), com candidaturas até 18 de maio.

Curso destinado a estudantes de Mestrado e de Doutoramento, bem como a profissionais que desenvolvam investigação científica na área da saúde.

Título/data/local do evento e fotografia do mar

Quais são os conceitos-chave para enfrentar os atuais desafios marinhos e costeiros? 

Representação de programação R

This course aims at providing students with basic knowledge of R programming, allowing them to manipulate and visualize data with R.

The conference focuses on "Algebra and its role in Computer Science", with special emphasis on the areas of study related to the work of M. V. Volkov, such as semigroups and automata.

Páginas