&ldquo;IIT Jodhpur is committed to impart quality education to facilitate the creation of qualified, competent and responsible human resources to meet the emerging technological challenges of the world. It is working towards creating an equitable learning platform that is positive, accessible and effective in the face of the modern societal and scientific advancements.

Flexibility in curriculum, in all its academic programs, encompassing elements of teaching, research, creativity, innovation and entrepreneurship is the most unique feature of IIT Jodhpur. The Department of Science and Technology (DST), under the National Mission on Cyber Physical Systems, has identified IIT Jodhpur as a Technology &amp; Innovation Hub in the area of Augmented Reality and Virtual Reality. The institute has also been nominated as the coordinator for the Jodhpur City and Knowledge Cluster by the Office of Principal Scientific Adviser, Government of India.

The sprawling 852-acre IIT Jodhpur campus is a majestic tribute to the deep-rooted diverse cultural heritage of the region. The campus is an architectural masterpiece, which is slated to become an international exemplar of sustainability with net-zero energy, and advanced water and waste management strategies.&rdquo;

IIT Jodhpur

Reachability, distance, and matching are some of the most fundamental graph problems that have been of particular interest in dynamic complexity theory in recent years [DKMSZ18, DMVZ18, DKMTVZ20]. Reachability can be maintained with first-order update formulas, or equivalently in DynFO in general graphs with n nodes [DKMSZ18], even under O(log n/loglog n) changes per step [DMVZ18]. In the context of how large the number of changes can be handled, it has recently been shown [DKMTVZ20] that under a polylogarithmic number of changes, reachability is in DynFOpar in planar, bounded treewidth, and related graph classes -- in fact in any graph where small non-zero circulation weights can be computed in NC. We continue this line of investigation and extend the meta-theorem for reachability to distance and bipartite maximum matching with the same bounds. These are amongst the most general classes of graphs known where we can maintain these problems deterministically without using a majority quantifier and even maintain witnesses. For the bipartite matching result, modifying the approach from [FGT], we convert the static non-zero circulation weights to dynamic matching-isolating weights. While reachability is in DynFOar under O(log n/loglog n) changes, no such bound is known for either distance or matching in any non-trivial class of graphs under non-constant changes. We show that, in the same classes of graphs as before, bipartite maximum matching is in DynFOar under O(log n/loglog n) changes per step. En route to showing this we prove that the rank of a matrix can be maintained in DynFOar, also under O(log n/loglog n) entry changes, improving upon the previous O(1) bound [DKMSZ18]. This implies similar extension for the non-uniform DynFO bound for maximum matching in general graphs and an alternate algorithm for maintaining reachability under O(log n/loglog n) changes [DMVZ18].

World University root node

Department of Computer Science & Engineering

arXiv preprint arXiv:2109.

Dynamic Meta-theorems for Distance and Matching

We show that for each single crossing graph H, a polynomially bounded weight function for all H-minor free graphs G can be constructed in Logspace such that it gives nonzero weights to all the cycles in G. This class of graphs subsumes almost all classes of graphs for which such a weight function is known to be constructed in Logspace. As a consequence, we obtain that for the class of H-minor free graphs where H is a single crossing graph, reachability can be solved in UL, and bipartite maximum matching can be solved in SPL, which are small subclasses of the parallel complexity class NC. In the restrictive case of bipartite graphs, our maximum matching result improves upon the recent result of Eppstein and Vazirani, where they show an NC bound for constructing perfect matching in general single crossing minor free graphs.

arXiv preprint arXiv:2103.

Reachability and Matching in Single Crossing Minor Free Graphs

A catalytic Turing machine is a model of computation that is created by equipping a Turing machine with an additional auxiliary tape which is initially filled with arbitrary content; the machine can read or write on auxiliary tape during the computation but when it halts auxiliary tape’s initial content must be restored. In this paper, we study the power of catalytic Turing machines with O(logn) -sized clean tape and a polynomial-sized auxiliary tape.We introduce the notion of randomized catalytic Turing machine and show that the resulting complexity class CBPL is contained in the class ZPP . We also introduce the notion of symmetricity in the context of catalytic computation and prove that, under a widely believed assumption, in the logspace setting the power of a randomized catalytic Turing machine and a symmetric catalytic Turing machine is equal to a deterministic catalytic Turing machine which runs in polynomial time.

International Computer Science Symposium in Russia

Randomized and Symmetric Catalytic Computation

We show that given an embedding of an O(log n) genus bipartite graph, one can construct an edge weight function in logarithmic space, with respect to which the minimum weight perfect matching in the graph is unique, if one exists. As a consequence, we obtain that deciding whether such a graph has a perfect matching or not is in SPL. In 1999, Reinhardt, Allender and Zhou proved that if one can construct a polynomially bounded weight function for a graph in logspace such that it isolates a minimum weight perfect matching in the graph, then the perfect matching problem can be solved in SPL. In this paper, we give a deterministic logspace construction of such a weight function for O(log n) genus bipartite graphs.

45th International Symposium on Mathematical Foundations of Computer Science …

Efficient Isolation of Perfect Matching in O (log n) Genus Bipartite Graphs

We show that given an embedding of an O(log n) genus graph G and two vertices s and t in G, deciding if there is a path from s to t in G is in unambiguous logarithmic space. Unambiguous computation is a restriction of nondeterministic computation where the nondeterministic machine has at most one accepting computation path on each input. An important fundamental question in computational complexity theory is whether this is an actual restriction or are unambiguous computations as powerful as general nondeterminism. We investigate this problem in the domain of logarithmic space bounded computations, where the corresponding unambiguous and general nondeterministic classes are UL and NL respectively. In 1997 Reinhardt and Allender showed that NL and UL are equal in a non-uniform model. More specifically they showed that if one can efficiently construct an O(log n)-bit min-unique weight function for a graph, then these classes are equal unconditionally as well. In other words, they gave a UL algorithm to solve reachability in graphs with a min-unique weight assignment. Using this approach reachability in various classes of graphs such as planar graphs, constant genus graphs, minor free graphs, etc., have been shown to be in UL by devising min-unique weight functions for those classes. In this paper we improve these results by constructing a min-unique weight function for O(log n) genus graphs. We define signature of a path in a graph as the parity of the number of crossings of that path with respect to each handle of the surface on which the graph is embedded. We construct our weight function in two steps. First we ensure that between any pair of vertices, amongst all paths having the same signature, the minimum weight path is unique. Now since in a genus g graph there are 2^{2g} many possible signatures, we use the hashing scheme of Fredman, Komlós and Szemerédi to isolate a unique minimum weight path among these 2^{2g} many paths isolated in the first step.

36th International Symposium on Theoretical Aspects of Computer Science …

Reachability in O (log n) Genus Graphs is in Unambiguous Logspace

The catalytic Turing machine is a model of computation defined by Buhrman, Cleve, Koucký, Loff, and Speelman (STOC 2014). Compared to the classical space-bounded Turing machine, this model has an extra space which is filled with arbitrary content in addition to the clean space. In such a model we study if this additional filled space can be used to increase the power of computation or not, with the condition that the initial content of this extra filled space must be restored at the end of the computation. In this paper, we define the notion of unambiguous catalytic Turing machine and prove that under a standard derandomization assumption, the class of problems solved by an unambiguous catalytic Turing machine is same as the class of problems solved by a general nondeterministic catalytic Turing machine in the logspace setting.