Please do contact me if you would like a copy of a paper not available as a link below.
Polynomial threshold functions and Boolean threshold circuits
Manuscript, 2013.
Patience of Matrix Games
Manuscript, 2012.
Approximating the minmax value of 3-player games within a constant is as hard as detecting planted cliques
Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates
The complexity of solving reachability games using value and strategy iteration
Learning Read-Constant Polynomials of Constant Degree Modulo Composites
Exact algorithms for solving stochastic games
The computational complexity of trembling hand perfection and other equilibrium refinements
Weights of Exact Threshold Functions
Exact Threshold Circuits
Hilbert's thirteenth problem and circuit complexity.
Depth Reduction for Circuits with a Single Layer of Modular Counting Gates.
Winning concurrent reachability games requires doubly-exponential patience.
A new characterization of ACC0 and probabilistic CC0.
Approximability and Parameterized Complexity of Minmax Values.
Constant Width Planar Branching Programs Characterize ACC0 in Quasipolynomial Size.
Deterministic Graphical Games Revisited.
Finding Equilibria in Games of No Chance.
Computing Symmetric Boolean Functions by Circuits with Few Exact Threshold Gates.
Dynamic Matchings in Convex Bipartite Graphs
Constant Width and Constant Depth Computation
PhD Dissertation, PD-06-13, 2006.
Lower Bounds for Circuits with Few Modular Gates using Exponential Sums
Note, 2006.
On Modular Counting with Polynomials.
Lower Bounds for Circuits With Few Modular and Symmetric Gates.
Some meet-in-the-middle circuit lower bounds.
Constant width planar computation characterizes ACC0.
Circuits on Cylinders.
|