<p>Not a complete answer, but hopefully a good starting point. It is very instructive to (always!) first consider the discrete analog of your question. If <span class="math-container">$X$</span> is some set and <span class="math-container">$f:X\to\{0,1\}$</span>, what is the minimal number of evaluation queries needed to uniquely identify <span class="math-container">$f$</span>? As already noted in the OP, the question only makes sense if one fixes a function class <span class="math-container">$F$</span> of possible candidate functions <span class="math-container">$f$</span> to consider.</p>
<p>This is a well-studied problem, where the key notion is the <em>teaching dimension</em> (which is the minimum size of a <em>teaching set</em>), see here:
<a href="https://www.cs.umd.edu/sites/default/files/scholarly_papers/NealGupta.pdf" rel="nofollow noreferrer">https://www.cs.umd.edu/sites/default/files/scholarly_papers/NealGupta.pdf</a></p>
<p>A teaching set <span class="math-container">$S\subset X$</span> is such that the values of <span class="math-container">$f$</span> on <span class="math-container">$S$</span> uniquely identify <span class="math-container">$f\in F$</span>, for a given fixed function class <span class="math-container">$F$</span>.</p>
<p>Nothing is stopping you from defining an <span class="math-container">$\epsilon$</span>-teaching dimension for real-valued functions. You can define an <span class="math-container">$\epsilon$</span>-teaching set <span class="math-container">$S\subset X$</span> to be such that all <span class="math-container">$f\in F$</span> that agree on <span class="math-container">$S$</span> all lie within an <span class="math-container">$\epsilon$</span>-tube (i.e., are all within <span class="math-container">$\epsilon$</span> in <span class="math-container">$\ell_\infty$</span> distance).</p>
<p>As you can see from the discussion in that paper I linked, the teaching dimension is a rather stringent notion, which motivates more &quot;interesting&quot; variants, such as the <em>recursive</em> teaching dimension. Here again, I encourage you to explore its natural real-valued extensions.</p>

CC BY-SA 4.0
2020-07-17T09:32:57.313Z
2020-07-20T10:30:13.827Z
2020-07-20T10:30:13.827Z
Aryeh
<p>Consider the following computational problem, where <span class="math-container">$I$</span> is the real interval <span class="math-container">$[-1,1]$</span>:</p>
<blockquote>
<p>There is a monotonically-increasing function <span class="math-container">$f: I\to I$</span>. You are allowed to access it only through queries of the kind: &quot;Given <span class="math-container">$x\in I$</span>, what is <span class="math-container">$f(x)$</span>?&quot;. Let <span class="math-container">$x_0$</span> be an element of <span class="math-container">$I$</span> such that <span class="math-container">$f(x_0)=0$</span> (if it exists). Your goal is to find a value <span class="math-container">$x$</span> such that <span class="math-container">$|x-x_0|&lt;\epsilon$</span>. How many queries do you need, as a function of <span class="math-container">$\epsilon$</span>?</p>
</blockquote>
<p>All real numbers have infinite precision, as in the Real RAM model. It is allowed to do arbitrary computaitons on such real numbers - the only costly operations are the queries.</p>
<p>Here, the solution is simple: using binary search, the interval in which <span class="math-container">$x$</span> can lie shrinks by 2 after each query, so <span class="math-container">$\log_2(1/\epsilon)$</span> queries are sufficient. This is also an upper bound, since an adversary can always answer in such a way that the possible interval for <span class="math-container">$x$</span> shrinks by at most 2 after each query.</p>
<p>However, one can think of more complicated problems of this kind, with several different functions and possibly different kinds of queries.</p>
<p>What is a term, and some references, for this kind of computational problems?</p>
<p><sub>Related posts in other sites:</sub></p>
<ul>
<li><sub>First posted on <a href="https://cs.stackexchange.com/q/128150/1342">cs.stackexchange</a>.</sub></li>
<li><sub><a href="https://mathoverflow.net/q/364871/34461">This MathOverflow post</a> is related, but there it is required to use a finite number of registers with a finite precision.</sub></li>
</ul>

<reference-request><complexity-classes><approximation-algorithms><query-complexity><computing-over-reals>
Complexity of approximating a real function using queries
Erel Segal-Halevi
# Complexity of approximating a real function using queries

(Asked by: username_0 on 2020-07-14)

Consider the following computational problem, where $I$ is the real interval $[-1,1]$:

> There is a monotonically-increasing function $f: I\to I$. You are allowed to access it only through queries of the kind: "Given $x\in I$, what is $f(x)$?". Let $x\_0$ be an element of $I$ such that $f(x\_0)=0$ (if it exists). Your goal is to find a value $x$ such that $|x-x\_0|<\epsilon$. How many queries do you need, as a function of $\epsilon$?

All real numbers have infinite precision, as in the Real RAM model. It is allowed to do arbitrary computaitons on such real numbers - the only costly operations are the queries.

Here, the solution is simple: using binary search, the interval in which $x$ can lie shrinks by 2 after each query, so $\log\_2(1/\epsilon)$ queries are sufficient. This is also an upper bound, since an adversary can always answer in such a way that the possible interval for $x$ shrinks by at most 2 after each query.

However, one can think of more complicated problems of this kind, with several different functions and possibly different kinds of queries.

What is a term, and some references, for this kind of computational problems?

Related posts in other sites:

* First posted on [cs.stackexchange](https://cs.stackexchange.com/q/128150/1342).
* [This MathOverflow post](https://mathoverflow.net/q/364871/34461) is related, but there it is required to use a finite number of registers with a finite precision.

**Tags:** reference-request, complexity-classes, approximation-algorithms, query-complexity, computing-over-reals

---

## 1 answers

### Answer by username_1 on 2020-07-17. Score: 4

Not a complete answer, but hopefully a good starting point. It is very instructive to (always!) first consider the discrete analog of your question. If $X$ is some set and $f:X\to\{0,1\}$, what is the minimal number of evaluation queries needed to uniquely identify $f$? As already noted in the OP, the question only makes sense if one fixes a function class $F$ of possible candidate functions $f$ to consider.

This is a well-studied problem, where the key notion is the *teaching dimension* (which is the minimum size of a *teaching set*), see here:
<https://www.cs.umd.edu/sites/default/files/scholarly_papers/NealGupta.pdf>

A teaching set $S\subset X$ is such that the values of $f$ on $S$ uniquely identify $f\in F$, for a given fixed function class $F$.

Nothing is stopping you from defining an $\epsilon$-teaching dimension for real-valued functions. You can define an $\epsilon$-teaching set $S\subset X$ to be such that all $f\in F$ that agree on $S$ all lie within an $\epsilon$-tube (i.e., are all within $\epsilon$ in $\ell\_\infty$ distance).

As you can see from the discussion in that paper I linked, the teaching dimension is a rather stringent notion, which motivates more "interesting" variants, such as the *recursive* teaching dimension. Here again, I encourage you to explore its natural real-valued extensions.


---

