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
Logótipos do Concurso Nacional para Jovens Cientistas e Investigadores e da Fundação da Juventude

Candidaturas até 15 de abril.

Logótipo e data do evento

Pensar global, agir local - Semana da Sustentabilidade Ciências ULisboa.

Título/data/local do evento

Lisbon AI Seminar, por Mattia Petrolo (CFCUL/RG1).

Seminário do Centro de Estatística e Aplicações da Universidade de Lisboa e do Centro de Matemática Computacional e Estocástica, por Taban Baghfalaki (Bordeaux University, Bordeaux, France).

Seminário do Departamento de Física de Ciências ULisboa, por Bruno Barros (IA).

Seminário Helena Avelar de Astronomia e Astrologia Antiga, por Levente László (Eötvös University).

BioISI Research Seminar, por Miguel Machuqueiro (BioISI - Ciências ULisboa).

Título/data/local do evento e pormenor de pintura representando uma mulher

Reasoning Seminar, por José Manuel Mestre (University of St. Andrews/Stirling).

Fotografia de três pessoas a apontarem para o teclado/ecrã de computador portátil

Workshop de participação gratuita, mediante inscrição até 16 de abril.

Hi-Phi Seminar, por Ignacio García-Pereda (CIUHCT), Silvia Di Marco (CFCUL), Hugo Soares (CIUHCT) e João L. Cordovil (CFCUL).

Seminário do Laboratório de Instrumentação e Física Experimental de Partículas, por Henrique Carvalho (LIP Minho).

Título/data/local do evento e imagem de arquivo do MUHNAC

Os estudantes de Ciências contra o regime ditatorial e colonialista - 1968-1974.

Título/data do evento, logótipo do projeto Ciências em Harmonia e título "Ninguém te vai amar como eu."

Uma sessão dinamizada e conduzida pelo GAPsi, a decorrer pelas 13h do dia 18 de abril.

O MUHNAC associa-se, uma vez mais, a estas comemorações, com um programa de atividades gratuitas subordinadas ao tema da edição de 2024 "Catástrofes e conflitos à Luz da Carta de Veneza".

Logótipos da Sociedade Portuguesa de Física e da comemoração do respetivo Jubileu

Nesta sessão, organizada em parceria com o NFEF-FCUL, será lançado um postal dos CTT evocativo dos 50 anos da SPF e será feito o lançamento do volume 47, n.º 1 da Gazeta de Física.

Mathematical Logic Seminar, por Jaime Ramos (IST - Universidade de Lisboa).

Seminário Doutoral I (Doutoramento em História e Filosofia das Ciências), por Joana Lima de Oliveira.

O programa inclui a atribuição de cartas de reconhecimento de mérito aos melhores alunos que concluíram a licenciatura em Geologia ano letivo 2023, seguida da apresentação do vídeo da excursão final integradora do Mestrado em Geologia da FCUL.

Logótipo de Ciências ULisboa, título "Dia de Ciências 2024" e frase apelando à participação

23 de abril. Virgínia Dignum, especialista Nações Unidas para IA, é oradora convidada.

Título/data/local do evento e logótipos das entidades organizadoras

An event specifically focused on technicalities & Data Science.

Comemorações do 30.º aniversário da VicenTuna - Tuna da Faculdade de Ciências da Universidade de Lisboa.

Título "Bolsas de Doutoramento Unite! ULisboa", logótipos das entidades promotoras e fotografia de jovem investigadora a utilizar um laptop na esplanada de um café

O 3.º concurso decorre até 30 de abril.

Talk @LASIGE, por Fernando Gallego Donoso (University of Malaga, Computational Intelligence in Biomedicine - ICB).
 

This 7th edition will once again gather specialists in the field of Combinatorial Optimization from several countries to present and discuss recent research work.

O encontro reúne cientistas, profissionais e estudantes de diferentes áreas e regiões do país focados em desenvolver a investigação marinha, em linha com a Década da Ciência Oceânica para o Desenvolvimento Sustentável, proclamada pelas Nações Unidas (2021-2030).

Páginas