Rafael
Oliveira,
Research
fellow
UC
Berkeley
Simons
Institute
for
the
Theory
of
Computing
Many important problems arising in computer science exhibit natural symmetries, which can often be used to give efficient algorithms for such problems. The natural symmetries of a problem have also been crucially used to prove computational hardness or impossibility results, and recently they feature in one of algebraic complexity theory's most fundamental problems: how to construct explicit polynomials which are hard to compute!
In this talk, I will describe my work on using the inherent symmetries of a general class of optimization problems to provide fast, efficient algorithms for such problems. I will also show the remarkable consequences of these algorithms in mathematics, computer science and quantum information theory!
More specifically, we will see how symmetries can be used to provide rigorous analysis of a general class of alternating minimization algorithms — a heuristic used in many areas of computer science.
Bio: Rafael Oliveira received his PhD in Computer Science from Princeton University in 2017. From 2017 to 2018 he was a postdoctoral researcher at the University of Toronto, and currently he is a research fellow at the UC Berkeley Simons Institute for the Theory of Computing.
His research interests lie in the interplay between mathematics and computer science, particularly in how optimization and computational complexity interact with other areas of mathematics and science, such as algebra, invariant theory, quantum information theory and analysis. Rafael uses these connections between optimization, complexity and invariant theory to provide novel algorithms for various computational problems arising in computer science.