Seminar • Algorithms and Complexity — When Optimization Meets Algebraic Complexity Theory: Exploring the Inherent Symmetries in ComputationExport this event to calendar

Wednesday, March 13, 2019 — 10:30 AM EDT

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.

Location 
DC - William G. Davis Computer Research Centre
1304
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
28
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
  1. 2019 (179)
    1. September (6)
    2. August (18)
    3. July (12)
    4. June (23)
    5. May (23)
    6. April (32)
    7. March (25)
    8. February (16)
    9. January (24)
  2. 2018 (221)
    1. December (16)
    2. November (19)
    3. October (26)
    4. September (23)
    5. August (17)
    6. July (20)
    7. June (13)
    8. May (25)
    9. April (34)
    10. March (24)
    11. February (3)
    12. January (1)
  3. 2017 (36)
  4. 2016 (21)
  5. 2015 (36)
  6. 2014 (33)
  7. 2013 (23)
  8. 2012 (4)
  9. 2011 (1)
  10. 2010 (1)
  11. 2009 (1)
  12. 2008 (1)