Anil Shukla

Assistant Professor
Computer Science and Engineering
Indian Institute of Technology, Ropar

Office: Room 214, Ramanujan Block,
Department of Computer Science and Engineering
Indian Institute of Technology, Ropar
Rupnagar - 140001, Punjab, India.
Email: anilshukla AT iitrpr DOT ac DOT in
Google Scholar | DBLP | ECCC

Education

• Ph.D. in Theoretical Computer Science, IMSc, Chennai (2011–2017), Advisor: Prof. Meena Mahajan
• M.Tech. in Department of Computer Science, IIT Kanpur (2008–2010), Advisor: Prof. Shashank K. Mehta
• B.E. in Computer Science, Chouksey Engineering College, Bilaspur (2002–2006)

Research Interests

Proof complexity, Computational complexity

Journal Publications

1. Extending Merge Resolution to a Family of QBF-Proof Systems
   Sravanthi Chede, Anil Shukla. ACM Transactions on Computation Theory (ACM TOCT), 2026. ISSN: 1942-3454.
2. Understanding Cutting Planes for QBFs
   Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla. Information and Computation, Volume 262 (2018).
3. Are Short Proofs Narrow? QBF Resolution is Not So Simple
   Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla. ACM Transactions on Computational Logic, Volume 19 (2018).
4. Feasible Interpolation for QBF Resolution Calculi
   Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla. Logical Methods in Computer Science, Volume 13 (2017).
5. Level-Ordered Q-Resolution and Tree-Like Q-Resolution are Incomparable
   Meena Mahajan, Anil Shukla. Information Processing Letters, Volume 116 (2016).

Conference Publications

1. On Proof Systems for #QBF
   Sravanthi Chede, Leroy Chew, Vaibhav Krishan, Anil Shukla.
   The 29th International Conference on Theory and Applications of Satisfiability Testing (SAT) 2026.
   July 20-23, 2026, Lisbon, Portugal [ECCC], [arXiv]
2. Circuits, Proofs and Propositional Model Counting
   Sravanthi Chede, Leroy Chew, Anil Shukla.
   44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS) 2024.
   December 16–18, 2024, Gandhinagar, India. [ECCC], [Proceedings]
3. Extending Merge Resolution to a Family of QBF-Proof Systems
   Sravanthi Chede, Anil Shukla.
   40th International Symposium on Theoretical Aspects of Computer Science (STACS) 2023.
   March 7-9, 2023, Hamburg, Germany [ECCC], [Proceedings]
4. Understanding Cutting Planes for QBFs
   Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla.
   36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS) 2016.
   December 13–15, 2016, Chennai, India [ECCC], [Proceedings]
5. Are Short Proofs Narrow? QBF Resolution is not Simple
   Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla.
   33rd Symposium on Theoretical Aspects of Computer Science (STACS) 2016.
   February 17-20, 2016, Orléans, France [ECCC], [Proceedings]
6. Feasible Interpolation for QBF Resolution Calculi
   Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla.
   42nd International Colloquium on Automata, Languages, and Programming (ICALP) 2015.
   July 6-10, 2015, Kyoto, Japan [ECCC], [Proceedings]

Data Sets

• Anil Shukla, Sravanthi Chede. Hamming weight based model counting benchmarks [Data set].
  Zenodo (2025). doi:10.5281/zenodo.15238543.
  • [Access Data Set], [Benchmark Description]

Technical Reports

• On Proof Complexity for Quantified Boolean Formulas, Doctoral Dissertation, The Institute of Mathematical Sciences, Chennai, February 2017.
• Resolution proof systems, pre-PhD Report, June 2013.
• Exact Algorithms for Graph Coloring and Related Problems, Master's Dissertation, IIT Kanpur, July 2010.

Preprints

1. Understanding Nullstellensatz for QBFs
   Sravanthi Chede, Leroy Chew, Balesh Kumar, Anil Shukla. Electron. Colloquium Comput. Complex. (ECCC), TR23 (2023).
2. Does QRAT simulate IR-calc? QRAT simulation algorithm for ∀Exp+Res cannot be lifted to IR-calc
   Sravanthi Chede, Anil Shukla. Electron. Colloquium Comput. Complex. (ECCC), TR21 (2021).
3. Relating two width measures for resolution proofs
   Andreas Krebs, Meena Mahajan, Anil Shukla. Electron. Colloquium Comput. Complex. (ECCC), TR16 (2016).

Students

Ph.D. Students

• Ravi Kumar (2026–Present)
  Title: Ongoing
• Sravanthi Chede (2020–2025)
  Title: Proof Complexity of Quantified Boolean Formulas and Propositional Model Counting, December 2025

M.Tech. Students

• Minakshi Lakhiwal (2025–Present) — Roll: 2025csm1011
  Title: Ongoing
• Sushruta Behera (2024–2026) — Roll: 2024csm1017
  Title: A Study of Partitioned-Operation Graphs for Knowledge Compilation
• Umesh Meena (2022–24) — Roll: 2022csm1016
  Title: Optimizing Graph Space Complexity: Harnessing Semi-Streaming Algorithms
• Hanumat Lal Vishwakarma (2021–23) — Roll: 2021csm1019
  Title: Deterministic Graph Sparsification Algorithm of Dynamic Fractional Matching
• KM Pooja (2021–23) — Roll: 2021csm1011
  Title: Connectivity Problem in Dynamic Graph Using Spanning Trees
• Harpal Singh (2020–22) — Roll: 2020aim1001
  Title: Resolution Proof Systems

Teaching

Current teaching

• CS101: Discrete Mathematical Structures, IIT Ropar. (Enrollment: 211)
• CS536: Graph Theory, IIT Ropar. (Enrollment: 01)

Workshops Attended

• Complexity Theory Update Meeting, IMSc, Chennai, 2026
• Complexity Theory Update Meeting, IMSc, Chennai, 2025
• Milestones and Motifs in the Theory of Proofs, Algebraic Computation, and Lower Bounds, IIT Gandhinagar, 2024
• Dagstuhl Seminar 20061 on SAT and Interactions, Germany, 2020
• Indian SAT+SMT School, TIFR, Mumbai, 2016
• Dagstuhl Seminar 16381 on SAT and Interactions, Germany, 2016
• Academic Research Summit, Infosys Pune, 2016
• Indo-UK Workshop on Computational Complexity, IMSc, 2015
• Workshop on Algorithms and Complexity, Infosys Mysore, 2012

Research Visit

• University of Leeds, UK (Apr–May 2015), Project: "Correctness by Construction" (Host: Prof. Olaf Beyersdorff)

Photo Gallery

View Photo Gallery