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.
Statement for EATCS Council Election 2021: I am honoured to be nominated to serve on the EATCS Council. If elected to serve, I will work toward further increasing the profile of the EATCS flagship conference ICALP, across all areas of theoretical computer science. I look forward to ICALP becoming a real-world conference again, with the unique experience that provides especially for junior members of the community, but I hope to help implement lessons from the Covid pandemic, in terms of using a virtual component to promore inclusivity and diversity. I would also work towards introducing test-of-time awards similar to those recently introduced at STOC, to honour the exemplary ICALP papers of the past. I wish to foster a more unified vision of theoretical computer science, with at least some portion of the keynote program being accessible and interesting to theorists regardless of research area.
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