Events 

Seminars 

Prof. I. G. Sarma Memorial Lecture Series 

Prof. Priti Shankar Memorial Seminar Series 

Multimedia Archive 



UPCOMING SEMINARS 

Series: Department Seminar Title: New Paradigms in Cache Architectures.  Speaker: 1. Mr. Jayesh Gaur
Senior Research Scientist and Manager
MicroArchitecture Research Lab (MRL)
Intel India
2. Mr. Anant Nori
Senior Research Scientist and Manager
MicroArchitecture Research Lab (MRL)
Intel India  Date and Time: Friday, October 05, 2018, 2:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract The memory wall continues to be a major performance bottleneck. Caching has been well recognized as a powerful solution to filter requests going to the main memory and boost performance. Unsurprisingly the general industry trend has therefore been to increase the amount of cache that is put on die. In fact, recent advances in technologies like embedded DRAM (eDRAM) and high bandwidth memory (HBM), have even allowed building very large multiMB to GB caches. All these solutions are driven by the conventional wisdom that increasing the hit rate in the cache subsystem improves average latency and bandwidth and hence gains performance.
At the MicroArchitecture Research Labs, India we have been fundamentally relooking at caching, and have shown that cache design and architecture is more than just increasing overall cache hit rates. In this talk we will discuss two of our recent works in this direction.
The first talk will focus on how efficiently large HBM or eDRAM caches can be managed. We show that blindly increasing hit rates for such large caches can in fact be detrimental to performance ! Instead we develop a dynamic access partitioning scheme that sacrifices some amount of hit rates in order to tap the main memory bandwidth and overall increase performance. This work was adjudged as the best paper at HPCA 2017.
In the second work, we do a fundamental reanalysis of the popular three level cache hierarchy and show that it is not the most efficient way of designing ondie caches. Instead we show that a much lower area, two level cache hierarchy, aided with a learning of the program behaviour, can outperform the more costly three level cache hierarchy, thereby presenting interesting areaperformancecost tradeoffs for cache designers. This work was published at ISCA 2018.
Speaker Bio: 1. Jayesh Gaur is a senior research scientist and manager at the MicroArchitecture Research Lab (MRL), Intel India where his focus is on improving the performance of modern out of order processors. Prior to joining MRL, he worked on the architecture of the last level cache of the Skylake family of Intel processors. Jayesh has published widely in architecture conferences and has been granted/filed for nearly two dozen patents. Jayesh has an MSE in Computer Engineering from University of Michigan, Ann Arbor and a BTech. in Electrical Engineering from IIT Kanpur.
2. Anant Nori is a senior research scientist and manager at MRL, Intel India. His focus is on novel prefetching techniques for large window processors. Prior to MRL, Anant worked on the architecture of the main memory controller for the Skylake family of Intel processors. Anant holds/has filed for a dozen patents in main memory optimizations, prefetching, quality of service etc and has been active in architecture publications. He holds an MTech. in Electrical Engineering from IIT Bombay, and a BTech. in Electrical Engineering from NIT Rourkela.
Host Faculty: Dr. Arkaprava Basu
 Series: Department Seminar Title: Sample complexity of partition identification using multiarmed bandits  Speaker: Prof. Sandeep Juneja
Professor and Dean
School of Technology and Computer Science
Tata Institute of Fundamental Research
Mumbai  Date and Time: Wednesday, September 26, 2018, 2:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Given a vector of probability distributions, or arms, each of which can be sampled independently, we consider the problem of identifying the partition to which this vector belongs from a finitely partitioned universe of such vector of distributions. We study this as a pure exploration problem in multi armed bandit settings and develop sample complexity bounds on the total mean number of samples required for identifying the correct partition with high probability. This framework subsumes well studied problems in the literature such as finding the best arm or the best few arms. We consider distributions belonging to the single parameter exponential family and primarily consider partitions where the vector of means of arms lie either in a given set or its complement. The sets considered correspond to distributions where there exists a mean above a specified threshold, where the set is a half space and where either the set or its complement is convex. The latter cases are considered in illustrative simple settings. In all these settings, we characterize the lower bounds on mean number of samples for each arm. Further, inspired by the lower bounds, and building upon Garivier and Kaufmann 2016, we propose algorithms that can match these bounds asymptotically with decreasing probability of error. Applications of this framework may be diverse. We briefly discuss a few associated with nested simulation and its applications to finance.
Speaker Bio: Sandeep is a Professor and Dean at the School of Technology and Computer Science in Tata Institute of Fundamental Research in Mumbai. His research interests lie in applied probability including in mathematical finance, Monte Carlo methods, multiarmed bandit based sequential decision making, and game theoretic analysis of queues. He is currently on the editorial board of Stochastic Systems. Earlier he has been on editorial boards of Mathematics of Operations Research, Management Science and ACM TOMACS.
Host Faculty: Prof. Shalabh Bhatnagar
 Series: Ph.D. Thesis Defense Title: Stochastic Approximation with Markov Noise: Analysis
and applications in reinforcement learning  Speaker: Mr. Prasenjit Karmakar
Ph.D student
Dept. of CSA
IISc  Faculty Advisor: Prof. Shalabh Bhatnagar
 Date and Time: Wednesday, September 26, 2018, 11:00 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Stochastic approximation algorithms are sequential nonparametric methods for finding a zero
or minimum of a function in the situation where only the noisy observations of the function
values are available. Two timescale stochastic approximation algorithms consist of two coupled
recursions which are updated with different (one is considerably smaller than the other) step
sizes which in turn facilitate convergence for such algorithms.
1) We present for the first time an asymptotic convergence analysis of two time scale stochastic
approximation driven by 'controlled' Markov noise. In particular, the faster and slower
recursions have nonadditive controlled Markov noise components in addition to martingale difference
noise. We analyze the asymptotic behavior of our framework by relating it to limiting differential inclusions in both time scales that are defined in terms of the ergodic occupation measures
associated with the controlled Markov processes.
2) Using a special case of our results, we present a solution to the offpolicy
convergence problem for temporaldifference learning with linear function approximation.
3) One of the important assumption in the earlier analysis is the pointwise boundedness (also called the 'stability') of the
iterates. However, finding sufficient verifiable conditions for this is very hard when the noise is Markov as well as when there are multiple timescales . We compile several aspects
of the dynamics of stochastic approximation algorithms with Markov iteratedependent noise
when the iterates are not known to be stable beforehand. We achieve the same by extending
the lockin probability (i.e. the probability of convergence to a specific attractor of the limiting
o.d.e. given that the iterates are in its domain of attraction after a sufficiently large number
of iterations (say) n_0) framework to such recursions. Specifically, with the more restrictive
assumption of Markov iteratedependent noise supported on a bounded subset of the Euclidean
space we give a lower bound for the lock in probability. We use these results to prove almost
sure convergence of the iterates to the specified attractor when the iterates satisfy an 'asymptotic
tightness' condition. This, in turn, is shown to be useful in analyzing the tracking ability of
general 'adaptive' algorithms. Additionally, we show that our results can be used to derive a
sample complexity estimate of such recursions, which then can be used for stepsize selection.
4) Finally, we obtain the first informative error bounds on function approximation for the policy evaluation algorithm proposed by Basu et al. when the aim is to find the risksensitive cost represented
using exponential utility. We also give examples where all our bounds achieve the “actual error”
whereas the earlier bound given by Basu et al. is much weaker in comparison. We show that
this happens due to the absence of difference term in the earlier bound which is always present
in all our bounds when the state space is large. Additionally, we discuss how all our bounds
compare with each other.


PAST SEMINARS 

Series: Ph.D. Thesis Defense Title: Integrating ReadCopyUpdate Synchronization and Memory Allocation  Speaker: Mr. Aravinda Prasad
Ph.D (ERP) student
Dept. of CSA
IISc  Faculty Advisor: Prof. K Gopinath & Dr. Vinayaka D Pandit (Organizational guide) IBM, Bangalore, India
 Date and Time: Wednesday, September 19, 2018, 11:00 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract The evolution of large multicore systems with thousands of cores has led
to the exploration of nontraditional procrastinationbased
synchronization techniques such as ReadCopyUpdate (RCU). Deferred
destruction is the fundamental technique used in such techniques where
writers in order to synchronize with the readers defer the freeing of
the objects until the completion of all preexisting readers. This
writerwait time period is referred to as a grace period (GP). The
readers, as a consequence, need not explicitly synchronize with the
writers resulting in low overhead, wait free readside synchronization
primitives.
We observe that the deferred destruction of objects leads to newer and
complex forms of interactions between the synchronization technique and
the memory allocator. We study and analyze the impact of such
interactions in the operating system kernels for enterprise workloads,
highperformance computing environments, idle systems and virtualized
environments. We explore different solutions to efficiently handle
deferred destructions where our general solution integrates
synchronization technique with the memory allocator. Our general
solution further exploits interaction between the synchronization
technique and memory allocator to optimize both of them.
In the first part we analyze the implication of RCU in enterprise
environments. We observe that RCU determines when the deferred object is
safe to reclaim and when it is actually reclaimed. As a result, the
memory reclamation of the deferred objects are completely oblivious of
the memory allocator state leading to poor memory allocator performance.
Furthermore, we observe that the deferred objects provide hints about
the future that inform memory regions that are about to be freed.
Although useful, hints are not exploited as the deferred objects are not
"visible" to memory allocators. We design Prudence, a new dynamic memory
allocator, that is tightly integrated with RCU to ensure visibility of
deferred objects to the memory allocator. Prudence exploits
optimizations based on the hints about the future during important state
transitions. Our evaluation in the Linux kernel shows that Prudence
performs 3.9x to 28x better in micro benchmarks compared to SLUB
allocator. It also improves the overall performance perceptibly (4%18%)
for a mix of widely used synthetic and application benchmarks.
In the second part we analyze the implication of deferred destruction in
idle and Highperformance computing (HPC) environments where the amount
of memory waiting for reclamation in a grace period is negligible due to
limited OS kernel activity. The default grace period computation is not
only futile but also detrimental as the CPU cycles consumed to compute a
grace period leads to jitter in HPC and frequent CPU wakeups in idle
environments. We design a frugal approach to reduce RCU grace period
overhead that reduces the number of grace periods by 68% to 99% and the
CPU time consumed by grace periods by 39% to 99% for NAS parallel
benchmarks and idle systems.
Finally, we analyze the implication of deferred destruction in a
virtualized environment. Preemption of RCUreaders can cause
multisecond latency spikes and can increase peak memory footprint
inside VMs which in turn can negate the serverconsolidation benefits of
virtualization. Although preemption of lock holders in VMs has been
wellstudied, the corresponding solutions do not apply to RCU due to its
exceedingly lightweight readside primitives. We present the first
evaluation of RCUreader preemption in a virtualized environment. Our
evaluation shows 50% increase in the peak memory footprint and 155%
increase in fragmentation for a microbenchmark. We propose Conflux, a
confluence of three mutually independent solutions that enhances the RCU
synchronization technique, memory allocator and the hypervisor to
efficiently handle the RCUreader preemption problem.
Speaker Bio: Aravinda Prasad is a PhD (ERP) student in the Department of Computer
Science and Automation at Indian Institute of Science, Bangalore. He is
advised by Prof. K Gopinath and Dr. Vinayaka D Pandit (IBM).
 Series: Research Student Colloquium Title: 1. Encoding secrets (in a Nonmalleable way)
2. Two algorithms based on separator on a planar graph  Speaker: 1. Ms. Sai Lakshmi Bhavana Obbattu, Ph.D student
2. Mr. Abhiruk Lahiri, Ph.D student  Date and Time: Friday, September 14, 2018, 4:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract 1. Nonmalleable codes generalize the classical notion of error correcting codes by providing a powerful guarantee even in scenarios where the error correcting codes cannot provide any: a decoded message is either the same or completely independent of the underlying message. Nonmalleable codes have seen a lot of exciting research in recent times. In this talk, I will give an introduction to NMCs and then focus on the question of nonmalleably encoding randomness. In particular, I will introduce our notion of Nonmalleable Randomness Encoders and present a construction for the same. Nonmalleable Randomness encoders have interesting applications to Privacy Amplification and Nonmalleable codes. This is joint work with Bhavana Kanukurthi and Sruthi Sekar (Eurocrypt 2018).
2. The problem of finding the minimum cut of a graph is one of the wellstudied problems. In this talk, we will consider the problem when the underlying graph is planar and directed. In a recent paper [SODA '18] an improved O(nloglogn) time algorithm is reported by Mozes et al. We will discuss their technique.
In the second part of this talk, we will discuss local search based approximation algorithm. In particular, we will discuss the idea of the paper by Gibson and Pirwani [ESA '10].
Speaker Bio: 1. Sai Lakshmi Bhavana Obbattu is a doctoral student at Indian Institute of Science, Bangalore, advised by Dr. Bhavana Kanukurthi. Her publication venues include the Theory of Cryptography Conference (TCC) and Eurocrypt. Her TCC publication on Fourstate Nonmalleable Codes was invited to the Journal of Cryptology, which is a premier journal for research in Cryptography. She received her Integrated Dual Degree (B.Tech and M.Tech) from IIT (BHU), Varanasi. Her research interests include Nonmalleable codes, Privacy Amplification, and Applied Multiparty computation.
2. Abhiruk Lahiri is a Ph.D. candidate under the guidance of Prof Sunil Chandran. His research interest is graph theory, algorithms.
Host Faculty: Prof. Sunil L Chandran & Prof. Shalabh Bhatnagar
 Series: Department Seminar Title: Submodular Maximization Under A Matroid Constraint: Asking more
from an old friend "Greedy Algorithm"  Speaker: Prof. Rahul Vaze (TIFR)
 Date and Time: Monday, September 10, 2018, 11:00 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract The classical problem of maximizing a submodular function
under a matroid constraint is considered.
Defining a new measure for the increments made by the greedy algorithm
at each step, called the {bf discriminant}, improved approximation
ratio guarantees are derived for the greedy algorithm.
The new guarantee subsumes all the previous known results for the greedy
algorithm, including the curvature based ones, and the derived
guarantees are shown to be tight via constructing specific instances. A
brief 'tutorialstyle' overview of prior results in the area will also
be provided.
Host Faculty: Dr. Siddharth Barman
 Series: Ph.D. Thesis Defense Title: Deep Learning with Minimal Supervision  Speaker: Mr. Gaurav Pandey
Ph.D Student
Dept. of CSA  Faculty Advisor: Prof. Ambedkar Dukkipati
 Date and Time: Wednesday, August 29, 2018, 11:30 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract In recent years, deep neural networks have achieved extraordinary performance on supervised learning tasks. Convolutional neural networks (CNN) have vastly improved the state of the art for most computer vision tasks including object recognition and segmentation. However, their success relies on the presence of a large amount of labeled data. In contrast, relatively fewer work has been done in deep learning to handle scenarios when access to ground truth is limited, partial or completely absent. In this thesis, we propose models to handle challenging problems with limited labeled information.
Our first contribution is a neural architecture that allows for the extraction of infinitely many features from an object while allowing for tractable inference. This is achieved by using the `kernel trick', that is, we express the inner product in the infinite dimensional feature space as a kernel. The kernel can either be computed exactly for single layer feedforward networks, or approximated by an iterative algorithm for deep convolutional networks. The corresponding models are referred to as stretched deep networks (SDN). We show that when the amount of training data is limited, SDNs with random weights drastically outperform fully supervised CNNs with similar architectures.
While SDNs perform reasonably well for classification with limited labeled data, they can not utilize unlabeled data which is often much easier to obtain. A common approach to utilize unlabeled data is to couple the classifier with an autoencoder (or its variants) thereby minimizing reconstruction error in addition to the classification error. We discuss the limitations of decoderbased architectures and propose a model that allows for the utilization of unlabeled data without the need of a decoder. This is achieved by jointly modeling the distribution of data and latent features in a manner that explicitly assigns zero probability to unobserved data. The joint probability of the data and the latent features is maximized using a two step EMlike procedure. Depending on the task, we allow the latent features to be onehot or realvalued vectors and define a suitable prior on the features. For instance, onehot features correspond to class labels and are directly used for the unsupervised and semisupervised classification tasks. For realvalued features, we use hierarchical Bayesian models as priors over the latent features. Hence, the proposed model, which we refer to as discriminative encoder (or DisCoder), is flexible in the type of latent features that it can capture. The proposed model achieves stateoftheart performance on several challenging datasets.
Having addressed the problem of utilizing unlabeled data for classification, we move to a domain where obtaining labels is a lot more expensive, that is, semantic image segmentation. Explicitly labeling each pixel of an image with the object that the pixel belongs to, is an expensive operation, in terms of time as well as effort.
Currently, only a few classes of images have been densely (pixellevel) labeled. Even among these classes, only a few images per class have pixellevel supervision. Models that rely on denselylabeled images, can not utilize a much larger set of weakly annotated images available on the web. Moreover, these models can not learn the segmentation masks for new classes, where there is no densely labeled data.
Hence, we propose a model for utilizing weaklylabeled data for semantic segmentation of images. This is achieved by generating fake labels for each image, while simultaneously forcing the output of the CNN to satisfy the meanfield constraints imposed by a conditional random field. We show that one can enforce the CRF constraints by forcing the distribution at each pixel to be close to the distribution of its neighbors.
The proposed model is very fast to train and achieves stateoftheart performance on the popular VOC2012 dataset for the task of weakly supervised semantic image segmentation.
 Series: M.Tech (Research) Colloquium Title: DataRaces and Static Analysis for InterruptDriven Kernels  Speaker: Nikita Chopra
 Faculty Advisor: Deepak D'Souza
 Date and Time: Thursday, August 23, 2018, 11:30 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Static analysis of concurrent programs is challenging due to the
exponential number of program points one needs to consider in a naive
analysis. Datarace free (DRF) programs are an important class of
concurrent programs. Programmers normally write DRF programs, as they
generally tend to obtain locks before accessing shared objects. There
are many techniques in the literature which exploit the property of
datarace freedom in programs to do an efficient static analysis on
them. One class of these techniques use an efficient controlflow
structure called a "SyncCFG" [De et al, 2011].
In this thesis we consider a class of interruptdriven programs that
model the kernel API libraries of some popular realtime embedded
operating systems and the synchronization mechanisms they use. Though
these programs are similar to classical concurrent programs, they make
use of nonstandard synchronization mechanisms like disabling
interrupts, suspending the scheduler, and flagbased synchronization.
Our aim is to carry out efficient SyncCFG style static analysis for the
class of racefree interruptdriven programs.
Since the definition of races as well as the construction of the
SyncCFG depend on the notion of "synchronization edges", we need a
suitable way of defining these edges for interruptdriven programs.
We give a principled way of defining them using a
key notion called "disjoint blocks". This notion also suggests an
efficient and effective lockset based analysis for race detection in
such programs.
We use our theory to carry out static analysis on the kernel library
of FreeRTOS, a popular realtime operating system, to detect races and
to infer simple relational invariants on key kernel variables and
datastructures. We have implemented the lockset algorithm for race
detection using CIL as the frontend. We were able to detect 14 races
in the FreeRTOS kernel library. All of these races were found to be
real races on inspection. We also carried out a regionbased
relational analysis using an implementation based on CIL/Apron, to
prove several relational invariants on the kernel variables and
abstracted datastructures.
Speaker Bio: Nikita Chopra is an MSc(Engg) student in the CSA department.
Host Faculty: Deepak D'Souza
 Series: Department Seminar Title: Approximate Kernel PCA Using Random Features: Computational vs. Statistical Tradeoff  Speaker: Prof. Bharath Sriperumbudur
Department of Statistics
The Pennsylvania State University  Date and Time: Tuesday, August 21, 2018, 2:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Kernel principal component analysis (KPCA) is a popular nonlinear dimensionality reduction technique, which generalizes classical linear PCA by finding functions in a reproducing kernel Hilbert space (RKHS) such that the function evaluation at a random variable X has maximum variance. Despite its popularity, kernel PCA suffers from poor scalability in big data scenarios as it involves solving an x n eigensystem leading to a computational complexity of O(n^3) with n being the number of samples. To address this issue, in this work, we consider a random feature approximation to kernel PCA which requires solving an m x m eigenvalue problem and therefore has a computational complexity of O(m^3), implying that the approximate method is computationally efficient if m<n with m being the number of random features. The goal of this work is to investigate the tradeoff between computational and statistical behaviors of approximate KPCA, i.e., whether the computational gain is achieved at the cost of statistical efficiency. We show that the approximate KPCA is both computationally and statistically efficient compared to KPCA in terms of the error associated with reconstructing a kernel function based on its projection onto the corresponding eigenspaces. Depending on the eigenvalue decay behavior of the covariance operator, we show that only n^{2/3} features (polynomial decay) or sqrt{n} features (exponential decay) are needed to match the statistical performance of KPCA, which means without losing statistically, approximate KPCA has a computational complexity of O(n^2) or O(n^{3/2}) depending on the eigenvalue decay behavior. We also investigate the statistical behavior of approximate KPCA in terms of the convergence of eigenspaces wherein we show that only sqrt{n} features are required to match the performance of KPCA and if fewer than sqrt{n} features are used, then approximate KPCA has a worse statistical behavior than that of KPCA.
Speaker Bio: Bharath Sriperumbudur is an Assistant Professor in the Department of Satistics at Pennsylvania State University. He received his PhD in Electrical Engineering from UC San Diego and had stints as a research fellow at University College London and University of Cambridge. His research interests include nonparametric statistics, empirical process theory, regularization and inverse problems, reproducing kernel spaces in probability and statistics and statistical learning theory.
Host Faculty: Prof. Ambedkar Dukkipati
 Series: Department Seminar Title: Inferring Insertion Times in Bloom Filters  Speaker: Prof. C V Ravishankar, UC Riverside
 Date and Time: Tuesday, August 21, 2018, 11:30 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Bloom filters are extremely useful in dealing with streaming data, but are easy to misuse.
We first illustrate pitfalls in using Bloom Filters, and show how to generalize our techniques
to infer insertion times. We introduce inferential filters, which integrate priors and information
latent in filters to make optimal queryspecific decisions.
We illustrate our approach on TimeDecaying Bloom Filters, which are probabilistic structures to
test membership on recently inserted items. As new items are inserted, memory of older items decays.
Incorrect query responses, however, will penalize the application using the filter. Current filters
may only be tuned to static penalties, and ignore much information latent in the filter. While our
methods are general, we focus here on inferential timedecaying filters, and show how to support
novel query types and sliding window queries with varying error penalties.
We have developed inferential versions of the existing Timing Bloom Filter and Generalized Bloom Filter.
Our experiments on real and synthetic datasets show that when penalties are dynamic and prior
probabilities are known, these filters reduce penalties for incorrect responses to slidingwindow
queries by up to 70%.
Speaker Bio: Chinya V Ravishankar is Professor of Computer Science at the Marlan and Rosemary Bourns College of Engineering at UC Riverside. Ravishankar’s current research and teaching focus is in the fields of Data Management as well as Computer Security. In the past, he has worked and taught in a wide range of areas, including Distributed Systems, Networking, and Programming Languages.
Prof. Ravishankar has served as Associate Dean for at the Marlan and Rosemary Bourns College of Engineering for the past 14 years. His current portfolio covers Research and Graduate Education. His earlier previous portfolio covered Undergraduate Education.
Before moving to UCR in 1999, Prof. Ravishankar was on the faculty of the EECS Department at the University of Michigan, Ann Arbor, between 1986—1999. He holds a PhD in Computer Sciences from the University of Wisconsin—Madison, and a bachelor’s degree in Chemical Engineering from the Indian Institute of Technology (IIT) Bombay.
Host Faculty: Prof. Jayant Haritsa
 Series: Ph.D. Thesis Defense Title: Typestates and Beyond: Verifying Rich Behavioral Properties Over Complex Programs  Speaker: Ashish Mishra
Ph.D Student, CSA Department  Faculty Advisor: Y.N. Srikant
 Date and Time: Friday, August 17, 2018, 10:00 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Statically verifying behavioral/dynamic properties of programs is an important
and challenging research problem. Typestates are the most prevalently used, static,
light‐weight verification systems for verifying program properties. In our work
we present both theoretical and practical contributions towards static analysis
and verification of Typestate defined properties. We dicuss two major challenges
in statically verifying typestate properties over programs.
The first challenge may be attributed to the ``complexity of programs'' being
analyzed. The state‐of‐the‐art static typestate analysis works cannot handle
formidably rich programming features like asynchrony, library calls and callbacks,
concurrency, etc. The second challenge may be attributed to ``complexity of the
property'' being verified. Classical typestates can only verify a property defined
through a finite state machine, and are inadequate to verify richer non‐regular
program properties. Currently, these rich behavioral properties are mostly
verified/enforced at runtime via explicit checks either by the programmer or the
compiler. Unfortunately, these runtime checks are costly, error‐prone, and lay an
extra burden on the programmer.
In this thesis we take small steps towards tackling both these challenges.
Addressing complex program features, we present an asynchrony‐aware static analysis
framework, taking Android applications as our use case. We use this framework to
develop a static typestate analysis to capture Android resource API usage protocol
violations. We present a set of benchmark applications for different resource types,
and empirically compare our typestate analysis with the state‐of‐the‐art synchronous
static analyses for Android applications.
Addressing the challenges associated with increasing complexity of properties, we
present an expressive notion of typestates called, Presburger definable typestates
or p‐typestates. p‐typestates associate an extra Pressburger definable property
along with the states of regular typestates. This allows p‐typestates to express many
useful non‐regular properties. We present a dependent type system for p‐typestates
and present a simple typestate‐oriented language incorporating p‐typestates called
Decidable Rich Interface Programming (DRIP) language. Further, typechecking such
rich p‐typestate properties requires a programmer to provide invariants for loops
and recursive structures. Unfortunately, providing these invariants is a non‐trivial
task even for expert programmers. To solve this problem, we present a simple and
novel loop invariant calculation approach for Pressburger definable systems. We
encode a number of real world programs in our dependently‐typed language to verify
several rich and non‐regular properties.
Finally we discuss several possible extensions of our thesis along both these directions.
Speaker Bio: Mr.Ashish Mishra is a Ph.D student in the CSA department. After submitting his thesis, he has been working as a postdoctoral research at North Eastern University, USA. His areas of interest are programming language theory, program analysis and verification, and semantics of programming languages.
Host Faculty: Y N Srikant
 Series: Department Seminar Title: On Complexity of Closest Pair Problem  Speaker: Mr. Karthik C.S.
Ph.D Student
Weizmann Institute of Science
Israel  Date and Time: Monday, August 13, 2018, 10:00 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Closest Pair is a fundamental problem in Computational Geometry, where we are given a set of n points in R^d and we would like to find the closest pair of points in the set. In this talk we will see that assuming the Strong Exponential Time Hypothesis for SAT, Closest Pair cannot be solved in subquadratic (in n) time when d=omega(log n) for all L_p metrics.
Based on two joint works  first one with Roee David and Bundit Laekhanukit and second one with Pasin Manurangsi.
Host Faculty: Dr. Arnab Bhattacharyya
 Series: CSA Faculty Colloquium Title: How to securely snapshot memory  Speaker: Prof. Vinod Ganapathy
Associate Professor
Dept. of CSA
IISc  Date and Time: Friday, August 10, 2018, 4:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Computer systems security has historically been a game of cat and mouse between attackers and defenders. Attackers develop novel techniques to bypass proposed defenses, while defenders must think ahead and foresee novel attacks. In this setting, how can the defender get the upper hand? This talk will make the case for security from the hardware up. We will consider the problem of securely obtaining snapshots of a computer system's memory. Snapshots play a key role in computer forensics, and it is therefore key to ensure that a machine can be snapshot free from an adversary's tampering. We will describe how adversaries have subverted these techniques in the past, and how stateoftheart approaches to obtaining snapshots fail. We will then propose a hardwarebased mechanism to obtain snapshots and show that it offers attractive benefits.
Speaker Bio: Vinod Ganapathy is an associate professor in the CSA department working on computer systems security.
Host Faculty: Prof. Sunil L Chandran & Prof. Shalabh Bhatnagar
 Series: Department Seminar Title: Interactive Visual Analysis of Large Urban Data using Urbane  Speaker: Dr. Harish Doraiswamy
Research Scientist
New York University  Date and Time: Thursday, August 02, 2018, 11:00 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract The recent explosion in the number and size of spatiotemporal data sets from urban environments and social sensors creates new opportunities for datadriven approaches to understand and improve cities. Visualization and visual analytics systems have been successfully used at enabling users to obtain insight: welldesigned visualizations substitute perception for cognition, freeing up limited cognitive/memory resources for higherlevel problems. Supporting the interactive response times these systems require is challenging as they often rely on computationally expensive spatial and spatiotemporal queries involving polygonal constraints of arbitrary shapes and sizes. This problem is further compounded as data set sizes increase.
In this talk I will first give an overview of Urbane, a multiresolution visual analytics framework that enables a datadriven analysis of cities. I will then present techniques that use GPUs to obtain real time performance for spatial aggregation queries and are at least two orders of magnitude faster than existing database systems.
Speaker Bio: Harish Doraiswamy is a Research Scientist at the NYU Center for Data Science and a Research Assistant Professor of Computer Science and Engineering at New York University. He received his Ph.D. in Computer Science and Engineering from the Department of Computer Science and Automation at Indian Institute of Science, Bangalore. His research lies in the intersection of computational topology, big data visualization, and databases. His recent research focuses on the visual analyses of large spatiotemporal datasets from urban environments.
Host Faculty: Prof. Vijay Natarajan
 Series: Research Student Colloquium Title: Data Races and Static Analysis for InterruptDriven Kernels  Speaker: Ms.Nikita Chopra
M.Sc.(Engg.) student
Dept. of CSA  Date and Time: Friday, July 27, 2018, 4:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Embedded software is widespread and increasingly employed in safetycritical applications in
medical, automobile, and aerospace domains.
In this work, we consider a class of interruptdriven programs that model the kernel API libraries of some popular realtime embedded operating systems and the synchronization mechanisms they use. We define a natural notion of data races and a happensbefore ordering for such programs. The key insight is the notion of disjoint blocks to define the synchronizeswith relation. This notion also suggests an efficient and effective lockset based analysis for race detection. It also enables us to define efficient "syncCFG" based static analyses for such programs, which exploit datarace freedom. We use this theory to carry out static analysis on the FreeRTOS kernel library to detect races and to infer simple relational invariants on key kernel variables and datastructures.
Speaker Bio: Nikita Chopra is an M.Sc.(Engg.) student in the CSA department. She is working in Programming Languages Lab under the supervision of Prof. Deepak D'Souza. Her broad research interests lie in the area of static program analysis.
Host Faculty: Prof. Sunil L Chandran & Prof. Shalabh Bhatnagar
 Series: Department Seminar Title: Foundations for Natural Proofs and Quantifier Instantiation  Speaker: Madhusudan Parthasarathy
 Date and Time: Friday, July 27, 2018, 11:30 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract The logics required to support program verification are much more
expressive than the class of decidable logics available today, and
beyond the quantifierfree logics supported by SMT solvers. In
particular, when dealing with unbounded structures such as arrays or
dynamically manipulated heaps, the current support for automated
reasoning falls short of what we desire. The typical ways of dealing
with such logics have been through heuristics, and in particular
quantifier instantiation heuristics to deal with quantified logics and
the socalled natural proof heuristics that employ recursionunfolding
tactics to deal with recursively defined datatypes.
We give foundational results that explain the efficacy of heuristics
used for dealing with quantified formulas and recursive
definitions. We develop a framework for first order logic (FOL) over
an uninterpreted combination of background theories. Our central
technical result is that systematic term instantiation is *complete*
for a fragment of FOL that we call safe. Coupled with the fact that
unfolding recursive definitions is essentially term instantiation and
with the observation that heap verification engines generate
verification conditions in the safe fragment explains the efficacy of
verification engines like natural proofs that resort to such
heuristics. Furthermore, we study FOL with recursive definitions that
have least fix point semantics and show that though they are not
amenable to complete procedures, we can systematically introduce
induction principles that in practice bridge the divide between FOL
and FOL with recursive definitions.
Speaker Bio: Madhusudan Parthasarathy is a Professor in the Computer Science Department of the University of Illinois at UrbanaChampaign, USA. His interests are in Software Verification, Security, Program Synthesis and Machine Learning, and Logic and Automata Theory.
Host Faculty: Deepak D'Souza
 Series: Ph.D. Colloquium Title: Design of a LargeScale Distributed File System for PeertoPeer Networks  Speaker: Mr. Hrishikesh Dewan
PhD(ERP)  Faculty Advisor: Prof. R. C. Hansdah and Dr. Girish Suryanarayana(Orgn)
 Date and Time: Wednesday, July 25, 2018, 3:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract We present, in this thesis, a distributed file storage system called Julunga. Julunga is designed
for peertopeer systems supporting federated data centre environments such as cloud computing centres as well
as individual nodes. In Julunga, the metadata, the namespace and the data blocks of the files are entirely
distributed with no hard limits on the number of files that can be accommodated in a single directory. Also,
there is no physical limit on the size of a file. Junlunga supports file of exabytes size with ease along
with the number of concurrent users updating, reading and writing to the same file or a directory. The
location of the data blocks of a file is determined by using functions, thus expunging the need for file
allocation tables. Many new data structures and algorithms were designed where locality and preferences
of users are considered to provide optimal storage locations for files and file system metadata. Julunga
is designed on top of a new overlay network design named 'Afuronto' that is suited for largescale
peertopeer networks requiring fast message transmission, and we use different operators as found in
evolutionary computing to emulate a semistructured network. We present the network structure and the
various algorithms required for essential communication and maintenance. We also study the proposed
network by simulation and compare its performance with existing overlay networks. The simulated results
show that, on the average, there are at most six hops required for a message originated at any node in
the network to be transferred to any other node in the network. The network so designed is scalable,
resilient to failures, and can include a node of arbitrary size in processing capacity, network bandwidth,
and storage.
Reaching consensus is an essential problem in the design of distributed systems. To date, many algorithms
for achieving consensus in a distributed system have been proposed. However, only a few of them works
under practical implementation. For Julnga, we have designed and used a new consensus algorithm called
Majuli. Majuli is designed such that it easier to understand for system developers and resembles natural
techniques of reaching agreement when acting cooperatively. We show the safety and the liveness
property of the proposed consensus algorithm and demonstrate its usefulness in a few distributed
algorithms used in Julunga that require agreement or consensus for their correct operations.
Finally, we describe a new data structure called HashTrie Tree that we have developed to parse
and locate REST based services. The implementation of the overlay network and the file system are
exposed as RESTbased services on top of HTTP(s) protocol. HashTrie Tree is used in our custom
HTTP server designed in C# that has optimum performance when compared with other RESTbased HTTP
servers such as Windows Communication Foundation, Jersey. We show how our implementation supports
REST based service declarations, organizes the various methods in an optimized way for faster
access and scale to support thousands of concurrent users.
 Series: M.Tech (Research) Colloquium Title: Guarding Terrain Using k Watchtowers  Speaker: Nitesh Tripathi
Dept. of CSA  Faculty Advisor: Prof. Sunil L. Chandran
 Date and Time: Tuesday, July 24, 2018, 4:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract The discrete kwatchtower problem for a polyhedral terrain T in 3D with n vertices is to
find k vertical segments, called watchtowers, of smallest height, whose bottom endpoints
(bases) lie on some vertices of T , and every point of T is visible from the top endpoint
(tip) of at least one of those watchtowers. In other words, we have to find k watchtowers
whose bottom endpoints (bases) lie on some vertices of T, such that every point of T is
visible from the tip of at least one watchtower and the maximum height among these k
watchtowers is minimized. Zhu gave an algorithm for this problem when k = 1
with running time O(n log n). Agrawal et al. proposed a polynomial time
algorithm using parametric search technique for this problem with k = 2. Surprisingly,
no result is known for the problem when k > 2. In this talk, we discuss our proposed algorithm to solve kwatchtower problem for a fixed constant k. Our algorithm does not use parametric search and it’s running
time is polynomial in n.
Speaker Bio: Nitesh is a Masters student in CSA department, working in Theory Lab. He is advised by Prof. Sunil L. Chandran.
 Series: Department Seminar Title: Learning discrete Markov Random Fields with nearly optimal runtime and sample complexity.  Speaker: Prof. Raghu Meka
Associate Professor
Department of Computer Science
UCLA  Date and Time: Monday, July 23, 2018, 5:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract We give an algorithm for learning the structure of an undirected graphical model that has essentially optimal sample complexity and running time. We make no assumptions on the structure of the graphical model. For Ising models, this subsumes and improves on all prior work. For general twise MRFs, these are the first results of their kind.
Our approach is new and uses a multiplicativeweight update algorithm. Our algorithm Sparsitron is easy to implement (has only one parameter) and holds in the online setting. It also gives the first provably efficient solution to the problem of learning sparse Generalized Linear Models (GLMs).
Joint work with Adam Klivans.
Speaker Bio: Raghu Meka is an Associate Professor in the CS department at UCLA. He is broadly interested in complexity theory, learning and probability theory. He got his PhD at UT Austin under the (wise) guidance of David Zuckerman. After that, he spent two years in Princeton as a postdoctoral fellow at the Institute for Advanced Study with Avi Wigderson, and at DIMACS, at Rutgers. And after that, he spent an enjoyable year as a researcher at the Microsoft Research Silicon Valley Lab.
Host Faculty: Dr. Arnab Bhattacharyya
 Series: Department Seminar Title: On Randomization and Combinatorics in Computational Geometry,Discrete Mathematics, and Combinatorial Representation Theory.  Speaker: Dr. Kunal Dutta
Postdoc Researcher
Data Shape group
Inria Sophia
France  Date and Time: Monday, July 23, 2018, 3:30 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract In this talk we shall see three very different areas of
applications of combinatorics in computer science and mathematics,
illustrating different flavours of combinatorial reasoning.
First, we consider lower bounds on the maximum size of an
independent set, as well as the number of independent sets, in kuniform
hypergraphs, together with an extension to the maximum size of a subgraph
of bounded degeneracy in a hypergraph. Joint works with C. R. Subramanian
(IMSc, Chennai), Dhruv Mubayi (UIC, Chicago) and Jeff Cooper (UIC,
Chicago) and Arijit Ghosh (IMSc Chennai).
Next, we shall look at Haussler's Packing Lemma from Computational
Geometry and Machine Learning, for set systems of bounded VC dimension. We
shall go through its generalization to the Shallow Packing Lemma for
systems of shallow cell complexity, and see how it can be used to prove
the existence of small representations of set systems, such as epsilon
nets, Mnets, etc. Joint works with Arijit Ghosh (IMSc, Chennai), Nabil
Mustafa (ESIEE Paris), Bruno Jartoux (ESIEE Paris) and Esther Ezra
(Georgia Inst. Tech., Atlanta).
The last problem is on the decomposition, into irreducible
representations, of the Weil representation of the full symplectic group
associated to a finite module of odd order over a Dedekind domain. We
shall discuss how a poset structure defined on the orbits of finite
abelian pgroups under automorphisms can be used to show the decomposition
of the Weil representation is multiplicityfree, as well as parametrize
the irreducible subrepresentations, compute their dimensions in terms of
p, etc. Joint works with Amritanshu Prasad (IMSc, Chennai).
Host Faculty: Prof. Sunil L Chandran

