White-Box vs. Black-Box Complexity of Search Problems: Ramsey and Graph Property Testing

by Ilan Komargodski, Moni Naor, and Eylon Yogev

Oded's comments

It is indeed embarrassing to review this work, given that it is dedicated to my 60th birthday. Still, it felt wrong for me to avoid reviewing it due to this embarrassment.

I found the abstract is quite hard to understand, since it covers four different models that are all related to the same theme. Descriving each of these models is quite non-trivial, and so the task undertaken by the abstract is quite impossible. The (3-page) introduction is indeed much more clear.

The general theme is the gap between black-box (BB) access to the object (or problem's instance) and free access to its (possiblly succinct) description (called white-box or WB). The objects being considered have exponential (in $n$) size, whereas efficiency is associated with polynomial (in $n$) time. The four main results mentioned in the abstarct (and in the introduction) are:

  1. On the hardness of solving the Ramsey problem in the WB model. It is know that in the BB model an exponential number of queries are needed in order to find a $n$-vertex set that is either a clique or an independent set (in an $2^{2n}$-vertex graph). Assuming the existence of collision resistebnce hashing, this paper shows that in the WB model the problem is hard on the average (wrt efficiently sampleable distribution of succinct representations of such graphs). Note that this problem is in TFNP, since a solution always exists (by ramsey's theorem).
  2. In contrast to the above, there is no generic transformation of BB lower bounds for TFNP problems to WB hardness results. Specifically, it is shown that there exists a TFNP search problem for which BB requires exponential number of queries, but is efficiently solvable in WB model (when the input is succienctly described). We note that the BB lower bound is due to instances that cannot be represented succinctly, whereas instances that can be succinctly represented will have trivial solutions (in the WB model).
  3. The foregoing fact (i.e., that the BB lower bound uses instances that can be succinctly represented) is no coincidence. The next result shows that any TFNP problem can be solve in BB model using a number of queries that is polynomial in the circuit size. Hence, exponential lower bounds in the BB model must be due to instances that do not have a succinct representation.
  4. Lastly the paper shows that approximate decisions (of the type considered in property testing) may be infeasible (in the WB model). We stress that while the notion of approximate decision is identical to the one used in property testing, this result refers to algorithms that run in time that is polynomial in their input (whereas in property testing one considers algorithms that cannot afford to read the entire input and rather access parts of it via queries).

The original abstract

Ramsey theory assures us that in any graph there is a clique or independent set of a certain size, roughly logarithmic in the graph size. But how difficult is it to find the clique or independent set? If the graph is given explicitly, then it is possible to do so while examining a linear number of edges. If the graph is given by a black-box, where to figure out whether a certain edge exists the box should be queried, then a large number of queries must be issued. But what if one is given a program or circuit for computing the existence of an edge? This problem was raised by Buss and Goldberg and Papadimitriou in the context of TFNP, search problems with a guaranteed solution.

We examine the relationship between black-box complexity and white-box complexity for search problems with guaranteed solution such as the above Ramsey problem. We show that under the assumption that collision resistant hash function exist (which follows from the hardness of problems such as factoring, discrete-log and learning with errors) the white-box Ramsey problem is hard and this is true even if one is looking for a much smaller clique or independent set than the theorem guarantees. This is also true for the colorful Ramsey problem where one is looking, say, for a monochromatic triangle.

In general, one cannot hope to translate all black-box hardness for TFNP into white-box hardness: we show this by adapting results concerning the random oracle methodology and the impossibility of instantiating it.

Another model we consider is that of succinct black-box, where there is a limitation on the size of the black-box (but no limitation on the computing time). In this case we show that for all TFNP problems there is an upper bound proportional to the description size of the box t imes the solution size. On the other hand, for promise problems this is not the case.

Finally, we consider the complexity of graph property testing in the white-box model. We show a property which is hard to test even when one is given the program for computing the graph (under the appropriate assumptions such as hardness of Decisional Diffie-Hellman). The hard property is whether the graph is a two-source extractor.

See ECCC TR17-015.


Back to list of Oded's choices.