Please do contact me if you would like a copy of a paper not available as a link below.
Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates
STOC 2012, to appear.
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.
Journal of Logic and Computation, to appear.
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
Manuscript, 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.
|