Showing 2025Show all
3 papers · 1 filter
quant-ph2025
On the hardness of approximating minimum distances of quantum codes
Elena Grigorescu, Vatsal Jha, Eric Samperton
The problem of computing distances of error-correcting codes is fundamental in both the classical and quantum settings. While hardness for the classical version of these problems h…
cs.CC2025
An elementary proof that linking problems are hard
Shannon Cheng, Anna Chlopecki, Saarah Nazar +1
We give a new, elementary proof of what we believe is the simplest known example of a ``natural'' problem in computational 3-dimensional topology that is -hard -- name…
math.QA2025
Towards a complexity-theoretic dichotomy for TQFT invariants
Nicolas Bridges, Eric Samperton
We show that for any fixed -dimensional TQFT over of either Turaev-Viro-Barrett-Westbury or Reshetikhin-Turaev type, the problem of (exactly) computing its inva…