Anil Seth

Professor, Department of CSE, IIT Kanpur., phone (office:) 0512-2597231


  • Ph.D. Computer Science, 1994, TIFR
    (Thesis: Complexity theory of higher type functionals)
  • Faculty: Institute of Mathematical Sciences, Chennai 1994-2001
  • Faculty: I.I.T. Kanpur, since 2001


  • [1] Anil Seth, ''There is No Recursive Axiomatization for Feasible Functionals of Type 2'', In the proceedings of the 7th annual IEEE Symposium on Logic in Computer Science, 1992.
  • [2] Anil Seth, ''Some Desirable Conditions for feasible functionals of type 2'', In the proceedings of the 8th annual IEEE Symposium on Logic in Computer Science, 1993.
  • [3] Anil Seth, ''Turing Machine Characterizations of Feasible Functionals of All Finite Types'', in Feasible Mathematics II, eds. J. Remmel and P. Clote, pages 401-428, Birkhauser, 1995.
  • [4] Anil Seth, ''Type 2 Polynomial Hierarchies'', In proc. Logic and Computational Complexity, ed. D. Leivant, LNCS 960, Springer, 1995.
  • [5] Anil Seth, ''When do Fixed Point Logics Capture Complexity Classes'', In proc. of the 10th annual IEEE Symposium on Logic in Computer Science, San Diego, 1995.
  • [6] Anil Seth, ''Sharper Results on the Expressive Power of Generalized Quantifiers'', In proc. of the 17th conference on Foundations of software technology and theoretical computer science, 1997, LNCS 1346, pp. 200-219.
  • [7] Anil Seth (with Anuj Dawar and Lauri Hella), ''Ordering Finite Variable Types with Generalized Quantifiers'', In proc. of 13th Annual IEEE Symposium on Logic in Computer Science, 1998.
  • [8] Anil Seth, ''On Lk(Q) Types and Boundedness of IFP(Q) on Finite Structures'', In proc. of 5th Asian Computing Science Conference, 1999, LNCS 1742, pp.334-346.
  • [9] Anil Seth (with Ravindra B. Keskar and R. Venugopal), ''Algorithms for energy optimization using processor instructions'', In the proc. of international Conference on Compilers, Architectures and Synthesis for Embedded Systems (CASES01), 2001, pp. 195-202.
  • [10] Anil Seth (with Comandur Seshadhri and Somenath Biswas), ''RAM Simulation of BGS Model of Abstract-state Machines'', Fundamenta Informaticae 77(1-2), 2007 (Special Issue on ASM'05), pp. 175-185.
  • [11] Anil Seth, ''An alternative construction in symbolic reachability analysis of second order pushdown automata,'' In Proc. Satellite workshops of DLT 2007, TUCS publication (45), 2007, pp. 80-95.
  • [12] Anil Seth, ''An alternative construction in symbolic reachability analysis of second order pushdown automata'', International Journal on Foundations of Computer Science 19(4), (Special Issue on RP07), August 2008, pp. 983-998. (This contains only some results from [11] above, but with detailed proofs.)
  • [13] Anil Seth, ''Games on multi-stack pushdown systems'', In Proc. Symposium on Logical Foundations of Computer Science, LFCS 2009 , Deerfield Beach, Florida, USA. LNCS, vol. 5407, pp. 395-408.
  • [14] Anil Seth, ''Games on Higher Order Multi-stack Pushdown Systems'', In proc. third international workshop on Reachability Problems 2009 (RP09), Palaiseau, France, September 23-25, 2009. LNCS, vol. 5797, pp. 203-216.
  • [15] Anil Seth, ''Global Reachability in Bounded Phase Multi-Stack Pushdown Systems'', To appear in proc. 22nd International Conference on Computer Aided Verification (CAV 2010), Edinburgh, UK, July 15-19, 2010.

Technical Reports

  • [1] Anil Seth, ''Type 2 Feasible Functionals in Bounded Arithmetic'', Technical Report, T.I.F.R., 1993
  • [2] Anil Seth, ''Implicit Definability vs. Weak Implicit Definability in Finite Model Theory'', manuscript, 1996
  • [3] Anil Seth, ''An Introduction to Finite Model Theory'', in the notes for School on finite model theory, held on Dec. 15-16, 1998 in Chennai.

Books Edited

  • LNCS 2556 (Jointly with Manindra Agrawal)
  • LNAI 6521 (Jointly with Mohua Banerjee)
  • LIPIcs 24 (Jointly with Nisheeth K. Vishnoi)

Invited Talk

  • A one hour invited talk on feasible functionals at the workshop ''Implicit Computational Complexity'' on July 1, 1999 in Trento, Italy.

Conferences PC

  • PC Co-Chair FSTTCS 2002
  • PC Member FSTTCS 2006
  • PC Member FSTTCS 2010
  • PC Co-Chair ICLA 2011
  • PC Member FSTTCS 2011
  • PC Member FSTTCS 2012
  • PC Co-Chair FSTTCS 2013
  • PC Member FoSSACS 2014
  • PC Member TAMC 2015
  • PC Member TAMC 2017
  • PC Member TAMC 2020
  • PC Member TAMC 2022

Schools & Meetings Organized

  • School on Finite Model Theory organized jointly with Anuj Dawar at IMSc. Chennai, India on December 15-16, 1998. The school was a satellite event to conference FST& TCS 1998.
  • Update meeting on formal methods, IIT Kanpur, April 2007
  • Second Indian winter school on Logic (with M. Banerjee), January 2008.
  • Seventh Indian Conference in Logic and Applications, IIT Kanpur, (with Sunil Simon), January 2017.


  • Recently (2019 onwards) taught
    • Algorithms II (CS345) [To non-CSE students]
    • Data Structures and Algorithms (ESO 207)
    • Mathematics of Computer Science-II [Mathematical Logic] (CS202)
    • Mathematics of Computer Science-I [Discrete Mathematics] (CS201)
  • Less Recently taught
    • Theory of Computation (CS340)
    • Finite Automata on Infinite Inputs (CS644)
    • Programs and Proofs (CS698)
    • Principles of Programming Languages (CS350)
    • Game Theory (CS684)
    • Logic in Computer Science
    • Fundamentals of Computing [JAVA] ESc101