Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Alon Rosen:

TR22-133 | 20th September 2022
Prahladh Harsha, Daniel Mitropolsky, Alon Rosen

Downward Self-Reducibility in TFNP

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

TR22-128 | 11th September 2022
Romain Bourneuf, Lukáš Folwarczný, Pavel Hubacek, Alon Rosen, Nikolaj Schwartzbach

PPP-Completeness and Extremal Combinatorics

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

TR22-011 | 25th January 2022
Andrej Bogdanov, Miguel Cueto Noval, Charlotte Hoffmann, Alon Rosen

Public-Key Encryption from Continuous LWE

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

ISSN 1433-8092 | Imprint