[Proof Complexity] Prague seminar on Monday - Rahul Santhanam
thapen
thapen at math.cas.cz
Wed May 18 16:28:44 CEST 2022
Rahul Santhanam will give an online proof complexity talk in our logic
seminar on Monday 23rd May, at 16:00 Prague time - see the announcement
below.
It will be broadcast on zoom. To join use the link
https://cesnet.zoom.us/j/472648284?pwd=ZTlxeHhqWlltR1AzZC9CTHgzZ2tRZz09
Passcode: 017107 (if required)
-------------------------------------------------------------------------
Speaker:Rahul Santhanam, University of Oxford
Title: On the Conjectures of Razborov and Rudich
Abstract
We say that Rudich's Conjecture holds for a propositional proof system
Q if there are no efficient Q-proofs of random truth table tautologies.
We say that Razborov's Conjecture holds for a propositional proof system
Q if there are no efficient Q-proofs of any truth table tautologies. A
fundamental task in proof complexity and the meta-mathematics of circuit
lower bounds is to understand for which Q these conjectures hold. We
show various results about these conjectures, including evidence for
their difficulty.
Based on joint work with Jan Pich.
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