2 papers
cs.CC2026
What is a POLYNOMIAL-TIME Computable L2-Function?
Aras Bacho, Svetlana Selivanova, Martin Ziegler
We give two natural definitions of polynomial-time computability for L2 functions; and we show them incomparable (unless complexity class FP_1 includes #P_1).
cs.CC2025
Second-Order Parameterizations for the Complexity Theory of Integrable Functions
Aras Bacho, Martin Ziegler
We develop a unified second-order parameterized complexity theory for spaces of integrable functions. This generalizes the well-established case of second-order parameterized compl…