InterestsComputational complexity, algorithms, bounded rationality.
I am a Professor of Computer Science at Oxford, and a Tutorial Fellow at Magdalen College. I obtained a PhD in Computer Science from the University of Chicago in 2005, working under the supervision of Prof. Lance Fortnow and Prof. Janos Simon. After postdoctoral stints at Simon Fraser University and the University of Toronto, I joined the University of Edinburgh as a Lecturer in Computer Science in 2008. I was promoted to Reader in 2013, and moved to Oxford in 2016. In 2013, I was awarded the ERC Consolidator Grant ALUnif on "Algorithms and Lower Bounds: A Unified Approach", which I held from March 2014 until August 2019.
Fighting Perebor: New and Improved Algorithms for Formula and QBF Satisfiability
Infeasibility of Instance Compression and Succinct PCPs for NP
Rahul Santhanam and Lance Fortnow
Circuit Lower Bounds for Merlin−Arthur Classes
- Randomised Algorithms
- Foundational Issues in Computational Learning
- Exact Algorithms and Fine-Grained Complexity
- Circuit Complexity
- Algorithms At Large