Laboratory of Mathematical Logic at PDMI

Вторник, 17 сентября, Zoom. Начало в 15:00.

Докладчик: А.В. Смаль.

Тема: Lifting Dichotomies.

Abstract

Lifting theorems are used to transfer lower bounds between Boolean function complexity measures. Such theorems have applications in many different areas, such as circuit complexity, communication complexity, proof complexity, etc. In this talk, we will systematically study the question, "For which gadgets does the lifting result hold?'' in the following settings: lifting from decision tree depth to decision tree size, lifting from decision tree depth to parity decision tree depth and size, and lifting from block sensitivity to deterministic and randomized communication complexities.

Доклад по совместной работе с Ярославом Алексеевым и Yuval Filmus.