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
Logótipos Ciências ULisboa e C-Academy, títulos dos cursos

Um programa de formação avançada em Cibersegurança para a administração pública e o setor privado desenvolvido pelo Centro Nacional de Cibersegurança, no âmbito do Plano de Recuperação e Resiliência.

Logótipos Ciências ULisboa e C-Academy, títulos dos cursos

Um programa de formação avançada em Cibersegurança para a administração pública e o setor privado desenvolvido pelo Centro Nacional de Cibersegurança, no âmbito do Plano de Recuperação e Resiliência.

Logótipo do evento, sobre um fundo branco

Um evento de reunião da comunidade nacional nas diversas vertentes da informática, com a ambição de ser o fórum de eleição para a divulgação, discussão e reconhecimento de trabalhos científicos.

Imagem do evento

Extended enrolement date until July 12th.

Logótipo do Workshop

A participação na 3.ª edição do Workshop é gratuita, mediante inscrição prévia.

Are you ready for this year's edition?

Imagem do evento - título, local e data do evento

Investigação Ecológica ao Serviço da Conservação

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