Past Talks

Formal verification is the rigorous process of mathematically demonstrating that code adheres to its specified requirements. A central challenge in this formal verification is constructing loop invariants and function summaries capable of summarizing all possible code behaviors. However, manually devising these invariants can be a laborious task, often acting as a significant deterrent for those who are not experts in the field. This presentation delves into the realm of automatic program verification (APV) tools, which have the capacity to systematically generate these essential invariants without necessitating the involvement of a domain expert. This innovation serves as a catalyst for broader adoption of formal verification methods. Currently, the best method for APV is SMT-based infinite state model checking, especially based on the IC3 algorithm.

In this talk, I explore two key struggles in such algorithms and our attempts to overcome them. The first problem is generalizing lemmas, learned locally while proving sub-goals, into an invariant of the whole system. We address the problem by coming up with a framework to generalize lemmas using lemmas learned previously. The second problem with such algorithms is that they get stuck in complicated code fragments. As a first step towards overcoming this, we add the capability to reason about uninterpreted functions in our algorithm. We implement our solutions in Spacer, the default model- checking engine inside Z3 – an open-source SMT solver. Our solutions improve the performance of Spacer on a wide variety of benchmarks.

The advent of Massive Open Online Courses (MOOCs) has tremendously increased the learning opportunities for the masses. However, one drawback of the current course setting (in both MOOCs and regular classroom teaching) is the ‘one-size-fits-all’ strategy of content delivery that does not cater to the individual learning needs and abilities of students. Personalised learning approaches tailored to address the unique needs, skills, and interests of each student have been shown to result in substantial improvements in learning outcomes of students, in addition to offering an immersive learning experience. Artificial Intelligence (AI) is being increasingly utilized in the development of personalized learning systems that use machine learning (ML) algorithms to create optimal customized learning paths or strategies tailored to suit each student’s cognitive abilities and learning requirements, that are learnt through the interactions of the student with the system.

As a part of our research, we developed novel AI based models and techniques for three foundational problems in personalized learning systems. This talk describes our research contributions to the problem of teaching a set of related topics, also referred to as a curriculum, to a student through adaptive sequencing of activities and learning resources. In this work, we examine two different settings for studying a concept, which is defined as the smallest unit of learning. The first is the learning by doing (LbD) setting where concepts are learned by doing activities or solving problems that also serve as assessments of their mastery of the concept. In the second setting, learning takes place through engagement with various educational resources such as videos, textbook sec- tions and worked-out examples. While much of the previous research on adaptive sequencing in these contexts lacks a rigorous mathematical construct, in our work, we develop personalized sequencing models utilizing principles from learning theory within the frameworks of optimization and decision-theory-based planning. Another novelty is that unlike many of the existing approaches for adaptive sequencing, our algorithms do not rely on any specific knowledge tracing paradigm for modeling the student learning, which improves personalization. Focused on the fundamental elements of concepts, content and assessment items, we propose AI based novel techniques for personalized tutoring of a curriculum to a student through optimal sequencing of content/concepts.

We first consider intelligent tutoring in the LbD setting, wherein the dependencies between the concepts in the curriculum are available as a curriculum graph, and a given concept is learned by performing an activity related to that concept (such as solving/answering a problem/question). For this setting, recent works have proposed algorithms based on multi-armed bandits (MAB), where activities are adaptively sequenced using the student response as a direct feedback. We model the problem in the piecewise stationary multi-armed bandit framework and propose CurriculumTutor, a novel technique that combines a MAB algorithm and a change point detection algorithm for adaptive activity sequencing. Our algorithm improves upon prior MAB algorithms for the LbD setting by (i) providing better learning gains, and (ii) reducing hyper-parameters, thereby improving personalisation. We show that our tutoring algorithm significantly outperforms prior approaches in the benchmark domain of two operand addition up to a maximum of four digits. In the second part of our work, we consider the setting where a concept is learned by engaging with different learning resources such as videos, tutorials and textbook sections. Specifically, we address the problem of computing a personalized sequence of learning resources/content to a student that maximizes the probability of mastery of a concept within a time horizon H. We assume that on engaging with a content, the evolution of student’s skill depends on (i) the student‘s learning profile and (ii) the content presented in the past. Mastery is examined at each time step using an assessment, which forms a binary feedback. We formulate this problem as an episodic fixed horizon Markov Decision Process (MDP). We also propose a novel online algorithm, OPT-CSEQ, based on upper confidence bounds for generalized linear contextual bandits. OPT-CSEQ learns an optimal personalized content sequence over episodes of interactions. We also present the regret analysis of OPT-CSEQ and demonstrate its effectiveness via numerical experiments.

Finally, we study the problem of automatically associating math problems with labels of concepts used to solve them, enabling such problems to be used for both practice and assessment of the associated concepts. We observe that in order to accurately identify all the pertinent concept labels for math questions, it is necessary to integrate the problem-solving technique into the tagging procedure. In this context, we designed and conducted an experiment in a graduate-level linear algebra course to understand if student explanations to solving mathematical problems can be employed to generate concept tags associated with those questions. Based on this exercise, we propose a method called Unsupervised Skill Tagging (UST) to tag math questions based on the most frequent unigrams and bigrams in the explanation text.

In the field of medical imaging, ultrasound imaging is crucial for disease assessment and clinical examinations. Plane wave imaging is a high-frame-rate ultrasound imaging technique that transmits non-steered ultrasound waves into the medium. The piezoelectric materials in the transducer capture the reflected signals from the medium to generate images of the region of interest. However, the resulting image quality is often poor when plane wave imaging is used with the standard Delay and Sum (DAS) Beamformer. Research on data-adaptive beamformers like the Minimum Variance Beamformer (MVDR) has enhanced image quality but at the cost of increased computational complexity, making real-time processing challenging. Integrating deep learning models in ultrasound beamforming has shown better performance in terms of resolution and contrast while significantly reducing artifacts compared to DAS. Despite this, the complexity of these models remains high, making them impractical for resource-constrained edge devices.

Towards the aforementioned objectives, we implemented a novel capsule network based beamformer called CapsBeam, designed to operate on raw radio-frequency data and provide an envelope of beamformed data through non-steered plane wave insonification. We conducted extensive performance evaluations, assessing resolution and contrast using the standard in-vivo, in-vitro, and in-silico datasets. In in-vivo data, our model improved detection of structures and abnormalities with reduced artifacts compared to the DAS beamforming. Similarly, for in-vitro and in-silico data, CapsBeam showed an enhancement in contrast and resolution compared to the DAS. To reduce the parameter redundancy and enhance the computational efficiency, we pruned the model using our multi-layer LookAhead Kernel Pruning (LAKP-ML) methodology, achieving a compression ratio of 85% without affecting the image quality. Additionally, the hardware complexity of the proposed model is reduced by applying quantization, simplification of non-linear operations, reordering loops, and parallelizing operations. Finally, we proposed a specialized accelerator architecture for the pruned and optimized CapsBeam model, implemented on a Zynq UltraScale+ MPSoC ZCU104 FPGA. The proposed accelerator achieved a throughput of 30 GOPS for the convolution operation and 17.4 GOPS for the dynamic routing operation.

Graphs are everywhere; many real-world complex systems like social networks, traffic networks, transaction networks, citation networks, etc. evolve over time, and most of the real-world graphs are heterogeneous, continuously evolving dynamic graphs (i.e. Heterogeneous continuous-time dynamic graph - HCTDG) in nature. This work aims to learn node embeddings by encoding heterogeneous temporal and structural dependencies at the same time for efficient downstream tasks. For continuous-time dynamic graphs (CTDGs), the two nodes’ local neighborhood determines whether they are likely to interact shortly and what kind of interaction they might engage in. We replaced the widely used neighbor-sampling with a neighbor-store, which stores and updates the neighborhood information of each node in a dictionary for faster calculation of structural information. Another major problem with CTDGs is their entangled structural and temporal dependencies. Existing approaches often adopt a sequential node embedding generation, lacking parallelization and scalability, particularly in large graphs. To introduce parallelism, we used a restarter to restart the training at any timestamp using interaction history. During training, the restart module initializes the node embeddings in multiple timestamps and learns to mimic the encoder through the knowledge distillation process, where the encoder transfers knowledge to the restarter. The training data sequence gets divided into multiple chunks by restarting from multiple timestamps simultaneously, resulting in parallelized learning of dynamic node embeddings. We introduce Heterogeneous Continuous-time dynamic Graph representation learning using neighbor-store with Restart ( HT-Graph ) to address the challenges of CTDGs by improving computational efficiency with neighbor-store and introducing parallelism through the restart module.

A coloring of the edges of a graph is said to be an acyclic edge coloring if it is a proper edge coloring (i.e. no two edges that share a common vertex get the same color) with the additional property that there are no cycles in the graph whose edges are colored using just two colors. A long-standing conjecture of Fiamcik and Alon states that any graph with maximum degree \Delta has an acyclic edge coloring using at most $\Delta+2$ colors. We shall look at a proof of Esperet and Parreau that shows that every graph has an acyclic edge coloring using at most $6\Delta$ colors. The proof serves as a simple demonstration of the power of the entropy compression technique in proving combinatorial bounds.

Two-player games are a fruitful way to represent and reason about several important synthesis tasks. These tasks include controller synthesis (where one asks for a controller for a given plant such that the controlled plant satisfies a given temporal specification), program repair (setting values of variables to avoid exceptions), and synchronization synthesis (adding lock/unlock statements in multi-threaded programs to satisfy safety assertions). In all these applications, a solution directly corresponds to a winning strategy for one of the players in the induced game. In turn, \emph{logically-specified} games offer a powerful way to model these tasks for large or infinite-state systems. Much of the techniques proposed for solving such games typically rely on abstraction-refinement or template-based solutions. In this paper, we show how to apply classical fixpoint algorithms, that have hitherto been used in explicit, finite-state, settings, to a symbolic logical setting. We implement our techniques in a tool called GenSys-LTL and show that they are not only effective in synthesizing valid controllers for a variety of challenging benchmarks from the literature, but often compute maximal winning regions and maximally-permissive controllers. We achieve 206X/ 13X speed-up (arithmetic/geometric mean) over the state-of-the-art, scale well for non-trivial LTL specifications, and synthesize controllers for previously unsolved benchmarks.

Given a graph, a conflict-free coloring is an assignment of colors to the vertices such that for every vertex, there is a color that appears exactly once in its neighborhood. The goal of the conflict-free coloring problem is to obtain such a coloring using the smallest number of colors. The problem was introduced in 2002 by Even, Lotker, Ron and Smorodinsky. The problem is NP-hard and has been studied on various classes of graphs (see the survey by Smorodinsky). In this talk, the speaker will describe the problem, and cover a few results.

The talk will be based on some results from the below two papers:

1. Conflict-Free Coloring Bounds on Open Neighborhoods (joint with Sriram Bhyravarapu and Rogers Mathew, Algorithmica 2022)
2. Extremal Results on Conflict-free Coloring (joint with Sriram Bhyravarapu, Shiwali Gupta and Rogers Mathew, under review)

Next-generation networks, including fifth-generation (5G) and beyond, are designed to accommodate advanced features and capabilities. A key enabler for this is network slicing, where each slice support Quality-of-Service (QoS) tailored to user requirements. Our goal is to develop various components of end-to-end network slice provisioning that ensures optimal resource allocation. We will first present a framework that addresses the question of revenue maximization for both 5G service aggregators and infrastructure providers while ensuring better user satisfaction.

We formulate a relevant revenue maximization problem and explore its solution in both offline and online settings. Our mechanism enables the End-to-End Orchestrator(EEO) to make admission decisions instantly upon request arrival, providing guarantees as to when the request can be enabled.

Among different network domains, resource allocation in Radio Access Network (RAN) plays an important role in the overall performance due to the time-varying nature of wireless networks. For this domain, we formulate a resource allocation problem to minimize the weighted long-term time average packet drop at the 5G wireless base station subject to certain QoS constraints. We then present two policies for this problem. The first one is a dynamic delay-guaranteed near-optimal admission and scheduling policy whose performance can be controlled with a couple of parameters. The second one is a delay-guaranteed sub-optimal policy that provides flow isolation. Further, we study the performance of these policies in the presence of a closed-loop flow rate-control mechanism.

Despite efficient admission control and scheduling mechanisms, networks can suffer from congestion if a huge number of packets are injected into them. Enabling closed-loop flow rate control mechanisms helps achieve better end-to-end flow rates without overwhelming the underlying network. To that end, we study the interactions between well-known closed-loop flow-rate control mechanisms and QoS-aware scheduling policies. Based on insights from this study, we propose a loosely coupled end-to-end rate control mechanism that achieves end-to-end flow QoS while ensuring minimal wastage of core-network resources.’

The main constituents of any heterogeneous network are the numerous end devices comprised of embedded or Internet of Things (IoT) devices, constrained by area footprint, memory, processing, and power consumption ratings. Additionally, these devices often process sensitive data that needs to be cryptographically protected against possible leakages to attackers. Therefore, these systems should not only be optimized in terms of classical parameters like power, performance, and area (PPA) but also need to be secured by design. Currently, Side Channel Analysis (SCA) and Fault Attacks (FA) pose a serious threat to these systems, which can either reduce or even eliminate the security levels of an embedded design. Depending on the target implementation sophisticated and advanced attack tools are already available in the market that require just one to a few hundred power measurements to extract the secret keys from a mathematically robust cryptographic implementation. Additionally, it is difficult to implement conventional encryption methods in IoT or embedded devices since they are typically resource-hungry in the public and private key configurations. Hence, novel measures must be adopted and have opened a new field of research known as lightweight cryptography. Therefore, validation and protection against implementation-based attacks, and designing lightweight counter-measures are considered to be of utmost importance and have been added as required design criteria in the National Institute of Standards and Technology (NIST) standardization call for lightweight cryptography. Additionally, a major threat to manufacturing ICs having secure compositions is the fact that most of the time the technology libraries, design components, and Electronic Design Automation (EDA) flows are from third parties. Accordingly, the EDA tools to manufacture Integrated Circuits (ICs) of these embedded systems must also be tuned to handle both the PPA optimizations and security realms in the design process. The classical EDA flows cannot detect side-channel leakages at early design stages or provide countermeasures against FAs and SCAs, let alone optimized countermeasures that have low footprints on power, performance, and area. Moreover, the existing EDA flow optimization techniques could conflict with the security requirements of IC design and provide adversaries with leakage surfaces. Also, in most cases, the security evaluation of ICs (SCA and FA) is carried out at the post-silicon stage incurring a significant loss, if the circuit-under-test is found to be vulnerable. In addition, the role of the EDA tool is pivotal in determining and evaluating countermeasures that suit their needs at the design stage itself in a tight time-to-market constraint. Hence, the primary goal of my work is to see how to reduce overall design cycle time in the tight time-to-market scenario by detecting early security flaws in the designs and adopting state-of-the-art techniques to generate SCA and FA-resistant lightweight IC designs.

Secure Multi-party Computation (MPC) is the standard-bearer and holy-grail problem in Cryptography that permits a collection of data-owners to compute a collaborative result, without any of them gaining any knowledge about the data provided by the other, except what is derivable from the result of the computation. This talk will discuss the fundamental concept of garbled circuits and the Yao’s two-party computation which is the first MPC construct in literature. In the end, I will briefly touch upon various applications of MPC.

Conflict-free coloring has been a problem of fundamental combinatorial interest over the last two decades. In this talk, I will survey the current results and present some connections to a different optimization problem related to the minimum dominating set.

The results can be found in https://arxiv.org/pdf/1812.01459.pdf, https://arxiv.org/abs/2110.06656, and https://arxiv.org/pdf/2301.00387.pdf

An intersection graph of a family $\mathcal{F}$ of sets is a graph $G$ with each set in $\mathcal{F}$ considered as a vertex, and an edge added between those pairs of vertices that correspond to non-disjoint sets. $B_0$-VPG graphs are intersection graphs of axis-parallel line segments in the plane and any such representation is called a $B_0$-VPG representation. In general, $B_k$-VPG is the class of graphs which can be represented as intersection graphs of $k$-bend paths in the same plane, where a $k$-bend path is a non-self-intersecting polyline in the plane made of at most $k+1$ axis-parallel line segments. In this thesis, we study a few classes of graphs and posets which have a $B_0$-VPG representation.

Cocomparability Flavor: E. Cohen, M. C. Golumbic, W. T. Trotter, and R. Wang (Order 2016) posed the question of characterizing $B_0$-VPG permutation graphs. We respond by characterizing $B_0$-VPG cocomparability graphs in the following way. In the characterization theorem, a $C_4$ together with exactly one chord is called a diamond and the chord is called the diamond diagonal. Moreover, two vertices $x$ and $y$ in a graph $G$ are diamond related if there exists a path from $x$ to $y$ in $G$ made up of diamond diagonals alone. Our theorem is as follows; A cocomparability graph $G$ is $B_0$-VPG if and only if (i) no two vertices of an induced $C_4$ in $G$ are diamond related, and (ii) $G$ does not contain an induced subgraph isomorphic to $\overline{C_6}$. This helps us show that the first condition in fact characterizes $B_0$-VPG permutation graphs since permutation graphs are $\overline{C_6}$-free. The characterization also leads to a polynomial-time recognition algorithm and its proof gives us a $B_0$-VPG drawing algorithm for the class of $B_0$-VPG cocomparability graphs. Our drawing algorithm starts by fixing any one of the many posets $P$ whose cocomparability graph is the input graph $G$, and it turns out that the resultant drawing is a new $2D$ visualization for such posets.

Outerplanar Flavor: Planar graphs have received the maximum attention from the perspective of $B_{k}$-VPG representations. Following up on a series of results and conjectures by various authors, D. Goncalves et al. [SODA 2018] showed that all planar graphs are $B_1$-VPG, and the same was proven earlier for outerplanar graphs by D. Catanzaro et al. [DAM 2017]. This is tight since many simple planar graphs like $4$-wheel, triangular prism and particularly among outerplanar graphs like $3$-sun, to name a few, are not $B_0$-VPG. Characterizing $B_0$-VPG outerplanar graphs will be a good step in this direction since some of the structures that forbid a planar graph from being $B_0$-VPG are also present among outerplanar graphs.

There are AT-free planar graphs which are not $B_0$-VPG. This piqued our interest in showing that AT-free outerplanar graphs are $B_0$-VPG. Our procedure has two steps. The first step shows that every AT-free outerplanar graph can be realized as an induced subgraph of a biconnected outerpath (that is, biconnected outerplanar graph whose weak dual is a path). Since $B_0$-VPG is a hereditary class (that is, closed under induced subgraphs), in order to prove that every AT-free outerplanar graph is $B_0$-VPG, it is sufficient to show that every biconnected outerpath is $B_0$-VPG which constitutes the second step. Our proofs are constructive and give a polynomial time $B_0$-VPG drawing algorithm for the class of biconnected outerpaths. The first step led us to characterize all the subgraphs of biconnected outerpaths and define the class as linear outerplanar graphs. We show that this class is a proper superclass of AT-free outerplanar graphs and a proper subclass of outerplanar graphs with pathwidth at most $2$. Moreover, we prove that a graph in this class can be realized both as an induced subgraph and as a spanning subgraph of (different) biconnected outerpaths.

Conclusion: Finally, we list out a few necessary conditions for a graph to be $B_0$-VPG. Moreover, we list out a few interesting examples, some of which help realize the necessity of these conditions, and one strange example which shows that these conditions are not sufficient. As a tailend, we discuss a few open questions and address the comments of the reviewers.

Programs are often subjected to significant optimizing and parallelizing transformations based on extensive dependence analysis. Formal validation of such transformations needs modeling paradigms which can capture both control and data dependences in the program vividly. Being value-based with an inherent scope of capturing parallelism, the untimed coloured Petri net (CPN) models, reported in the literature, fit the bill well; accordingly, they are likely to be more convenient as the intermediate representations (IRs) of both the source and the transformed codes for translation validation than strictly sequential variable-based IRs like sequential control flow graphs (CFGs). The main contribution of the work is to develop a novel path-based equivalence checking technique for Petri net based models of programs for validating several parallelizing transformations.

In this talk first we explore an extension of the notion of circular coloring form graphs to signed graphs. In particular we present a bipartite analogue of the generalized Mycielski graphs on odd cycles and investigate their circular chromatic number. To prove the lower bound of 4 we use an elementary notion of the algebraic topology, namely the winding number of a closed curve, thus presenting in an elementary manner a strong connection between the two subjects.

Suffix Trees discovered in 1973 is a powerful data structure for string processing. They are at the heart of many search engines like Google and of modern genome sequencing packages in Computational Biology. Their practical implementations were possible through a lot of developments in space efficient data structures. We will see a guided tour of suffix trees, their applications and space efficient data structures in this talk.

We survey some recent graph algorithms that are based on picking a vertex at random and declaring it to be a part of the solution. This simple idea has been deployed to obtain state-of-the-art parameterized, exact exponential time, and approximation algorithms for a number of problems, such as Feedback Vertex Set and 3-Hitting Set. We will also discuss a recent 2-approximation algorithm for Feedback Vertex Set in Tournaments that is based on picking a vertex at random and declaring it to /not/ be part of the solution.

This presentation mainly focuses on orientations of graphs and mixed multigraphs. An orientation of an undirected graph G is an assignment of exactly one direction to each edge of $G$. The oriented radius of an undirected graph $G$ is the smallest radius among all the orientations of $G$. Let $\overline{f}(F)$ denote the maximum oriented radius of graphs in the family $F$. Let $\overline{f}(r) = \overline{f}(F_r)$ where $F_r$ denotes the family of all graphs of radius $r$. The oriented diameter of an undirected graph $G$ is the smallest diameter among all the orientations of G. Let $\overline{g}(F)$ denote the maximum oriented diameter of graphs in the family $F$. Let $\overline{g}(d) = \overline{g}(F_d)$ where $F_d$ denotes the family of all graphs of diameter $d$. A mixed multigraph is a multigraph which may contain both undirected and directed edges. An orientation of a mixed multigraph $G$ is an assignment of exactly one direction to each undirected edge of $G$. For each $r \in \mathbb{N}$, let $\overline{f}(r)$ denote the smallest number such that any strongly connected bridgeless mixed multigraph with radius at most $\overline{f}(r)$.

One of the most famous studies on strong orientations of undirected graphs was carried out by Chvátal and Thomassen [J. Comb. Theory. Ser. B., 1978]. They proved that $\forall r \in \mathbb{N}$, there exists an undirected 2-edge connected graph of radius $r$ such that every orientation of it has radius at least $r^2+r$. First, we focus on such strongly connected orientations of undirected graphs. Chvátal and Thomassen [J. Comb. Theory. Ser. B., 1978] gave a lower bound of $(1/2)d^2+d$ and an upper bound of $2d^2+2d$ for $\overline{g}(d)$. This upper bound is obtained as a corollary from the upper bound for $\overline{f}(r)$. We improved the upper bound on $\overline{g}(d)$ to $1.373d^2+6.971d-1$, which outperforms the former upper bound for all values of d greater than or equal to 8. The proof is constructive and lends itself to a polynomial time algorithm.

Since our attempts to reduce the gap between the upper and lower bounds on $\overline{g}(d)$ any further were not fruitful, we studied the bounds on $\overline{g}(d)$ for specific values of $d$. It is an easy exercise to prove that $\overline{g}(1) = 3$. Chvátal and Thomassen [J. Comb. Theory. Ser. B., 1978, 1978] proved that $\overline{g}(2) = 6$. For $d \ge 3$, the exact value of $\overline{g}(d)$ is unknown. For $\overline{g}(3)$, Kwok, Liu and West [J. Comb. Theory. Ser. B., 2010] obtained improved lower and upper bounds of 9 and 11 respectively. For $\overline{g}(4),$ the bounds provided by Chvátal and Thomassen were 12 and 40 and no better bounds were known. By extending the method we used for diameter-d graphs, along with an asymmetric extension of a technique used by Chvátal and Thomassen, we have improved this upper bound to 21. We also give an upper bound of 47 for $\overline{g}(5)$ as an easy corollary.

We then shifted our focus to the problem of finding strong orientations of mixed multigraphs. A mixed multigraph G can be oriented to a strongly connected digraph if and only if G is connected and bridgeless [Boesch and Tindell, Am. Math. Mon., 1980]. We improve the current best upper bound of $4r^2+4r$ on $\overline{f}(r)$ [Chung, Garey and Tarjan, Networks, 1985] to $1.5r^2+r+1$. En route, we also show that if each edge of $G$ lies in a cycle of length at most $\eta$, then the oriented radius of G is at most $1.5r\eta$. All these proofs are constructive and lend themselves to polynomial time algorithms.

Our study of strongly connected orientations of undirected and mixed graphs and algorithms furnishing such orientations led us to the discovery of some families of graphs that provide lower bounds to the oriented radius and diameter of undirected and mixed graphs. From this, we were able to provide a marginally better lower bound, $\overline{f}(r) \ge r^2+3r-1$, for mixed multigraphs. While this marginal improvement does not help with asymptotic estimates, it clears a natural suspicion that, like undirected graphs where $\overline{f}(r) = r^2+r$, $\overline{f}(r)$ may be equal to $r^2+r$ for mixed multigraphs. Further, we now know that the new upper bound for $\overline{f}(r)$ is tight up to a multiplicative factor of 1.5.

Finally, we discuss some existing open problems which defied all attacks for a long period of time. Chvátal and Thomassen [J. Comb. Theory. Ser. B., 1978] asked the following important question. Does there exist an orientation $G*$ of $G$ such that for every edge $uv$ that lies in a cycle of length $k$ in $G$, either arc $uv$ or arc $vu$ will lie in a directed cycle of length at most $h(k)$ in $G*$? The bound for $h(k)$ provided by Chvátal and Thomassen is exponential. It is still unknown whether $h(k)$ could be bounded by a polynomial or even a linear function of $k$.

The eternal vertex cover problem is a dynamic variant of the classical vertex cover problem defined in terms of an infinite attacker-defender game played on a graph. In each round of the game, the defender reconfigures a fixed number of guards from one vertex cover to another, following certain rules of the game in response to an attack on an edge chosen by the attacker. The minimum number of guards to be placed on the vertices of a graph G so that any sequence of attacks on its edges can be defended this way is the eternal vertex cover number of G, denoted by evc(G). It was known from the literature that given a graph G and an integer k, checking whether evc(G) <= k is NP-hard. Further, it was known that for any graph G, mvc(G) <= evc(G) <= 2mvc(G), where mvc(G) is the vertex cover number of G. Though a characterization of graphs for which evc(G)=2mvc(G) existed in literature, a characterization of graphs for which evc(G)=mvc(G) remained as an open problem, since 2009. We solved this problem partly by achieving such a characterization that works for a class of graphs that includes chordal graphs, internally triangulated planar graphs and locally connected graphs. This characterization yielded a polynomial time algorithm for precisely determining eternal vertex cover number of any biconnected chordal graph G and an algorithm for determining a safe strategy for guard movements in each round of the game using only evc(G) guards. Though the eternal vertex cover problem was only known to be in PSPACE in general, it follows from our new characterization that the problem is in NP for locally connected graphs, a graph class which includes all biconnected internally triangulated planar graphs. We also provided reductions establishing NP-completeness of the problem for locally connected graphs and in particular, for biconnected internally triangulated planar graphs. As far as we know, these were the first NP-completeness results known for the problem for any graph class. Our later attempts were to extend these algorithmic and complexity results to larger graph classes. To achieve this, it was found to be necessary to improve the lower bound on the eternal vertex cover number from the known trivial bound given by the vertex cover number. We showed that the size of the smallest vertex cover of a graph G that contains all its cut vertices is a lower bound to its eternal vertex cover number. For a class of graphs including chordal graphs, the eternal vertex cover number is shown to be at most one more than the new lower bound. As a consequence of this lower bound, we could generalize our earlier results to obtain a quadratic complexity algorithm for finding the eternal vertex cover number of any chordal graph. Another consequence was a polynomial time approximation scheme (PTAS) for finding the eternal vertex cover number of internally triangulated planar graphs, for which exact determination of eternal vertex cover number was shown to be NP-hard from our previous result. Though the new lower bound we obtained was useful for graphs classes like chordal graphs, the bound was far from being tight for some simple graph classes like cactus graphs. To address this gap, we introduced the notion of a certain substructure property in the context of the eternal vertex cover problem and derived a new lower bounding technique for the problem based on the property. We applied the technique to obtain a linear time algorithm for computing the eternal vertex cover number of cactus graphs. We also generalized this to obtain a quadratic time algorithm for the problem for any graph whose each block is either a chordal graph or a cactus graph. We could simplify the proof of correctness of a linear time recursive algorithm for computing the eternal vertex cover number of maximal outerplanar graphs known in literature. This algorithm works by splitting the input graph G into some relevant maximal outerplanar subgraphs and computing some parameters including the eternal vertex cover number of these subgraphs. The simplification of the proof is obtained by applying our earlier characterization to decide whether evc(H)=mvc(H) or not for such relevant maximal outerplanar subgraphs H of G.

Hrubes and Wigderson (2015) initiated the complexity-theoretic study of noncommutative arithmetic formulas with inverse gates. They introduced the Rational Identity Testing (RIT) problem which is to decide whether a noncommutative formula with inverses computes zero in the free skew field, equivalently whether there exists a nonzero matrix evaluation for the input formula. In the white-box setting, there are deterministic polynomial-time algorithms due to Garg, Gurvits, Oliveira, and Wigderson (2016) and Ivanyos, Qiao, and Subrahmanyam (2018). A central open problem in this area is to design an efficient deterministic black-box identity testing algorithm for such formulas. In this talk, I’ll present our recent work that solves this problem for the first nested inverse case. More precisely, we obtain a deterministic quasipolynomial-time black-box RIT algorithm for noncommutative rational formulas of inversion height two via a hitting set construction. It is joint work with V. Arvind (IMSc) and Partha Mukhopadhyay (CMI) accepted at RANDOM 2022

Graph Neural Networks (GNN) are used extensively for analyzing graph-structured data with higher accuracy for node classification, graph classification, and link prediction, in areas such as social networks (analyzing human interactions), chemistry (molecule discovery, protein folding prediction), transportation, fast-placement of chips, etc. The vertices and edges in the case of a GNN are associated with high dimensional feature vectors. The patterns of interests are often hidden/entangled in these feature vectors. The operations in GNNs consist of data-driven, irregular, with interleaved dense and regular neural network operations. Hence, performance optimizations applied for graph processing and traditional DNNs cannot be applied easily to GNNs. Several forms of parallelism can be explored in GNNs - operator-level, feature vector-level, graph-partition-level, model-level, etc. Since there is a need for studying larger and deeper GNN models, there is also the need to accelerate and improve the performance and scalability of GNN training/inference algorithms on heterogeneous hardware architectures. We aim to provide GNN-specific programming abstractions for heterogeneous hardwares. We briefly introduce how graph programming models have evolved to process graph neural networks, and then introduce the challenges in processing graph neural networks on heterogeneous architectures. The presentation will conclude with an high level overview of future work.

An intersection graph of a family F of sets is a graph G with each set in F considered as a vertex, and an edge added between exactly those pairs of vertices that correspond to non-disjoint sets. B0-VPG graphs are intersection graphs of axis-parallel line segments in the plane and any such intersection representation is called a B0-VPG representation. In this thesis, we study a few graphs and posets which have such a B0-VPG representation. Cohen, Golumbic, Trotter, and Wang (Order, 2016) pose the question of characterizing B0-VPG permutation graphs. We respond here by characterizing B0-VPG cocomparability graphs. This helps us show that a simple necessary condition in fact characterizes B0-VPG permutation graphs. The characterization also leads to a polynomial-time recognition algorithm and its proof gives us a B0-VPG drawing algorithm for the class of B0-VPG cocomparability graphs. Our drawing algorithm starts by fixing any one of the many posets P whose cocomparability graph is the input graph G. On the set of axis-parallel line segments in the plane, we define a binary relation $<_2$ as $p <_2 q$ if and only if they are non-intersecting and the bottom-left endpoint of p precedes the top-right endpoint of q in the product order on $R^2$. The reflexive closure $\le_2$ of the relation $<_2$ restricted to the line segments of our drawing turns out to be a partial order isomorphic to the poset P. This gives a new 2D visualization for such posets.

Following the above result, we show that all AT-free outerplanar graphs are B0-VPG. In the course of the argument, we show that any AT-free outerplanar graph can be identified as an induced subgraph of a biconnected outerplanar graph whose weak dual is a path. Our B0-VPG drawing procedure works for such graphs and has the potential to be extended to larger classes of outerplanar graphs. Finally, we define a new class of graphs, viz. linear outerplanar graph, as the class of all biconnected outerplanar graphs whose weak dual is a path, and their subgraphs. This does not include all outerplanar graphs whose weak dual is a linear forest. We characterize this graph class and show that a graph in this class can be realized both as an induced subgraph and as a spanning subgraph of (different) biconnected linear outerplanar graphs. The recognition of linear outerplanar graphs and the construction of a biconnected linear outerplanar supergraph can be done in polynomial time. Hence one can extend various drawings and geometric representations available for biconnected linear outerplanar graphs to this larger class.

Deep Neural Networks (DNN) are deployed in many real-world problems with stringent constraints on the processing hardware. However, growth in network sizes of the DNN models leads to an exponential increase in computational effort and required memory size. Dedicated domain-specific hardware accelerators are thus used to increase the performance of the inference of DNNs. CNNs constitute the major class of DNN networks. Here, The input tensors in each layer of Deep Neural Network (DNN) models are often partitioned/tiled to get accommodated in the limited onchip memory of accelerators. This leads to redundant data movement between the accelerator and different levels of the memory hierarchy degrading the performance and energy consumption during convolution. Studies show that efficient tiling schedules (commonly referred to as mapping) for a given accelerator and DNN model reduce the data movement between the accelerator and different levels of the memory hierarchy improving the performance. However, finding layer-wise optimum mapping for a target architecture with a given energy and latency envelope is an open problem due to the huge search space in the mappings.

We worked on a Reinforcement Learning (RL) based automated mapping approach to find optimum schedules of DNN layers for a given architecture model without violating the specified energy and latency constraints. In the work done, A Deep Q-Learning (DQN) agent learns a generalized policy by analyzing the complex relationship between the layer shape, target resources, and performance parameters. The learned policies easily adapt to a wide range of DNN models with different hardware configurations, facilitating transfer learning and improving the training time. Experiments show that the proposed work improves latency and energy consumption by an average of 21.5% and 15.6% respectively compared to the state-of-the-art approach for a wide range of DNN models running on NVIDIA Deep Learning Accelerator (NVDLA). The training time of RL-based transfer learning is 15× faster than that of GAMMA. RL-based tiling experiments showed that despite utilizing a highly optimized tiling, the PE utilization is relatively low. In addition to this, the weight tensor occupies a major chunk of on-chip storage and has to persist throughout the convolution process. All these are fundamental limitations of spatial domain convolution where arithmetic complexity is less. In the meantime, Recent studies show that FFTbased convolutions are faster compared to spatial domain convolutions due to higher arithmetic intensity resulting in better utilization of hardware systems whose compute–to–memory ratios are increasing over time. Moreover, FFT-based convolution offers an opportunity to tile the tensors more efficiently. Compared to spatial domain convolution acceleration, research on FFT-based convolution accelerators are in a nascent stage. In the due course of research. it is planned to explore FFT-based convolution accelerators particularly to work on dataflow and memory mapping problems associated with it. Currently, An initial design of FFT-based convolution accelerator is proposed. The proposed design features a optimum Overlap and Discard (OaD) method of convolution, DCT-based compression of filter kernels, JPEG-based compression of ofmap, event-based scheduling of FFT processor and a Gauss Complex multiplier. The OaD method of convolution simplifies the tiling problem by decomposing the ifmap into well defined patches. The convolution on these patches can be computed independently.

Graphs are abstract structures used to represent binary relationships among objects. The objects are called vertices and the relation between them are called edges. Colored graphs are those where each vertex/edge is colored with a color from a finite set of colors. Graphs are tremendously powerful in modeling complex structures and hence efficient methods for searching for desired patterns in graphs are of extreme importance in Computer Science. In particular, problems related to finding subgraphs of a certain color pattern have received a lot of attention in the literature. A well-known example is the class of questions in Ramsey Theory that deals with the existence of monochromatic subgraphs (where all edges have the same color) of a specific type like cliques, spanning trees and paths. In this work, we focus on fundamental questions related to finding balanced subgraphs instead of monochromatic subgraphs where balanced means having equal number of edges of each color. These problems come under a subarea of Ramsey Theory known as Zero-Sum Ramsey Theory.

Given a graph whose edges are colored, the Maximum Balanced Connected subgraph problem is to identify a maximum-sized subgraph that is connected and balanced. While finding a maximum-sized monochromatic connected subgraph is easy (using breadth-first search or depth-first search), we show that Maximum Balanced Connected subgraph is NP-hard even on graphs whose edges are colored using 2 colors. We then study the complexity of the problem on special graph classes like split graphs, bipartite graphs, chordal graphs and planar graphs. We also describe a fixed-parameter tractable (with respect to the size of the solution subgraph as the parameter) algorithm for general graphs. Then, we study a variant of the problem where the solution subgraph is required to be a path. We call this problem Maximum Balanced Path and show that it is NP-hard even on split graphs but is fixed-parameter tractable (with respect to the size of the solution subgraph as the parameter) in general graphs.

We believe that this study is the starting point towards understanding the complexity of finding balanced substructures in graphs.

This presentation mainly focuses on orientations of graphs and mixed multigraphs. An orientation of an undirected graph G is an assignment of exactly one direction to each edge of $G$. The oriented radius of an undirected graph $G$ is the smallest radius among all the orientations of $G$. Let $\overline{f}(F)$ denote the maximum oriented radius of graphs in the family $F$. Let $\overline{f}(r) = \overline{f}(F_r)$ where $F_r$ denotes the family of all graphs of radius $r$. The oriented diameter of an undirected graph $G$ is the smallest diameter among all the orientations of G. Let $\overline{g}(F)$ denote the maximum oriented diameter of graphs in the family $F$. Let $\overline{g}(d) = \overline{g}(F_d)$ where $F_d$ denotes the family of all graphs of diameter $d$. A mixed multigraph is a multigraph which may contain both undirected and directed edges. An orientation of a mixed multigraph $G$ is an assignment of exactly one direction to each undirected edge of $G$. For each $r \in \mathbb{N}$, let $\overline{f}(r)$ denote the smallest number such that any strongly connected bridgeless mixed multigraph with radius at most $\overline{f}(r)$.

One of the most famous studies on strong orientations of undirected graphs was carried out by Chvátal and Thomassen [J. Comb. Theory. Ser. B., 1978]. They proved that $\forall r \in \mathbb{N}$, there exists an undirected 2-edge connected graph of radius $r$ such that every orientation of it has radius at least $r^2+r$. First, we focus on such strongly connected orientations of undirected graphs. Chvátal and Thomassen [J. Comb. Theory. Ser. B., 1978] gave a lower bound of $(1/2)d^2+d$ and an upper bound of $2d^2+2d$ for $\overline{g}(d)$. This upper bound is obtained as a corollary from the upper bound for $\overline{f}(r)$. We improved the upper bound on $\overline{g}(d)$ to $1.373d^2+6.971d-1$, which outperforms the former upper bound for all values of d greater than or equal to 8. The proof is constructive and lends itself to a polynomial time algorithm.

Since our attempts to reduce the gap between the upper and lower bounds on $\overline{g}(d)$ any further were not fruitful, we studied the bounds on $\overline{g}(d)$ for specific values of $d$. It is an easy exercise to prove that $\overline{g}(1) = 3$. Chvátal and Thomassen [J. Comb. Theory. Ser. B., 1978, 1978] proved that $\overline{g}(2) = 6$. For $d \ge 3$, the exact value of $\overline{g}(d)$ is unknown. For $\overline{g}(3)$, Kwok, Liu and West [J. Comb. Theory. Ser. B., 2010] obtained improved lower and upper bounds of 9 and 11 respectively. For $\overline{g}(4),$ the bounds provided by Chvátal and Thomassen were 12 and 40 and no better bounds were known. By extending the method we used for diameter-d graphs, along with an asymmetric extension of a technique used by Chvátal and Thomassen, we have improved this upper bound to 21. We also give an upper bound of 47 for $\overline{g}(5)$ as an easy corollary.

We then shifted our focus to the problem of finding strong orientations of mixed multigraphs. A mixed multigraph G can be oriented to a strongly connected digraph if and only if G is connected and bridgeless [Boesch and Tindell, Am. Math. Mon., 1980]. We improve the current best upper bound of $4r^2+4r$ on $\overline{f}(r)$ [Chung, Garey and Tarjan, Networks, 1985] to $1.5r^2+r+1$. En route, we also show that if each edge of $G$ lies in a cycle of length at most $\eta$, then the oriented radius of G is at most $1.5r\eta$. All these proofs are constructive and lend themselves to polynomial time algorithms.

Our study of strongly connected orientations of undirected and mixed graphs and algorithms furnishing such orientations led us to the discovery of some families of graphs that provide lower bounds to the oriented radius and diameter of undirected and mixed graphs. From this, we were able to provide a marginally better lower bound, $\overline{f}(r) \ge r^2+3r-1$, for mixed multigraphs. While this marginal improvement does not help with asymptotic estimates, it clears a natural suspicion that, like undirected graphs where $\overline{f}(r) = r^2+r$, $\overline{f}(r)$ may be equal to $r^2+r$ for mixed multigraphs. Further, we now know that the new upper bound for $\overline{f}(r)$ is tight up to a multiplicative factor of 1.5.

Finally, we discuss some existing open problems which defied all attacks for a long period of time. Chvátal and Thomassen [J. Comb. Theory. Ser. B., 1978] asked the following important question. Does there exist an orientation $G*$ of $G$ such that for every edge $uv$ that lies in a cycle of length $k$ in $G$, either arc $uv$ or arc $vu$ will lie in a directed cycle of length at most $h(k)$ in $G*$? The bound for $h(k)$ provided by Chvátal and Thomassen is exponential. It is still unknown whether $h(k)$ could be bounded by a polynomial or even a linear function of $k$.

The eternal vertex cover problem is a dynamic variant of the classical vertex cover problem defined in terms of an infinite attacker-defender game played on a graph. In each round of the game, the defender reconfigures a fixed number of guards from one vertex cover to another following certain rules of the game in response to an attack on an edge chosen by the attacker. The minimum number of guards to be placed on the vertices of a graph G so that any sequence of attacks on its edges can be defended this way is the eternal vertex cover number of G, denoted by evc(G). It was known from the literature that given a graph G and an integer k, checking whether evc(G) <= k is NP-hard. Further, it was known that for any graph G, mvc(G) <= evc(G) <= 2mvc(G), where mvc(G) is the vertex cover number of G.

Though a characterization of graphs for which evc(G)=2mvc(G) existed in literature, a characterization of graphs for which evc(G)=mvc(G) remained as an open problem, since 2009. We solved this problem partly by achieving such a characterization that works for a class of graphs that includes chordal graphs, internally triangulated planar graphs and locally connected graphs. This characterization yielded a polynomial time algorithm for precisely determining eternal vertex cover number of any biconnected chordal graph G and an algorithm for determining a safe strategy for guard movements in each round of the game using only evc(G) guards.

Though the eternal vertex cover problem was only known to be in PSPACE in general, it followed from our new characterization that the problem is in NP for locally connected graphs, a graph class which includes all biconnected internally triangulated planar graphs. We also provided reductions establishing NP-completeness of the problem for locally connected graphs and in particular, for biconnected internally triangulated planar graphs. As far as we know, these were the first NP-completeness results known for the problem for any graph class.

Our later attempts were to extend these algorithmic and complexity results to larger graph classes. To achieve this, it was found to be necessary to improve the lower bound on the eternal vertex cover number from the known trivial bound given by the vertex cover number. We showed that the size of the smallest vertex cover of a graph G that contains all its cut vertices is a lower bound to its eternal vertex cover number. For a class of graphs including chordal graphs, the eternal vertex cover number is shown to be at most one more than the new lower bound. As a consequence of this lower bound, we could generalize our earlier results to obtain a quadratic complexity algorithm for finding the eternal vertex cover number of any chordal graph. Another consequence was a polynomial time approximation scheme (PTAS) for finding the eternal vertex cover number of internally triangulated planar graphs, for which exact determination of eternal vertex cover number was shown to be NP-hard from our previous result.

Though the new lower bound we obtained was useful for graphs classes like chordal graphs, the bound was far from being tight for some simple graph classes like cactus graphs. To address this gap, we introduced the notion of a certain substructure property in the context of the eternal vertex cover problem and derived a new lower bounding technique for the problem based on the property. We applied the technique to obtain a linear time algorithm for computing the eternal vertex cover number of cactus graphs. We also generalized this to obtain a quadratic time algorithm for the problem for any graph whose each block is either a chordal graph or a cactus graph.

We could simplify the proof of correctness of a linear time recursive algorithm for computing the eternal vertex cover number of maximal outerplanar graphs known in literature. This algorithm works by splitting the input graph G into some relevant maximal outerplanar subgraphs and computing some parameters including the eternal vertex cover number of these subgraphs. The simplification of the proof is obtained by applying our earlier characterization to decide whether evc(H)=mvc(H) or not for such relevant maximal outerplanar subgraphs H of G.

Malware has been a constant threat to the community and it impacts almost all devices which are connected to the Internet like laptops, mobile phones, servers, etc. Malware detection is a well-studied research area from the past 20 years and several static and dynamic techniques were developed to deal with malware in an efficient manner. But still, the malware remains an unsolved problem and new variants of malware are emerging day by day. Hence we started our research with malware detection on Windows OS based personal computers. We have analyzed basically the Portable Executable (PE) features since they are the most popular and effective static features for detecting Windows malware. We conducted experiments to reduce the number of features required to predict the maliciousness of executables. We achieved an accuracy of 98.55% and a false positive rate of 1.58% with just 10 PE features. Due to the gaining popularity of Linux OS in recent years, we also analyzed the importance of Executable and Linkable Format (ELF) features in malware detection. Recent trend in malware attacks is to use vulnerable Internet of Things (IoT) devices as attack vectors for distributed attacks targeting critical computing infrastructures. These devices are an easy target for malware due to its limited computational resources, constant online connection, and poor security design. Our goal is to develop a novel, fast, cross-architecture, and resource-efficient malware detection methodology for resource-constrained computing systems which make use of static (and dynamic, if needed to improve the efficiency) features from the executables and implement the framework on a real IoT network. The developed system will deal with the challenges raised by the IoT devices like constrained-resources, heterogeneity of architecture etc. Since most of the IoT devices use different versions of Linux OS, we first extracted the ELF header features from Linux executables and applied the chi-square feature selection technique to reduce the number of features to 34, without impacting the overall accuracy. Compared to other state-of-the-art works, the framework achieved an accuracy around 99% with less than 0.1% false positive and false negative rate and time taken to train these models was very less.

Graph coloring usually refers to a proper vertex coloring of graphs where no two adjacent vertices are colored with the same color. The proper vertex coloring problem is a minimization problem where the challenge is to identify the minimum possible number of colors that can be used to properly vertex color a graph. Coupon coloring is another type of vertex coloring problem. A coloring of a graph using k colors is said to be a coupon coloring if the neighbourhood of each vertex has at least one vertex of each of the k colors. Here maximizing the number of colors is the challenge.Coupon coloring problem has many direct applications in network science and other disciplines. Like a resource allocation problem in a network where all nodes are to be assigned with resources in an efficient way with the constraint that each node can only access the resources allocated to it or its neighbours. In real world applications it may not be always necessary to limit the neighbourhood to open neighbourhood as a node can make use of the resource assigned to them as well. The problem we are considering is less challenging in closed neighbourhood hence we stick to the open neighbourhood. We refer to coupon coloring of a graph using k colors as a k-coupon coloring. While it is easy to achieve and verify a 1-coupon coloring, to determine whether a graph is 2-coupon colorable is a NP complete problem. Goddard and Henning conjecture that If G is a simple triangulated planar graph of order at least 4, then G has a 2-Coupon coloring. This paper mainly focuses on our study of this conjecture and attempts to settle it.

With the increasing demand for high-performance computing in the application domains with stringent power budgets, coarse-grained reconfigurable array (CGRA) architectures have become a popular choice among researchers and manufacturers. Loops are the hot-spots of kernels running on CGRAs and hence several techniques have been devised to optimize the loop execution. However, works in this direction are predominantly software-based solutions. This work addresses the optimization opportunities at a deeper level and introduces a hardware-based loop control mechanism that can support arbitrarily nested loops up to four levels. Major contributions of this work are, a lightweight Hardware Loop Block (HLB) for CGRAs that eliminates control instruction overhead of loops and an acyclic graph transformation that removes loop branches from the application CDFG. A centralized implementation of HLB will be devised to reduce the area/power overhead. The effect of combining hardware and software-based loop optimizations will be analyzed. In addition, this work will focus on optimizing the CGRA instruction memory hierarchy to better support the loop execution. We plan to introduce a loop buffer to cache the instructions that make up the loop body so that instruction fetch/decode costs can be reduced.

This talk will provide an overview of video compression algorithms and the current standards that are widely used. It will highlight some of the challenges in video compression to tradeoff compression efficiency with encoding speed and the potential opportunities for performance optimization in codecs. The talk will cover examples of prior performance optimization work in x265, MulticoreWare’s open-source implementation of HEVC/H.265.