research
∙
03/19/2023
A proof complexity conjecture and the Incompleteness theorem
Given a sound first-order p-time theory T capable of formalizing syntax ...
share
research
∙
01/25/2023
Extended Nullstellensatz proof systems
For a finite set F of polynomials over fixed finite prime field of size ...
research
∙
08/24/2022
On the existence of strong proof complexity generators
The working conjecture from K'04 that there is a proof complexity genera...
research
∙
04/10/2021
Information in propositional proofs and algorithmic proof search
We study from the proof complexity perspective the (informal) proof sear...
research
∙
04/24/2020
Small circuits and dual weak PHP in the universal theory of p-time algorithms
We prove, under a computational complexity hypothesis, that it is consis...
research
∙
04/06/2020
A limitation on the KPT interpolation
We prove a limitation on a variant of the KPT theorem proposed for propo...
research
∙
09/09/2019
The Cook-Reckhow definition
The Cook-Reckhow 1979 paper defined the area of research we now call Pro...
research
∙
05/30/2019