University COVID-19 update

The University of Waterloo is constantly updating our most Frequently Asked Questions.

Questions about buildings and services? Visit the list of Modified Services.

Please note: The University of Waterloo is closed for all events until further notice.

Special Seminar - Diego CifuentesExport this event to calendar

Friday, February 2, 2018 — 9:30 AM EST

Title: Polynomial systems: Graphical structure, Geometry, and Applications

Speaker: Diego Cifuentes
Affiliation: MIT
Room: MC 5501

Abstract:

Various problems in areas such as robotics, power systems, computer vision, cryptography, and chemical reaction networks, can be modeled by systems of polynomial equations, and in many cases the resulting systems have a simple sparsity structure. In the  first part of this talk we represent this sparsity structure with a graph, and study the algorithmic and complexity consequences of this graphical abstraction. In particular, we derive novel algorithms to solve polynomial systems. These methods outperform existing techniques by orders of magnitude in certain applications from algebraic statistics and vector addition systems.

The second part of this talk focuses on the problem of minimizing a polynomial function subject to polynomial equality constraints. This problem captures many important applications, including Max-Cut, tensor low rank approximation, the triangulation problem, and rotation synchronization. Although these problems are nonconvex, tractable semidefinite programming (SDP) relaxations have been proposed. We show novel guarantees on the quality of this relaxations. In particular, we prove that estimation problems such as camera triangulation, rank one tensor approximation and rotation synchronization can be solved exactly by SDP relaxations in the low noise regime.

Location 
MC - Mathematics & Computer Building
5501
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
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
1
2
3
  1. 2020 (89)
    1. September (11)
    2. August (11)
    3. July (17)
    4. June (11)
    5. May (6)
    6. March (11)
    7. February (11)
    8. January (11)
  2. 2019 (167)
    1. December (5)
    2. November (15)
    3. October (18)
    4. September (15)
    5. August (9)
    6. July (17)
    7. June (18)
    8. May (16)
    9. April (9)
    10. March (24)
    11. February (13)
    12. January (8)
  3. 2018 (138)
  4. 2017 (103)
  5. 2016 (137)
  6. 2015 (136)
  7. 2014 (88)
  8. 2013 (48)
  9. 2012 (39)
  10. 2011 (36)
  11. 2010 (40)
  12. 2009 (40)
  13. 2008 (39)
  14. 2007 (15)