Testing convexity of functions over finite domains
Aleksandrs Belovs, Eric Blais, Abhinav Bommireddi · Society for Industrial and Applied Mathematics eBooks · 2019
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 in the usual uniform model, and prove an upper bound in the distribution-free setting.2.We show a tight lower bound of queries for testing convexity of functions f: [n] → ℝ 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] → ℝ with query complexity O(log2 n). We also show that any non-adaptive tester must use queries in this setting. Thus, adaptivity yields an exponential improvement for this problem.4.For functions f: [n]d → ℝ over domains of dimension d ≥ 2, we show a non-adaptive query lower bound .