20 citations · 86 across the 16 of their papers we have counts for
17 papers
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…
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,…
Declassification Policy for Program Complexity Analysis
Emmanuel Hainry, Bruce M. Kapron, Jean-Yves Marion +1
In automated complexity analysis, noninterference-based type systems statically guarantee, via soundness, the property that well-typed programs compute functions of a given complex…
The Computational Complexity of Equilibria with Strategic Constraints
Bruce M. Kapron, Koosha Samieefar
Computational aspects of solution notions such as Nash equilibrium have been extensively studied, including settings where the ultimate goal is to find an equilibrium that possesse…
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…
A tier-based typed programming language characterizing Feasible Functionals
Emmanuel Hainry, Bruce M. Kapron, Jean-Yves Marion +1
The class of Basic Feasible Functionals BFF is the type-2 counterpart of the class FP of type-1 functions computable in polynomial time. Several characterizations have been sug…