## Seminars

**February 09, 2019.**

*Can we save energy if we allow for errors in computing?*Prof. Janak Patel, Professor at UIUC

**Abstract:**
A brief overview of present understanding of tradeoff between Energy and Errors in Computing will be presented. Prevailing understanding of a chip’s behaviour under large process variations with statistical delay assumptions leads one to conclude that a small number of errors are likely as we progress further down on Moore’s Law. This understanding is challenged by a new hypothesis on the behaviour of microprocessor like large chips in the presence of process variations. A Thought Experiment is presented which leads to the new hypothesis. The new hypothesis states that in every large CMOS chip, there exist critical operations points (frequency, voltage) such that it divides the 2-D space (F, V) in to two distinct spaces: 1. Error-free operation and 2. Massive errors (i.e. completely inoperable). Two attempts at disproving this hypothesis with real physical experiments will be described. Some consequences of the hypothesis on energy savings in large data centres are also suggested. Alternate ways of saving energy in computers are suggested.

**Time:**11 am

**Venue:** Room 1/102

**January 08, 2019.**

*Regular abstractions with applications to Infinite state verification.*Dr. Prakash Saivasan, Postdoctoral Researcher at Institute of Theoretical Computer Science, TU Braunschweig

**Abstract:**
Recursive programs even over finite data domains are infinite state due to the unboundedness of the call stack. While sequential recursive programs can be modelled and verified via pushdown systems, verification in the presence of concurrency, which is undecidable in general, remains an interesting and challenging problem. The focus of my research so far has been to address this problem via different techniques: under-approximations, accelerations and via regular abstractions. In this talk I will present one of our result on regular abstractions.

A regular abstraction is the approximation of an infinite state system as a finite automaton. For instance, one may approximate the behaviors (as a language) of a recursive program/pushdown system by its downward closure (i.e. the collection of all subwords of words in the language), this is always a regular language. One may also disregard the order of letters in the words and consider the Parikh-image of a language. Again for recursive programs/ pushdown systems, this is representable by a finite state automaton.

I will explain the main ideas behind our results on computing regular abstractions for automata equipped with a counter. While such representations for pushdown systems involves an exponential blowup, we will see that the situation is significantly better for counter systems. It is polynomial for both upward and downward closures and quasi-polynomial for Parikh-image abstraction.

I will then show how to use the above result to carry out verification of quantitative properties for procedural programs. Our Quantitative logic provides the ability to express arithmetic constraints over the execution times of procedure invocations. In this logic one may express properties such as “within the execution of each invocation of a procedure P, the time spent in executing invocations of procedures Q and R is less than 15%”.

Time permitting, I will also explain a second application of our result: in deciding the control state reachability problem for an under-approximation (bounded-stage runs) of concurrent recursive programs communicating via shared memory.

**Time:**2:30 pm - 3:30 pm

**Venue:** Room 6/202

**December 12, 2018.**

*Minimum Transactions Problem.*Niranka Banerjee, Research Fellow at Institute of Mathematical Sciences

**Abstract:**
We are given a directed graph G(V, E) on n vertices and m edges where each edge has a positive weight associated with it. The influx of a vertex is defined as the difference between the sum of the weights of edges entering the vertex and the sum of the weights of edges leaving the vertex. The goal is to find a graph G(V, E) such that the influx of each vertex in G(V, E) is same as the influx of each vertex in G(V, E) and |E| is minimal. We show that: 1. finding the optimal solution for this problem is NP-hard, 2. the optimal solution has at most n − 1 edges, and we give an algorithm to find one such solution with at most n − 1 edges in O(m log n) time, and 3. for one variant of the problem where we can delete as well as add extra edges to the graph, we can compute a solution that is within a factor 3/2 from the optimal solution

**Time:** 4 pm

**Venue:** Room 6/202

**November 12, 2018.**

*Some Aspects of Computational Journalism.*Prof. Niloy Ganguly, Professor at Indian Institute of Technology Kharagpur

**Abstract:**
Due to the enormous amount of information being carried over online systems today, no user can access all such information. Therefore, to help the users, all major online organizations deploy information retrieval (content recommendation, search or ranking) systems to find important information. Current information retrieval systems have to make certain design choices. For example, news recommendation systems need to decide on the quality of recommended news stories, how much emphasis to give to a story’s long-term importance over its recency or freshness etc. Similarly, retrieval systems over user generated contents (e.g., in social media like Facebook and Twitter) need to take into account the content posted by heterogeneous user groups. However, such design choices can introduce unintended biases in the contents presented to the users. For example, the recommended contents may have poor quality or less news value, or the news discourse may get hijacked by hyper-active demographic groups. In this work, we want to systematically measure the effect of such design choices in the retrieval systems (recommendation systems in particular), and build alternate retrieval systems that mitigate the biases in the recommendation output.

**Time:** 10 am - 11 am

**Venue:** Room 7/209

**November 2, 2018.**

*Air Quality, Citizen Science and Capacity Building Powered by Earth Observations.*Dr. Pawan Gupta, Professor at USRA, NASA Marshall Space Flight Center, Huntsville, AL

**Abstract:**
In this talk, I will discuss the global air quality monitoring status, gaps, and opportunities. The role of Earth Observing Satellites (EOS) in global air quality monitoring will be discussed. Examples of various air quality applications where satellite data have successfully used will be presented. The role of low-cost air-quality monitor network in understanding spatial and temporal gradient in column and surface particles loading will also be discussed. I will also discuss some of the NASA resources and capacity-building programs to support the use of space-based observations for monitoring and decision-making activities around the world.

**Time:** 2 pm - 3 pm

**Venue:** Room 1/102

**September 5, 2018.**

*Privacy and Security in Online Social Media.*Prof. Ponnurangam Kumaraguru, Professor at IIIT Delhi

**Abstract:**
With an increase in usage of the Internet, there has been an exponential increase in the use of online social media. Websites like Facebook, Instagram, YouTube, Twitter, Reddit, Pinterest, and Flickr have changed the way the Internet is being used. There is a dire need to investigate, measure, and understand different facets of online social media from various perspectives (computational, cultural, psychological). A large amount of data, and understanding of the behaviour on social networks can be used to address various societal problems that users face on the Internet. Real world scalable systems need to be built to reduce the impact of these problems on the users. I will describe briefly some cool projects that we work on: Spam Campaigns on Twitter, Follower Count Fallacy, I Spy With My Little Eye, #KillFies, and #BlueWhale Most of our research work is made available for public use through tools or online services. Our work derives techniques from Computational Social Science, Data Science,
Statistics, Network Science, and Human Computer Interaction. I will be more than happy to clarify, discuss any of our work in detail, as required, after the talk.

**Time:** 10 am - 11 am

**Venue:** Room 6/202

**August 17, 2018.**

*Collusion in Online Media.*Dr. Tanmoy Chakraborty, Assistant Professor at IIIT Delhi

**Abstract:**
Decentralized social media, accessed through Internet-based forums, promise greater responsiveness, larger coverage, and reduced vulnerability to authoritative biases. Unfortunately, they also come with limited liability for disinformation and collusive persuasion, locking communities into "echo chambers'' of opinion. Recent world events provide ample testimony that collusion is a serious challenge to unbiased truth discovery and opinion formation. In the talk, I shall address our ongoing effort in understanding different forms of collusion happening around Twitter. In particular, I shall present our recently-developed system, called SoptCU which detects collusive followers involved in blackmarket services. The talk will end with a glimpse of the overall research activities going on in our group.

**Time:** 11 am - 12 pm

**Venue:** Room 7/102

**August 07, 2018.**

*From Linear recurrences to probabilistic verification via Diophantine approximation.*Dr Nikhil Balaji, Research Associate at University of Oxford.

**Abstract:**
Given a linear recurrence sequence (LRS) with initial conditions defining an infinite sequence, the Skolem problem, asks if zero ever occurs in this infinite sequence. The decidability of this problem has been open for several decades. Currently decidability is known only for LRS of an order up to 4. A series of papers due to Ouaknine and Worrell show that decidability of certain related problems on linear recurrences would solve in longstanding open problems in Diophantine approximation. For arbitrary orders (i.e., number of terms the n^{th} depends on), the only known complexity result is NP-hardness from a 2003 paper of Blondel and Portier.

In this talk, I'll give a different proof of this result, which is arguably simpler and interestingly yields a subclass of LRS for which the Skolem problem which is NP-complete. I'll also mention a few open problems closely related to the Skolem problem.

Along the way, we see how this simple problem relates to verification of probabilistic systems and highlight a few related questions and observations.

Partly based on joint work with S. Akshay and Nikhil Vyas

**Time:** 3:30 pm

**Venue:** Room 7/102

**May 29, 2018.**

*Matching under preferences: Stability is ubiquitous but popularity is hard to find.*Dr. Sushmita Gupta, Postdoctoral researcher at University of Bergen, Norway.

**Abstract:**Matching under preferences is a research area that finds numerous applications in practice as diverse as assigning colleges to students, workers to firms, kidney donors to recipients and users to servers in a distributed internet service, to just name a few.

In the first part of the talk, I will discuss canonical problems in this area, namely, stable matching and its generalization, popular matching. These problems are at the very heart of the intersection between Computer Science and Economics. In the second part of the talk, I will present a new result that resolved the arguably main open problem in the subarea of popular matching: In an arbitrary graph, deciding if a popular matching exists is NP-complete. The computational complexity of this problem has been unknown for over a decade, during which it was repeatedly posed as a fundamental open question.

**Time:** 11 am – 12 pm

**Venue:** Room 7/202

**May 9, 2018.**

*Understanding research: Curation, Growth, and Applications.*Dr. Mayank Singh, PhD, CSE, Indian Institute of Technology, Kharagpur.

**Abstract:**Understanding scholarly articles is a key ingredient of impressive research recipe. With the tremendous advancement in internet infrastructure, we are witnessing an ongoing explosion in scholarly information generation. In this talk, I attempt to discuss some of the challenges emanating from scholarly volume overload. In particular, I will look into three different dimensions: (i) metadata, structure, bibliography and experimental performance extraction from scholarly articles, (ii) designing network-assisted ageing growth models for evolving citation networks with novel proposal of temporal signatures, and (iii) leveraging textual and network information to design long-term scientific prediction and venue categorization frameworks.

**Time:**3:00 PM – 4:00

**Venue:**Room 6/202

**May 1, 2018.**

*The Billion Building Challenge.*Dr. Nipun Batra, Postdoc at University of Virginia.

**Abstract:**Buildings contribute roughly one-thirds of the total energy consumption. Energy breakdown – providing energy consumption at a per-appliance level can help occupants save up to 15% energy. In this talk, I will propose the building billion challenge – providing an energy breakdown to a billion buildings. Previous approaches required sensor hardware to be installed in each home and thus do not scale well. Towards the challenge, I will present my approach called collaborative sensing which provides an energy breakdown without installing any additional sensors. The key intuition is that the energy consumption variation across buildings can be represented via a low dimensional representation. Our approach leverages transfer learning techniques to scale energy breakdown to regions with none to low instrumentation. Finally, I will talk about providing actionable insights based on the energy breakdown data, and about making energy breakdown research comparable.

**Time:**4:30 PM – 5:30

**Venue:**Room 7/202

**April 19th, 2018.**

*Probabilistic Graphical Models.*Mr. Ajay Ghanti and Mr. Harish Kashyap.

**Speakers Bio:**Mr. Ajay Ghanti currently is the CTO of MCG and co-founder of Diagram.AI. He is leading the ML and Data Science teams out of Mysore, India. Mr. Harish Kashyap has a Masters from Northeastern University, Boston in Electrical Engineering. He is currently the founder of Mysuru Consulting Group and Diagram.AI.

**Time:**4:30 PM

**Venue:**5/203

**April 13th, 2018.**

*Mechanism Design for Stochastic Multi-armed Bandit Problems.*Shweta Jain, Ph.D. CSA at IISc Bangalore.

**Abstract:**The multi-armed bandit (MAB) problem is widely studied in the machine learning literature, in the context of online learning. My recent work has studied the MAB problem when the arms are controlled by strategic agents. Dealing with strategic agents warrants the use of principled tools such as game theory and mechanism design in conjunction with online learning, and leads to non-trivial technical challenges. My research offers novel mechanisms for stochastic MAB problems in the various representative, generic settings inspired by applications such as smart grids, crowdsourcing, Internet advertising, and procurement auction. In this talk, I will discuss in detail about one particular problem of designing a low regret, combinatorial, randomized mechanism for the MAB problem, where, we consider a problem of selecting a subset of agents to solve a general combinatorial optimization problem.

**Time:**11 am to 12 noon.

**Venue:**7/202

**April 10th, 2018.**

*Architecting DRAM Based Memory Subsystem For Performance.*Dr. Venkata Kalyan Tavva (Kalyan), Hardware Performance Architect at laboratories of IBM Systems.

**Abstract:**In this talk, to begin with, the fundamentals of memory subsystem are presented. With an improved understanding of the memory subsystem, the talk next dives into the details of two performance improvement techniques. The first technique, namely, Enhanced Fine Granularity Refresh (EFGR), revisits the standard DRAM refresh process to question the fundamental design choices involved during a refresh. EFGR increases the availability of the DRAM banks by refreshing fewer banks of a rank per-refresh and achieves parallel operation of request service and the refresh. Following EFGR, an intuitive DRAM command scheduling technique, namely, just in-time bank access (JIBA), is presented that exploits the DRAM charateristics for power and performance improvement. JIBA reduces the operating power of DRAM by delaying the bank activation operation by taking cues from the current data bus utilization.

**Time:**11 am to 12 noon.

**Venue:**6/202

**April 4th, 2018.**

*Trip Report on GIAN COURSE + SCEC 17 + HiPC 17.*Tom Glint Issac, Ph.D., CSE.

**Abstract:**In this talk, I would like to give a comprehensive presentation on some research problems in Computer Systems. I will share experiences gained by participating in the following: GIAN COURSE + SCEC + HiPC 17.

The* GIAN Course on Emerging Computational Devices, Architectures and Systems* includes the following topics: Emerging logic and memory devices; Circuit Architecture design using Emerging Logic and Memory, Processor-in-Memory Architectures using emerging devices; Neuromorphic and Brain Inspired Computational Models; Computing Using Coupled Oscillator Systems; and Other Emerging Computational Models.

The *Workshop on Software Challenges to Exascale Computing (SCEC 17)* was focused on sharing the challenges faced by large problems that require HPC hardware to solve.

The *IEEE International Conference on High-Performance Computing (HiPC 2017)* is a forum for researchers to present their work on areas of algorithms, system software, and architectures.

**Time:** 4:30pm –5:30pm, (Wed)

**Venue:** 7/202

**5th April 2018.**

*Partitioning Problems on Graphs with Bounded Tree-Width.*Prof. Subrahmanyam Kalyanasundaram, Department of Computer Science and Engineering, IIT Hyderabad.

**Abstract:** For an undirected graph G, we consider the following problems: given a fixed graph H, can we partition the vertices of G into two sets A and B such that neither the induced graph G[A] nor G[B] (i) contains H as a subgraph? and (ii) contain H as an induced subgraph?

The problems are NP-complete and are expressible in monadic second order logic (MSOL). The MSOL formulation, together with Courcelle’s theorem implies linear time solvability on graphs with bounded tree-width. This approach yields algorithms with running time f(|\phi|, t) * n, where |\phi| is the length of the MSOL formula, t is the tree-width of the graph and n is the number of vertices of G. The dependency of f(|\phi|, t) on |\phi| can be as bad as a tower of exponentials.

In this talk, we describe explicit combinatorial algorithms for the problems for the case when G has bounded tree-width. Our algorithms run in 2^{O(t^r)} * n time, when H is any fixed graph of order r. This is joint work with N. R. Aravind and Anjeneya Swami Kare.

**Time:** 3:00 pm to 4:00pm, (Thu)

**Venue:** 5/202

**March 21st, 2018.**

*Introduction to Containers.*Mr. Dharmit Shah, Software Engineer at Red Hat.

**Abstract:**In this talk, we’ll explore Linux containers and how they are taking over the development and deployment story across the software industry. We’ll start with Linux containers, talk about how Docker made them popular and finally how Kubernetes has made them ready for production workloads.

**Time:**4:30pm –5:30pm, (Wed)

**Venue:**7/202

**24th January 2018.** *Probabilistic Models and Inference Algorithms for Single-cell Genomics: Applications in Cancer Evolution. *Dr. Hamim Zafar, Graduate Researcher, Department of Computer Science, Rice University.

**Abstract:** Rapidly emerging single-cell DNA sequencing technologies offer promising datasets to further our understanding of diverse facets of cancer biology and genetics. Specifically, it will have a profound impact in resolving the tumor heterogeneity that complicates the diagnosis and treatment of cancer patients and causes relapse and drug resistance. However, novel computational methods are required to perform this task, which is challenged by uncertainties in the underlying evolutionary processes. Moreover, technical artifacts introduced during the sequencing process further complicate this task. Novel computational methods are required for the analysis and interpretation of large-scale single-cell genomic datasets for elucidating tumor heterogeneity and evolution.

In this talk, I will introduce probabilistic models and statistical inference algorithms for elucidating tumor heterogeneity and evolution from single-cell DNA sequencing data. These algorithms probabilistically model the possible mutational histories as well as the sources of uncertainties due to technical artifacts in the data. The mutation discovery algorithm employs a probabilistic model of the technical artifacts and dynamic programming for detecting point mutations from raw single-cell sequencing data. The second method introduces a continuous-time Markov chain to model the underlying mutational events in cancer and infers a tumor phylogeny, a binary leaf-labeled tree that represents the mutational history of a tumor helping guide patient-specific treatment. The final method introduces a tree-structured non-parametric

Bayesian clustering framework to reconstruct the cell subpopulations in a tumor and their mutation content. Using these methods, I analyze several cancer datasets and uncover tumor phylogenies, driver mutations and cell subpopulations that are more biologically plausible than previously reported analyses. To close, I will give a brief outlook on a wider range of future directions towards providing novel computational and data-driven approaches aimed at improvement of patient well-being through advancements in the understanding of biological processes and phenomena.

**Time:** 4:30pm –5:30pm, (Wed)

**Venue:** 6/202

**10th January 2018.*** Markov Chain Monte Carlo simulations for the rational design of molecular systems. *Dr. Kaustubh Rane, Assistant Professor, Chemical Engineering.

**Abstract:** The rational design of molecular systems involves the systematic manipulation of molecular-scale variables to obtain the desired properties. A famous example is the design of drug molecules in the pharmaceutical industry. The field makes extensive use of computer simulations to predict the results of the above manipulations.

The behavior of a molecular system is governed by the density of molecules at different locations. Here, density refers to how well the molecules are “packed.” The local density fluctuates, resulting in a distribution of densities. In this talk, I will explain the application of Markov Chain Monte Carlo (MCMC) simulations to predict such distributions. We will also discuss the usefulness of density-distributions in rational design and the challenges involved in performing the above MCMC simulations.