All reports by Author Spencer Peters:

__
TR22-145
| 4th November 2022
__

Alexander Golovnev, Siyao Guo, Spencer Peters, Noah Stephens-Davidowitz#### Revisiting Time-Space Tradeoffs for Function Inversion

__
TR21-141
| 28th September 2021
__

Alexander Golovnev, Siyao Guo, Spencer Peters, Noah Stephens-Davidowitz#### On the (im)possibility of branch-and-bound search-to-decision reductions for approximate optimization

Revisions: 1

Alexander Golovnev, Siyao Guo, Spencer Peters, Noah Stephens-Davidowitz

We study the black-box function inversion problem, which is the problem of finding $x \in [N]$ such that $f(x) = y$, given as input some challenge point $y$ in the image of a function $f : [N] \to [N]$, using $T$ oracle queries to $f$ and preprocessed advice $\sigma \in ... more >>>

Alexander Golovnev, Siyao Guo, Spencer Peters, Noah Stephens-Davidowitz

We study a natural and quite general model of branch-and-bound algorithms. In this model, an algorithm attempts to minimize (or maximize) a function $f : D \to \mathbb{R}_{\geq 0}$ by making oracle queries to a heuristic $h_f$ satisfying

\[

\min_{x \in S} f(x) \leq h_f(S) \leq \gamma \cdot ...
more >>>