[Proof Complexity] Prague seminar on Monday - Robert Robere
thapen
thapen at math.cas.cz
Wed Mar 2 16:27:48 CET 2022
Robert Robere will give an online proof complexity talk in our logic
seminar on Monday 7th March, at 16:00 Prague time - see the announcement
below.
To join use the link
https://cesnet.zoom.us/j/472648284?pwd=ZTlxeHhqWlltR1AzZC9CTHgzZ2tRZz09
Passcode: 017107 (if required)
-------------------------------------------------------------------------
Speaker:Robert Robere, McGill University
Title: On Semi-Algebraic Proofs and Algorithms
Abstract
We discuss a new characterization of the Sherali-Adams proof system, a
standard propositional proof system considered in both proof complexity
and combinatorial optimization, showing that there is a degree-d
Sherali-Adams refutation of an unsatisfiable CNF formula F if and only
if there is an ε > 0 and a degree-d conical junta J such that viol(x) −
ε = J, where viol(x) counts the number of falsified clauses of F on an
input x. This result implies that the linear separation complexity, a
complexity measure recently studied by Hrubes (and independently by de
Oliveira Oliveira and Pudlak under the name of weak monotone linear
programming gates), monotone feasibly interpolates Sherali-Adams proofs,
sharpening a feasible interpolation result of Hakoniemi. On the
lower-bound side, we prove a separation between the conical junta degree
of viol(x) - 1 and Resolution width; since Sherali-Adams can simulate
Resolution this also separates the conical junta degree of viol(x) - 1
and viol(x) - ε for arbitrarily small ε > 0. Finally, by applying known
lifting theorems, we can translate this separation into separations
between extension complexity and monotone circuit complexity.
This talk is based on joint work with Noah Fleming, Mika Goos, and
Stefan Grosser.
For more information see the seminar web page at
https://calendar.math.cas.cz/logic-seminar-actual .
_______________________________________________
Logic-seminar mailing list
Logic-seminar at math.cas.cz
https://list.math.cas.cz/listinfo/logic-seminar
More information about the Proof-Complexity
mailing list