.png)
COLLOQUIUM
Thursday, February 18, 17:15, Zoom channel 958-115-833
Marc Vinyals (Technion)
Trade-offs between Length, Space, and Weights in the Cutting Planes Proof System
Linear threshold functions (of the form ) are simple, well-studied computing devices, yet surprisingly powerful when they are composed together. A basic question is how large the coefficients need to be to have enough expressive power and, while this question is well understood in the context of circuits, this is not at all the case in the context of propositional proofs.
In this talk we will discuss what we know about coefficients in the cutting planes proof system, which uses linear threshold functions, and show that there are cases where exponentially large coefficients are needed if we want to build proofs that are efficient with respect to other complexity measures.
This is joint work with Susanna de Rezende, Or Meir, Jakob Nordström,
Toniann Pitassi, and Robert Robere.
Everyone is welcome!