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…
MMH* with arbitrary modulus is always almost-universal
Khodakhast Bibak, Bruce M. Kapron, Venkatesh Srinivasan
Universal hash functions, discovered by Carter and Wegman in 1979, are of great importance in computer science with many applications. MMH is a well-known -universal…
Unweighted linear congruences with distinct coordinates and the Varshamov--Tenengolts codes
Khodakhast Bibak, Bruce M. Kapron, Venkatesh Srinivasan
In this paper, we first give explicit formulas for the number of solutions of unweighted linear congruences with distinct coordinates. Our main tools are properties of Ramanujan su…
The Cayley graphs associated with some quasi-perfect Lee codes are Ramanujan graphs
Khodakhast Bibak, Bruce M. Kapron, Venkatesh Srinivasan
Let be the ring of Gaussian integers modulo a positive integer . Very recently, Camarero and Martínez [IEEE Trans. Inform. Theory, {\bf 62} (2016), 1183--1192], showed…
Type-two Iteration with Bounded Query Revision
Bruce M. Kapron, Florian Steinberg
Motivated by recent results of Kapron and Steinberg (LICS 2018) we introduce new forms of iteration on length in the setting of applied lambda-calculi for higher-type poly-time com…
Type-two polynomial-time and restricted lookahead
Bruce M. Kapron, Florian Steinberg
This paper provides an alternate characterization of type-two polynomial-time computability, with the goal of making second-order complexity theory more approachable. We rely on th…
A generalization of Schönemann's theorem via a graph theoretic method
Khodakhast Bibak, Bruce M. Kapron, Venkatesh Srinivasan
Recently, Grynkiewicz et al. [{\it Israel J. Math.} {\bf 193} (2013), 359--398], using tools from additive combinatorics and group theory, proved necessary and sufficient condition…
On a restricted linear congruence
Khodakhast Bibak, Bruce M. Kapron, Venkatesh Srinivasan
Let , , and be all positive divisors of . For , define ${\cal C}_l:=\lbrace 1 \leqslant x\le…
Counting surface-kernel epimorphisms from a co-compact Fuchsian group to a cyclic group with motivations from string theory and QFT
Khodakhast Bibak, Bruce M. Kapron, Venkatesh Srinivasan
Graphs embedded into surfaces have many important applications, in particular, in combinatorics, geometry, and physics. For example, ribbon graphs and their counting is of great in…
Dynamic graph connectivity with improved worst case update time and sublinear space
David Gibb, Bruce Kapron, Valerie King +1
This paper considers fully dynamic graph algorithms with both faster worst case update time and sublinear space. The fully dynamic graph connectivity problem is the following: give…
On an almost-universal hash function family with applications to authentication and secrecy codes
Khodakhast Bibak, Bruce M. Kapron, Venkatesh Srinivasan +1
Universal hashing, discovered by Carter and Wegman in 1979, has many important applications in computer science. MMH, which was shown to be -universal by Halevi and Krawczyk…
Restricted linear congruences
Khodakhast Bibak, Bruce M. Kapron, Venkatesh Srinivasan +2
In this paper, using properties of Ramanujan sums and of the discrete Fourier transform of arithmetic functions, we give an explicit formula for the number of solutions of the line…