BARC talk by Benjamin Rossman

Monday, February 17, 2025, Benjamin Rossman, Associate Professor at the Duke University, USA, will give a talk on "Formula Size-Depth Tradeoffs for Iterated Permutation Matrix Multiplication".

Abstract
Rossman will describe recent, nearly tight size-depth tradeoffs for AC0 formulas computing the product of k n-by-n permutation matrices (a logspace-complete problem believed to lie outside NC1).  Full paper at https://arxiv.org/abs/2406.16015

Bio
Benjamin Rossman is an associate professor in the Computer Science and Mathematics Departments and a member of the Theory Group at Duke University. Previously, he held a faculty position at the University of Toronto and postdoctoral positions at the Tokyo Institute of Technology and National Institute of Informatics in Japan. He completed his PhD at MIT under the supervision of Madhu Sudan.
Benjamin's research interests lie in computational complexity theory, in particular circuit complexity (lower bounds in combinatorial models of computation), as well as finite model theory (the study of logical definability on finite structures). His research has been supported by NSERC Discovery and Accelerator Grants, an Ontario Early Researcher Award, and a Sloan Research Fellowship.

Hosts:
Amir Yehudayoff, Srikanth Srinivasan and Nutan Limaye