All reports by Author Alon Rosen:

__
TR22-133
| 20th September 2022
__

Prahladh Harsha, Daniel Mitropolsky, Alon Rosen#### Downward Self-Reducibility in TFNP

Revisions: 1
,
Comments: 1

__
TR22-128
| 11th September 2022
__

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

__
TR22-011
| 25th January 2022
__

Andrej Bogdanov, Miguel Cueto Noval, Charlotte Hoffmann, Alon Rosen#### Public-Key Encryption from Continuous LWE

Prahladh Harsha, Daniel Mitropolsky, Alon Rosen

A problem is downward self-reducible if it can be solved efficiently given an oracle that returns

solutions for strictly smaller instances. In the decisional landscape, downward self-reducibility is

well studied and it is known that all downward self-reducible problems are in PSPACE. In this

paper, we initiate the study of ...
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 >>>

Andrej Bogdanov, Miguel Cueto Noval, Charlotte Hoffmann, Alon Rosen

The continuous learning with errors (CLWE) problem was recently introduced by Bruna

et al. (STOC 2021). They showed that its hardness implies infeasibility of learning Gaussian

mixture models, while its tractability implies efficient Discrete Gaussian Sampling and thus

asymptotic improvements in worst-case lattice algorithms. No reduction between CLWE and

LWE ...
more >>>