Mathematical Logic Seminar

Towards New Characterizations of Parallel Complexity Classes

Videoconferência

Por Melissa Antonelli (University of Helsinki).

Implicit computational complexity is an active area of theoretical computer science, aiming to provide machine-independent characterizations of relevant complexity classes. One of the seminal works in this field appeared in 1964, when Cobham introduced a function algebra closed under bounded recursion on notation and able to capture FP, the class of functions computable in polynomial time. Since then, several complexity classes have been characterized using limited recursion schemas. Recently, an elegant algebra was defined by Bournez and Durand, who, in 2019, showed that ordinary differential equations (ODEs) offer a natural tool for algorithmic design and characterized FP via a special ODE schema. The overall goal of our study is precisely that of generalizing this approach to parallel computation and of providing (possibly uniform) ODE-style characterizations for small circuit classes. In particular, in this talk I will present the global aim and methodology at the basis of our in progress study and sketch our first result, namely our proposal for an original characterization of AC0 due to ODEs.

[Joint work with A. Durand and J. Kontinen]


Transmissão via Zoom.

16h00
CMAFcIO - Centro de Matemática, Aplicações Fundamentais e Investigação Operacional

Mathematical Logic Seminar, por Luís Cruz-Filipe (University of Southern Denmark).

Seminário Doutoral em Ciências do Mar, por Pedro Nunes.

Designação dos prémios, sobre uma imagem abstrata em tons cor de laranja

As candidaturas decorrem até 23 de fevereiro, com uma nova metodologia de avaliação.

Título/data/local do evento, logótipo da RedeMov e fotografia de torniquete de acesso a meio de transporte

Evento no âmbito do Ciclo de Conferências "Conversas à 6.ª", promovido pela redeMOV da Universidade de Lisboa.

Fauna e flora, investigação e educação, pela lente de cientistas e jovens biólogos.

Um convite à descoberta da vida na Serra de Grândola.

Pormenor de homem a folhear um livro

M50 - Programa de Formação Universitária para Maiores de 50 anos.

Seminário do Centro de Física Teórica e Computacional, por Pedro Jorge (Departamento de Física, Faculdade de Ciências, Universidade do Porto, and Centro de Fotónica Aplicada do INESC TEC, Portugal).

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 Bruno Santos (Stockholm University, Sweden).

Seminário Doutoral II (Doutoramento em Biologia), por Ana Sofia Lopes.

Fotografia de árvores sem folhas e de bancos de jardim

Estudantes de pós-graduação em Matemática da Faculdade de Ciências da ULisboa falam, de forma descontraída e informal, sobre o seu trabalho.

Fotografia de sinal identificativo de vinha

Apresentação de candidaturas até 28 de fevereiro.

Hi-Phi Seminar, por Ana Simões (CIUHCT/Ciências) e Ana Matilde Sousa (CIEBA/FBAUL).

Conferência do Centro Interuniversitário de História das Ciências e da Tecnologia, por Luís Campos Ribeiro (CIUHCT, Ciências ULisboa).

Título/data/local do evento, logótipo do projeto e fotografia da oradora

Seminário TWIN2PIPSA, por Sophie Jackson (Yusuf Hamied Department of Chemistry, University of Cambridge).

Título do evento, sobre uma fotografia do Large Hadron Collider

The objective of the course is to introduce the physics, analysis methods and results on the physics areas covered by the LHC experiments.

Theory of Computing Seminar, por Mateusz Skomra (LAAS/CNRS).

Colóquio de Matemática, por José Francisco Rodrigues (DM-Ciências ULisboa).

Título/data/local do evento e logótipos dos organizadores

O Departamento de Matemática e o Núcleo de Estudantes de Matemática e Matemática Aplicada associam-se às celebrações do Dia Internacional da Matemática.

Logótipo do Dia Internacional da Matemática, sobre um fundo branco

Atividades a decorrer em Ciências ULisboa nos dias 13 e 14 de março.

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 Gustavo Soutinho (Faculdade de Economia da Universidade do Porto - FEP e Instituto Superior de Saúde Pública da Universidade do Porto - ISPUP).

Mão humana a interagir com um ecrã virtual

Novos prazos de submissão de candidaturas a projetos IC&DT e PeX.

Fotografia de participantes numa anterior edição da Jobshop Ciências

O maior evento de empregabilidade de Ciências, a decorrer nos dias 09 e 10 de abril.

23 de abril de 2024 assinalamos o 113.º aniversário da Faculdade de Ciências da Universidade de Lisboa.

Título e data do evento, inseridos em fotografia de cinco jovens em contexto de investigação

Pré-inscrições já disponíveis!

Páginas