Alexander May

collaborators

3 papers

cs.CR2019

Noisy Simon Period Finding

Alexander May, Lars Schlieper, Jonathan Schwinger

Let $f : F_{2}^{n} \to F_{2}^{n}$ be a Boolean function with period $s$ . It is well-known that Simon's algorithm finds $s$ in time polynomial in $n$ on q…

cs.DS2019

Better Sample -- Random Subset Sum in $2^{0.255 n}$ and its Impact on Decoding Random Linear Codes

Andre Esser, Alexander May

We propose a new heuristic algorithm for solving random subset sum instances $a_{1}, \dots, a_{n}, t \in Z_{2^{n}}$ , which play a crucial role in cryptographic constructions. O…

cs.CR2019

Quantum Period Finding is Compression Robust

Alexander May, Lars Schlieper

We study quantum period finding algorithms such as Simon and Shor (and its variants Ekerå-Håstad and Mosca-Ekert). For a periodic function $f$ these algorithms produce -- via some…

Noisy Simon Period Finding

Better Sample -- Random Subset Sum in 20.255n and its Impact on Decoding Random Linear Codes

Quantum Period Finding is Compression Robust

Better Sample -- Random Subset Sum in $2^{0.255 n}$ and its Impact on Decoding Random Linear Codes