Professor, École Normale Supérieure de Lyon
Pascal Koiran is professor of computer science at Ecole Normale Superieure de Lyon. His current research is centered on lower bounds and upper bounds in algebraic complexity. He has worked on lower bounds for sums of powers of affine functions in one variable, a (seemingly) simple model that remains poorly understood even today. He has also proposed an approach to VP versus VNP based on the study of sums of products of sparse polynomials in one variable (the "real tau conjecture") or two variables (the "tau conjecture for Newton polygons"). On the complementary topic of upper bounds, he has worked on depth reduction for arithmetic circuits, on factorization of polynomials, and on black box circuit reconstruction.
Lower Bounds in Computational Complexity , Fall 2018Visiting Scientist