[Proof Complexity] MIAO seminar Tue Sep 16 at 14:00 CET with Dmitry Sokolov: Searching for falsified clause in random log n-CNFs is hard for randomized communication

[Jakob Nordström]

Dear all,

On Tuesday September 16 at 14:00, we are happy to welcome Dmitry Sokolov 
from EPFL, who will present a seminar titled "Searching for falsified 
clause in random log n-CNFs is hard for randomized communication". You 
find the abstract at the bottom of this message.

We will run this as a MIAO hybrid seminar at the University of 
Copenhagen. Local participants are warmly welcome to the new location of 
the Algorithms and Complexity Section at Vibenshuset, Lyngbyvej 2, while 
other participants are equally warmly welcome to join virtually at 
https://lu-se.zoom.us/j/61925271827 . Please feel free to share this 
information with colleagues who you think might be interested. We are 
also hoping to record the seminar and post on the MIAO Research YouTube 
channel https://youtube.com/@MIAOresearch for people who would like to 
hear the talk but cannot attend.

More information about the MIAO seminar series can be found at 
https://jakobnordstrom.se/miao-seminars/ . If you do not wish to receive 
these announcements, or receive several copies of them, please send a 
message to jn at di.ku.dk.

Best regards,
Jakob Nordström

**********

/Tuesday Sep 16 at 14:00 at the Algorithms and Complexity Section at the 
University of Copenhagen, Vibenshuset, Lyngbyvej 2, and on Zoom
*Searching for falsified clause in random log n-CNFs is hard for 
randomized communication
*(Dmitry Sokolov, EPFL)
/
We show that for a randomly sampled unsatisfiable O(log n)-CNF over n 
variables the randomized two-party communication cost of finding a 
clause falsified by the given variable assignment is linear in n. The 
proof of the result is a mix of the closure technique that comes from 
proof complexity and structure vs. randomness approach that comes from 
lifting theorems.

Based on joint work with Artur Riazanov, Anastasia Sofronova, and 
Weiqiang Yuan.


Jakob Nordström, Professor
University of Copenhagen and Lund University
Phone: +45 28 78 38 11 / +46 70 742 21 98
https://jakobnordstrom.se