Saint Petersburg, 199178, Russia, Line 14th (Vasilyevsky Island), 29
(812) 363-68-71, (812) 363-68-72
ru en

Новости

17.02.2021
Trade-offs between Length, Space, and Weights in the Cutting Planes Proof System

Trade-offs between Length, Space, and Weights in the Cutting Planes Proof System

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

Announcement

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!