I am an Associate Professor (Reader) in Informatics at Univeristy of Edinburgh, and a member of the Laboratory for Foundations of Computer Science.
My research interests are in algorithms and complexity, with an emphasis on
complexity theory and its applications to cryptography, game theory and learning theory.
I received my Ph.D. in Computer Science from Chicago in 2005. My advisors were
Lance Fortnow and
Janos Simon. From 2005-2007 I was a postdoc with Valentine Kabanets in the School of Computing Science at
Fraser University, and from 2007-2008 I was visiting the Theory Group in the
Department of Computer Science at University of Toronto. I joined
Edinburgh in August 2007.
- Medium-Uniformity and Circuit Lower Bounds
(with Ryan Williams), CCC 2013.
- Lower Bounds on Interactive Compressibility
by Constant-Depth Circuits (with Arkadev Chattopadhyay), FOCS 2012.
- Macroscopes: Models for Collective Decision
Making (with Subramanian Ramamoorthy and Andras Salamon), Collective
- Instance Compression for the Polynomial
Hierarchy and Beyond (with Chiranjit Chakraborty), IPEC 2012.
- On the Limits of Sparsification (with Srikanth Srinivasan), ICALP 2012.
- Stronger Lower Bounds and Randomness-Hardness Tradeoffs using
Associated Algebraic Complexity Classes (with Maurice Jansen),
- Marginal Hitting Sets imply Super-Polynomial Lower Bounds for
Permanent (with Maurice Jansen), ITCS 2012.
- Exponential Lower Bounds for
AC0-Frege Imply Super-Polynomial Frege Lower Bounds (with Yuval Filmus and Toniann Pitassi), ICALP 2011.
- Robust Simulations and
Significant Separations (with Lance Fortnow), ICALP 2011.
- Permanent does not have Succinct
Polynomial Size Arithmetic Circuits of Constant Depth (with Maurice Jansen), ICALP 2011.
- The Complexity of Explicit
Constructions , CiE 2010.
- Fighting Perebor: New and Improved Algorithms for Formula and QBF Satisfiability , FOCS 2010.
- Bounding Rationality by Discounting
Time (with Lance Fortnow), ICS 2010.
- Effectively Polynomial Simulations
(with Toniann Pitassi), ICS 2010.
- Fractional Pebbling and Thrifty
Branching Programs (with Mark Braverman, Stephen Cook, Pierre McKenzie
and Dustin Wehr), FSTTCS 2009.
- Unconditional Lower Bounds against Advice (with Harry Buhrman
and Lance Fortnow), ICALP 2009.
- Fixed-Polynomial Size Circuit Lower Bounds (with Lance Fortnow
and Ryan Williams), CCC 2009.
- Branching Programs for Tree
Evaluation (with Mark Braverman, Stephen Cook, Pierre Mckenzie and
Dustin Wehr), MFCS 2009.
- Infeasibility of Instance Compression and Succinct PCPs for NP
(with Lance Fortnow), STOC 2008.
- Circuit Lower Bounds for Merlin-Arthur Classes , STOC 2007.
- Some Results on Average-Case Hardness within the Polynomial Hierarchy (with Aduri Pavan and Variyam Vinodchandran), FSTTCS 2006.
- Graph Model Selection using Maximum Likelihood (with Ivona Bezakova and Adam Kalai), ICML 2006.
- Making Hard Problems Harder (with Joshua Buresh-Oppenheim), CCC 2006.
- Hierarchies for Semantic Classes (with Lance Fortnow and Luca
trevisan), STOC 2005.
- Hierarchy Theorems for Probabilistic
Polynomial Time (with Lance Fortnow), FOCS 2004.
- Holographic Proofs and Derandomization (with Dieter van Melkebeek), CCC 2003.
- Segregators, Separators and Time versus
Space , CCC 2001.