Home Publications Thesis CV

Research Associate Department of Computer Science University of Oxford Email: erfan [dot] khaniki [at] cs [dot] ox [dot] ac [dot] uk [Google Scholar] [DBLP]

About me

I am a research associate (postdoc) in the Department of Computer Science at the University of Oxford, hosted by Ján Pich.
Previously, I was a PhD student at the Institute of Mathematics of the Czech Academy of Sciences and the Department of Algebra at the Faculty of Mathematics and Physics of Charles University, where I was advised by Pavel Pudlák.
Before that, I completed my MSc at the Department of Mathematical Sciences of Sharif University of Technology, where I was advised by Mohammad Ardeshir and Pavel Pudlák. Prior to that, I earned my BScs at the Department of Mathematical Sciences and the Computer Engineering Department of Sharif University of Technology, where I was advised by Mohammad Ardeshir.

Research Interests

Proof Complexity and Bounded Arithmetic, including its Model Theory

Intuitionistic Arithmetic and its Model Theory

Publications

(In mathematics and theoretical computer science, author order is typically alphabetical.)

• How hard is it to prove the Dual Weak Pigeonhole Principle constructively?
  Erfan Khaniki
  Submitted manuscript, 2025
  
• Efficient adversaries
  Erfan Khaniki, Ján Pich, Dmitry Sokolov
  Submitted manuscript, 2025
  
• The Proof Analysis Problem
  Noel Arteche, Albert Atserias, Susanna F. de Rezende, Erfan Khaniki
  To appear in the 66th Annual Symposium on Foundations of Computer Science (FOCS 2025), 2025
  [arXiv]
• Jump operators, Interactive Proofs and Proof Complexity Generators
  Erfan Khaniki
  In the 65th Annual Symposium on Foundations of Computer Science (FOCS 2024), pages: 573-593, 2024
  
• The provably total functions of basic arithmetic and its extensions
  Mohammad Ardeshir, Erfan Khaniki, Mohsen Shahriari
  Archive for Mathematical Logic, 64: 205–257, 2025
  [arXiv]
• From Proof Complexity to Circuit Complexity via Interactive Protocols
  Noel Arteche, Erfan Khaniki, Ján Pich, Rahul Santhanam
  In the 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024), volume 297 of Leibniz International Proceedings in Informatics (LIPIcs), pages 12:1-12:20, 2024
  [arXiv]
• TFNP Intersections Through the Lens of Feasible Disjunction
  Pavel Hubáček, Erfan Khaniki, Neil Thapen
  In the 15th Innovations in Theoretical Computer Science Conference (ITCS 2024), volume 287 of Leibniz International Proceedings in Informatics (LIPIcs), pages 63:1–63:24, 2024
• New relations and separations of conjectures about incompleteness in the finite domain
  Erfan Khaniki
  The Journal of Symbolic Logic, 87(3):912–937, 2022
  [arXiv]
• On Proof complexity of Resolution over Polynomial Calculus
  Erfan Khaniki
  ACM Transactions on Computational Logic, 23(3), 2022
  [ECCC]
• Nisan-Wigderson Generators in Proof Complexity: New Lower Bounds
  Erfan Khaniki
  In the 37th Computational Complexity Conference (CCC 2022), volume 234 of Leibniz International Proceedings in Informatics (LIPIcs), pages 17:1–17:15, 2022
  [ECCC]
• Not all Kripke models of HA are locally PA
  Erfan Khaniki
  Advances in Mathematics, 397:22, 2022
  [arXiv]
• A Counterexample to Polynomially Bounded Realizability of Basic Arithmetic
  Mohammad Ardeshir, Erfan Khaniki, Mohsen Shahriari
  Notre Dame Journal of Formal Logic, 60(3):481–489, 2019

Thesis

• (Im)possibility results in Proof Complexity and Arithmetic
  PhD Thesis
  Co-winner of the 2024 Sacks Prize for the most outstanding doctoral dissertation in mathematical logic
  Co-winner of the 2023 Antonín Svoboda for the best PhD thesis