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

### Ilan Komargodski Moni Naor Eylon Yogev

###
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.

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 computation time). In this case we show that
for all TFNP problems there is an upper bound proportional to the description size of the box
times 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.

Paper: PDF. Slides:
ppt.

##### (Somewhat) Related On-Line
Papers:

- Ilan Komargodski, Moni Naor and Eylon Yogev,
*
Collision Resistant Hashing for Paranoids: Dealing with Multiple Collisions*
Abstract , PDF .

Back to: On-Line Publications, Recent Papers

Back Home