<p>What you call the "revealing complexity" is sometimes called <strong>the (deterministic) query complexity of exact learning with membership queries</strong>. </p>

<p>Exact learning refers to the fact that you have to exactly identify $x\in C$ at the end, as opposed to being (say) probably approximately correct (as in PAC learning). Membership queries refers to the fact that you can query the individual bits of $x$ (as opposed to being given a random sample according to some distribution, as in PAC learning). </p>

<p>See <a href="https://cstheory.stackexchange.com/questions/14526/combinatorial-characterization-of-exact-learning-with-membership-queries">this related question</a> where I explain some of what's known about this complexity measure.
For example, we know that the deterministic query complexity of exactly learning a concept class $C\subseteq \{0,1\}^n$ with membership queries is characterized up to a factor of $\log |C|$ by the complexity measure defined in <a href="http://dx.doi.org/10.1137/S0097539704412910" rel="nofollow noreferrer">this paper by Servedio and Gortler</a> or the <a href="http://dl.acm.org.libproxy.mit.edu/citation.cfm?id=225311" rel="nofollow noreferrer">extended teaching dimension of Hegedus</a>. Both measures are combinatorial in nature. Whether there is a combinatorial measure that captures this complexity without a $\log|C|$ factor is unknown to me (and probably an open problem).</p>

CC BY-SA 3.0
2017-01-11T17:00:58.883Z
Thanks for the answer! Indeed a combinatorial parameter to characterize the "revealing complexity"! But I found it hard to compute $\gamma^C$ for general concept class, probably it is NP-hard?
Zihan Tan
CC BY-SA 3.0
2017-01-11T17:21:37.367Z
On the other hand, it seems that for most concept classes, the upper bound given by $O(\frac{\log |C|}{\gamma^C})$ is $O(n)$. But what we care more is probably what classes have revealing complexity bounded away from $n$ for example $n-\Omega(\log n)$. Was there some characterization for that?
Zihan Tan
CC BY-SA 3.0
2017-01-11T18:46:16.657Z
The lower bound of $\min\{\log|C|,1/\gamma_C\}$ is at most quadratically far from the true answer. So it can give you an estimate that is quadratically close to the revealing complexity. I don't know if there's anything known for determining if the complexity is $n-\Omega(\log n)$.
Robin Kothari
CC BY-SA 3.0
2017-01-11T04:33:35.850Z
2017-01-11T04:33:35.850Z
Robin Kothari
<p>An initially unknown string $x$ is known to be in $C\subseteq \{0,1\}^n$. Every round you are allowed to reveal one bit of $x$ (on your choice, and adaptively). How many bits do you need to reveal in order to be certain about what $x$ is?</p>

<p>For example, if $C=\{x\mid \text{parity}(x)=0\}$, then $(n-1)$ bits are needed. If $C=\{e_i\mid i\in [n], e_i=(0,0,\cdots,0,1(\text{i}^{th}\text{coordinate}),0,\cdots, 0)\}$ then also $(n-1)$ bits are needed. But if $C=\{0^p1^{n-p}\mid p\in [n]\}$ then only $\log n$ bits are needed since we can binary search the position where the alternation happens.</p>

<p>Was this "revealing complexity" $RC(C)$ studied before? If not, what is some combinatorial feature (or any sufficient/necessary conditions) of $C$ with $RC$ to be $n-o(\log n)$?</p>

<p>Any previous results or new ideas are appreciated.</p>

CC BY-SA 3.0
2017-01-10T23:52:43.507Z
That's query complexity: https://en.wikipedia.org/wiki/Decision_tree_model. There is quite a bit known, this is probably the best understood complexity measure of Boolean functions.
Sasho Nikolov
CC BY-SA 3.0
2017-01-11T00:04:30.740Z
What you are asking for is very similar to what are called "evasive" functions (the evasive functions require $n$ queries). I don't there is a simple characterization: for example it's still open whether every nontrivial monotone graph property is evasive (known for $n$ a prime power via tools from algebraic topology). See https://en.wikipedia.org/wiki/Aanderaa%E2%80%93Karp%E2%80%93Rosenberg_conjecture
Sasho Nikolov
CC BY-SA 3.0
2017-01-11T00:12:17.663Z
@SashoNikolov Thanks! But I thought this is different from decision-tree complexity since in that case you need to know whether or not $x$ is in $C$ but now you need to know what it is exactly (knowing that it is in $C$).
Zihan Tan
CC BY-SA 3.0
2017-01-11T00:18:02.773Z
Ah yes, you are right. I missed that. It is still related to query complexity though..you are asking for the query complexity of the identity function under a promise.
Sasho Nikolov
CC BY-SA 3.0
2017-01-11T00:22:31.370Z
@SashoNikolov Yes, and this seems to be a query complexity of a partial function, and I did not know of any results on that~
Zihan Tan
CC BY-SA 3.0
2017-01-11T03:07:46.980Z
Cross-post: http://mathoverflow.net/questions/259282/
usul
CC BY-SA 3.0
2017-01-11T04:23:50.253Z
@SashoNikolov Thanks for information. For your observation, I think probably it is not universally correct? Please see the third example I give in the second paragraph, worst case complexity of membership testing would be $O(n)$ but revealing complexity is $O(\log n)$. Anyway I will do more literature search on it!
Zihan Tan
CC BY-SA 3.0
2017-01-20T06:16:15.213Z
This is very similar to the term "Witness" as discussed by Jukna in his book 'Extremal Combinatorics' Chapter 11.
Avishay Tal
CC BY-SA 3.0
2017-01-21T21:04:55.493Z
@AvishayTal Thanks, and the definition is almost the same except "revealing complexity" is defined for a class $\mathcal{C}$, while in the book, witness is mostly analyzed with respect to individual strings $x$ inside the class.
Zihan Tan
<cc.complexity-theory><co.combinatorics>
Was this complexity measure studied before?
Zihan Tan
# Was this complexity measure studied before?

(Asked by: username_0 on 2017-01-10)

An initially unknown string $x$ is known to be in $C\subseteq \{0,1\}^n$. Every round you are allowed to reveal one bit of $x$ (on your choice, and adaptively). How many bits do you need to reveal in order to be certain about what $x$ is?

For example, if $C=\{x\mid \text{parity}(x)=0\}$, then $(n-1)$ bits are needed. If $C=\{e\_i\mid i\in [n], e\_i=(0,0,\cdots,0,1(\text{i}^{th}\text{coordinate}),0,\cdots, 0)\}$ then also $(n-1)$ bits are needed. But if $C=\{0^p1^{n-p}\mid p\in [n]\}$ then only $\log n$ bits are needed since we can binary search the position where the alternation happens.

Was this "revealing complexity" $RC(C)$ studied before? If not, what is some combinatorial feature (or any sufficient/necessary conditions) of $C$ with $RC$ to be $n-o(\log n)$?

Any previous results or new ideas are appreciated.

**Tags:** cc.complexity-theory, co.combinatorics
> **Comments:**
> **username_1**: That's query complexity: https://en.wikipedia.org/wiki/Decision_tree_model. There is quite a bit known, this is probably the best understood complexity measure of Boolean functions.  
> **username_1**: What you are asking for is very similar to what are called "evasive" functions (the evasive functions require $n$ queries). I don't there is a simple characterization: for example it's still open whether every nontrivial monotone graph property is evasive (known for $n$ a prime power via tools from algebraic topology). See https://en.wikipedia.org/wiki/Aanderaa%E2%80%93Karp%E2%80%93Rosenberg_conjecture  
> **username_0**: @SashoNikolov Thanks! But I thought this is different from decision-tree complexity since in that case you need to know whether or not $x$ is in $C$ but now you need to know what it is exactly (knowing that it is in $C$).  
> **username_1**: Ah yes, you are right. I missed that. It is still related to query complexity though..you are asking for the query complexity of the identity function under a promise.  
> **username_0**: @SashoNikolov Yes, and this seems to be a query complexity of a partial function, and I did not know of any results on that~  
> **username_2**: Cross-post: http://mathoverflow.net/questions/259282/  
> **username_0**: @SashoNikolov Thanks for information. For your observation, I think probably it is not universally correct? Please see the third example I give in the second paragraph, worst case complexity of membership testing would be $O(n)$ but revealing complexity is $O(\log n)$. Anyway I will do more literature search on it!  
> **username_3**: This is very similar to the term "Witness" as discussed by Jukna in his book 'Extremal Combinatorics' Chapter 11.  
> **username_0**: @AvishayTal Thanks, and the definition is almost the same except "revealing complexity" is defined for a class $\mathcal{C}$, while in the book, witness is mostly analyzed with respect to individual strings $x$ inside the class.  

---

## 1 answers

### Answer by username_4 on 2017-01-11. Score: 6 | Accepted answer

What you call the "revealing complexity" is sometimes called **the (deterministic) query complexity of exact learning with membership queries**.

Exact learning refers to the fact that you have to exactly identify $x\in C$ at the end, as opposed to being (say) probably approximately correct (as in PAC learning). Membership queries refers to the fact that you can query the individual bits of $x$ (as opposed to being given a random sample according to some distribution, as in PAC learning).

See [this related question](https://cstheory.stackexchange.com/questions/14526/combinatorial-characterization-of-exact-learning-with-membership-queries) where I explain some of what's known about this complexity measure.
For example, we know that the deterministic query complexity of exactly learning a concept class $C\subseteq \{0,1\}^n$ with membership queries is characterized up to a factor of $\log |C|$ by the complexity measure defined in [this paper by Servedio and Gortler](http://dx.doi.org/10.1137/S0097539704412910) or the [extended teaching dimension of Hegedus](http://dl.acm.org.libproxy.mit.edu/citation.cfm?id=225311). Both measures are combinatorial in nature. Whether there is a combinatorial measure that captures this complexity without a $\log|C|$ factor is unknown to me (and probably an open problem).

> **Comments:**
> **username_0**: Thanks for the answer! Indeed a combinatorial parameter to characterize the "revealing complexity"! But I found it hard to compute $\gamma^C$ for general concept class, probably it is NP-hard?  
> **username_0**: On the other hand, it seems that for most concept classes, the upper bound given by $O(\frac{\log |C|}{\gamma^C})$ is $O(n)$. But what we care more is probably what classes have revealing complexity bounded away from $n$ for example $n-\Omega(\log n)$. Was there some characterization for that?  
> **username_4**: The lower bound of $\min\{\log|C|,1/\gamma_C\}$ is at most quadratically far from the true answer. So it can give you an estimate that is quadratically close to the revealing complexity. I don't know if there's anything known for determining if the complexity is $n-\Omega(\log n)$.  

---

