Events 

Seminars 

Prof. I. G. Sarma Memorial Lecture Series 

Prof. Priti Shankar Memorial Seminar Series 

Multimedia Archive 



UPCOMING SEMINARS 

Series: Department Seminar Title: Representation and Representative Families  Speaker: Dr Fahad Panolan
Postdoctoral Researcher, University of Bergen, Norway  Date and Time: Monday, April 16, 2018, 11:00 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract A subfamily F' of a family F, where each set in F is of size p, is a qrepresentative family for F if the following condition holds: for every set A in F and a set B of size q such that A is disjoint from B, there exists a set A' in F such that A' is disjoint from B. By the classic result of Bollobas, every family of sets of size p has a qrepresentative family with at most $binom{p+q}{p}$ sets (which is independent of the size of F). The notion of representative families can be extended to matroids. A subfamily F' of a family F, where each set in F is of size p and is an independent set of a matroid M, is a qrepresentative family for F if the following condition holds: for every set A in F and a set B of size q such that A is disjoint from B, and A union B is an independent set in M, there exists a set A' in F such that A' is disjoint from B, and A' union B is an independent set in M. By the two families theorem of Lovasz, every family of independent sets of size p in a linear matroid has a qrepresentative family with at most $binom{p+q}{p}$ sets. We designed fast algorithms to compute qrepresentative families on both set systems (uniform matroid) and linear matroids. In this talk, I demonstrate how the efficient construction of representative families on set systems as well as linear matroids can be used to design fast parameterized algorithms.
Our algorithm for the computation of a representative family on a linear matroid crucially uses the given linear representation of the matroid. Unfortunately, for some well known matroids like transversal matroids and gammoids, so far we only know how to compute their linear representations in randomized polynomial time and those algorithms uses Polynomial Identity Testing (PIT). Derandomization of PIT and deterministic polynomial time computation of linear representations of transversal matroids and gammoids are long standing open problems. To overcome this, we defined a notion of union representation of matroids and give a deterministic computation of union representation of a transversal matroid in time quasipolynomial in the rank of the matroid. The notion of union representation yields a fast deterministic computation of representative families on transversal matroids.
Host Faculty: Prof. Matthew Jacob
 Series: Department Seminar Title: The Billion Buildings Challenge  Speaker: Dr Nipun Batra
Postdoctoral Researcher, University of Virgina, Charlottesville  Date and Time: Wednesday, April 11, 2018, 11:00 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Buildings contribute roughly onethird of the total energy consumption. Energy breakdown  providing energy consumption at a perappliance 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.
Speaker Bio: Nipun Batra is a CS postdoc at the University of Virginia. Previously, he completed his PhD from IIIT Delhi and his bachelors from Delhi College of Engineering. His work has received various awards such as best doctoral consortium presentation at SenSys 2015, best demo award at Buildsys 2014, finalist in the UChicago Urban Indian challenge, among others. He recently served as the TPC chair of the NILM 2018 workshop.
Host Faculty: Prof. Matthew Jacob
 Series: Ph.D. Thesis Defense Title: Static analysis and automated testing of fileprocessing programs  Speaker: Mr. Raveendra Kumar Medicherla
Ph.D student (ERP)
Dept of CSA  Faculty Advisor: Prof. K V Raghavan & Dr. M Girish Chandra (Organizational guide, TCS Limited)
 Date and Time: Monday, April 02, 2018, 10:30 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Programs that process data residing in files are widely used in domains
such as banking, healthcare, networking, and logfile analysis. For these
programs, there is a strong need for automated tool support for analysis
and transformation tasks such as bug detection, program understanding, and
program remodularization. However, due to the complex idioms used in
fileprocessing programs, precise analysis of these programs as well as
automated testing of these programs is a challenging task. These are the
problems that we address in this thesis.
Our first contribution is about dataflow analysis of fileprocessing
programs. Our key insight here is that the analysis of a file processing
program can be made more precise and useful if knowledge of the input file
format of the program is made available to the analysis and incorporated
into the transfer functions. We show empirical results for this using
standard dataflow problems. We also develop two novel applications of this
technique  the first one to specialize a program to a given "restricted"
input file format, and the second one to verify if a program "conforms" to
a given input file format. Experiments on a set of benchmark programs
showed that our approach provides precise output compared to naive
approaches.
For precise dataflow analysis of programs with multiple procedures,
*context sensitive* interprocedural data flow analysis is required. It is
very expensive in its full form. As our second contribution, we propose a
*prefix* approximation for contextsensitive analysis, wherein a prefix of
the full context stack is used to tag dataflow facts. Our technique, which
is in contrast with the standard *suffix* approximation technique, is
designed to be more scalable on programs that have distinct *application*
and *library* layers, while offering comparable or even better precision
within the application layer. We analyzed several large enterprise
fileprocessing programs using an implementation of our technique and
compared it with the suffix approximation technique. Performance of our approach
was several times better than that of the suffix approximation,
while generally not suffering any precision penalty in the application
layer of the programs. It is notable that this approach could be equally
applicable in the context of non fileprocessing programs as well.
Our final contribution is regarding automated testing of fileprocessing
programs. *Fuzz testing* is an automated softwaretesting technique that
aims to uncover runtime errors by executing the target program with a
large number of inputs generated automatically and systematically. *Grey
box* fuzzing is a kind of fuzzing that employs lightweight instrumentation
of the program, and observes the behaviors exhibited on a set of test
runs. It then uses this information to generate new test inputs that might
exercise other behaviors. This process is iterated until as many behaviors
as possible get exhibited. AFL is a stateoftheart fuzzer for
fileprocessing programs. With AFL, if a test input causes a new region of
code in the program to be reached, it is considered as a new behavior. In
other words, code coverage is the objective. However, a vulnerability at a
program point may not get exploited in every visit to the program point;
only certain program paths that lead to that point may expose the
vulnerability. We extend greybox fuzzing to take into account a given
vulnerability of interest (e.g., buffer overruns), and to try explicitly to
traverse paths that are likely to expose such vulnerabilities. We have
implemented our approach by enhancing AFL, in the context of the buffer
overrun vulnerability. We evaluated our approach on a suite of benchmark
programs, and compared it with AFL in its standard form. Our approach
uncovered many more number of buffer overflow errors in these
benchmarks compared to standard AFL for the same given amount of fuzzing
time.
 Series: Research Student Colloquium Title: 1) BE NOT ASHAMED OF THE PIMPLE  FLAUNT IT!
2) Modelling Dynamic Networks  Speaker: 1) Ullas Aparanji
2) Shubham Gupta  Date and Time: Friday, March 23, 2018, 4:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract 1) "Stopping by Code on a Summer Evening"
Whose fields these are I think I know.
His implementation is in a structure though
He will not see me stopping here
To watch his structure's size just grow.
My little compiler must think it queer
To parse a struct without definition near
With the header files, it shall make
The darkest translation unit of the year.
I give my numbing brain a shake
To ask if there is some mistake.
The implementation all the struct did sweep
Only a handle is all we have at stake.
The structure is scary, dark and deep.
I have the speaker to make me weep,
And pointers are here to ruin my sleep,
And pointers are here to ruin my sleep.

We'd like to have a design pattern to hide the implementation details of an interface from
ordinary clients, so that the implementation may be modified without the need to recompile the
modules dependent upon it. This benefits the programmer as well since a simple interface can
be created, and most details can be hidden in another file. This is important for providing binary
code compatibility through different versions of a shared library, for example.
In case you didn't get that previous paragraph, fret not. It's not relevant for following the talk
(but I guarantee that it will be comprehensible ex post facto). I will be discussing the very basic
nuances of what the Pimple is to demystify its effectiveness and usage, and will convince you
rigorously why you shouldn't despise the "measly" Pimple (oops, inadvertent pun :P). This talk
will be comprehensible to anybody with a very basic understanding of the C programming
language (in particular, structures in C, and a rudimentary understanding of pointers (though
some of you might argue that there is nothing rudimentary about pointers (by the way, the ability
to parse nested parentheses is not a strict requirement to understand the talk (although the
ability to bear my puns is an absolute necessity) :P))), and nothing deeper than this is required
to follow along :)
2) Networks, like everything else in real world, change with time. For example, over time, new
nodes take birth while old nodes are lost into oblivion. Local disturbances in the network ripple
through it, to show their effect on the overall community structure. Since the behaviour,
stability and dynamics of the network are a function of the community structure, in order to
understand the networks, one needs to explicitly model the temporal aspect of these networks.
Most of the earlier work done in the domain of network modelling was restricted to static
networks (which are frozen in time). But as more computational power became available and
practical applications like large scale social network analysis emerged, researchers started
searching for good dynamic network models. In this talk, I will give a brief overview of the
literature on network modelling (both static and dynamic). I will then describe our recently
proposed Evolving Latent Space Model (ELSM) for dynamic networks and demonstrate its
performance on secondary tasks like community detection and link prediction. Can we see the
future using ELSM? Stay tuned!
Speaker Bio: 1) Ullas Aparanji is a second year PhD student, advised by Prof. Y N Srikant. His technical area of
interest lies in Programming Languages, Compilers and Program Analysis. His nontechnical
area of interest lies in poetry, puns and parenthesesnesting (hey, that's alliteration (almost)! :P)
2) Shubham Gupta is a PhD candidate at Statistics and Machine Learning Group, Department of
Computer Science and Automation, IISc. He is working under the guidance of Dr. Ambedkar
Dukkipati. His broad research interests lie in the domain of clustering relational data, with the
focus, at present, on statistical modelling of networks. I n general, he is a big fan of probability
theory and likes to apply it to all sorts of unconventional real life situations like finding the
optimal time for going to mess etc.
Host Faculty: Prof. Sunil Chandran & Prof. Shalabh Bhatnagar
 Series: Department Seminar Title: Stochastic gradient algorithms on Riemannian manifolds.  Speaker: Prof. Hiroyuki Kasai,
The University of ElectroCommunications, Tokyo  Date and Time: Friday, March 23, 2018, 1:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract There has been recently increasing interest in optimization algorithms on Riemannian manifolds in machine learning, statistical learning, and signal processing fields. This talk addresses Riemannian stochastic gradient algorithms, and introduce s some stateofthearts results for finitesum
problems carried out recently. These include variance reduced RSVRG and R  S Q N  V R algorithms , a n d also a new variant RSRG . In this talk, we will particularly address how they are different from, and what challenges exist in comparisons to the algorithms in the Euclidean case.
Speaker Bio: Hiroyuki Kasai received his B.Eng., M.Eng., and Dr.Eng. degrees in Electronics, Information, and Communication Engineering from Waseda University, Tokyo, Japan in 1996, 1998, and 2000, respectively. He was a visiting researcher at British Telecommunication BTexacT Technologies, U.K. during 2000 ‒ 2001. He joined Network Laboratories, NTT DoCoMo, Japan, in 2002, and since 2007 has been an Associate Professor at The University of ElectroCommunications, Tokyo. He was a senior policy researcher at Council for Science, Technology and Innovation Policy (CSTP), Cabinet Office of Japan, during 20112013. He was a visiting researcher at the Technical University of Munich, Germany during 20142015. His research interests include machine learning, optimization, and multimedia signal processing.
Host Faculty: Dr. Partha PratimTalukdar
 Series: Ph.D. Thesis Defense Title: Geometric and Topological Methods for Biomolecular Visualization  Speaker: Talha Bin Masood
 Faculty Advisor: Prof. Vijay Natarajan
 Date and Time: Thursday, March 22, 2018, 3:00 PM
 Venue: CSA Faculty Room, (Room No. 101, Ground floor)
Abstract In recent years, techniques from the field of scientific visualization and computational geometry have increasingly found application in the study of biomolecular structure. In this thesis, we focus on the problems related to identification and visualization of cavities and channels in proteins. In the first part of the thesis, we describe two methods: one for extraction and visualization of biomolecular channels, and the other for extraction of cavities in uncertain data. We also describe the two software tools based on the proposed methods, called ChExVis and RobustCavities. In the second part of the thesis, we describe efficient GPU based parallel algorithms for two geometric structures widely used in the study of biomolecules. One of the structures we discuss is discrete Voronoi diagram which finds applications in channel visualization, while the other structure is alpha complex which is extremely useful in studying geometric and topological properties of biomolecules.
In this talk, we will focus on the software tool called ChExVis designed for extraction and visualization of channels in biomolecules. We will describe the alpha complex based framework for extraction of geometrically feasible channels. In addition, we will present novel ways of visualizing the aminoacids lining the channels together with their physicochemical properties. We will discuss a few case studies that demonstrate the utility of the proposed method. Secondly, we will describe our integrated topological and geometric approach towards identifying biomolecular cavities in uncertain data. We propose an approach that connects userspecified cavities by computing an optimal conduit within the region occupied by the molecule. Later, we will also briefly touch upon GPU based algorithms for faster computation of discrete Voronoi diagram and alpha complex.
Speaker Bio: Talha is a Ph.D. candidate in Computer Science at the Dept. of Computer Science and Automation, Indian Institute of Science, Bangalore. He received B.Tech. degree from Aligarh Muslim University, and M.E. degree from Indian Institute of Science, both in Computer Science and Engineering. His research interests include Scientific visualization, Computational geometry, Computational topology, and their applications to structural biology.


PAST SEMINARS 

Series: Ph.D. Colloquium Title: Interactions Between the ProcrastinationBased
Synchronization and Memory Allocator  Speaker: Mr. Aravinda Prasad
Ph.D student (ERP)
Dept. of CSA  Faculty Advisor: Prof. K Gopinath
 Date and Time: Tuesday, March 20, 2018, 12:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract The evolution of 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 procrastinationbased synchronization
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 deferred destruction 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 microbenchmarks 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: CSA Distinguished Lecture Title: Software Challenges for Extreme Heterogeneity  Speaker: Prof. Vivek Sarkar, Georgia Institute of Technology
 Date and Time: Tuesday, March 20, 2018, 11:00 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract It is widely recognized that a major disruption is under way in
computer hardware as processors strive to extend, and go beyond, the
endgame of Moore's Law. This disruption will include new forms of
heterogeneous processors, heterogeneous memories, nearmemory
computation structures, and, in some cases, Nonvon Neumann computing
elements. In this talk, we summarize the software challenges for
these levels of "extreme heterogeneity", with a focus on the role of
programming systems, which encompass programming models, compilers and
related tools, and runtime systems. These challenges anticipate a new
vision for programming systems that goes beyond their traditional role
of mapping a specific subcomputation to a specific hardware platform,
to an expanded world view in which programming systems manage the
global selection of computation and data mappings of subcomputations
on heterogeneous subsystems. We will discuss recent trends in
programming models, compilers, and runtime systems that point the way
towards addressing the challenges of extreme heterogeneity.
Speaker Bio: Vivek Sarkar is a Professor in the School of Computer Science, and the
Stephen Fleming Chair for Telecommunications in the College of
Computing at at Georgia Institute of Technology, since August 2017.
Prior to joining Georgia Tech, Sarkar was a Professor of Computer
Science at Rice University, and the E.D. Butcher Chair in Engineering.
During 2007  2017, Sarkar led Rice's Habanero Extreme Scale Software
Research Laboratory which focused on unifying parallelism and concurrency
elements of highend computing, multicore, and embedded software stacks
(http://habanero.rice.edu). He also served as Chair of the Department
of Computer Science at Rice during 2013  2016.
Prior to joining Rice in 2007, Sarkar was Senior Manager of Programming
Technologies at IBM Research. His research projects at IBM included
the X10 programming language, the Jikes Research Virtual Machine for
the Java language, the ASTI optimizer used in IBM's XL Fortran product
compilers, and the PTRAN automatic parallelization system. Sarkar
became a member of the IBM Academy of Technology in 1995, and was
inducted as an ACM Fellow in 2008. He has been serving as a member of
the US Department of Energy's Advanced Scientific Computing Advisory
Committee (ASCAC) since 2009, and on CRA's Board of Directors since 2015.
Host Faculty: R. Govindarajan
 Series: Department Seminar Title: Speeding up MWU based approximation schemes for positive LPs and
some applications  Speaker: Prof. Chandra Chekuri
Department of Computer Science
University of Illinois, UIUC  Date and Time: Friday, March 16, 2018, 11:00 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract One of the recent exciting directions in algorithms is developing
faster algorithms for various problems in discrete and combinatorial
optimization via sophisticated continuous optimization methods. The
multiplicative weight update (MWU) method is an older technique and
has been used to approximately solve positive linear programs
(packing, covering and mixed packing and covering LPs) starting from
the early 90s. MWU based methods have some advantages when dealing
with implicit linear programs that arise frequently in combinatorial
optimization. We build upon several existing ideas and propose some
new ones to obtain significantly faster algorithms for several
problems. The talk will illustrate some examples including MetricTSP,
spanning tree packing, and geometric packing and covering problems.
Based on joint work with Kent Quanrud.
Host Faculty: Dr. Anand Louis
 Series: CSA Distinguished Lecture Title: Predictive Control Methods for Networked CyberPhysical Systems  Speaker: Prof. Daniel Quevedo,
Paderborn University, Germany  Date and Time: Wednesday, March 14, 2018, 3:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract The opportunities provided by feedback control of networked dynamical systems are enormous.
Yet it is by no means clear how to harness modern communication, network and
computation technologies to obtain highquality designs. The main stumbling blocks stem
from the significant gaps which exist between understanding of constituent parts and the
challenges faced when bringing them together. The vast realm of applications of networked
cyberphysical systems brings a variety of issues. A common thread is that many of the
standard paradigms that allow the separation of computation, communications and systems
control are no longer valid. Thus, the need for more holistic approaches arises.
This talk illustrates how various communication and computation aspects can be integrated
into suitable predictive control formulations.
Speaker Bio: Daniel Quevedo is Head of the Chair for Automatic Control (Regelungs und Automatisierungstechnik) at Paderborn University, Germany. He received Ingeniero Civil Electrónico and M.Sc. degrees from the Universidad Técnica Federico Santa María, Chile, in 2000. In 2005, he was awarded the Ph.D. degree from the University of Newcastle in Australia.
Dr. Quevedo was supported by a full scholarship from the alumni association during his time at the Universidad Técnica Federico Santa María and received several universitywide prizes upon graduating. He received the IEEE Conference on Decision and Control (CDC) Best Student Paper Award in 2003 and was also a finalist in 2002. In 2009 he was awarded a fiveyear Research Fellowship from the Australian Research Council.
Prof. Quevedo is Associate Editor of the IEEE Control Systems Magazine, Editor of the International Journal of Robust and Nonlinear Control, and serves as Chair of the IEEE Control Systems Society Technical Committee on Networks & Communication Systems. His research interests are in control of networked systems and of power converters.
Host Faculty: Prof. Shalabh Bhatnagar
 Series: Faculty Colloquium Title: Provable Fairness  Speaker: Dr. Siddharth Barman
Assistant Professor
Dept. of CSA  Date and Time: Friday, March 09, 2018, 4:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Fairness is a fundamental consideration in many realworld allocation problems. This talk will provide a formal framework to address this consideration in the context of indivisible resources/goods. Specifically, we will deem an allocation of indivisible goods to be fair if it is envyfree up to one good (EF1), which means that each participant (in the allocation problem) prefers its own bundle over the bundle of any other participant, up to the removal of one good.
In the first part of the talk, I will present recent work which leads a somewhat surprising result that economic efficiency is not sacrificed by imposing fairness. Here, an allocation is said to be efficient if it satisfies Pareto efficiency. In particular, I will detail a (pseudo) polynomialtime algorithm for finding allocations which are both EF1 and Pareto efficient.
The second part of the talk will address fairness in sponsored search auctions, which are a critical revenuegenerating mechanism employed by online search engines. Sponsored search auctions entail assigning advertisement slots among bidders/advertisers, and in these settings fairness is an important concern to ensure quality of service. I will describe our work on truthful auctions which are not only fair (i.e., lead to EF1 allocations) but also approximately maximize welfare.
Including joint work with Sanath Krishnamurthy and Rohit Vaish (preprint https://arxiv.org/abs/1707.04731) along with Ganesh Ghalme, Shweta Jain, Pooja Kulkarni, and Shivika Narang.
Speaker Bio: Siddharth Barman is an Assistant Professor of Computer Science and Ramanujan Fellow at the Indian Institute of Science. Siddharth's research interests lie in the design, analysis, and applications of algorithms. His current research focuses on algorithmic game theory and approximation algorithms. Siddharth received his Ph.D. from the University of Wisconsin  Madison and held a postdoctoral position at the California Institute of Technology.
Host Faculty: Prof. Sunil L Chandran
 Series: Research Student Colloquium Title: 1. A brief introduction to Arithmetic circuit complexity
2. Prudent Memory Reclamation in ProcrastinationBased Synchronization  Speaker: 1. Mr. Nikhil Gupta
2. Mr. Aravinda Prasad  Date and Time: Friday, February 23, 2018, 4:00 PM
 Venue: CSA Lecture Hall (Room No. 117, Ground Floor)
Abstract 1. Arithmetic circuit complexity theory deals with computation of multivariate polynomials over a
field F using addition (+) and multiplication (*) operations. One of the computation model that
captures this computation is arithmetic circuits, with the size of circuit as an associated
measure. An interesting question is, given a polynomial, to find tight lower bounds on the size of
arithmetic circuits computing it. This is important, because a superpolynomial lower bound on
the size of arithmetic circuits computing the ‘symbolic permanent’ would give a separation
between VP and VNP (algebraic analogues of P and NP respectively).
There are several ways to prove lower bounds. One of the approaches is the complexity
measure approach, in which a complexity measure like ‘evaluation dimension’, ‘rank of partial
derivative matrix’ etc is chosen to give lower bounds. In this talk, I will give a skeleton to prove
lower bounds using the complexity measure and state some wellknown results.
Another important problem in this area is to give a deterministic polynomial time algorithm to
test, if a given arithmetic circuit computes the zero polynomial (PIT). An efficient randomized
algorithm is known for PIT due to SchwartzZippel lemma, but derandomizing this is a long
standing open problem. This is important from the perspective of complexity theory because an
efficient deterministic PIT would either give a superpolynomial lower bound on the size of
circuits computing the ‘symbolic permanent’ or show that the problems in the boolean
complexity class NEXP can’t be computed by polynomial size boolean circuits.
2. Procrastination is the fundamental technique used in synchronization
mechanisms such as ReadCopyUpdate (RCU) where writers, in order to
synchronize with readers, defer the freeing of an object until there are
no readers referring to the object. The synchronization mechanism
determines when the deferred object is safe to reclaim and when it is
actually reclaimed. Hence, such memory reclamations are completely
oblivious of the memory allocator state. This induces poor memory
allocator performance, for instance, when the reclamations are
illtimed. Furthermore, deferred objects provide hints about the future
that inform memory regions that are about to be freed. Although useful,
hints are not exploited as deferred objects are not "visible" to memory
allocators.
We introduce Prudence, a dynamic memory allocator, that is tightly
integrated with the synchronization mechanism to ensure visibility of
deferred objects to the memory allocator. Such an integration enables
Prudence to (i) identify the safe time to reclaim deferred objects'
memory, (ii) have an inclusive view of the allocated, free and
abouttobefreed objects, and (iii) exploit optimizations based on the
hints about the future during important state transitions. Our
evaluation in the Linux kernel shows that Prudence integrated with RCU
performs 3.9x to 28x better in microbenchmarks compared to SLUB, a
recent memory allocator in the Linux kernel. It also improves the
overall performance perceptibly (4%18%) for a mix of widely used
synthetic and application benchmarks. Further, it performs better (up to
98%) in terms of object hits in caches, object cache churns, slab
churns, peak memory usage and total fragmentation, when compared with
the SLUB allocator.
Speaker Bio: 1. Nikhil Gupta is a first year Ph.D. student at the department of CSA under prof. Chandan Saha.
He works in the area of algebraic complexity theory.
Relevant lab(s): theoretical Computer Science
2. Aravinda Prasad is a PhD (ERP) student, where he is advised by Prof. K
Gopinath and Dr. Vinayaka D Pandit (IBM).
Relevant lab(s): Computer Systems and Software
Host Faculty: Prof. Sunil Chandran & Prof. Shalabh Bhatnagar
 Series: Department Seminar Title: 1. Blockchain Technology: Promise and Prospects for Industrial and Societal Applications
2. Cryptocurrencies and Blockchains  Speaker: 1. Prof. Y. Narahari
2. Prof. C.E.Veni Madhavan  Date and Time: Friday, February 23, 2018, 2:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract 1. The bitcoin, unleashed in 2008, was for a specific need (digital currency) but offered a spectacular new data structure for achieving tamper proof record keeping.
In this talk, we introduce the building blocks of blockchain technology and survey the rich variety of industrial and societal applications where it can be deployed. In particular, we describe a trusted B2B collaborative platform that we are currently designing using smart contracts inspired by game theoretic analysis.
2. Cryptocurrencies in particular the first and wellknown Bitcoin and others such as Ethereum, are canonical examples of the blockchain paradigm. Minting or generating new elements or coins of this form of currency relies on the notion of proofofwork. Generation of proofofwork is based on solving a computationally intensive problem such as finding a specific form of hash string. Cryptocurrencies have serendipitously heralded a digital information revolution in the form of blockchains, a broad term, for distributed ledger technologies. As monetary instruments these attempt to provide for the many attractive properties of fiat currency such as privacy, anonymity, transferability, fungibility. However, these are different, from State backed denominational fiat currencies, with respect to the properties of fixed, storeofvalue, mediumofexchange, arbitrage within jurisdictional boundaries, seigniorage in fiscal governance, taxation and law enforcement.
An alternative paradigm of cryptographic digital cash, the analog of fiat currency, in the form of digital coins, coupons or tokens, predates the contemporary examples of cryptocurrencies. Our work is on such a system of virtual money. We discuss these paradigms of cryptonomics from perspectives of science, technology, economics, applications, mathematics, governance and humanusage factors.
Speaker Bio: 1. Y. Narahari is a professor in the Department of Computer Science and Automation. His current interests are in topics at the interface of computer science and game theory.
2. Prof.C.E.Veni Madhavan, after formal retirement in August 2014, continues to work in the CSA department on various scientific mentoring and R&D projects with government, academia and industry.
Host Faculty: Prof. Vinod Ganapathy
 Series: Department Seminar Title: WBTS: The new class of WSTS without WQO  Speaker: Alain Finkel
 Date and Time: Thursday, February 22, 2018, 3:30 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract We present the framework based on ideals which was recently used to
obtain new deep results on Petri nets and extensions. We will present
the proof of the powerful but littleknown ErdösTarski theorem. We
argue that the theory of ideals prompts a renewal of the theory of
Well Structured Transitions Systems (WSTS) by providing a way to
define a new class of monotonic systems, the socalled Well Behaved
Transition Systems (WBTS), which properly contains WSTS, and for which
coverability is still decidable by a forward algorithm.
Speaker Bio: Alain Finkel is a professor at the Ecole Normale Superieure, Cachan,
and a member of the Laboratory for Specification and Verification at
ENS Cachan. He is wellknown for his work on verification of
infinitestate systems. He is a recipient of the CAV award in 2017 for
his work on Well Structured Transition Systems.
Host Faculty: Deepak D'Souza
 Series: CSA Distinguished Lecture Title: An Introduction to WellStructured Transition Systems  Speaker: Alain Finkel
 Date and Time: Wednesday, February 21, 2018, 3:30 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract WellStructured Transition Systems (WSTS) are a general class of
infinite state systems, which allow a certain ordering on states that
is compatible with the transition relation of the system. Many
verification problems turn out to be decidable for this general class
of systems. In particular, the theory of WSTS yields decidability
results for important classes of system models like Petri Nets and
Lossy Channel Systems.
In this talk we will present the concepts, the story, some WSTS
models, some applications to different questions, and the main
decidability results for WSTS.
Speaker Bio: Alain Finkel is a professor at the Ecole Normale Superieure, Cachan,
and a member of the Laboratory for Specification and Verification at
ENS Cachan. He is wellknown for his work on verification of
infinite state systems. He is a recipient of the CAV award in 2017 for
his work on WSTS.
Host Faculty: Deepak D'Souza
 Series: CSA Distinguished Lecture Title: Data Analytics – Opportunities and Responsibilities  Speaker: Prof. Venkat V.S.S.Sastry
Head
Royal Military College of Science
Shrivenham
United Kingdom  Date and Time: Wednesday, February 21, 2018, 2:15 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract With rapid developments in computing power, phenomenal rate at which data being generated a second, there are numerous opportunities to exploit the data for the benefit to all concerned – design better products and deliver what is needed just in time. The sheer size of data available that cannot fit into a computer’s memory requires new ways of analysing the data, and new algorithms. Patterns in the data can reveal inherent relationships and also expose anomalous events. These opportunities do come with attendant challenges and raises many ethical questions too.
Data analysis is becoming increasingly multidisciplinary in nature and requires sound technical skills as well as good communication skills. When dealing with data, the scientist is often confronted with ethical considerations that need to be addressed right up front. Access to data alone is not sufficient to justify further analysis as the results may have farreaching implications. This is particularly relevant when working with data in cyberspace.
The talk provides an overview of some of the applications that are being pursued here at Cranfield University. These range from digital forensics, forensic investigations, cybersecurity, learning/learner analytics and vehicle health monitoring. The level of technical details are kept to a minimum to make the talk accessible to public. The younger generation should find the examples sufficiently motivating to take up the discipline.
Speaker Bio: Dr. Venkat V S S Sastry obtained his PhD in applied mathematics from Indian Institute of Science, Bangalore (1980). After a brief period as Research assistant at IISc, Bangalore working on Helicopter Dynamics, he moved to Open University, Milton Keynes where he worked as postdoctoral research fellow (1981  1984) on acoustic wave propagation over rigidporous media and acoustictoseismic coupling in poroelastic media. He continued his interests in acoustic wave propagation at Plymouth Polytechnic (1984  1987) as Research Fellow working on scattering of acoustic waves by fluidloaded elastic objects. He subsequently joined Department of Mathematics and Statistics, as Lecturer at Plymouth Polytechnic (1987  1989). In November 1989, Dr. Sastry joined Department of Applied Mathematics and Operational Research, the then Royal Military College of Science, Shrivenham where he continues as Head of Applied Mathematics and Scientific Computing (2003  ), Centre for Simulation and Analytics, Shrivenham where he continues as Head of Applied Mathematics and Scientific Computing (2003  ), Centre for Simulation and Analytics, School of Cranfield Defence and Security. He is currently Programme Director for Chevening Cyber Security Fellowship (2014  ).
Dr. Sastry is the principal investigator on an ASTRAEA 2 project "Sense and Avoid" (BAESYSTEMS) and principal investigator on "What to do Learners within an mLearning Environment Need?", (ONRG Grant N629091017121) and is CoChair on Working Group for Testing and Evaluation, Mobile Learning Environments Project. He is winner of The Engineer, Technology + innovation awards 2008 for best collaborative research team, BAE Systems, Cranﬁeld and Lancaster Universities for work on conﬂict avoidance and resolution algorithms for unmanned aerial vehicles.
Dr. Sastry is passionate about eAssessment and measurement of performance in academic setting; and has been administering diagnostic tests using bespoke software developed at Cranfield University since 2002. He has been organising a two day conference on EAssessment in Practice since 2008. Since 2012 he joined CAA Programme Committee as eAssessment in Practice Chair.
Host Faculty: Prof. Shalabh Bhatnagar
 Series: Ph.D. Thesis Defense Title: Falcon : A Graph Manipulation Language for Distributed Heterogeneous Systems  Speaker: Unnikrishnan C
 Faculty Advisor: Y.N. Srikant
 Date and Time: Monday, February 19, 2018, 10:00 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Graphs model relationships across realworld entities in web graphs, social network graphs, and road network graphs. Graph algorithms analyze and transform a graph to discover graph properties or to apply a computation. For instance, a pagerank algorithm computes a rank for each page in a webgraph, and a community detection algorithm discovers likely communities in a social network, while a shortest path algorithm computes the quickest way to reach a place from another, in a road network. In Domains such as social information systems, the number of edges can be in billions or trillions. Such large graphs are processed on distributed computer systems or clusters.
Graph algorithms can be executed on multicore CPUs, GPUs with thousands of cores, multiGPU devices, and CPU+GPU clusters, depending on the size of the graph object. While programming such algorithms on heterogeneous targets, a programmer is required to deal with parallelism and and also manage explicit data communication between distributed devices. This implies that a programmer is required to learn CUDA, OpenMP, MPI, etc., and also the details of the hardware architecture. Such codes are error prone and difficult to debug. A Domain Specific Language (DSL) which hides all the hardware details and lets the programmer concentrate only the algorithmic logic will be very useful.
With this as the research goal, Falcon, a graph DSL, and its compiler have been developed. Falcon programs are explicitly parallel and Falcon hides all the hardware details from the programmer. Large graphs that do not fit into the memory of a single device are automatically partitioned by the Falcon compiler. Another feature of Falcon is that it supports mutation of graph objects and thus enables programming dynamic graph algorithms. The Falcon compiler converts a single DSL code to heterogeneous targets such as multicore CPUs, GPUs, multiGPU devices, and CPU+GPU clusters. Compiled codes of Falcon match or outperform stateoftheart graph frameworks for different target platforms and benchmarks.
Speaker Bio: Mr.Unnikrishnan is a Ph.D student of the CSA department and is currently pursuing his postdoc research in Singapore.
Host Faculty: Y.N. Srikant
 Series: CSA Distinguished Lecture Title: On the Complexity of Training a Neural Network  Speaker: Prof. Santosh Vempala
Frederick Storey chair
and Distinguished Professor of Computer Science
Georgia Tech
Atlanta  Date and Time: Friday, February 16, 2018, 11:30 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract The empirical successes of deep learning currently lack rigorous explanation and the effectiveness of gradient descent in particular has mostly been a mystery. As a first step, we focus on training neural networks with a single hidden layer of unbiased activation units and find a surprisingly general polynomialtime analysis of gradient descent, exploiting new connections with tools from spherical harmonics. On the other hand, when the target function is generated by a network using arbitrary biases, the problem is intractable. We construct a family of simple neural networks with a single hidden layer, smooth activation functions and benign input distributions that is hard to learn in the sense that any statistical query algorithm (including all known variants of stochastic gradient descent with any loss function, for any model architecture) needs an exponential number of queries. In describing these results, we will discuss several open problems.
Speaker Bio: Santosh Vempala is Frederick Storey chair and Distinguished Professor of Computer Science at Georgia Tech, where he served as the founding director of the Algorithms and Randomness Center (20062011). Vempala's research interests are broadly in the theory of algorithms, including algorithmic tools for sampling, learning, optimization and data analysis; highdimensional geometry; randomized linear algebra; and ComputingforGood (C4G). He graduated from CMU in 1997 advised by Avrim Blum and then taught at MIT until 2006 except for a year as a Miller Fellow at UC Berkeley. Vempala is also a Sloan, Guggenheim, ACM and generally excitable Fellow, especially when a phenomenon that appears complex from one perspective, turns out to be simple from another. In recent years, he has been trying to understand how to model the computational abilities of the brain.
Host Faculty: Dr. Anand Louis
 Series: Ph.D. Thesis Defense Title: Data Structures and Algorithms to Analyze Concurrency in Android Applications  Speaker: Ms. Pallavi Maiya H P
PhD Student
Dept. of CSA  Faculty Advisor: Prof. Aditya S Kanade
 Date and Time: Friday, February 16, 2018, 10:00 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Android is a popular mobile operating system, providing a rich ecosystem for
the development of applications which run on the Android platform. Entities
such as the device user, network and sensors interact continuously with the
mobile device causing an Android application to face a continuous stream of
input (events). In spite of having to perpetually handle a huge volume of
events, Android applications are expected to be responsive to new events
from the environment. The Android framework achieves this by exposing
applications to a concurrency model which combines multithreading with
asynchronous eventbased dispatch. While this enables development of
efficient applications, unforeseen thread interleavings combined with
nondeterministic ordering of events can lead to subtle concurrency bugs in
Android applications.
In an Android application, threads communicate through shared variables
and by sending events to each other's event queues. Even though typically
a thread processes events in its event queue and invokes corresponding event
handlers in a FIFO order, this ordering however can be altered by attributes
such as delays and priorities associated with the events. The existing literature
extensively describes techniques to detect concurrency bugs such as data races,
deadlocks and atomicity violations in multithreaded programs. Recent works
also present techniques to analyze bugs manifested due to singlethreaded
eventdriven concurrency. However, the complex eventdriven semantics of
Android applications combined with the threadbased semantics render a naive
extension of such concurrency analysis techniques either less effective or
unsound for Android applications. This thesis takes the initial steps towards
developing data structures and algorithms to facilitate effective dynamic
concurrency analysis of Android applications.
We firstly formalize the concurrency behaviour of Android applications by
giving concurrency semantics. Using this semantics we derive a set of rules
to reason about the happensbefore ordering between operations in an Android
execution trace. These rules induce a partial order called a
happensbefore (HB) relation on the operations of an execution trace. Our HB
relation generalizes the so far independently studied HB relations for
multithreaded programs and singlethreaded eventdriven programs. We have
developed a happensbefore based dynamic race detector for Android
applications, called DroidRacer, which detects data races across threads as
well as race conditions between memory accesses from different event handlers
on the same thread. DroidRacer has detected several races in various Android
applications.
We identify a major bottleneck in the computation of the HB relation for
Android applications, that of discovering HB order between event handlers
executed on the same thread. HB order between events in Android is
characterized by complex HB rules which order a pair of event handlers by
inspecting, for example, the order between operations which enqueued the
corresponding events. Android applications usually receive a large number of
events even within a short span of time, which increases the cost of evaluating
such HB rules. As a result HB computation using standard data structures such
as vector clocks alone becomes inefficient in case of Android applications.
We propose a novel data structure, called "event graph", that maintains a subset
of the HB relation to efficiently infer order between any pair of events. We
present an algorithm, called EventTrack, which improves efficiency of vector
clock based HB computation for eventdriven programs using event graphs.
Evaluation of EventTrack against a stateoftheart HB computation technique
for Android applications, yielded significant speedup.
The scope of the happensbefore based dynamic race detector is limited to the
thread interleaving corresponding to the execution trace inspected. However, a
systematic state space exploration technique such as a stateless model checker
can explore all the thread interleavings, and also identify harmful
manifestations of data races which may happen only when multiple racing memory
accesses are performed in a particular order. Partial order reduction (POR) is
a technique used by stateless model checkers to reduce the state space to be
explored while preserving certain interesting program properties. The existing
POR techniques selectively explore different thread interleavings only to
reorder pairs of racing operations from different threads. However, they fail
to follow this strategy for events and hence end up eagerly exploring all
possible ordering between event handlers executed on the same thread, even if
reordering them does not lead to different states. We propose a new POR
technique based on a novel backtracking set called the "dependencecovering
set". Events handled by the same thread are reordered by our POR technique only
if necessary. We prove that exploring dependencecovering sets suffices to
detect all deadlock cycles and assertion violations. To evaluate effectiveness
of our POR scheme, we have implemented a dynamic algorithm to compute
dependencecovering sets. On execution traces obtained from a few Android
applications, we demonstrate that our technique explores many fewer transitions
—often orders of magnitude fewer— compared to exploration based on persistent
sets, a popular POR technique which explores all possible orderings between
events.
The tools, (i) Droidracer, a race detector for Android applications, (ii) a
standalone implementation of EventTrack, to compute HB relation over Android
execution traces, and (iii) EMExplorer  a proofofconcept model checking
framework which simulates the nondeterministic behaviour exhibited by Android
applications, developed by this thesis have been made public.
 Series: Department Seminar Title: Understanding Indian Climate through a spatiotemporally coherent Random Field  Speaker: Dr. Adway Mitra
Postdoctoral Fellow
International Center for Theoretical Sciences (ICTSTIFR)
Bangalore  Date and Time: Thursday, February 15, 2018, 4:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Climatic conditions have a profound impact on the lives of a billion people in India. However, several questions related to Indian climate are still unanswered to climate scientists. The widespread availability of highquality climatic data along with advances in Data Science and Machine Learning have opened up scope for a datadriven approach to these problems. Climatic data is spatiotemporal in nature, where each climatic variable (temperature, rainfall, wind speed etc) is measured at different locations and timepoints. Climatic processes can occur at different spatial and temporal scales, but usually each process spans many spatial and temporal locations. We build a spatiotemporal model based on Markov Random Field, where climatic processes are encoded by discrete latent variables and spatiotemporal coherence maintained through edge potential functions. This model is used as the basis of our approach to three problems – detection of largescale anomaly events, daily rainfall simulation and understanding spatiotemporal dynamics of Indian Monsoon.
A slight deviation (anomaly) from normal conditions (climatology) can have severe impacts. In India, the most significant impacts are caused by excess/deficient rainfall and excess temperature. The most significant anomalies are those that extend over a large area and/or persist for a long time, which we call “anomaly events”. Detection and localizing such events in space and time is a challenge, and we try to address it using our proposed models. The model also allows us to estimate several statistical properties at local and regional scale, which are in turn used as inputs to stochastic models to simulate daily climatic conditions across India. We show that our simulations reflect spatiotemporal properties of the process much more accurately than simulations done by dynamical models used by climate scientists. We also identify homogeneous zones across the landmass, within which rainfall simulation may be carried out more accurately. Additionally, we use our framework to identify common spatial and temporal patterns of rainfall over India during monsoon season, which provide important insights into the dynamics of this highly complex phenomena, and creates some scope for rainfall prediction at local and regional scale.
Speaker Bio: Adway Mitra is currently a postdoctoral fellow in International Center for Theoretical Sciences (ICTSTIFR) in Bangalore. He received his Ph.D. from Indian Institute of Science in 2016, under the guidance of Prof. Chiranjib Bhattacharyya. Prior to that he received M.E. from IISc in 2010, and B.E. from Jadavpur University in 2008. His primary research interest is in modeling complex spatiotemporal processes, especially climate, using Statistics, Data Mining and Machine Learning.
Host Faculty: Prof. Chiranjib Bhattacharyya

