All reports by Author Noah Stephens-Davidowitz:

__
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

__
TR19-173
| 28th November 2019
__

Divesh Aggarwal, Siyao Guo, Maciej Obremski, Joao Ribeiro, Noah Stephens-Davidowitz#### Extractor Lower Bounds, Revisited

Revisions: 1

__
TR19-159
| 11th November 2019
__

Noah Stephens-Davidowitz, Vinod Vaikuntanathan#### SETH-hardness of Coding Problems

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

Divesh Aggarwal, Siyao Guo, Maciej Obremski, Joao Ribeiro, Noah Stephens-Davidowitz

We revisit the fundamental problem of determining seed length lower bounds for strong extractors and natural variants thereof. These variants stem from a ``change in quantifiers'' over the seeds of the extractor: While a strong extractor requires that the average output bias (over all seeds) is small for all input ... more >>>

Noah Stephens-Davidowitz, Vinod Vaikuntanathan

We show that assuming the strong exponential-time hypothesis (SETH), there are no non-trivial algorithms for the nearest codeword problem (NCP), the minimum distance problem (MDP), or the nearest codeword problem with preprocessing (NCPP) on linear codes over any finite field. More precisely, we show that there are no NCP, MDP, ... more >>>