2 papers
cs.CC2025
Tight Quantum Time-Space Tradeoffs for Permutation Inversion
Akshima, Tyler Besselman, Kai-Min Chung +2
In permutation inversion, we are given a permutation , and want to prepare some advice of size , such that we can efficiently invert any image in time $…
cs.CC2025
Direct Sums for Parity Decision Trees
Tyler Besselman, Mika Göös, Siyao Guo +2
Direct sum theorems state that the cost of solving instances of a problem is at least times the cost of solving a single instance. We prove the first such results in th…