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

Seminário de Lógica Matemática, por Luís Pereira (Universidade de Lisboa).

Planta

As candidaturas terminam a 20 de março, estando previstos vários eventos de matchmaking para ajudar os participantes a encontrar parceiros para os seus projetos.

Jardins que dialogam, Jardins que se ouvem.

Horta Solar

A 21 de março, CIÊNCIAS celebra o segundo aniversário da Horta Solar, um projeto pioneiro que alia a produção de alimentos à geração de energia limpa.

Pintura abstrata em tons de azul, laranja e amarelo

Seminário do Centro de Física Teórica e Computacional, por Mariana Oliveira (ICECO - Aveiro Institute of Materials, University of Aveiro, Portugal).

Representação de folhas de árvores

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

Logótipo C-Academy

Combinando teoria e prática, o curso prepara os alunos para compreenderem a infraestrutura digital moderna e aplicarem esses conhecimentos em cenários reais, com foco em arquiteturas robustas, deteção de erros e soluções para redes de alto desempenho.

Alunos de CIÊNCIAS

Uma iniciativa gratuita, dirigida aos estudantes do 1.º e 2.º ciclo de estudos de CIÊNCIAS, com inscrições até 20 de março.

Título "Cybersecurity Executive Program Edição 2025", sobre um fundo em tons de verde

Adotar boas medidas e práticas de Cibersegurança é fundamental nos dias de hoje, para qualquer empresa, para proteger a integridade, confidencialidade e disponibilidade de dados sensíveis e pessoais, reduzindo o risco de ataques e fraudes.

Título/data/local do evento e representação de floresta

Esta é a altura certa para fazer os últimos preparativos para uma agrofloresta viçosa e produtiva que nos dará fruta, biodiversidade e sombra nos meses mais quentes.

Logótipo da Semana da Sustentabilidade

O foco da da SDS’25 é abrir espaço à reflexão sobre como as nossas ações, hoje, poderão influenciar o amanhã, sendo, assim, o lema desta Edição “Pelo Futuro, o Amanhã começa Hoje“.

Fotografia de criança a observar plantas com uma lupa

This course aims to explore ways of communicating science to non-specialized audiences, such as policy makers, industry, general public (including students and teachers), through their engagement and participation in citizen science activities.

Sala de aula

Curso creditado para efeitos de progressão na carreira dos professores do Ensino Secundário dos grupos 500 e 550, com candidaturas até 25 de março.

Reitoria da ULisboa

O ato eleitoral decorrerá nos dias 31 de março e 01 de abril de 2025.

Fotografia de coleção de insetos

The course includes several case studies of insect adaptation, and the most recent overview on insect evodevo, plasticity, ecophysiological responses and conservation under global change.

Título/data/local do evento e fotografia aérea de vias urbanas

Conferência da redeMOV, por Gabriel Costa Valença.

A leading venue for presenting and discussing the latest research, industrial practice and innovations in dependable and secure computing.

O maior evento de empregabilidade de CIÊNCIAS, a decorrer nos dias 08 e 09 de abril.

Título do evento

A collaborative initiative supported by five Portuguese research centers, aimed at strengthening and connecting the geometry research community in Portugal.

Título/data/local do evento e fotografia da cidade de Lisboa

The conference aims to bring together students and young researchers working in Mathematics, Statistics, and Applications with a view to fostering discussions and collaborations amongst participants.

Título "Para um ensino humanista das ciências" e logótipos das entidades organizadoras

O evento tem como tema principal "Para um ensino humanista das ciências" e conta com a participação de vários professores de CIÊNCIAS.

Microplásticos em suspensão no oceano

O curso tem como objetivo 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 - candidaturas até 22 de março.

Banner do Dia de Ciências 2025

A 29 de abril assinalamos o 114.º aniversário de CIÊNCIAS.

Junte-se a nós no Grande Auditório de CIÊNCIAS para uma tarde de celebração que reúne toda a comunidade da Faculdade.

Fotografia de fábrica a emitir poluição para a atmosfera

The course aims at enabling the participants to use different methods to measure the impacts of pollutants on ecosystems.

Páginas