# Parameterized Convexity Testing111The work of the first author was supported
by the Israel Science Foundation, grant number 592/17 and 822/18. The work of
the second author was supported by the Israel Science Foundation, grant number
379/21.

Abhiruk Lahiri222Ariel University, Israel<EMAIL_ADDRESS>Ilan
Newman333University of Haifa, Israel<EMAIL_ADDRESS>Nithin
Varma444Chennai Mathematical Institute, India<EMAIL_ADDRESS>
###### Abstract

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
$\varepsilon\in(0,1),s\in\mathbb{N}$, and oracle access to a function,
$\varepsilon$-tests convexity in $O(\log(s)/\varepsilon)$, 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\leq n$, our query complexity
bound is at least as good as that of the optimal convexity tester (Ben
Eliezer; ITCS 2019) with complexity $O(\frac{\log\varepsilon
n}{\varepsilon})$; 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(\frac{\log(\varepsilon n)}{\varepsilon})$ expressed in
terms of the input size and obtain a more efficient algorithm.

##  1 Introduction

A function $f:[n]\to\mathbb{R}$ is convex if $f(x)-f(x-1)\leq f(x+1)-f(x)$ for
all $x\in\\{2,3,\dots,n-1\\}$. Convexity of functions is a natural and
interesting property. Given oracle access to a function $f$, an
$\varepsilon$-tester for convexity has to decide with high constant
probability, whether $f$ is a convex function or whether every convex function
evaluates differently from $f$ on at least $\varepsilon n$ domain points,
where $\varepsilon\in(0,1)$. Parnas, Ron, and Rubinfeld [PRR06] gave an
$\varepsilon$-tester for convexity that has query complexity $O(\frac{\log
n}{\varepsilon})$. Blais, Raskhodnikova, and Yaroslavtsev [BRY14] showed that
this bound is tight for constant $\varepsilon$ for nonadaptive
algorithms555The queries of a nonadaptive algorithm does not depend on the
answers to the previous queries. The algorithm is adaptive otherwise.. An
improved upper bound of $O(\frac{\log(\varepsilon n)}{\varepsilon})$ was shown
by Ben-Eliezer [Ben19] in a work on the more general question of testing local
properties. Recently, Belovs, Blais and Bommireddi [BBB20] complemented this
result by showing a tight lower bound of $\Omega(\frac{\log(\varepsilon
n)}{\varepsilon})$.

In this work, we further investigate and develop new insights into this well-
studied problem, thereby asserting that there is more way to go towards a full
understanding of testing convexity of functions $f:[n]\to\mathbb{R}$. We show
that the number of distinct discrete derivatives $s$, as opposed to the input
size $n$, is the right input parameter to express the complexity of convexity
testing, where a discrete derivative is a value of the form $f(x+1)-f(x)$ for
$x\in[n-1]$. Specifically, we design a nonadaptive convexity tester with query
complexity $O(\frac{\log s}{\varepsilon})$, and complement it with a nearly
matching lower bound of $\Omega(\frac{\log(\varepsilon s)}{\varepsilon})$. Our
work is motivated by the work of Pallavoor, Raskhodnikova and Varma [PRV18]
who introduced the notion of parameterization in the setting of sublinear
algorithms.

Our results bring out the fine-grained complexity of the problem of convexity
testing. In particular, $s\leq n$ always and therefore, our tester is at least
as efficient as the state of the art convexity testers. Furthermore, the
parameterization that we introduce, enables us to circumvent the worst case
lower bounds expressed in terms of the input size $n$ and obtain more
efficient algorithms when $s<<n$.

###  1.1 Our Results

We begin our investigation with the simple and highly restricted case of
testing convexity of functions $f:[n]\to\mathbb{R}$ having at most two
distinct discrete derivatives. We design an adaptive algorithm that exactly
decides convexity by making $5$ queries and a nonadaptive algorithm that
$\varepsilon$-tests convexity by making $O(1/\varepsilon)$ queries. The
highlight is that both these algorithms are deterministic.

######  Theorem 1.1.

There exists a deterministic algorithm that, given oracle access to a function
$f:[n]\to\mathbb{R}$ having at most $2$ distinct discrete derivatives, exactly
decides convexity by making at most $5$ adaptive queries.

Theorem 1.1 is significant because one can construct simple examples of two
distributions, both over functions having at most $2$ distinct discrete
derivatives, one over convex functions and the other over non-convex
functions, such that no nonadaptive deterministic algorithm making $o(n)$
queries can distinguish the functions. Therefore, the above result shows the
power of adaptivity even in this restricted setting.

We also design a constant-query deterministic nonadaptive testing algorithm
for convexity of functions $f:[n]\to\mathbb{R}$ having at most $2$ distinct
discrete derivatives.

######  Theorem 1.2.

Let $\varepsilon\in(0,1)$. There exists a deterministic nonadaptive $1$-sided
error $\varepsilon$-tester for convexity of functions $f:[n]\to\mathbb{R}$
having at most $2$ distinct discrete derivatives with query complexity
$O(1/\varepsilon)$.

Next, we consider the general case of functions $f:[n]\to\mathbb{R}$ having at
most $s$ distinct discrete derivatives and design the following nonadaptive
tester.

######  Theorem 1.3.

Let $\varepsilon\in(0,1)$. There exists a nonadaptive $1$-sided error
$\varepsilon$-tester with query complexity $O(\frac{\log s}{\varepsilon})$ for
convexity of real-valued functions $f:[n]\to\mathbb{R}$ having at most $s$
distinct discrete derivatives.

We complement Theorem 1.3 with the following lower bound that is tight for
constant $\varepsilon\in(0,1)$. The bound holds even for adaptive testers,
thereby showing that one cannot hope for a separation between adaptive and
nonadaptive testers for this general setting.

######  Theorem 1.4.

For every sufficiently large $s\in\mathbb{N}$, every
$\varepsilon\in[1/s,1/9]$, and for every sufficiently large $n\geq s$, every
$\varepsilon$-tester for convexity of functions $f:[n]\to\mathbb{R}$ having at
most $s$ distinct derivatives has query complexity
$\Omega\left(\frac{\log(\varepsilon s)}{\varepsilon}\right)$.

###  1.2 Related Work

The study of property testing was initiated by Rubinfeld and Sudan [RS96] and
Goldreich, Goldwasser and Ron [GGR98]. The first example where
parameterization has helped in the design of efficient testers is the work of
Jha and Raskhodnikova [JR13] on testing the Lipschitz property. A systematic
study of parameterization in sublinear-time algorithms was initiated by
Pallavoor, Raskhodnikova and Varma [PRV18] and studied further by [Bel18,
CS19, Sur20, NV21].

In this work, we are concerned only with convexity of real-valued functions
over a $1D$ domain. We would like to note that not much is known about testing
convexity of functions over higher dimensional domains. One possible reason
behind this could be the following: there is no single definition of discrete
convexity for real-valued functions of multiple variables. For a good overview
of this topic, we refer interested readers to the textbook by Murota on
discrete convex analysis [Mur03]. Ben Eliezer [Ben19], in his work on local
properties, studied the problem of testing convexity of functions of the form
$f:[n]^{2}\to\mathbb{R}$ and designed a nonadaptive tester with query
complexity $O(n)$. Later, Belovs, Blais and Bommireddi [BBB20] showed a
nonadaptive query lower bound of $\Omega(\frac{n}{d})^{\frac{d}{2}}$ for
testing convexity of real-valued functions over $[n]^{d}$. For functions of
the form $f:[3]\times[n]\to\mathbb{R}$, they design an adaptive tester with
query complexity $O(\log^{2}n)$ and show that the complexity of nonadaptive
testing is $O(\sqrt{n})$.

##  2 Preliminaries

For a natural number $n\in\mathbb{N}$, we denote by $[n]$, the set
$\\{1,2,\dots,n\\}$. Let $B\subseteq[n]$. For $x\in B$, the
$\mathsf{order}(x)$ is the number of points $y\in B$ such that $y\leq x$.
Points $x,y\in B$ are _consecutive_ if
$|\mathsf{order}(x)-\mathsf{order}(y)|=1$. A function $f:B\to\mathbb{R}$ is
_convex_ if and only if

$\frac{f(y)-f(x)}{y-x}\leq\frac{f(z)-f(y)}{z-y}$ (1)

for all $x,y,z\in B$ such that $x<y<z$. A set of points $V\subseteq B$ is said
to _violate_ convexity if ${\left.\kern-1.2ptf\right|_{V}}$ is not convex.

For a function $f:[n]\to\mathbb{R}$, and $i\in[n]$, we use the term ‘discrete
derivative’ at $i$ for $\Delta(f,i)=f(i+1)-f(i)$. We denote by
$\Delta_{f}:[n-1]\to\mathbb{R}$, the derivative function
$\Delta_{f}(i)=\Delta(f,i),~{}i=1,\ldots,n-1$. The cardinality of the range of
$\Delta_{f}$ is referred to as the _number of distinct discrete derivatives_
of $f$. A function $f:[n]\to\mathbb{R}$ is convex if and only if $\Delta_{f}$
is monotone non-decreasing.

######  Fact 2.1.

If $f:B\to\mathbb{R}$ is not convex, then there exists three consecutive
points $x,y,z\in B$ that violate eq. 1.

We note that although convexity of $f$ is equivalent to monotonicity of
$\Delta_{f}$, it is not true that if $f$ is $\varepsilon$-far from being
convex then $\Delta_{f}$ is $\nu$-far from monotonicity for some positive
constant $\nu$. E.g., consider $f$ that is defined by $f(i)=i,~{}i\in[k]$,
$f(k+1)=k$ and $f(j)=j-1,~{}j=k+2,\ldots n$. Then $f$ if nearly
$\frac{1}{2}$-far from being convex for $k=n/2$, while $\Delta_{f}$ is almost
the $1$-constant function.

Let $\varepsilon\in(0,1)$. A function $f:[n]\to\mathbb{R}$ is
$\varepsilon$-far from convex if every convex function evaluates differently
from $f$ on at least $\varepsilon n$ points. A _basic $\varepsilon$-tester_
for convexity gets oracle access to a function $f$, a parameter $\varepsilon$,
and is such that, it accepts if $f$ is convex, and rejects, with probability
at least $\varepsilon$, if $f$ is $\varepsilon$-far from convex.

##  3 Deterministic Convexity Testers for Functions having at most $2$
Distinct Discrete Derivatives

We start with the very simple case in which $f$ has only $2$ distinct
derivatives (if $f$ has only $1$ distinct derivative then $f$ is a degree $1$
function and, in particular, convex) and prove Theorem 1.1 and Theorem 1.2.

Let the range of $\Delta_{f}$ be $\\{r_{1}<r_{2}\\}$. We do not assume that
the algorithm knows the values $r_{1},r_{2}$ but we will refer to them in our
proofs and reasoning below. As it turns out, in this case there is a
deterministic adaptive algorithm that can precisely decide if $f$ is convex,
making only $5$ queries. This is based on the fact that the class of convex
functions having at most two distinct derivatives is very restricted.

######  Observation 3.1.

If $f$ is convex and $\Delta_{f}$ takes at most two values $\\{r_{1}<r_{2}\\}$
then $f$ is of the following form: there is $j\in[n]$ such that
$f(i)=a+r_{1}(i-1),i=1,\ldots,j$ and
$f(i)=a+r_{1}(j-1)+r_{2}(i-j),~{}i=j+1,\ldots n$ for some $r_{1}<r_{2}$ and
some $a$. We denote such $f$ as $f_{a,r_{1},j,r_{2}}$.

Observation 3.1 suggests Algorithm 1 as a test for convexity.

1:oracle access to function $f:[n]\to\mathbb{R}$ having at most $2$ distinct
derivatives

2:Query $f(1),f(2),f(n-1),f(n)$.

3:Define $f_{1}(x)\coloneqq f(1)+(x-1)(f(2)-f(1))$ and $f_{2}(x)\coloneqq
f(n)-(n-x)(f(n)-f(n-1))$.

4:Query $f(j)$ such that $f_{1}(j)=f_{2}(j)$.

5:Reject if the function restricted to $1,2,j,n-1,n$ is not convex or
$f(j)\neq f_{1}(j)$, and accept otherwise.

Algorithm 1

######  Remark 3.2.

Algorithm 1 is a _deterministic, adaptive_ algorithm; it can make the last
query only after knowing the values of $f$ at the first $4$ points. Moreover,
if $f$ is a function having at most $2$ distinct discrete derivatives, then
there is always an integer point $j\in[n]$ such that $f_{1}(j)=f_{2}(j)$.

######  Lemma 3.3.

Algorithm 1 accepts every convex function having at most $2$ distinct
derivatives, and rejects every function having at most $2$ distinct
derivatives that is not convex.

We note that the lemma asserts that Algorithm 1 decides convexity correctly on
every function that has at most $2$ distinct derivatives, regardless of the
distance to convexity.

###### Proof.

If $f$ is convex, then the restriction of $f$ to every subset of $[n]$ is also
convex and Algorithm 1 accepts.

Suppose $f$ is not convex. This immediately implies that $f$ has two distinct
discrete derivatives, which we denote by $r_{1}<r_{2}$. Now, it is necessary
that $r_{1}=\Delta_{f}(1)$ and $r_{2}=\Delta_{f}(n-1)$ for the restriction of
$f$ to $\\{1,2,n-1,n\\}$ to be convex, for otherwise Algorithm 1 immediately
rejects.

Assuming that the restriction of $f$ to the set $S=\\{1,2,n-1,n\\}$ is convex,
Observation 3.1 implies that the only convex function with $2$ distinct
derivatives that is consistent with $f$ on the points in $S$ is the function
$f^{*}$ (from Observation 3.1), where the value of $j\in[n]$ is unique and is
as determined by Algorithm 1. If $f(j)\neq f^{*}(j)$, then the restriction of
$f$ to $S\cup\\{j\\}$ is not convex and Algorithm 1 rejects. In the rest of
the proof, we argue that if $f(j)=f^{*}(j)$, then $f$ and $f^{*}$ has to
evaluate to the same value on every point in $[n]$ and that $f$ is convex.
Specifically, each one of the discrete derivatives of $f$ upto the $j$ must be
$r_{1}$, for otherwise, $f(j)$ will be larger than $f^{*}(j)$. Moreover, each
one of the discrete derivatives of $f$ from $j$ upto $n$ must be $r_{2}$, for
otherwise, $f(j)$ will be smaller than $f^{*}(j)$. That is, the functions are
identical on every point in $[n]$. ∎

###  3.1 A Nonadaptive Deterministic Convexity Tester for Functions having at
most $2$ Distinct Discrete Derivatives

As remarked above, Algorithm 1 is deterministic and decides convexity exactly
under the promise that $f$ has at most $2$ distinct derivatives. However, it
is _adaptive_. What can be said about nonadaptive algorithms for the same
problem? It is easy to see that for any deterministic algorithm that makes
$q<n-1$ _nonadaptive_ queries $Q\subset[n]$, there are two functions $g,h$,
both having at most $2$ distinct derivatives, for which $g|_{Q}=h|_{Q}$ but
$g$ is convex while $h$ is not convex. Hence there is no deterministic
nonadaptive algorithm that decides convexity exactly, while making at most
$n-2$ queries. This line of reasoning immediately extends to a $\Omega(n)$
lower bound on randomized nonadaptive algorithms that exactly decide
convexity.

Here we come back to the property testing scenario. We show that there is a
_deterministic nonadaptive_ tester, Algorithm 2, that accepts every convex
function $f$ and rejects every function $f$ that is $\varepsilon$-far from
convex, under the promise that $f$ has at most $2$ distinct derivatives.
Algorithm 2 makes only $O(1/\varepsilon)$ nonadaptive deterministic queries.

Algorithm 2

1:$\varepsilon\in(0,1)$; oracle access to function $f:[n]\to\mathbb{R}$ having
at most $2$ discrete derivatives

2:$S\leftarrow\\{x_{i}(=i\varepsilon n)|~{}i=1,\ldots,1/\varepsilon\\}$

3:Query $f(1),f(2),f(n-1),f(n)$ and $f(x_{i}),f(x_{i}+1)$ for all
$i=1,\ldots,1/\varepsilon$

4:Set $r_{1}\leftarrow f(2)-f(1)$ and $r_{2}\leftarrow f(n)-f(n-1)$

5:Reject if $r_{1}>r_{2}$

6:Let $j\in[1/\varepsilon]$ be the largest integer such that
$f(x_{j})=f(1)+r_{1}(x_{j}-1)$

7:Reject if for some $i\geq j+1$, $f(x_{i})\neq f(n)-r_{2}(n-x_{i})$ and
accept otherwise

######  Claim 3.4.

Algorithm 2 accepts every convex function $f$ and rejects every function $f$
that is $\varepsilon$-far from convex, provided that $f$ has at most $2$
distinct derivatives. Further, Algorithm 2 is a deterministic nonadaptive
tester making $O(1/\varepsilon)$ queries.

###### Proof.

The claim about the query complexity is clear. Further, by Observation 3.1, if
$f$ is convex having at most $2$ distinct derivatives, then for some
$j^{*}\in[n]$, the function $f$ is of the form given in the observation. Let
$x_{j}\leq j^{*}\leq x_{j+1}$. Then $f$ is consistent with $j$ in the
acceptance criterion of Algorithm 2, and hence will be accepted.

Next, consider a function $f$ that is accepted by Algorithm 2. That is, there
exists $j\in[1/\varepsilon]$ such that $f(x_{i})=f(1)+r_{1}(x_{i}-1)$ for
every $i\leq j$, and that $f(x_{i})=f(n)-r_{2}(n-x_{i})$ for every $i\geq
j+1$, where $r_{1}\leq r_{2}$ are the two distinct discrete derivatives of
$f$. Since $f(x_{j})=f(1)+r_{1}(x_{j}-1)$, the function $f$ is a linear
function when restricted to the set $[x_{j}]$. Similarly, when restricted to
the set $[n]\setminus[x_{j+1}-1]$, the function $f$ is linear with slope
$r_{2}$. Further, it can be seen that $f$ can be corrected to be convex by
changing the values for $x_{j}+1\leq i\leq x_{j+1}-1$ to be consistent with
$f_{f(1),r_{1},j^{*},r_{2}}$. As this changes at most $\varepsilon n$ points,
it implies that $f$ is $\varepsilon$-close to convex. ∎

##  4 Convexity Tester for Functions having at most $s$ Distinct Discrete
Derivatives

In this section, we describe our convexity tester for the case that the
function $f:[n]\to\mathbb{R}$ has at most $s$ distinct discrete derivatives
and prove Theorem 1.3. A basic tester is presented in Algorithm 3. For
simplicity, we assume throughout this section, that $s/\varepsilon$ is an
integer that divides $n$.

The top level idea is the following: suppose that $f$ is convex with at most
$s$ distinct discrete derivatives, and let $B$ be a set of
$\ell=1+\frac{2s}{\varepsilon}$ nearly equally spaced consecutive pairs of
points in $[n]$ starting with $1,2$, namely,
$B=\\{1,2\\}\cup\\{i\cdot\frac{\varepsilon n}{2s}-1,i\cdot\frac{\varepsilon
n}{2s}:~{}i=1,\ldots\ell-1\\}$. Let $x_{i}=i\cdot\frac{\varepsilon n}{2s}$ for
$i\in[\ell-1]$. By the assumption on $f$, the function $\Delta_{f}|_{I}$ is
the constant function on at least $\ell-s$ of the intervals
$I=[x_{i},x_{i+1}-1]$. Further, if $\Delta_{f}|_{I}$ is constant on
$I=[x_{i},x_{i+1}-1]$, then obviously
$f(j)=f(x_{i})+(j-x_{i})\cdot\Delta_{f}(x_{i})$ for $j\in I$. Thus in order to
check that $f$ is convex, we first check that $f|_{B}$ is convex using the
nonadaptive, 1-sided error basic $\varepsilon$-tester of Belovs et al. [BBB20]
by making $O(\log(\varepsilon|B|))$ queries. Afterwards, we test that $f$ is
close to being a linear function on most intervals $I$. To test “linearity” of
$f|_{I}$ on most such $I$, it is enough to pick a random such interval and
test the distance to the appropriate linear function, which will result in a
large enough success probability. The details follow.

Algorithm 3 invokes Algorithm 4 as a subroutine, where Algorithm 4 is a basic
tester for convexity of functions defined over subdomains of $[n]$. The
following theorem can be proven by modifying the analysis of the convexity
tester by Belovs et al. [BBB20] in a fairly straightforward manner. We have
included its proof in the Appendix.

######  Theorem 4.1 (Belovs et al. [BBB20]).

Let $B\subseteq[n]$. There exists a basic $\varepsilon$-tester for convexity
of functions of the form $f:B\to\mathbb{R}$ that works for all
$\varepsilon\in(0,1)$ with query complexity $O(\log(\varepsilon|B|))$.

Algorithm 3 Convexity Tester

1:parameter $\varepsilon\in(0,1)$; oracle access to function
$f:[n]\to\mathbb{R}$; upper bound $s$ on the number of distinct discrete
derivatives in $f$

2:Let $B=\\{1,2\\}\cup\\{i\cdot\frac{\varepsilon
n}{2s}-1,i\cdot\frac{\varepsilon
n}{2s}:~{}i=1,\ldots\frac{2s}{\varepsilon}\\}$.

3:Test convexity of $f|_{B}$ with parameter $\varepsilon/32$ using Algorithm 4
and reject if that execution rejects.

4:Sample a point $x\in_{R}[n]$ u.a.r.

5:Let $y\leftarrow\left\lfloor\frac{2sx}{\varepsilon n}\right\rfloor$.

6:Reject if the points $y-1,y,x,y-1+\frac{\varepsilon
n}{2s},y+\frac{\varepsilon n}{2s}$ violate convexity.

Algorithm 4 Basic Tester for Convexity over Subdomains of $[n]$

1:oracle access to a function $g:B\to\mathbb{R}$; parameter $\varepsilon$

2:repeat $\lceil 24\log(2\varepsilon|B|)\rceil$ times:

3: Draw a point $a\in B$ uniformly at random.

4: Let $a^{\prime}\in B$ be such that
$\mathsf{order}(a^{\prime})=\mathsf{order}(a)+1$.

5: Pick a number $k$ uniformly at random from $\\{0,1,\dots,\lceil\log
2\varepsilon|B|\rceil\\}$.

6: Let $h\in B$ be a point such that $\mathsf{order}(h)$ is a multiple of
$2^{k}$, where, with probability $1/2$, the point $h$ is the smallest such
point larger than $a$, and with probability $1/2$, it is the largest such
point smaller than $a$.

7: Let $h^{\prime}\in B$ be such that
$\mathsf{order}(h^{\prime})=\mathsf{order}(h)+1$.

8: Reject if the set $\\{a,a^{\prime},h,h^{\prime}\\}$ violates convexity.

9:end repeat

Lemma 4.2 shows that Algorithm 3 is indeed a basic $\varepsilon$-tester for
convexity. Our convexity tester with query complexity $O(\log(s)/\varepsilon)$
is obtained by $O(1/\varepsilon)$ repetitions of Algorithm 3. This completes
the proof of Theorem 1.3.

######  Lemma 4.2.

Algorithm 3, rejects with probability at least $\varepsilon/32$, every
function $f$ having at most $s$ distinct discrete derivatives that is
$\varepsilon$-far from convex.

###### Proof.

It is enough to argue that Steps 3-6 of Algorithm 3 rejects with probability
at least $\varepsilon/32$.

If $f|_{B}$ is $\varepsilon/32$-far from being convex, by Theorem 4.1, one
iteration of Algorithm 4 rejects with probability at least $\varepsilon/32$.

In the rest of the proof, we assume that $f|_{B}$ is $\varepsilon/32$-close to
convex. In other words, it is possible to modify $f|_{B}$ in at most
$\frac{\varepsilon|B|}{32}$ points in $B$ in order to make $f|_{B}$ convex.

Let $b_{k}$ for $k\in[2s/\varepsilon]$ be shorthand for the index
$k\cdot\frac{\varepsilon n}{2s}-1$, and let $b_{0}$ stand for the index $1$.
Let $I_{k}$ denote the interval of indices $\\{b_{k}+1,\dots,b_{k+1}\\}$ for
$k\in[(2s/\varepsilon)-1]$. Let $I_{0}$ denote the interval of indices
$\\{2,\dots,b_{1}\\}$. For $k\in[(2s/\varepsilon)-1]$, the interval $I_{k}$ is
_nearly linear_ if

$f(b_{k}+1)-f(b_{k})=\frac{f(b_{k+1})-f(b_{k}+1)}{b_{k+1}-(b_{k}+1)}=f(b_{k+1}+1)-f(b_{k+1}).$
(2)

The interval $I_{0}$ is nearly linear if

$f(2)-f(1)=\frac{f(b_{1})-f(1)}{b_{1}-1}=f(b_{1}+1)-f(b_{1}).$ (3)

We first prove a lower bound on the number of nearly linear intervals. Recall
that there is a way to modify $f|_{B}$ by changing its values on at most
$\varepsilon\cdot|B|/32$ _bad_ points. For $k\in[(2s/\varepsilon)-1]$, the
interval $I_{k}$ is bad if one among $b_{k},b_{k}+1,b_{k+1},b_{k+1}+1$ is a
bad point, and is good otherwise. Likewise, $I_{0}$ is bad if one among
$1,2,b_{1},b_{1}+1$ is a bad point, and is good otherwise. The number of bad
intervals is, therefore, at most $\varepsilon|B|/16$, since a bad point can
make at most two intervals bad. Now, $\varepsilon|B|/16$ is at most $15s/16$,
by substituting the value of $|B|$.

For $k\in[(2s/\varepsilon)-1]$, if the interval $I_{k}$ is good, then none of
the points in $\\{b_{k},b_{k}+1,b_{k+1},b_{k+1}+1\\}$ are bad, and hence we
have

$f(b_{k}+1)-f(b_{k})\leq\frac{f(b_{k+1})-f(b_{k}+1)}{b_{k+1}-(b_{k}+1)}\leq
f(b_{k+1}+1)-f(b_{k+1}).$ (4)

Similarly, if $I_{0}$ is good, then

$f(2)-f(1)\leq\frac{f(b_{1})-f(1)}{b_{1}-1}\leq f(b_{1}+1)-f(b_{1}).$ (5)

For a good interval $I_{k}$ (or $I_{0}$) for $k\in[(2s/\varepsilon)-1]$ that
is not nearly linear, one of the inequalities in Equation 4 (Equation 5,
respectively) must be a strict inequality. Since the number of distinct
discrete derivatives in $f$ is at most $s$, the number of distinct discrete
derivatives among restricted to the good points is also at most $s$. Since the
function $f$ restricted to the good points is convex, the number of good
intervals with strict inequalities (in Equation 4 or Equation 5) is at most
$s-1$. Hence, the number of good intervals that are not nearly linear is at
most $s-1$.

Since $f$ is $\varepsilon$-far from being convex and each interval has at most
$\frac{\varepsilon n}{2s}$ indices, the restriction of $f$ to the set of
indices belonging to good nearly linear intervals, has distance at least
$\varepsilon n-\frac{15s}{16}\cdot\frac{\varepsilon
n}{2s}-s\cdot\frac{\varepsilon n}{2s}=\varepsilon n-\frac{\varepsilon
n}{2}-\frac{15\varepsilon n}{32}$ from convexity.

For $k\in[(2s/\varepsilon)-1]$, for a good nearly linear interval $I_{k}$, we
use $D_{k}$ to denote the Hamming distance of
${\left.\kern-1.2ptf\right|_{I_{k}}}$ to the linear function
$g_{k}:I_{k}\to\mathbb{R}$ defined as $g_{k}(x)=f(b_{k}+1)+(x-b_{k}-1)\cdot t$
for $x\in I_{k}$, where $t=f(b_{k+1}+1)-f(b_{k+1})$. Similarly, if $I_{0}$ is
good, we use $D_{0}$ to denote the Hamming distance of
${\left.\kern-1.2ptf\right|_{I_{0}}}$ to the linear function
$g_{0}:I_{0}\to\mathbb{R}$ defined as $g_{0}(x)=f(1)+(x-1)\cdot t$, where
$t=f(2)-f(1)$.

Consider the restriction of $f$ to the set of indices that belong to the good
nearly linear intervals. We can make this restriction convex by replacing
${\left.\kern-1.2ptf\right|_{I_{k}}}$ with $g_{k}$ for each $k$ such that
$I_{k}$ is a good nearly linear interval. Hence,

$\sum_{\begin{subarray}{c}k:I_{k}\\\ \text{nearly linear}\\\ \text{and
good}\end{subarray}}D_{k}\geq\varepsilon n-\frac{\varepsilon
n}{2}-\frac{15\varepsilon n}{32}\geq\frac{\varepsilon n}{32}.$

The proof will be completed by arguing that there are at least $D_{k}$ points
$x$ in a good nearly linear interval $I_{k}$ such that Algorithm 3 rejects by
sampling $x$ in Step 6.

Consider a good nearly linear interval $I_{k}$ such that
$f(b_{k}+1)-f(b_{k})=t$. Consider the (favorable) set $F$ consisting of all
points $z\in I_{k}$ such that $f(z)-f(b_{k}+1)=t\cdot(z-b_{k}-1)$ and
$f(b_{k+1})-f(z)=t\cdot(b_{k+1}-z)$. Clearly, both $b_{k}+1$ and $b_{k+1}$ are
in $F$. If Algorithm 3 samples, in Step 6, a point $z\notin F$, it rejects. We
now show that we can repair the function values at points not in $F$ and make
${\left.\kern-1.2ptf\right|_{I_{k}}}$ be equal to $g_{k}$. Consider an
interval of points $\\{x,x+1,\dots,y\\}$ such that none of them are in $F$,
and where, both $x-1$ and $y+1$ are in $F$. Since $x-1$ and $y+1$ are both in
$F$, we have that $f(y+1)-f(x-1)=t\cdot(y-x+2)$. We repair the function on the
interval $\\{x,x+1,\dots,y\\}$ by assigning the value
$f(x-1)+(x^{\prime}-x+1)\cdot t$ for all $x^{\prime}\in\\{x,x+1,\dots,y\\}$.
We can repair the function on the whole interval and make
${\left.\kern-1.2ptf\right|_{I_{k}}}$ be equal to $g_{k}$ by applying the same
modification on every such maximal subinterval, where the maximality is in the
sense of not belonging to $F$.

Hence, the probability that the tester rejects in Step 6 is at least
$\varepsilon/32$. This completes the proof. ∎

##  5 Lower Bound

In this section, we prove Theorem 1.4.

######  Lemma 5.1.

For every sufficiently large $s\in\mathbb{N}$, every
$\varepsilon\in[1/s,1/9]$, and for every sufficiently large $n\geq s$, every
$\varepsilon$-tester for convexity of functions $f:[n]\to\mathbb{R}$ having at
most $s$ distinct derivatives has query complexity
$\Omega\left(\frac{\log(\varepsilon s)}{\varepsilon}\right)$.

###### Proof.

We use Yao’s principle. Let $s\in\mathbb{N}$ and $\varepsilon\in[1/s,1/9]$.
Consider the distributions $\mathcal{D}_{0}$ and $\mathcal{D}_{1}$ from Belovs
et al. [BBB20] (proof of Theorem 1.3) of functions $f:[s]\to\mathbb{R}$. Every
function sampled from these distributions have at most $s$ distinct
derivatives. Moreover, every function sampled from $\mathcal{D}_{0}$ is
convex, and every function sampled from $\mathcal{D}_{1}$ is $\varepsilon$-far
from convex. They show that every tester distinguishing these distributions,
with probability at least $2/3$, has to make at least
$\Omega\left(\frac{\log(\varepsilon s)}{\varepsilon}\right)$ queries.

Consider an integer $n\geq s$ that is an integer multiple of $s$. Let $k$
denote $n/s$. We define distributions $\mathcal{D}^{\prime}_{0}$ and
$\mathcal{D}^{\prime}_{1}$ of functions $f:[n]\to\mathbb{R}$ as follows.

For $b\in\\{0,1\\}$, to sample a function $f$ from $\mathcal{D}^{\prime}_{b}$,
first sample a function $g$ from $\mathcal{D}_{b}$. For $i\in[s]$, let
$f((i-1)k+1)=g(i)$. For $i\in[s-1]$, let
$\mathsf{slope}_{i}=\frac{g(i+1)-g(i)}{k}$. Now, for all $j\in[k-1]$ and for
all $i\in[s-1]$, set $f((i-1)k+1+j)=f((i-1)k+1)+j\cdot\mathsf{slope}_{i}$.

By construction, every function sampled from $\mathcal{D}^{\prime}_{0}$ is
convex. Additionally, every function sampled from $\mathcal{D}^{\prime}_{1}$
is $\varepsilon$-far from convex. To see this, consider a function $f$ sampled
from $\mathcal{D}^{\prime}_{1}$ that is $\varepsilon$-close to being convex.
Let $g$ denote the function sampled from $\mathcal{D}_{1}$ from which we
constructed $f$. Let $B\subseteq[n]$ denote the set of _bad_ points such that
changing the values of $f$ on points in $B$ makes it convex. Since $f$ is
piecewise linear, it is clear that for each point in $B$ of the form
$(i-1)k+1$ for $i\in[s]$, either the set of $k-1$ points
$\\{(i-1)k+1+j:j\in[k-1]\\}$, or the set of $k-1$ points
$\\{(i-2)k+1+j:j\in[k-1]\\}$ has to belong to $B$. Thus, the number of points
in $B$ of the form $(i-1)k+1$ for $i\in[s]$ is at most $|B|/k=\varepsilon s$.
By construction of $f$, we know that for all $i\in[s]$, it holds that
$f((i-1)k+1)=g(i)$. Thus, the distance of $g$ to convexity is at most
$\varepsilon s$.

Consider a deterministic algorithm $A$ that distinguishes these distributions
by making $o\left(\frac{\log(\varepsilon s)}{\varepsilon}\right)$ queries. One
can use $A$ to distinguish, with the same success probability, the
distributions $\mathcal{D}_{0}$ and $\mathcal{D}_{1}$ by making at most twice
the number of queries as $A$, which leads to a contradiction. ∎

## References

  * [BBB20] Aleksandrs Belovs, Eric Blais, and Abhinav Bommireddi.  Testing convexity of functions over finite domains.  In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 2030–2045, 2020.
  * [Bel18] Aleksandrs Belovs.  Adaptive lower bound for testing monotonicity on the line.  In Eric Blais, Klaus Jansen, José D. P. Rolim, and David Steurer, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2018, August 20-22, 2018 - Princeton, NJ, USA, volume 116 of LIPIcs, pages 31:1–31:10, 2018\.
  * [Ben19] Omri Ben-Eliezer.  Testing local properties of arrays.  In 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA, volume 124 of LIPIcs, pages 11:1–11:20, 2019.
  * [BRY14] Eric Blais, Sofya Raskhodnikova, and Grigory Yaroslavtsev.  Lower bounds for testing properties of functions over hypergrid domains.  In IEEE 29th Conference on Computational Complexity, CCC 2014, Vancouver, BC, Canada, June 11-13, 2014, pages 309–320. IEEE Computer Society, 2014.
  * [CS19] Deeparnab Chakrabarty and C. Seshadhri.  Adaptive boolean monotonicity testing in total influence time.  In Avrim Blum, editor, 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA, volume 124 of LIPIcs, pages 20:1–20:7, 2019.
  * [GGR98] Oded Goldreich, Shafi Goldwasser, and Dana Ron.  Property testing and its connection to learning and approximation.  J. ACM, 45(4):653–750, 1998.
  * [JR13] Madhav Jha and Sofya Raskhodnikova.  Testing and reconstruction of lipschitz functions with applications to data privacy.  SIAM J. Comput., 42(2):700–731, 2013.
  * [Mur03] Kazuo Murota.  Discrete convex analysis, volume 10 of SIAM monographs on discrete mathematics and applications.  SIAM, 2003.
  * [NV21] Ilan Newman and Nithin Varma.  New sublinear algorithms and lower bounds for LIS estimation.  In 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference), volume 198 of LIPIcs, pages 100:1–100:20, 2021.
  * [PRR06] Michal Parnas, Dana Ron, and Ronitt Rubinfeld.  Tolerant property testing and distance approximation.  J. Comput. Syst. Sci., 72(6):1012–1042, 2006.
  * [PRV18] Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and Nithin Varma.  Parameterized property testing of functions.  ACM Trans. Comput. Theory, 9(4):17:1–17:19, 2018.
  * [RS96] Ronitt Rubinfeld and Madhu Sudan.  Robust characterizations of polynomials with applications to program testing.  SIAM J. Comput., 25(2):252–271, 1996.
  * [Sur20] Ramesh Krishnan Pallavoor Suresh.  Improved algorithms and new models in property testing.  PhD thesis, Boston University, 2020.

##  Appendix A Basic Tester for Convexity over Subdomains of $[n]$

In this section, we prove Theorem 4.1. All definitions and lemmas in this
section are straightforward generalizations of those by Belovs et al. [BBB20].

######  Definition A.1 (Test-Set, and its Root, Hub, and Scale).

Consider a point $a\in B$ and an integer $k$. Let $h\in B$ be one among the
two points closest to $a$ such that $\mathsf{order}(h)$ is a multiple of
$2^{k}$. Let $a^{\prime},h^{\prime}\in B$ be such that
$\mathsf{order}(a^{\prime})=\mathsf{order}(a)+1$, and
$\mathsf{order}(h^{\prime})=\mathsf{order}(h)+1$. We refer to
$\\{a,a^{\prime},h,h^{\prime}\\}$ as the _test-set_ with _root_ $a$, _hub_
$h$, and _scale_ $2^{k}$.

######  Lemma A.2.

Consider points $x,y\in B$ such that $\mathsf{order}(x)<\mathsf{order}(y)-1$.
Then there exists test-sets with roots $x$ and $y$ respectively, having a
common hub and scales at most $2(\mathsf{order}(y)-\mathsf{order}(x)).$

###### Proof.

Consider the smallest integer $k$ such that there exists a unique multiple $m$
of $2^{k}$ satisfying $\mathsf{order}(x)\leq m\leq\mathsf{order}(y)$. There
are at least $2$ multiples of $2^{k-1}$ in the range
$[\mathsf{order}(x),\mathsf{order}(y)]$. If there were only one multiple of
$2^{k-1}$ in that range, then it contradicts our assumption that $k$ is the
smallest integer such that there is a unique multiple of $2^{k}$ in
$[\mathsf{order}(x),\mathsf{order}(y)]$. Now, since there are at least $2$
multiples of $2^{k-1}$ in the range $[\mathsf{order}(x),\mathsf{order}(y)]$,
we have that $2^{k-1}\leq(\mathsf{order}(y)-\mathsf{order}(x))$.

The lemma follows by setting $h\in B$ such that $\mathsf{order}(h)=m$ as the
common hub of the test-sets with roots $x$ and $y$, and $2^{k}$ as their
scale. ∎

######  Lemma A.3.

Consider a set $\\{x,y,z\\}\subseteq B$ that violates convexity such that
$\mathsf{order}(x)<\mathsf{order}(y)<\mathsf{order}(z)$. At least one of the
test-sets involving $x,y,$ or $z$ violate convexity. Moreover, scale is not
exceeding
$2\cdot\max\\{\mathsf{order}(z)-\mathsf{order}(y),\mathsf{order}(y)-\mathsf{order}(x)\\}$.

###### Proof.

Let $x^{\prime},y^{\prime},z^{\prime}\in B$ be such that
$\mathsf{order}(x^{\prime})=\mathsf{order}(x)+1$,
$\mathsf{order}(y^{\prime})=\mathsf{order}(y)+1$, and
$\mathsf{order}(z^{\prime})=\mathsf{order}(z)+1$.

Let $h_{1}$ be the common hub for test-sets involving $x$ and $y$, as
guaranteed by Lemma A.2 and let $h_{1}^{\prime}\in B$ be such that
$\mathsf{order}(h_{1}^{\prime})=\mathsf{order}(h_{1})+1$. By Lemma A.2, the
test-sets $\\{x,x^{\prime},h_{1},h_{1}^{\prime}\\}$, and
$\\{h_{1},h_{1}^{\prime},y,y^{\prime}\\}$ both have scale at most
$2(\mathsf{order}(y)-\mathsf{order}(x))$.

Similarly, let $h_{2}\in B$ be the common hub for test-sets of $y$ and $z$
with scale at most $2(\mathsf{order}(z)-\mathsf{order}(y))$ and let
$h_{2}^{\prime}\in B$ be such that
$\mathsf{order}(h_{2}^{\prime})=\mathsf{order}(h_{2})+1$. Note that
$\\{y,y^{\prime},h_{2},h_{2}^{\prime}\\}$, and
$\\{h_{2},h_{2}^{\prime},z,z^{\prime}\\}$ are the test-sets being alluded to
in this case.

If none of the aforementioned four test-sets violate convexity, then, we
immediately have the following inequalities:

$\displaystyle\frac{f(y)-f(x)}{y-x}\leq\frac{f(y)-f(h_{1}^{\prime})}{y-h_{1}^{\prime}}\leq
f(y^{\prime})-f(y)\leq\frac{f(z)-f(y)}{z-y}.$

This contradicts our assumption that $\\{x,y,z\\}$ violates convexity. ∎

We are now ready to prove Theorem 4.1. The query complexity of Algorithm 4 is
clear from its description. Additionally, it always accepts convex functions.
Consider a function $f:B\to\mathbb{R}$ that is $\varepsilon$-far from convex.
The total number of possible scales for test-sets (see Algorithm 4) is at most
$1+\lceil\log_{2}(2\varepsilon|B|)\rceil$. Hence, the total number of test-
sets is at most $2|B|\cdot(1+\lceil\log_{2}(2\varepsilon|B|)\rceil)$.

We will construct a set $C\subseteq B$ such that $|C|\geq\varepsilon\cdot|B|$
and for every $a\in C$, one of the test-sets rooted at $a$ of scale at most
$1+\lceil\log_{2}(2\varepsilon|B|)\rceil$ violate convexity. Initialize $C$ to
be $\emptyset$. If $|C|<\varepsilon\cdot|B|$, then
${\left.\kern-1.2ptf\right|_{B\setminus C}}$ is not convex. We can find
consecutive points $x<y<z\in B\setminus C$, such that $f$ violates convexity
on these three points. Since $C$ contains fewer than $\varepsilon|B|$ many
points, we have that
$\max\\{\mathsf{order}(y)-\mathsf{order}(x),\mathsf{order}(z)-\mathsf{order}(y)\\}$
is at most $\varepsilon|B|$. Hence, by Lemma A.3, we know that there exists a
violating test-set involving either $x,y,$ or $z$ of scale at most
$2\varepsilon|B|$. We add such a point to set $C$. Hence, we have at least
$\varepsilon n$ violating test-sets. Therefore, the tester rejects with
probability at least $\frac{2\varepsilon}{\log(2\varepsilon n)}$ in a single
iteration.


* [Sch21] Martin Schwald.  On the definition of irreducible holomorphic symplectic manifolds and their singular analogs.  International Mathematics Research Notices, 2021.
  * [Slo80] Peter Slodowy.  Simple singularities and simple algebraic groups, volume 815 of Lecture Notes in Mathematics.  Springer, Berlin, 1980.
  * [Ste85] Hans Sterk.  Finiteness results for algebraic $K3$ surfaces.  Math. Z., 189(4):507–513, 1985.
  * [Sze99] Balázs Szendrői.  Some finiteness results for Calabi-Yau threefolds.  J. London Math. Soc. (2), 60(3):689–699, 1999.
  * [Tot10] Burt Totaro.  The cone conjecture for Calabi-Yau pairs in dimension 2.  Duke Math. J., 154(2):241–263, 2010.
  * [Tot12] Burt Totaro.  Algebraic surfaces and hyperbolic geometry.  In Current developments in algebraic geometry. Selected papers based on the presentations at the workshop “Classical algebraic geometry today”, MSRI, Berkeley, CA, USA, January 26–30, 2009, pages 405–426. Cambridge: Cambridge University Press, 2012.
  * [Ueh04] Hokuto Uehara.  Calabi-Yau threefolds with infinitely many divisorial contractions.  J. Math. Kyoto Univ., 44(1):99–118, 2004.
  * [VS93] Ernest B Vinberg and Osip V Shvartsman.  Discrete groups of motions of spaces of constant curvature.  In Geometry II, pages 139–248. Springer, 1993.
  * [Wil94] P. M. H. Wilson.  Minimal models of Calabi-Yau threefolds.  In Classification of algebraic varieties (L’Aquila, 1992), volume 162 of Contemp. Math., pages 403–410. Amer. Math. Soc., Providence, RI, 1994.