3 papers
cs.LO2025
Complete and tractable machine-independent characterizations of second-order polytime
Emmanuel Hainry, Bruce M. Kapron, Jean-Yves Marion +1
The class of Basic Feasible Functionals BFF is the second-order counterpart of the class of first-order functions computable in polynomial time. We present several implicit charact…
cs.CC2024
The Computational Complexity of Variational Inequalities and Applications in Game Theory
Bruce M. Kapron, Koosha Samieefar
We present a computational formulation for the approximate version of several variational inequality problems, investigating their computational complexity and establishing PPAD-co…
cs.CR2024
On Separation Logic, Computational Independence, and Pseudorandomness (Extended Version)
Ugo Dal Lago, Davide Davoli, Bruce M. Kapron
Separation logic is a substructural logic which has proved to have numerous and fruitful applications to the verification of programs working on dynamic data structures. Recently,…