Mathematical Logic Webinar

On logic and randomized computation

Transmissão através de Videoconferência

Por Melissa Antonelli (University of Bologna).

Interactions between logic and theoretical computer science have been deeply investigated in the realm of deterministic computation but, strikingly, when switching to the probabilistic framework, the literature does not offer much. The main goal of our study is precisely to start bridging this gap by developing inherently quantitative logics and investigating their relations with specific aspects of randomized models. This talk is conceived as an overview of our work (in particular, of ongoing research) and is bipartite. In the first part, I will introduce our quantitative counting propositional logics, which are basically obtained by endowing standard propositional systems with counting quantifiers, expressing the probability of the (argument) formula. I will show that the classical fragment, CPL, is strongly linked to complexity theory, as characterizing the full counting hierarchy. On the other hand, in the context of programming language theory, the intuitionistic counting logic, iCPL_0, provides the first probabilistic correspondence in the style of Curry and Howard In the second part of the talk, I will introduce the more expressive logic MQPA, the language of which is defined by extending that of PA with measure-quantifiers. This logic is strongly connected to probabilistic computation, as shown by some results, such as “randomized arithmetization”. Starting from this, we are also developing randomized bounded theories, in order to logically characterize probabilistic complexity classes, following the path delineated by Buss’ and Ferreira’s bounded arithmetics. (Part of this work, which is still in progress, has been conducted during my visiting period at NOVA University.)


Transmissão via Zoom.

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

Uma história divertida para os mais novos, cuja venda reverte 1€ para o Grupo Lobo.

Pormenor do catálogo da Mostra Bibliográfica

Mostra bibliográfica disponível de 03 de outubro a 30 de novembro de 2022.

Cartaz do evento

À conversa com Mário Felício, ex-aluno da Licenciatura em Bioquímica de Ciências ULisboa, atualmente a trabalhar na consultora Deloitte.

Fotografia de alunos de Ciências ULisboa

03 de outubro, Sala 6.1.36, pelas 15h00.

Banner do evento

Celebrando o início de um novo Ano Académico, esta sessão solene é um importante marco na vida académica da ULisboa e junta toda a sua Comunidade.

Geodiversidade

Palestra no âmbito das comemorações do Dia Internacional da Geodiversidade, por Carlos Marques da Silva (DG Ciências ULisboa).

This colloquium seeks to debate ideas from the arts, humanities and sciences on the process of empathy.

Imagem ilustrativa do curso, acompanhada de diversas informações

Um curso dirigido ao público geral e estudantes de arte ou ciência (a partir dos 16 anos), com interesse em desenho de observação, ilustração, e biologia, com ou sem experiência em desenho.

Banner do evento

No dia 6 de outubro, a ULisboa dá as boas-vindas aos seus estudantes na Cidade Universitária!

Banner do evento

Talk @LASIGE, por Bruno Loff (Faculdade de Ciências, Universidade do Porto).

Banner do evento

Participe até 12 de outubro / Submit you application until 12 October.

Banner do evento

Ciências ULisboa estará presente, de 13 a 16 de outubro, no Festival Internacional de Ciência - FIC.A

Cartaz do evento

Um evento repleto de atividades científicas, culturais e educativas, com jogos, demonstrações, palestras, entre muitas outras atividades. 

Research at the Faculty of Sciences

Join us on 26 October 2022 for the 4th edition of Ciências Research Day.