sreejithav@iitgoa.ac.in
F10, Mining Building
IIT Goa, Farmagudi, Ponda, Goa-403401

Sreejith A V (ശ്രീജിത്ത് എ വി)

Assistant Professor, School of Mathematics and Computer Science

Research Interests
Theoretical Computer Science
Logic, Finite model theory
Automata theory, Algebraic automata theory
Computational complexity

Background
B. Tech: College of engineering,Thiruvananthapuram (CET)
M. Tech: IIT, Madras
Ph.D: Institute of Mathematical Sciences, Chennai (under Prof. Kamal Lodaya)
Other Research Positions: University of Tubingen, TIFR - Mumbai, LIAFA - Paris, CMI - Chennai, University of Warsaw - Poland

Announcements

Research Summary

PhD Thesis: Regular quantifiers in Logic (won ACM India Honourable Mention for the dissertation)

Extensions of temporal logic

Linear temporal logic (LTL) and similarly first order logic (FO) over words cannot do modulo counting. For example, the language (aa)* is not definable in LTL. In our paper [Sre], we showed the equivalence of modulo counting extensions of FO and LTL (called FOMOD, LTLMOD respectively). We also looked at the complexity of satisfiability of LTLMOD, various sublogics [LS] and two variable fragments of FO [LS].

Descriptive complexity

First order logic (using arbitrary arithmetic predicates) over words is expressively equivalent to AC0 circuits. Similarly, modulo counting quantifiers and CC0 circuits (see this book by Howard Straubing) are closely related. The relation between many of these circuit classes are open. We look at these questions from the perspective of logic. In our paper [KS] we show that these classes are different for "highly uniform" circuit classes.

Linear Orderings

From the work of Schutzenberger we understand the relation between first order logic and monadic second order logic over finite words. In our work [CS] we looked at the relation between many logics (including FO, WMSO etc) over countable linear orderings. In another work [MS], we gave similar algebraic characterization for two variable FO.

Publications/Notes

11. Notes on Parity games (pdf, abstract)
10. Block Product for finite monoids with generalized associativity, with Saptarshi Sarkar, and Bharat Adsul (pdf, abstract)
9. Block products for algebras over countable words and applications to logic, with Saptarshi Sarkar, and Bharat Adsul, LICS 2019. (pdf, abstract)
8. Two-variable first order logic with counting quantifiers: Complexity Results, with Kamal Lodaya,   DLT 2017. (pdf, abstract)
7. Two-variable logic over countable linear orderings, with Amaldev ManuelMFCS 2016. (pdf, full, abstract)
6. Limited Set quantifiers over Countable Linear Orderings, with Thomas Colcombet, ICALP 2015. (pdf, full, abstract)
5. Counting quantifiers and linear arithmetic on word models, with Kamal Lodaya Asian Logic Conference (ALC), 2014. (pdf)
4. On lower bounds for multiplicative circuits and linear circuits in noncommutative domains, with V. Arvind and S. Raja,  CSR, 2014. (pdf, abstract)
3. Non-definability of Languages by Generalized First-order Formulas over (N, +), with Andreas KrebsLICS 2012. (pdf, full, abstract)
2. Expressive Completeness for LTL With Modulo Counting and Group Quantifiers, Electronic Notes in Theoretical Comp Sci (ENTCS), 2011. (pdf, abstract)
1. LTL can be more succinct, with Kamal Lodaya ATVA 2010. (pdf, abstract)

Teaching

2020
Combinatorial optimization (CS520)
Data Structure (CS113)
2019
Jul-Dec: Logic (CS 228)
Jan-May: Advanced Algorithms (CS 315)
2018
Logic (CS 228): IIT Goa (July-Dec)
Computer Programming (CS 101): Summer course, IIT Goa
Computer Networks Course (CS 348): IIT Goa (Jan-May)
Computer Networks Lab (CS 378): IIT Goa (Jan-May)
Reading Logic with Prince
2016
Descriptive Complexity Theory: An Introduction in Indian School on Logic and its Applications (ISLA),  PSG college of Technology, Coimbatore (March). See the wiki link for Descriptive Complexity,
2012
Verification: Semester course for graduate and undergraduate students in Wilhelm-Schickard-Institute for Informatik, University of Tubingen, Germany (March-August). We looked at Linear temporal logic and its applications