White-Box vs. Black-Box Complexity of Search Problems

DOI10.1145/3341106zbMath1473.68096OpenAlexW2964063279WikidataQ127461037 ScholiaQ127461037MaRDI QIDQ5215463

Eylon Yogev, Moni Naor, Ilan Komargodski

Publication date: 11 February 2020

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3341106

zbMATH Keywords

Ramsey theoryblack-box hardnesswhite-box hardness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Generalized Ramsey theory (05C55) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)

Related Items (6)

Non-malleable codes for bounded parallel-time tampering ⋮ On the complexity of collision resistant hash functions: new and old black-box separations ⋮ Statistical difference beyond the polarizing regime ⋮ Collision-resistance from multi-collision-resistance ⋮ Unnamed Item ⋮ Two's company, three's a crowd: consensus-halving for a constant number of agents

This page was built for publication: White-Box vs. Black-Box Complexity of Search Problems