Showing cs.CCShow all
2 papers · 1 filter
cs.CC2026
A search-to-decision reduction for the linear code equivalence problem
Jean-François Biasse, Giacomo Micheli, Benjamin Prada +1
We present a polynomial-time reduction from the search variant of the linear code equivalence problem (i.e. the search for a linear isometry between the inputs) to its decisional v…
cs.CC2025
Realizable Circuit Complexity: Embedding Computation in Space-Time
Benjamin Prada, Ankur Mali
Classical circuit complexity characterizes parallel computation in purely combinatorial terms, ignoring the physical constraints that govern real hardware. The standard classes $\m…