research-article

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

Authors:

Ilan Komargodski,

Moni Naor,

Eylon YogevAuthors Info & Claims

Journal of the ACM (JACM), Volume 66, Issue 5

Article No.: 34, Pages 1 - 28

https://doi.org/10.1145/3341106

Published: 23 July 2019 Publication History

Get Access

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 exists (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 the complexity of an algorithm is measured as a function of the description size of the object in the box (and no limitation on the computation time). In this case, we show that for all TFNP problems there is an efficient algorithm with complexity proportional to the description size of the object in the box times the solution size. However, 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 that 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.

References

[1]

Noga Alon and Joel Spencer. 2008. The Probabilistic Method (3rd ed.). John Wiley.

Abstract

References

Cited By

Index Terms

Recommendations

Impossibility results on weakly black-box hardness amplification

Counting Complexity of Solvable Black-Box Group Problems

SZK Proofs for Black-Box Group Problems

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Funding Sources

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

HTML Format

Share

Share this Publication link

Share on social media

Affiliations