Rahul Santhanam

I am a Lecturer in Informatics at 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 Simon Fraser University, and from 2007-2008 I was visiting the Theory Group in the in the Department of Computer Science at University of Toronto. I joined Edinburgh in August 2007.

Conference Papers and Preprints

• On the Limits of Sparsification (with Srikanth Srinivasan), ECCC report 2011.
• Stronger Lower Bounds and Randomness-Hardness Tradeoffs using Associated Algebraic Complexity Classes (with Maurice Jansen), STACS 2012 (to appear).
• Marginal Hitting Sets imply Super-Polynomial Lower Bounds for Permanent (with Maurice Jansen), ITCS 2012 (to appear).
• 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 (invited talk).
• 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.
• Uniform Hardness Amplification in NP via Monotone Codes (with Joshua Buresh-Oppenheim and Valentine Kabanets), ECCC Report 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.
• Resource Tradeoffs and Derandomization , ECCC Report 2002.
• Segregators, Separators and Time versus Space , CCC 2001.