PhD Seminar • Algorithms and Complexity • Minimizing Discrete Convex FunctionsExport this event to calendar

Friday, May 20, 2022 — 2:00 PM to 3:00 PM EDT

Please note: This PhD seminar will be given online.

Abhinav Bommireddi, PhD candidate
David R. Cheriton School of Computer Science

Supervisor: Professor Eric Blais

Minimizing convex functions over convex domains is well studied but relatively little is known about minimizing convex functions over discrete domains. Minimizing convex functions over discrete domains is challenging because we no longer have the property that local minimum implies global minimum, which is crucial for efficient minimization of convex functions over convex domains. 

In this talk, we consider the problem of minimizing convex functions over the hypergrid [n]^d, where [n] = {1, 2, \ldots, n}, and show that there is a polynomial time minimization algorithm in two dimensions, and for any constant dimension greater than two, there is a quasi-polynomial time minimization algorithm.


To join this PhD seminar on Zoom, please go to https://uwaterloo.zoom.us/j/5935948458.

Location 
Online PhD seminar
200 University Avenue West

Waterloo, ON N2L 3G1
Canada
Event tags 

S M T W T F S
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
1
2
  1. 2024 (96)
    1. April (19)
    2. March (27)
    3. February (25)
    4. January (25)
  2. 2023 (296)
    1. December (20)
    2. November (28)
    3. October (15)
    4. September (25)
    5. August (30)
    6. July (30)
    7. June (22)
    8. May (23)
    9. April (32)
    10. March (31)
    11. February (18)
    12. January (22)
  3. 2022 (245)
  4. 2021 (210)
  5. 2020 (217)
  6. 2019 (255)
  7. 2018 (217)
  8. 2017 (36)
  9. 2016 (21)
  10. 2015 (36)
  11. 2014 (33)
  12. 2013 (23)
  13. 2012 (4)
  14. 2011 (1)
  15. 2010 (1)
  16. 2009 (1)
  17. 2008 (1)