Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Noah Stephens-Davidowitz:

TR24-018 | 28th January 2024
Huck Bennett, Surendra Ghentiyala, Noah Stephens-Davidowitz

The more the merrier! On the complexity of finding multicollisions, with connections to codes and lattices

We study the problem of finding multicollisions, that is, the total search problem in which the input is a function $\mathcal{C} : [A] \to [B]$ (represented as a circuit) and the goal is to find $L \leq \lceil A/B \rceil$ distinct elements $x_1,\ldots, x_L \in A$ such that $\mathcal{C}(x_1) = ... more >>>

TR23-193 | 3rd December 2023
Eldon Chung, Alexander Golovnev, Zeyong Li, Maciej Obremski, Sidhant Saraogi, Noah Stephens-Davidowitz

On the randomized complexity of range avoidance, with applications to cryptography and metacomplexity

We study the Range Avoidance Problem (Avoid), in which the input is an expanding circuit $C : \{0,1\}^n \to \{0,1\}^{n+1}$, and the goal is to find a $y \in \{0,1\}^{n+1}$ that is not in the image of $C$. We are interested in the randomized complexity of this problem, i.e., in ... more >>>

TR22-145 | 4th November 2022
Alexander Golovnev, Siyao Guo, Spencer Peters, Noah Stephens-Davidowitz

Revisiting Time-Space Tradeoffs for Function Inversion

Revisions: 1

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

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

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

TR19-173 | 28th November 2019
Divesh Aggarwal, Siyao Guo, Maciej Obremski, Joao Ribeiro, Noah Stephens-Davidowitz

Extractor Lower Bounds, Revisited

Revisions: 1

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

TR19-159 | 11th November 2019
Noah Stephens-Davidowitz, Vinod Vaikuntanathan

SETH-hardness of Coding Problems

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

ISSN 1433-8092 | Imprint