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. 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.

The algorithmic paradigms at the forefront of exciting new research in the field of algorithms in India include, but are not limited to, approximation algorithms, randomized algorithms, computational geometry, online algorithms, dynamic algorithms, parameterized algorithms, algorithmic game theory, and theoretical foundation of machine learning and big data. Some of the exciting results include constant factor approximation algorithm for finding a maximum independent set of rectangles, improved bounds for perfect sampling of k-coloring in graphs, an optimal FPT-approximation scheme for k-way cut, and a new online algorithm for caching.

The leading institutes where such research has been conducted include Chennai Mathematical Institute, Indian Institute of Science, Indian Institute of Technology Bombay, Indian Institute of Technology Goa, Indian Institute of Technology Kanpur, Indian Institute of Technology Delhi, and the Institute of Mathematical Sciences. Here, we explore some of the results of this research.

Back to Top

Automata Theory and Verification Research

Automata theory and formal languages. In the area of formal languages and automata theory, Indian researchers have contributed toward finding alternate characterizations of interesting language classes by means of logic, expressions, and algebra. We highlight a seminal result that presents regular expressions for transducers.

Transducer expressions. A finite state transducer is an extension of a finite state automaton with outputs and recognizes transformations. Regular functional word transductions have different machine characterizations including streaming string transducers, two-way transducers as well as logical characterizations. In 2018, Vrunda Dave, Paul Gastin, and S. Krishna (IIT Bombay) proposed regular transducer expressions (RTE) to capture regular transductions over finite and infinite strings.⁸ At the level of transformations, this is the analogue of the classical Kleene theorem in automata theory that says regular expressions capture regular languages. Unlike finite state automata, the ability to move in both directions (two-wayness) increases expressiveness and complexity in transducers, making this equivalence with respective expressions non-trivial.

While the machine model is two-way, the corresponding expression must be computed in a one-way manner. This is achieved by viewing the problem algebraically and defining a transition monoid of the two-way transducer. The transition monoid compactly summarizes the runs of the transducer in all directions, between any pair of states, and helps to unambiguously “factorize” in a oneway manner, the runs of the two-way transducer. The building blocks of the RTE are simple functions describing outputs of individual transitions, and are merged using suitable combinators that unite the factorized blocks of a run. The algebraic approach seamlessly provides the equivalence between RTE and deterministic two-way transducers both over finite and infinite words.

In formal language theory, aperiodic languages are a proper subclass of regular languages, and a seminal result of Schützenberger states that star-free regular expressions recognize precisely aperiodic languages. Unlike regular expressions, star-free expressions allow negation; in the setting of functions, the corresponding analogue is unclear. In 2021, Krishna, Gastin, and Luc Dartois showed the analogue of Schutzenberger’s result for transformations.⁹ Corresponding to aperiodic two-way transducers, they propose transducer expressions in which the use of Kleene-star is restricted. The Kleene star is allowed only on expressions, which are aperiodic and have bounded synchronization delay. Recently they have proposed an efficient algorithm for translation between transducers and expressions.⁷ Their algorithm is the first known one which has an elementary complexity.

Formal verification. In the area of formal verification, there has been contributions from India in terms of formal models and verification algorithms for different settings. Formal models have been introduced for some classes of database-driven systems, distributed algorithms, and memory models, among others. New verification algorithms haven been proposed for classes of {Timed, Probabilistic, Multi-pushdown, Message-passing} models of automata. We elaborate here a bit on one of our favorites:

A well-structured model for persistent Intel x86. An impressive result by Abdulla et al. is a formal model for the Persistent Intel x86 architecture. Though not the first formal model for Persistent Intel x86, this one has the property of being well structured. While the model gives rise to infinite state space, well structuredness gives a well quasi ordering between the infinite states, which guarantees that there will not be infinite descending chains. This crucial property can be exploited to obtain terminating verification algorithms. Thanks to this, the authors show that verifying safety properties is decidable. K. Narayan Kumar (CMI, Chennai) and Prakash Saivasan (IMSc, Chennai) are co-authors of this work.¹

Back to Top

Computational Complexity Research

The research themes include algebraic complexity theory, communication complexity, codes, expander graphs and their connections to probabilistically checkable proofs, and the dynamic complexity of reachability. We highlight two excellent recent results in the field of algebraic complexity:

• In July 2021, Nutan Limaye (IIT, Bombay), Srikanth Srinivasan (IIT Bombay), and Sebastian Tavenas (Savoie University) obtain a break-through in algebraic complexity theory by showing the first superpolynomial lower bounds against constant-depth arithmetic circuits over fields of characteristic zero (or of large characteristic). This paper was subsequently presented at this year’s IEEE 2021/2022 Symposium on Foundations of Computer Science and won the best paper award.²⁷
• About six months prior to that, Arkadev Chattopadhyay (TIFR, Mumbai), Rajit Datta (CMI), and Partha Mukhopadhyay (CMI) showed an exponential monotone arithmetic circuit complexity lower bound for a polynomial that has depth-3 arithmetic circuits of polynomial size⁶ at the 2021 Symposium on Theory of Computing.

Arithmetic circuits and lower bounds. An arithmetic circuit is a directed acyclic graph (DAG). Its nodes are gates. Each in-degree zero node is an input gates labeled by a variable x_i or scalar. Each internal gate has in-degree 2 and is labeled + or X (sum or product gate). Clearly, each gate computes a polynomial and the output gate produces the polynomial computed by the circuit (for example, see the accompanying figure).

Figure. An example of an arithmetic circuit.

The circuit size is the number of gates. Its depth is the length of the longest input to output path. The circuit in the figure has size 6 and depth 2. In 1979, Valiant defined the algebraic analogues of P and NP, denoted VP and VNP. where VP stands for families of polynomials that have polynomial size and polynomial-degree arithmetic circuits and VNP contains easily described but potentially hard polynomials. He also raised the VP vs. VNP problem and suggested they could be easier to separate than P and NP. However, while superlinear lower bounds for arithmetic circuits computing explicit polynomials were easy to show (Baur and Strassen, 1983), superpolynomial lower bounds for constant-depth circuits in the Boolean setting was shown in the 1980s (Furst, Sax, and Sipser in 1983 followed by Hästad in 1986 showing optimal lower bounds for the parity function).

Lower bounds for constant-depth arithmetic circuits. We outline Limaye et al.’s result. Consider the iterated matrix product X₁ X₂ ··· X_d where each X₁ is an n × n matrix of distinct variables X_ijk 1 < j, k < n. The (1, 1)^th entry of this matrix product is the explicit polynomial P_n,d, which is homogeneous of degree d. They show that for d = o(log n) the size of any (constant) depth c arithmetic circuit computing P_n,d has size at least n^dε for a constant ε > 0 that depends on c. A surprising aspect is the proof is based on the so-called partial derivative method, due to Nisan and Wigderson in 1995, which is a standard method for many of the arithmetic circuit lower bounds and in recent years believed to be inadequate for arithmetic circuits of depth more than 3. It is known that P_n,d has “large” dimensional partial derivative space. On the other hand, exploiting the circuit structure, Limaye et al. show the partial derivative space for any polynomial computed by a size s circuit has “small” dimension (as a function of s). Combining the two yields the lower bound on s.

The circuit structure they exploit is set-multilinearity. The polynomial P_n,d is homogeneous of degree d, and it is set multilinear: each nonzero monomial has exactly one variable from each X_i. A set-multilinear circuit for P_n,d is one in which each gate computes some set-multilinear polynomial (in a subset of the variable sets X₁ X₂ ··· X_d). Their lower bound result has two components:

• Any depth c size s arithmetic circuit computing a degree P set-multilinear polynomial P can be transformed into a depth 2c size poly(s)d^O(d) set-multilinear circuit for P.
• Depth c set-multilinear circuits for P_n,d, for d = O(log n), requires n^dε for some constant ε > 0 depending on c.

Lower bounds for monotone arithmetic circuits. The result of Chattopadhyay et al. concerns monotone polynomials and monotone arithmetic circuits. A multivariate polynomial with rational (or real) coefficients is monotone if all nonzero coefficients are positive. A monotone arithmetic circuit is allowed to use only positive numbers as scalars. Thus, monotone circuits compute monotone polynomials. The power of “non-monotone” computation in arithmetic circuits was first studied in 1980 by Valiant (who else?) and he showed an explicit monotone n-variate polynomial that requires exponential size monotone circuits but can be computed by polynomial size circuits if allowed subtractions. Chattopadhyay et al. show an explicit n-variate monotone polynomial that has depth three polynomial size arithmetic formulas but requires exponential size monotone arithmetic circuits. An added dimension to their paper is the use of communication complexity techniques to prove the lower bound.

Back to Top

Algorithms Research

The last few years have seen some exciting new research in the field of algorithms in India. As noted earlier, the algorithmic paradigms at the forefront for such research include approximation algorithms, randomized algorithms, computational geometry, online algorithms, dynamic algorithms, parameterized algorithms, algorithmic game theory and theoretical foundation of machine learning and big data, among others. We highlight a few excellent recent results in the field of algorithms.

A k-coloring of a graph, G = (V, E), is an assignment of colors from the set [k] = {1, 2, …, k} to the vertices so that adjacent vertices are assigned different colors. That is, it is a function f: V → [k], so that for any edge uv ∈ E, we have that f(u) ≠ f(v). Bhandari and Chakraborty⁴ considered the problem of randomly sampling colorings of a given graph. The input is a graph G and an integer k: goal is to generate a G-coloring uniformly at random from the set of all k-colorings of G. That is, let G be the set of all functions f: V → [k], so that for any edge uv ∈ E, we have that f(u) ≠ f(v), then the objective is to output a function g ∈ G with probability . The problem of sampling k-colorings has several implications in theoretical computer science and statistical mechanics. For example, in statistical mechanics, sampling proper colorings is central to simulation-based studies of phase transitions and correlation decay.

The problem is computationally tractable if we are allowed significantly more colors than the maximum degree Δ of the graph. The more colors we are allowed, the easier it appears to be to produce a random k-coloring. Indeed, if k is much smaller than Δ, it is NP-hard to even determine whether a valid k-coloring exists. Sampling algorithms, therefore, typically require a lower bound on k in terms of Δ to guarantee efficiency. There has been a steady stream of works that have progressively reduced the lower bound on k in terms of Δ. Bhandari and Chakraborty⁴ presented a randomized algorithm that takes as input an undirected n-vertex graph G with maximum degree Δ and an integer k > 3Δ and returns a random proper k-coloring of Δ. The distribution of the coloring is perfectly uniform over the set of all proper k-colorings; the expected running time of the algorithm is poly(k, n) = Õ (n Δ² · log(k)). This improved upon a result of Huber (STOC 1998) who obtained a polynomial time perfect sampling algorithm for k > Δ² + 2Δ. Prior to this work, no algorithm with expected running time poly(k, n) was known to guarantee perfectly sampling with sub-quadratic number of colors in general. This paper appeared at STOC 2020, where Bhandari and Chakraborty received the Danny Lewin Best Student Paper Award.

---

In the area of formal verification, there has been contributions from India in terms of formal models and verification algorithms for different settings.

---

Here, we briefly note two other results of great importance: In the Maximum Independent set of Rectangles (MISR) problem, we are given a set of axis-parallel rectangles in the plane and the goal is to select a subset of non-overlapping rectangles of maximum cardinality. The problem was known to admit a polynomial time approximation scheme running in quasi-polynomial time, however in polynomial time finding even a constant factor approximation algorithm was well known open problem for decades. In a recent breakthrough, Mitchell³² obtained the first constant factor approximation algorithm for MISR. His algorithm achieves an approximation ratio of 10. In a recent paper, Khan,¹¹ together with his colleagues, designed (2 + ε)-approximation algorithm for MISR based on a recursive partitioning scheme.

Kumar,²¹ together with his colleagues, considered two generalizations of the classical weighted paging problem that incorporate the notion of delayed service of page requests. The first is the (weighted) Paging with Time Windows (PAGETW) problem, which is like the classical weighted paging problem except that each page request only needs to be served before a given deadline. This problem arises in many practical applications of online caching, such as the “deadline” I/O scheduler in the Linux kernel and video-on-demand streaming. The second, and more general, problem is the (weighted) (PAGED) problem, where the delay in serving a page-request results in a penalty being assessed to the objective. This problem generalized the caching problem to allow delayed service, a line of work that has recently gained traction in online algorithm. Authors give O(log k log n)-competitive algorithms for both the PAGETW and PAGED problems on n pages with a cache of size k. This significantly improves on the previous best bounds of O(k) for both problems. This paper appeared in STOC 2020.

Worst-case running time analysis has been at the center of nearly all developments in theoretical computer science since the inception of the field. Nevertheless, this approach to measuring algorithm efficiency has its own limitations. It is never the case the input size is the only aspect of the input instance that affects the running time of an algorithm. Further, it is rarely the case that the input instances we want to solve look like the instances on which the algorithm performs the worst. In particular, the real-world instances are not worst-case instances; they exhibit additional structure that can often be exploited algorithmically. Thus, there is a real need for a mathematical framework that allows us to express the running time of algorithms in terms of both input size and the structural properties of the input instances. A particularly successful attempt at creating such a mathematical model is the field of Parameterized Complexity. This area has bloomed greatly in India, over the last two decades.

---

There is a real need for a mathematical framework that allows us to express the running time of algorithms in terms of both input size and the structural properties of the input instances.

---

The goal of Parameterized Complexity is to find ways of solving NP-hard problems more efficiently than brute force—the aim is to restrict the combinatorial explosion to a parameter that is hopefully much smaller than the input size. Formally, a parameterization of a problem is assigning an integer k to each input instance and we say that a parameterized problem is fixed-parameter tractable (FPT) if there is an algorithm that solves the problem in time f(k)|I|^O(1), where |I| is the size of the input and d is an arbitrary computable function depending on the parameter k only. There is also a theory of hardness that allows us to show that certain parametrized problem is not amenable to this approach. We highlight a result about Graph Isomorphism in this area that include authors from Indian institutes.

In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of and G and H, f: V(G) → V (H) such that any two vertices u and v of G are adjacent in G if and only if f(u) and f(v) are adjacent in H. In the Graph Isomorphism problem, given two graphs G and H, the objective is to test whether G and H are isomorphic. The Graph Isomorphism problem is arguably the most widely known problem whose membership in P is unknown, but which is not believed to be NP-hard. After decades of research, a quasi-polynomial time algorithm was proposed by Babai in 2015.²

While the existence of a polynomial-time algorithm on general graphs is still elusive, the complexity of Graph Isomorphism has been well understood on several classes of graphs, where structural properties of graphs in question have been used to design polynomial-time procedures solving the problem. Classic results in this area include an n^o(d)-time algorithm on graphs of maximum degree d,^3,30 a polynomial-time algorithm for planar graphs,^22,23,24,36 an n^o(g)-time algorithm on graphs of Euler genus g,^10,31 an O(n^k+4.5)-time algorithm for graphs of treewidth k,⁵ an n^O(k)-time algorithm for graphs of rankwidth k,^16,19 an n^f(|H|)-time algorithm for graphs excluding a fixed graph H as a minor,³⁵ and an n^f(|H|)-time algorithm for graphs excluding a fixed graph H as a topological minor¹⁴ (where f is some computable function).

In all the results mentioned here, the degree of the polynomial bound on the running time depends on the parameter—maximum degree, genus, treewidth, rankwidth, or the size of the excluded (topological) minor—in at least a linear fashion. Since the parameter can be as high as linear in the size of the graph, for large values of the parameter the running time bound of the quasi-polynomial-time algorithm of Babai,² which works on general graph, is preferable. During the last few years, there has been several successful attempts of bridging this gap by using the group-theoretic approach of Babai in conjunction with structural insight about considered graph classes. This led to algorithms with running time of the form n^polylog(p), where p is any of the following parameters: maximum degree,¹⁷ Euler genus,³³ treewidth,³⁷ and the size of a fixed graph H excluded as a minor.²⁰ We refer to a recent survey¹⁵ for an excellent exposition.

A parallel line of research is to turn the aforementioned algorithms into fixed-parameter algorithms for the parameters in question. That is, instead of a running time bound of the form n^f(p) for a computable function f and a parameter p, we would like to have an algorithm with running time bound f(p) · n^c for a universal constant c. In other words, the degree of the polynomial governing the running time bound should be independent of the parameter; only the leading multiplicative factor may depend on it. In this line of research, Lokshtanov et al.²⁸ developed an FPT algorithm for Graph Isomorphism parameterized by treewidth. This result has been subsequently improved and simplified,¹⁸ as well as used to give a slice-wise logspace algorithm. In 2015, Kawarabayashi²⁵ announced an FPT algorithm for Graph Isomorphism parameterized by the Euler genus of the input graph, with a linear dependency of the running time on the input size. Very recently, Neuen³⁴ proposed a different and simpler algorithm for this case, which runs in time 2^{O(g4log g)}, for some constant c. The recent survey¹⁵ mentions obtaining FPT algorithms with parameterizations by the size of an excluded minor, maximum degree, and the size of an excluded topological minor as important open problems. (Note that the last parameter, the size of an excluded topological minor, generalizes the other two.)

Lokshtanov et al.²⁹ essentially solve the first of these open problems. Graph Isomorphism in graphs excluding a fixed graph H as a minor can be solved by an algorithm working in time f(H) · n^O(1), where f is some function. In other words, it shows these problems are fixed-parameter tractable when parameterized by the size of the excluded minor. The underlying approach is based on decomposing the graph in a canonical way into unbreakable (intuitively, well-connected) parts, which essentially provides a reduction to the case where the given H-minor-free graph is unbreakable itself. This is complemented by an analysis of unbreakable H-minor-free graphs, which reveals that every such graph can be canonically decomposed into a part that admits few automorphisms and a part that has bounded treewidth. This paper appeared in STOC 2022.²⁹

We also mention another result in brief. In the MIN k-CUT problem, input is an edge weighted graph G and an integer k, and the task is to partition the vertex set into k non-empty sets, such that the total weight of the edges with endpoints in different parts is minimized. When k is part of the input, the problem is NP-complete and hard to approximate within any factor less than 2. Lately, the problem had received significant attention from the perspective of parameterized approximation, and several algorithms were presented at the top venues of theoretical computer science. In this paper, authors give a parameterized approximation algorithm with best possible approximation guarantee, and best possible running time dependence on said guarantee (up to Exponential Time Hypothesis (ETH) and constants in the exponent). In particular, for every ε > 0, the algorithm obtains a (1 + ε)-approximate solution in time (k/ε)^O(k)n^O(1). The paper appeared at FOCS 2020.²⁶