Seminário

Exponential Separation Between Powers of Regular and General Resolution Over Parities

Sala 8.2.02, Ciências ULisboa

Por Pavel Dvořák (TIFR / Charles University).

Proving super-polynomial lower bounds on the size of proofs of unsatisfiability of Boolean formulas using resolution over parities is an outstanding problem that has received a lot of attention. Very recently, Efremenko, Garlík, and Itsykson [STOC'24] proved the first exponential lower bounds on the size of ResLin proofs that were additionally restricted to be bottom-regular. Extending their work, I'll show that there are formulas for which such regular ResLin proofs of unsatisfiability continue to have exponential size even though there exist short proofs of their unsatisfiability in ordinary, non-regular resolution. This is the first super-polynomial separation between the power of general ResLin and that of regular ResLin for any natural notion of regularity.

This is joint work with Sreejata Kishor Bhattacharya and Arkadev Chattopadhyay. 

12h00
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é 22 de novembro.

Grupo de estudantes

27 de novembro: A Cerimónia contará com a intervenção do Secretário de Estado Adjunto e do Trabalho, Adriano Rafael Moreira.

O evento tem como objetivo aproximar a ciência da sociedade, promovendo o diálogo aberto e a reflexão conjunta sobre temas ligados à mente, cérebro e cognição.

Título "Gostarias de realizar uma mobilidade Erasmus+?" e fotografia de estudante

Candidaturas de 01 a 31 de dezembro - as sessões informativas têm início a 19 de novembro.

Cesto com legumes

O curso tem como principal objetivo capacitar para a implementação e gestão sustentável de espaços de cultivo nas cidades, promovendo a segurança alimentar e a autonomia na produção de alimentos - candidaturas até 02 de novembro.

Logótipo C-Academy

O curso fornece uma compreensão abrangente dos princípios e práticas fundamentais da cibersegurança e da privacidade, com aplicação tanto em contextos genéricos como em sistemas críticos - candidaturas até 07 de novembro.

Logótipo C-Academy

O curso proporciona uma visão aprofundada das tecnologias que suportam o desenvolvimento e integração de aplicações web - candidaturas até 10 de novembro.

Nesta sessão, apresentada por Lídia André (PhD), serão discutidos novos modelos de dependência capazes de representar simultaneamente as regiões centrais e extremas de distribuições multivariadas, com especial ênfase em métodos de inferência modernos baseados em redes neuronais.

Natal 2025

Uma oportunidade única de estudantes e professores do ensino secundário dialogarem diretamente com especialistas de várias áreas científicas.

Vida marinha

O Projeto ULISSES está de volta para a 6.ª edição! As candidaturas decorrem até 15 de dezembro.

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 - candidaturas até 12 dezembro.

Representação de pessoa a interagir com tecnologia

O curso introduz o conceito de Digital Twins e a sua aplicação estratégica no contexto do serviço público, com foco na modernização digital, otimização de processos e apoio à decisão - candidaturas até 11 de janeiro.

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 - candidaturas até 19 de dezembro.

Imagem exemplificativa da área da deteção remota

Este curso avançado tem como objetivo fornecer acesso e ferramentas para a aquisição e processamento de dados de deteção remota para diferentes aplicações, usando imagens multiespectrais de satélite, drone, terrestres e LiDAR, com foco na caracterização da vegetação e da paisagem, bem como das suas mudanças ao longo do tempo - candidaturas até 19 de dezembro.

Duas pessoas a interagirem num contexto de realidade virtual

O curso explora o potencial da Realidade Virtual (VR) e Aumentada (AR) como ferramentas inovadoras nos processos de onboarding e desenvolvimento de competências - candidaturas até 25 de janeiro.

Ginásio "inundado" de tecnologia

Um programa único na Europa, com o objetivo de capacitar para a integração crítica, segura e eficaz de ferramentas digitais na intervenção clínica - candidaturas até 30 de janeiro.

Imagem abstrata

Neste curso, será promovida uma abordagem multidisciplinar, apresentando as descobertas mais recentes sobre o tema e desafiando a forma tradicional de considerar as associações simbióticas como exceções e não como a regra - candidaturas até 09 de janeiro.

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.

Pessoas a analisarem dados

Candidaturas até 13 de fevereiro.

Um curso prático, limitado a um pequeno número de participantes, destinado a quem procura formação básica em teoria e estatística macroecológica e deseja familiarizar-se com algumas das potenciais utilizações de vários métodos avançado - candidaturas até 13 de fevereiro.