# Parameterized Convexity Testing

arXiv: https://arxiv.org/abs/2110.13012 · HTML: https://mlsanity.com/paper/2110.13012/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Oct 2021.

## Built on by (most cited first, 1 of 1)

- [Learning and Testing Convex Functions](https://mlsanity.com/paper/2511.11498/) (2025)

## Abstract (arXiv)

In this work, we develop new insights into the fundamental problem of convexity testing of real-valued functions over the domain [n]. Specifically, we present a nonadaptive algorithm that, given inputs eps ∈ (0,1), s ∈ mathbbN, and oracle access to a function, eps-tests convexity in O(log (s)/eps), where s is an upper bound on the number of distinct discrete derivatives of the function. We also show that this bound is tight. Since s ≤ n, our query complexity bound is at least as good as that of the optimal convexity tester (Ben Eliezer; ITCS 2019) with complexity O(fraclog eps neps); our bound is strictly better when s = o(n). The main contribution of our work is to appropriately parameterize the complexity of convexity testing to circumvent the worst-case lower bound (Belovs et al.; SODA 2020) of Omega(fraclog (eps n)eps) expressed in terms of the input size and obtain a more efficient algorithm.