101 citations · 491 across the 53 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
cs.CC2014
Function spaces for second-order polynomial time
Akitoshi Kawamura, Arno Pauly
In the context of second-order polynomial-time computability, we prove that there is no general function space construction. We proceed to identify restrictions on the domain or th…
cs.CC2011★ 9 cited
Many-one reductions and the category of multivalued functions
Arno Pauly
Multi-valued functions are common in computable analysis (built upon the Type 2 Theory of Effectivity), and have made an appearance in complexity theory under the moniker search pr…
cs.CC2009★ 2 cited
The Complexity of Iterated Strategy Elimination
Arno Pauly
We consider the computational complexity of the question whether a certain strategy can be removed from a game by means of iterated elimination of dominated strategies. In particul…