Colóquio de Matemática

Why does Computational Complexity (also) belong to a Mathematics department?

Sala 6.2.33, Ciências ULisboa (com transmissão via Zoom)

Por Bruno Loff (University of Porto).

The 2021 Abel prize in Mathematics was awarded to Avi Wigderson, a researcher in Computational Complexity. But why was he even eligible? Isn't Computational Complexity part of computer science?

In the talk, I will make the argument that Computational Complexity is a foundational mathematical discipline. For this purpose, I will give a survey of its history, starting with Hilbert's address to the World Congress of Mathematics in 1900, through Alan Turing's invention of the computer and the discovery and eventual formalization of the P vs NP problem. I will try to convince you that this is one of the most interesting unsolved mathematical problems of our time. I will then give a brief introduction to communication complexity and Karchmer-Wigderson games, as an approach to solving the area's fundamental problems, co-invented by Avi Wigderson.

Time permitting, I may sketch the state of the art and describe known barriers to solving the P vs NP problem, I may enumerate some broad applications of the field, I may describe an algebraic-geometric variant of the P vs NP problem, or we can do a back-and-forth in ask-me-anything style.

The talk will be very broad-scope, light-touch, and is directed at a general mathematical audience.


Transmissão via Zoom.

16h00
Departamento de Matemática | Ciências ULisboa
Cartaz do evento

Palestra por Francisco Lobo (CIÊNCIAS ULisboa / Instituto de Astrofísica e Ciências do Espaço), no âmbito do Encontro com a Astronomia.

Pormenor de mecanismo de relógio

Concerto no âmbito do programa Música na Universidade de Lisboa.

Orquestra

Concerto no âmbito do programa Música na Universidade de Lisboa.

Banner Ser Cientista

A 10.ª edição do Ser Cientista realiza-se entre 21 e 25 de julho - vem investigar connosco!

Estátua representativa da biodiversidade do planeta Terra

Seminário de Tese no âmbito do Doutoramento em Biologia e Ecologia das Alterações Globais, por Rita Pereira Eusébio.

Título e data da iniciativa

A iniciativa conta com a participação do MARE - Centro de Ciências do Mar e do Ambiente e do LASIGE Computer Science and Engineering Research Centre.

Aluna a utilizar um computador portátil

A Escola Doutoral Unite! Widening visa apoiar diretamente estudantes de doutoramento que realizem investigação numa das quatro áreas estratégicas selecionadas pelo projeto - as candidaturas decorrem até 26 de julho.

Pormenor de lâmpada

Candidaturas a decorrer de 01 a 30 de setembro.

Microplásticos no ocerano

O curso procura dar formação sobre a problemática da contaminação por detritos de plástico dos nossos ecossistemas, bem como alertar para os potenciais efeitos deletérios nos organismos, utilizando uma abordagem de ensino científico, com um discurso adequado a formandos sem formação científica - candidaturas até 03 de agosto.

Logótipo do evento, sobre fotografia dos Açores

Um simpósio internacional que reúne investigadores especializados em várias disciplinas (taxonomia, ecologia da vegetação, biogeografia, filogeografia, paleoecologia ou conservação da biodiversidade), focados na flora e vegetação terrestre e marinha da região da Macaronésia (Açores, Madeira, Selvagens, Canárias e Cabo Verde).

Quatro investigadores num laboratório

O curso visa capacitar investigadores, docentes e técnicos para integrar os princípios da economia circular em ambientes laboratoriais académicos - candidaturas até 16 de setembro.

Composição de imagens relativas à área das ciências forenses

O curso visa dotar os formandos com os conhecimento necessários à integração de equipas profissionais multidisciplinares nas áreas Médico-Legais e Forenses, em Laboratórios ou Serviços Médico-Legais e Forenses - candidaturas até 27 de julho.

Três investigadores num laboratório

O curso visa capacitar profissionais para aplicar os princípios da economia circular em ambientes laboratoriais industriais, promovendo práticas sustentáveis e eficientes - candidaturas até 17 de setembro.

Logótipo do evento

Um evento promovido pelo Departamento de Física da Faculdade de Ciências da ULisboa, com um duplo objetivo: valorizar a diversidade e excelência da formação dos doutorados e promover um espaço de diálogo direto entre empresas e estudantes.

Cientista a trabalhar com tubos de ensaio

Os participantes neste curso irão adquirir os conhecimentos essenciais à integração de equipas profissionais multidisciplinares na área das Análises Clínicas/Patologia Clínica, em laboratórios privados, públicos, hospitalares ou do Estado - candidaturas até 27 de julho.

Saída de campo (Geologia)

O curso, com candidaturas até 20 de julho, convida os professores do Ensino Básico e Secundário a explorar a Geologia a partir das rochas que afloram nas imediações da sua escola.

Gotas de água

O curso visa capacitar os formandos para a aplicação dos índices de qualidade ecológica utilizados na avaliação da qualidade ambiental em sistemas de transição, no âmbito da Diretiva Quadro da Água (DQA) - candidaturas até 31 de agosto.

Astronauta, banhado pela luz solar, no meio de uma floresta

Candidaturas até 30 de julho - um evento único, que reunirá estudantes de mestrado e doutoramento com investigadores e líderes da indústria de toda a Europa para uma experiência inesquecível.

Lupa e caneta sobre página com texto e gráfico

O curso visa dar formação inicial a estudantes de pós-graduação sobre o processo de escrita, submissão e publicação de trabalhos científicos, focando principalmente a publicação de artigos científicos em revistas internacionais com revisão por pares.

Iconografia relacionada com a temática do curso

O curso fornece uma exploração aprofundada de isótopos estáveis como uma ferramenta valiosa em Ecologia, usando assinaturas isotópicas para rastrear processos ecológicos e revelando insights sobre o ciclo de nutrientes e água, interações de espécies e condições ambientais em diversos ecossistemas e comunidades.

Composição de três imagens relativas à área da deteção remota

2.ª edição do curso, com candidaturas até 18 de outubro.

O evento pretende reunir investigadores que trabalhem sobre temas ligados à indústria e sobre património técnico e industrial, para uma reflexão prospetiva sobre o património industrial e atuais vias de colaboração no seu estudo, salvaguarda e preservação.

Computador portátil a projetar imagem de sequência biológica

O curso visa a aquisição de conhecimentos sobre as ferramentas bioinformáticas disponíveis para efetuar análises de sequências de DNA e proteínas, bem como a autonomia e espírito crítico na utilização dessas ferramentas. Procura igualmente desenvolver competências na utilização de software de bioinformática disponível gratuitamente na Internet e na interpretação do significado biológico dos resultados.

Bola de cristal colocada no solo

O curso tem como objetivo apresentar aos participantes um estado da arte atualizado sobre a diversidade da biota do solo e os papéis funcionais desempenhados pelos organismos do solo nos principais processos ecológicos.

A conferência visa reunir os principais especialistas no domínio da Imagiologia Médica por Micro-ondas (MMWI) e incluirá palestras, apresentações e pósteres de resumos revistos por pares e artigos de conferências, bem como workshops em áreas satélite de investigação com interesse para a investigação em MMWI.