<p>I am looking for a property testing algorithem for testing mononicity for functions of the form <span class="math-container">$f :\{0,1,2\}^n\rightarrow \{0,1\}$</span> which means that whenever <span class="math-container">$x \le y$</span> then <span class="math-container">$f(x) \le f(y)$</span> and by <span class="math-container">$x \le y$</span> i mean that <span class="math-container">$x=x_1x_2\dots x_n \le y=y_1y_2\dots y_n$</span> iff <span class="math-container">$x_i \le y_i$</span> for every <span class="math-container">$i \in [n]$</span>.
i am familiar only with property testing monotnicity with boolean functions ( functions of the form <span class="math-container">$f :\{0,1\}^n\rightarrow \{0,1\}$</span> where the algorithem samples <span class="math-container">$\mathcal{O}(\frac{m}{\epsilon})$</span> edges from the boolean hypercube of dimension n and returns no if one of them was non monotone with respect to <span class="math-container">$f$</span> ( the boolean hypercube is an undirected graph whose verticies are the vectors of the set <span class="math-container">$\{0,1\}^n$</span> and where every two verticies <span class="math-container">$x,y \in \{0,1\}^n$</span> that differ by only one coordinate are connected by an edge.furthermore an edge <span class="math-container">$xy$</span> is non monotone with respect to <span class="math-container">$f$</span> if <span class="math-container">$x \le y$</span> and <span class="math-container">$ f(x) \gt f(y)$</span> ).  is there any way to generilize the problem from functions  <span class="math-container">$f :\{0,1\}^n\rightarrow \{0,1\}$</span> to  <span class="math-container">$f :\{0,1,2\}^n\rightarrow \{0,1\}$</span> ? or maybe another simpler method that could work, or any hint or reference that may help.</p>

CC BY-SA 4.0
2024-07-13T18:07:03.447Z
See, e.g., https://theoryofcomputing.org/articles/v010a017/ ("monotonicity testing over the hypergrid"). By the way, for the hypercube there is a $\sqrt{n}$-query tester (can do better than linear in $n$).
Clement C.
CC BY-SA 4.0
2024-07-14T06:26:12.940Z
@ClementC. thanks for the reference.
usul
<reference-request><property-testing><monotone>
Testing monotonicity for functions of the form $f :\{0,1,2\}^n\rightarrow \{0,1\}$
usul
# Testing monotonicity for functions of the form $f :\{0,1,2\}^n\rightarrow \{0,1\}$

(Asked by: username_0 on 2024-07-13)

I am looking for a property testing algorithem for testing mononicity for functions of the form $f :\{0,1,2\}^n\rightarrow \{0,1\}$ which means that whenever $x \le y$ then $f(x) \le f(y)$ and by $x \le y$ i mean that $x=x\_1x\_2\dots x\_n \le y=y\_1y\_2\dots y\_n$ iff $x\_i \le y\_i$ for every $i \in [n]$.
i am familiar only with property testing monotnicity with boolean functions ( functions of the form $f :\{0,1\}^n\rightarrow \{0,1\}$ where the algorithem samples $\mathcal{O}(\frac{m}{\epsilon})$ edges from the boolean hypercube of dimension n and returns no if one of them was non monotone with respect to $f$ ( the boolean hypercube is an undirected graph whose verticies are the vectors of the set $\{0,1\}^n$ and where every two verticies $x,y \in \{0,1\}^n$ that differ by only one coordinate are connected by an edge.furthermore an edge $xy$ is non monotone with respect to $f$ if $x \le y$ and $ f(x) \gt f(y)$ ). is there any way to generilize the problem from functions $f :\{0,1\}^n\rightarrow \{0,1\}$ to $f :\{0,1,2\}^n\rightarrow \{0,1\}$ ? or maybe another simpler method that could work, or any hint or reference that may help.

**Tags:** reference-request, property-testing, monotone
> **Comments:**
> **username_1**: See, e.g., https://theoryofcomputing.org/articles/v010a017/ ("monotonicity testing over the hypergrid"). By the way, for the hypercube there is a $\sqrt{n}$-query tester (can do better than linear in $n$).  
> **username_0**: @ClementC. thanks for the reference.  

---

## 0 answers

