Roman Edenhofer

activity

20242026

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

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