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:
- 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).
-
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).
-
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.
-
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.