7

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.

Sasho Nikolov
  • 18,189
  • 2
  • 67
  • 115
Zihan Tan
  • 437
  • 2
  • 12
  • 2
    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 Jan 10 '17 at 23:52
  • 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 – Sasho Nikolov Jan 11 '17 at 00:04
  • 1
    @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 Jan 11 '17 at 00:12
  • 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 Jan 11 '17 at 00:18
  • @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 Jan 11 '17 at 00:22
  • Cross-post: http://mathoverflow.net/questions/259282/ – usul Jan 11 '17 at 03:07
  • @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 Jan 11 '17 at 04:23
  • This is very similar to the term "Witness" as discussed by Jukna in his book 'Extremal Combinatorics' Chapter 11. – Avishay Tal Jan 20 '17 at 06:16
  • @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 Jan 21 '17 at 21:04

1 Answers1

6

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 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 or the extended teaching dimension of Hegedus. 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).

Robin Kothari
  • 13,617
  • 2
  • 60
  • 116
  • 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 Jan 11 '17 at 17:00
  • 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 Jan 11 '17 at 17:21
  • 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 Jan 11 '17 at 18:46