For a field F, char(F) > 3, and an affine map A : F^n -> F^m we form a contradiction by picking some b not in A({0,1}^n) and saying Ax = b. This can be written as a system of 0-1 unsatisfiable linear equations over F expressible in the language of algebraic proof systems like Res(lin), NS, PC over F. One may think of these instances as the Subset Sum principle in positive characteristic. I'll suggest some hardness criterions for such instances and prove lower bounds for linear decision trees, tree-like Res(lin) and some restricted dag-like Res(lin) refutations. I'll also discuss work in progress on lower bounds for general dag-like Res(lin) refutations and PC refutations of these instances.
Logic seminar
usually takes place each Monday at 16:00 in IM, rear building, ground floorChair: Pavel Pudlak, Neil Thapen, Jan Krajíček
More information on the old seminar web page. The programme is announced via the mailing list.
On the Complexity of Algebraic Proofs of Membership in the Complement of an Affine Image of the Boolean Cube
Fedor Part
Institute of Mathematics
Monday, 29. November 2021 - 16:00 to 17:30
Average-case hardness of clique
Susanna de Rezende
Institute of Mathematics
Monday, 15. November 2021 - 16:00 to 17:30
We will start by recalling what is currently known about the hardness of refuting the clique formula on random graphs. We will then sketch some ideas on how to generalize these results to stronger proof systems.
New developments in reverse mathematics
Damir Dzhafarov
University of Connecticut and Charles University
Monday, 8. November 2021 - 16:00 to 17:30
I will give a brief introduction to reverse mathematics, focusing on computable combinatorics, and survey some recent trends and results in the subject. No prior background beyond basic logic is necessary.
On the strength of the Sherali-Adams proof system
Ilario Bonacina
UPC Barcelona
Monday, 25. October 2021 - 16:00 to 17:30
This talk is about Sherali-Adams when considered as a propositional proof system. We will present some propositional proof systems equivalent to it and we will prove two results upper-bounding the strength of Sherali-Adams. More precisely, we will prove that (1) depth-2 Frege + PHP p-simulates Sherali-Adams with unary coefficients, and (2) depth-2 Frege +"wtPHP" p-simulates Sherali-Adams (with coefficients in binary). The "wtPHP" is a new combinatorial principle, some sort of "weighted" version of the pigeonhole principle.
This talk is based on a joint work with Maria Luisa Bonet.