[Proof Complexity] Mon Jun 9 at 16:00 (note the time!) with Michael Whitmeyer: Communication complexity of collision-finding and bit pigeonhole principle

[Jakob Nordström]

Dear all,

On Monday June 9 at 16:00 CE(S)T (note the time!) we will gather for 
what is looking likely to be the last MIAO seminar for this spring 
semester, where Michael Whitmeyer from the  University of Washington 
will give a talk titled "Communication complexity of collision-finding 
and bit pigeonhole principle". You find the abstract at the bottom of 
this message.

This will be a video seminar 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

**********

/Monday June 9 at 16:00 CE(S)T (note the time!) on Zoom
*Communication complexity of collision-finding and bit pigeonhole principle
*(Michael Whitmeyer, University of Washington)
/
This talk focuses on the communication complexity of a collision-finding 
problem, which has applications to the complexity of cutting-plane 
proofs, which make inferences based on integer linear inequalities.

In one of our results, we prove a near optimal lower bound on the 
k-party number-in-hand communication complexity of collision-finding. 
This implies a nearly optimal 2^{n^(1-o(1))} lower bound on the size of 
tree-like cutting-planes refutations of the bit pigeonhole principle 
CNFs, which are compact and natural propositional encodings of the 
negation of the pigeonhole principle, improving on the best previous 
lower bound of 2^Ω(√n) for tree-like refutations.

In our main result we focus on a model of 2-party communication in which 
the protocol is no longer represented as a tree but as a directed 
acyclic graph (DAG) of protocol states. DAG-like protocols let one focus 
on a measure of protocol size rather than just depth. For cutting planes 
proofs there is a natural connection of proof size to the size of 
so-called triangle-DAG protocols. Using a refinement of a 
bottleneck-counting framework of Haken and Cook and Sokolov for 
triangle-DAG communication protocols, we give a 2^Ω(n^(1/4)) lower bound 
on the size of fully general (not necessarily tree-like) cutting planes 
refutations of the same bit pigeonhole principle formulas, improving on 
the best previous lower bound of 2^Ω(n^(1/8)).

Based on joint work with Paul Beame.


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