Separations in proof complexity and TFNP by Göös, M, Hollender, A, Jain, S, Maystre, G, Pires, W, Robere, R, Tao, R

Separations in proof complexity and TFNP by Göös, M, Hollender, A, Jain, S, Maystre, G, Pires, W, Robere, R, Tao, R

Why are proof complexity lower bounds hard? by Pich, J, Santhanam, R

“…Another interpretation is that an analogue of the Razborov-Rudich `natural proofs' barrier holds in proof complexity: under reasonable hardness assumptions, there are natural distributions on hard tautologies for which it is infeasible to show proof complexity lower bounds for strong enough proof systems. …”

Relating Proof Complexity Measures and Practical Hardness of SAT by Järvisalo, M, Matsliah, A, Nordström, J, Živný, S

On the relative proof complexity of deep inference via atomic flows by Anupam Das

“…We consider the proof complexity of the minimal complete fragment, KS, of standard deep inference systems for propositional logic. …”
Get full text

Pebble Games, Proof Complexity, and Time-Space Trade-offs by Jakob Nordstrom

“…This is a survey of research in proof complexity drawing on results and tools from pebbling, with a focus on proof space lower bounds and trade-offs between proof size and proof space.…”
Get full text

A Finite-Model-Theoretic View on Propositional Proof Complexity by Erich Grädel, Martin Grohe, Benedikt Pago, Wied Pakusa

“…We establish new, and surprisingly tight, connections between propositional proof complexity and finite model theory. Specifically, we show that the power of several propositional proof systems, such as Horn resolution, bounded-width resolution, and the monomial calculus of bounded degree, can be characterised in a precise sense by variants of fixed-point logics that are of fundamental importance in descriptive complexity theory. …”
Get full text

From proof complexity to circuit complexity via interactive protocols by Arteche, N, Khaniki, E, Pich, J, Santhanam, R

“…<p>Folklore in complexity theory suspects that circuit lower bounds against <strong>NC</strong>¹ or <strong>P</strong>/poly, currently out of reach, are a necessary step towards proving strong proof complexity lower bounds for systems like Frege or Extended Frege. …”

Iterated lower bound formulas: a diagonalization-based approach to lower bounds in proof complexity by Santhanam, R, Tzameret, I

“…This is the first equivalence between proof complexity lower bounds and standard algebraic complexity lower bounds. …”

Frege systems for quantified Boolean logic by Beyersdorff, O, Bonacina, I, Chew, L, Pich, J

“…Such a direct transfer from circuit to proof complexity lower bounds has often been postulated for propositional systems but had not been formally established in such generality for any proof systems prior to this work.…”

Interaction and Depth against Nondeterminism in Proof Search by Ozan Kahramanogullari

“…We demonstrate our method on deep inference systems for multiplicative linear logic and classical logic, discuss its proof complexity and its relation to focusing, and present implementations.…”
Get full text

Polylogarithmic Cuts in Models of V^0 by Sebastian Müller

“…We can then exploit our result in Proof Complexity to observe that Frege proof systems can be sub exponentially simulated by bounded depth Frege proof systems. …”
Get full text

Feasible Interpolation for QBF Resolution Calculi by Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla

“…In sharp contrast to classical proof complexity we are currently short of lower bound techniques for QBF proof systems. …”
Get full text

Towards Uniform Certification in QBF by Leroy Chew, Friedrich Slivovsky

“…We pioneer a new technique that allows us to prove a multitude of previously open simulations in QBF proof complexity. In particular, we show that extended QBF Frege p-simulates clausal proof systems such as IR-Calculus, IRM-Calculus, Long-Distance Q-Resolution, and Merge Resolution. …”
Get full text

NP-hardness of minimum circuit size problem for OR-AND-MOD circuits by Hirahara, S, Oliveira, I, Santhanam, R

“…A significant number of works have demonstrated the central role of this problem and its variations in diverse areas such as cryptography, derandomization, proof complexity, learning theory, and circuit lower bounds. …”

Pseudo-finite hard instances for a student-teacher game with a Nisan-Wigderson generator by Jan Krajíček

“…The hard-core set is defined in a non-standard model of true arithmetic and has applications in a forcing construction relevant to proof complexity.…”
Get full text

On the logical complexity of cyclic arithmetic by Anupam Das

“…These results improve upon the bounds on proof complexity and logical complexity implicit in Simpson '17 and also an alternative approach due to Berardi & Tatsuta '17. …”
Get full text

Propositional proof systems : efficiency and automatizability by Alekhnovitch, Mikhail, 1978-

Get full text

Red-blue and standard pebble games : complexity and applications in the sequential and parallel models by Liu, Quanquan C. (Quanquan Catherine)

Get full text

On Sizes of Linear and Tree-Like Proofs for any Formulae Families in Some Systems of Propositional Calculus by Levon A. Apinyan, Anahit A. Chubaryan

“…The comparison of results obtained here with the bounds obtained formerly for the steps of proofs for the same formulas in the mentioned systems shows the importance of the size of proof among the other characteristics of proof complexities.…”
Get full text