All reports by Author Nikolaj Schwartzbach:

__
TR23-060
| 17th April 2023
__

Sagnik Saha, Nikolaj Schwartzbach, Prashant Nalini Vasudevan#### The Planted $k$-SUM Problem: Algorithms, Lower Bounds, Hardness Amplification, and Cryptography

Revisions: 1

__
TR22-128
| 11th September 2022
__

Romain Bourneuf, Lukáš Folwarczný, Pavel Hubacek, Alon Rosen, Nikolaj Schwartzbach#### PPP-Completeness and Extremal Combinatorics

Sagnik Saha, Nikolaj Schwartzbach, Prashant Nalini Vasudevan

In the average-case $k$-SUM problem, given $r$ integers chosen uniformly at random from $\{0,\ldots,M-1\}$, the objective is to find a set of $k$ numbers that sum to $0$ modulo $M$ (this set is called a ``solution''). In the related $k$-XOR problem, given $k$ uniformly random Boolean vectors of length $\log{M}$, ... more >>>

Romain Bourneuf, Lukáš Folwarczný, Pavel Hubacek, Alon Rosen, Nikolaj Schwartzbach

Many classical theorems in combinatorics establish the emergence of substructures within sufficiently large collections of objects. Well-known examples are Ramsey's theorem on monochromatic subgraphs and the Erdos-Rado sunflower lemma. Implicit versions of the corresponding total search problems are known to be PWPP-hard; here "implicit" means that the collection is represented ... more >>>