IMSc Webinar

Communication complexity based approaches to KRW conjecture, lifting theorems and formula lower bounds

Sajin Koroth

Simon Fraser University

Webinar: join at https://meet.google.com/eve-nqjk-jhm Despite the tremendous progress in the last couple of decades, many of the fundamental questions about the nature of computation remain open. This lack of progress is explained by limitations of well-known techniques that drove progress in the past. The main focus of complexity theory in recent times has been the search for tools and techniques that avoid such barriers. This talk is motivated by the following (seemingly different) fundamental questions that remain wide open: Are there natural problems that are poly-time solvable but cannot be solved efficiently by parallel computation? What connections exist between optimality in weak and strong models of computation? We make progress on both the problems using connections and tools from communication complexity that avoid the known barriers. We make progress on the first question, known as the $P eq NC^1$ problem, by studying a related conjecture called KRW conjecture (proposed by Karchmer, Raz, and Wigderson in the ’90s). KRW conjecture reduces the $P eq NC^1$ problem to studying a fundamental operation of Boolean functions called block-composition in the framework of communication complexity. We prove a variant of the KRW conjecture and open up a path to solve $P eq NC^1$ via a restricted version of the KRW conjecture. Block-composition is also a central operation that underlies a fundamental approach to the second question, known as “lifting theorems”. Lifting theorems, try to lift lower bounds from a weaker model of computation (usually decision trees) to a stronger model of computation (usually communication complexity). We make progress on this problem by proving new lifting theorems that work for a large class of Boolean functions. Because of the efficiency and generality of our lifting theorems, our results have found applications in many different areas including circuit complexity, proof complexity, and quantum communication complexity. The challenges involved in studying these problems in the framework of communication are fundamentally different, and looking forward, we suggest new approaches and tools.