Roman Edenhofer

collaborators

3 papers

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

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

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