[Colloquium] Todays Theory Speaker

Tue Jan 15 13:53:59 CST 2019

Dimitry Sokolov
KTH Royal Institute of Technology

Title: “Monotone Circuit Lower Bounds from Resolution”

Abstract: For any unsatisfiable CNF formula F that is hard to refute in the Resolution proof system, we show that a gadget-composed version of F is hard to refute in any proof system whose lines are computed by efficient communication protocols --- or, equivalently, that a monotone function associated with F has large monotone circuit complexity. Our result extends to monotone real circuits, which yields new lower bounds for the Cutting Planes proof system.

As an application, we show that a monotone version of the XOR-SAT function has exponential monotone circuit complexity. Since XOR-SAT is in NC^2, this improves qualitatively on the monotone vs. non-monotone separation of Tardos (1988). Another corollary is that monotone span programs can be exponentially more powerful than monotone circuits.

Tuesday, January 15, 2019

Ry. 251 @ 3:30 pm

(Refreshments will be served prior to the talk in Ry. 255 @ 3:15pm)

Donna Brooms-Blue

Department Secretary
Computer Science Department
John Crerar Library Building
5730 So. Ellis Ave.
Chicago, IL. 60637
(773) 702-6614 - Office
(773) 702-8487 - Fax
donna at cs.uchicago.edu

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20190115/60e09e77/attachment-0004.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Dmitry Sokolov.docx
Type: application/vnd.openxmlformats-officedocument.wordprocessingml.document
Size: 17054 bytes
Desc: not available
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20190115/60e09e77/attachment-0001.docx>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20190115/60e09e77/attachment-0005.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Dimitry.pdf
Type: application/pdf
Size: 122456 bytes
Desc: not available
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20190115/60e09e77/attachment-0001.pdf>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20190115/60e09e77/attachment-0006.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.gif
Type: image/gif
Size: 2340 bytes
Desc: not available
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20190115/60e09e77/attachment-0001.gif>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20190115/60e09e77/attachment-0007.html>