Roman Edenhofer

activity

20242026

collaborators

4 papers

quant-ph2026

Robust subspace designs and the power of a unique small quantum witness

Simon Apers, Roman Edenhofer, Benjamin Mathieu-Bloise +1

The concept of subspace designs was introduced by Guruswami and Xing (STOC'13), and explicit constructions were given by Guruswami and Kopparty (FOCS'13). These are families of sub…

cs.DS2026

A Space-space Trade-off for Directed st-Connectivity

Roman Edenhofer

We prove a space-space trade-off for directed $s t$ -connectivity in the catalytic space model. For any integer $k \leq n$ , we give an algorithm that decides directed $s t$ -connectivi…

quant-ph2025

Dequantization and Hardness of Spectral Sum Estimation

Roman Edenhofer, Atsuya Hasegawa, François Le Gall

We give new dequantization and hardness results for estimating spectral sums of matrices, such as the log-determinant. Recent quantum algorithms have demonstrated that the logarith…

quant-ph2024

Directed st-connectivity with few paths is in quantum logspace

Simon Apers, Roman Edenhofer

We present a $BQSPACE (O (lo g n))$ -procedure to count $s t$ -paths on directed graphs for which we are promised that there are at most polynomially many paths starting in $s$ …