Theory
On the Complexity of Nash Equilibria in Anonymous Games / Boolean function monotonicity testing requires (almost) n1/2 non-adaptive queries / Indistinguishability Obfuscation for Turing Machines with Unbounded Memory / In Faster Canonical Forms for Primitive Coherent Configurations
With his former student Li-Yang Tan (PhD ’14), he will use random projections to prove lower bounds on Boolean circuits.
Two papers prove new lower bounds; one gives significant quantitative improvements over earlier lower bounds. The third paper reports progress in solving certain dynamic graph problems s using a deterministic approach.
About
Theory research includes computational complexity, algorithms and data structures, cryptography, quantum computing, computational geometry, approximation algorithms, computational game theory, algorithmic graph theory and combinatorics, online algorithms, computational learning theory, algebraic computation, optimization, randomness in computing, parallel and distributed computing, algorithmic coding theory, and theoretical aspects of areas such as networks, privacy, information retrieval, computational biology, and databases.
Theory of Computing Group 
Add to GMail