PhD Seminar • Algorithms and Complexity • Testing Convexity of Functions Over Finite DomainsExport this event to calendar

Friday, May 27, 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

Testing convexity of functions is an approximate version of the decision problem “Is a given unknown function convex?”. In this, given an unknown function, we need to determine if it is convex or “far” from convex. The unknown function is given via a valuation oracle which we query to get the function value at a point. We refer to an algorithm that performs the testing task as non-adaptive if it submits all its queries before looking at the function value on any of the points, and adaptive otherwise. 

We show that any non-adaptive algorithm that tests convexity of functions f : [n]^d \to \mathbb{R} for d \geq 2, has query complexity that is linear in n and exponential in d. To understand if adaptivity helps, we consider the problem of testing convexity of functions over a stripe, [3] x [n], and show that there exists an adaptive testing algorithm that does exponentially better than any non-adaptive one.

The results in this talk are from the following paper: Testing Convexity of Functions Over Finite Domains. Joint work with: Aleksandrs Belovs, Eric Blais. In, SODA 2020.


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
26
27
28
29
30
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
2
3
4
5
6
  1. 2022 (132)
    1. August (1)
    2. July (13)
    3. June (17)
    4. May (20)
    5. April (24)
    6. March (22)
    7. February (16)
    8. January (19)
  2. 2021 (210)
    1. December (21)
    2. November (13)
    3. October (12)
    4. September (21)
    5. August (20)
    6. July (17)
    7. June (11)
    8. May (16)
    9. April (27)
    10. March (20)
    11. February (13)
    12. January (19)
  3. 2020 (217)
  4. 2019 (255)
  5. 2018 (217)
  6. 2017 (36)
  7. 2016 (21)
  8. 2015 (36)
  9. 2014 (33)
  10. 2013 (23)
  11. 2012 (4)
  12. 2011 (1)
  13. 2010 (1)
  14. 2009 (1)
  15. 2008 (1)