Algorithms, Proofs, and Communication
Robert Robere - Rutgers University and Institute for Advanced Study, Princeton
Feb. 26, 2019, 10:10 a.m. - Feb. 26, 2019, 11 a.m.
McConnell 321
ABSTRACT:
In recent years, an exciting line of work has melded three threads of research in computational complexity theory --- circuit complexity, proof complexity, and communication complexity --- showing how to translate tools and techniques from one field to the others. Applying such "translation" results has led to the resolution of a number of problems in all of these fields, some long-standing.
In this talk, I will survey some examples of these new "translation" theorems in my own work: particularly, in the theory of cutting planes proofs, which have their roots in integer programming, and in the theory of secret sharing schemes, which are cryptographic tools that have close connections to circuit complexity theory. In both areas we resolved long-standing lower bound problems by developing and applying such translation results. Time permitting, I will also survey some recent progress made on a unified theory of complexity which contains both of these examples and some others.
****
Robert Robere is a postdoctoral research fellow jointly appointed between DIMACS, at Rutgers University, and the Institute for Advanced Study in Princeton. He received his PhD from the University of Toronto, where he was supervised by Toniann Pitassi and Stephen Cook. His main research interests are in computational complexity theory, and particularly in the theory of lower bounds for boolean circuits and propositional proof systems. He also has a long-standing interest in the theory of satisfiability and SAT solvers.
ALL ARE WELCOME
