Communications of the ACM
Theory Research in India: 2019–2022
Credit: Synthetick
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. This has led to developing theories of transformations, applications to verification of timed/recursive/concurrent/probabilistic systems, database theory, distributed algorithms, programs running under weak memory models and cryptographic protocols. 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. This lower-bound result also yields the first deterministic sub-exponential time polynomial identity testing algorithm for constant-depth arithmetic circuits via the unconditional construction of pseudo-random generators based on the lower bound for an explicit polynomial.
No entries found