Paper Info
Title
Testing convexity of functions over finite domains.
Abstract
We establish new upper and lower bounds on the number of queries required to test convexity of functions over various discrete domains. 1. We provide a simplified version of the non-adaptive convexity tester on the line. We re-prove the upper bound [MATH HERE] in the usual uniform model, and prove an [MATH HERE] upper bound in the distribution-free setting. 2. We show a tight lower bound of [MATH HERE] queries for testing convexity of functions f : [n]ϵ → R on the line. This lower bound applies to both adaptive and non-adaptive algorithms, and matches the upper bound from item 1, showing that adaptivity does not help in this setting. 3. Moving to higher dimensions, we consider the case of a stripe [3] × [n]. We construct an adaptive tester for convexity of functions f : [3] × [n] → R with query complexity O(log2n). We also show that any non-adaptive tester must use [MATH HERE] queries in this setting. Thus, adaptivity yields an exponential improvement for this problem. 4. For functions f : [n]d → R over domains of dimension d ≥ 2, we show a non-adaptive query lower bound [MATH HERE].
Year
DOI
Venue
2020
10.5555/3381089.3381214
SODA '20: ACM-SIAM Symposium on Discrete Algorithms Salt Lake City Utah January, 2020
Field
DocType
Citations 
Discrete mathematics,Convexity,Computer science
Conference
0
PageRank 
References 
Authors
0.34
0
3
Name
Order
Citations
PageRank
Aleksandrs Belovs113114.50
Eric Blais228622.49
Abhinav Bommireddi300.34