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 do Centro de Estatística e Aplicações da Universidade de Lisboa e do Centro de Matemática Computacional e Estocástica, por Miguel Pereira (Cogitars, UK).

Geometry and Physics Seminar, por Pedro M. Silva (CMAFcIO).

Seminário em Biologia Humana e Ambiente, por João Brandão (National Institute of Health Dr. Ricardo Jorge - INSA / Researcher at the Centre for Environmental and Marine Studies - CESAM_FCUL).

Título do evento, logótipos da ULisboa/DGES e fotografia de peças de xadrez

Sentes-te perdido/a em relação ao teu futuro académico/profissional? Ainda não sabes qual a melhor área a seguir ou como definir a tua carreira? Este workshop é para ti!

Roundtable by the 2nd year MSc students.

Logótipos de Ciências ULisboa/GAPsi e calendarização das palestras

Uma conversa sobre ti, alguém amigo ou apenas acerca de ansiedade.

Data Science Seminar, por Ana Filipa Rodrigues (LASIGE).

Logótipo do concurso

As candidaturas à 21.ª edição decorrem até 06 de dezembro.

Título da iniciativa, logótipos das entidades envolvidas e fotografias de dois jovens

Voa alto com o teu talento no Talent Bootcamp em CIÊNCIAS.

Logótipo do evento, sobre um fundo cor-de-rosa

Marcam presença neste concerto a Orquestra Sinfónica Juvenil, o Coro da Universidade de Lisboa (CUL) e o Coro do Instituto Gregoriano de Lisboa, com Direção de Christopher Bochmann.

Título/data/local do evento e fotografia de cantor

Concerto pelo Duo de canto e piano, no âmbito da Temporada Darcos, e que integra o programa Música na Universidade de Lisboa.

Seminário Doutoral III (Doutoramento em Biologia), por Susana Martins.

Seminário do Centro de Física Teórica e Computacional, por Emanuel Dutra (Instituto Português do Mar e da Atmosfera, Lisbon, Portugal).

Título do programa, fotografia de dois jovens e logótipo da Rede Alumni CIÊNCIAS

As candidaturas estão abertas até dia 09 de dezembro.

Título/data/local do evento e fotografia de autocarro

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

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 Joaquin Cavieres (University of Gӧttingen, Germany).

Fotografia do Professor Pedro Miranda

Lição de Jubilação "Wind and water: on-going research on climate processes".

Sessão de Natal em CIÊNCIAS

Uma iniciativa dedicada a sensibilizar toda a sociedade, em especial os jovens, para os desafios climáticos que enfrentamos e para o papel crucial que podem desempenhar na construção de um futuro sustentável. 

Título/data/local do evento e fotografia de António Sampaio da Nóvoa

A sessão será presidida por Sua Excelência O Presidente da República, Marcelo Rebelo de Sousa.

Conversas sobre a geologia rica e fascinante do Parque Natural Sintra-Cascais, com a participação de vários docentes de CIÊNCIAS.

Título "5th edition ULisses", sobre fotografia do mar

Apresentação de candidaturas até 15 de dezembro.

Um dia para aprender sobre produção caseira de cogumelos, da teoria à prática! Cada participante leva consigo um kit de cogumelos produzido nesta tarde e ainda todo o conhecimento para o fazer novamente de forma autónoma!

Título/data/local do evento e fotografia da oradora

TWIN2PIPSA Seminar, por Ana Vila Verde (University of Duisburg-Essen).

An annual meeting that aims to bring together Evolutionary Biologists working in Portugal and abroad in order to promote scientific cohesion and excellence. This meeting is a forum for scientists of all academic levels (from master students to principal investigators), to present their work and discuss, fostering new ideas and collaborations.

Páginas