Theory Research in India: 2019–2022

The deep connections between logic and automata theory have led to extensive applications in formal specification and verification of systems. In recent years, research has focused on extensibility of such techniques to infinite-state systems. Logic has also been the ground for foundational research, revisiting classical model theory from computational perspectives. This has led to results in Skolem Löwenheim theorems in the finite, synthesis of Boolean functions and Skolem functions, definability in first-order theories of graphs, algebraic characterizations, block products of algebraic structures, and decidable fragments of first-order modal logics. The last few years has been a productive period for research in the field of computational complexity in India. The topics in which significant research has been done include algebraic complexity theory, communication complexity, research on codes and expanders arising out of connections to probabilistically checkable proofs, and the dynamic complexity of reachability. Notably, in July 2021, a break-through was achieved in the field of algebraic complexity, showing the first superpolynomial lower bounds against constant-depth arithmetic circuits over fields of characteristic zero or large characteristic.