MIAO/BARC talk by Dmitry Sokolov

Tuesday, September 16, 2025, Dmitry Sokolov, Scientist at EPFL, Switzerland, will give a talk on "Searching for falsified clause in random log n-CNFs is hard for randomized communication".

Abstract:
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.

Dmitry Sokolov

Host:
Jakob Nordström