Events 

Seminars 

Prof. I. G. Sarma Memorial Lecture Series 

Prof. Priti Shankar Memorial Seminar Series 

Multimedia Archive 



UPCOMING SEMINARS 

Series: M.Sc. (Engg) Thesis Defense Title: On the gap between outcomes of voting rules  Speaker: Ms. Anurita Mathur
M.Sc. student
Dept. of CSA  Faculty Advisor: Dr. Arnab Bhattacharyya
 Date and Time: Friday, November 24, 2017, 2:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Through the course of history, a variety of voting rules have been used to
determine election outcomes. The traditional way in social choice theory to
evaluate a voting rule is by checking whether it satisfies axioms deemed to
be desirable for voting rules. Celebrated results in social choice theory
say that even for a small set of seemingly necessary axioms, no voting rule
exists satisfying them. In the face of such impossibility results, it
becomes challenging to justify why certain voting rules work well in
practice. Although in theory, these rules may yield drastically different
outcomes, for realworld datasets, behavioural social choice analyses have
found that the rules are often in perfect agreement with each other! This
work attempts to give a mathematical explanation of this phenomenon.
In this work, we formulate a quantitative approach towards comparing voting
rules by viewing them as two players engaged in a zerosum game. If rule A
selects candidate c_1 while rule B selects candidate c_2, the payoff for A
is the number of voters who prefer c_1 to c_2 minus the number who prefer
c_2 to c_1.The optimal voting rule according to this criterion
(corresponding to the optimal randomized strategy for the game) is the
"gametheoretic rule" (GT) while the best deterministic strategy is the
wellknown Minimax voting rule. We investigate rigorously how various
common voting rules fare against each other in terms of the minimum payoff
they receive for arbitrary voting profiles. We also study the case when the
voting profiles are drawn from a mixture of multinomial logit
distributions. This scenario corresponds to a population consisting of a
small number of groups, each voting according to a latent preference
ranking. We supplement the theoretical findings by empirically comparing
the payoff of voting rules when they are applied to user preferences for
movies as determined from the Netfix competition dataset. On this dataset,
we find that the Minimax rule, the Schulze rule, and a deterministic
variant of the GT rule perform the best in our framework.
 Series: Ph.D. Thesis Defense Title: Stochastic Recursive Inclusions: Theory and Applications  Speaker: Mr. Arunselvan R
Ph.D student
Dept. of C.S.A  Faculty Advisor: Prof. Shalabh Bhatnagar
 Date and Time: Friday, November 24, 2017, 11:30 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Stochastic approximation algorithms encompass a class of iterative schemes that converge to a sought value
through a series of successive approximations, even with erroneous observations. Such algorithms
naturally arise in reinforcement learning, game theory, optimization, financial mathematics and cyberphysical
systems. The first stochastic approximation algorithm was developed by Robbins and Monro in 1951 to solve
the rootfinding problem. In 1977 Ljung showed that the asymptotic behavior of a stochastic approximation
algorithm can be studied by associating a deterministic ODE, called the associated ODE, and studying it's
asymptotic behavior instead. In 1996 Benaim and Benaim and Hirsch used the dynamical systems approach
to develop a framework to analyze generalized stochastic approximation algorithms. One bottleneck
in deploying this framework was the requirement on stability (almost sure boundedness) of the iterates. In 1999
Borkar and Meyn developed a unified set of assumptions that guaranteed both stability and convergence of
stochastic approximations. However, the aforementioned frameworks did not account for scenarios with
setvalued mean fields. In 2005 Benaim, Hofbauer and Sorin showed that the dynamical systems approach to
stochastic approximations can be extended to scenarios with setvalued meanfields. Again, stability of the
iterates was assumed.
The main focus of this talk will be on stochastic approximation methods with setvalued dynamical systems
(stochastic recursive inclusions), with applications to reinforcement learning and optimization. In the first
part of this talk we will discuss an extension of the BorkarMeyn theorem to the scenario of stochastic
recursive inclusions. As an application of this framework we will discuss a solution
to the `approximate drift problem'. In the second part of this talk we will discuss the problem of gradient
methods with errors. We will discuss a framework for the stability and convergence of gradient methods,
even when the errors are `nondiminishing'. Our work extends the results of Bertsekas and Tsitsiklis, and
Mangasarian and Solodov. Using our framework, we present a fast and hasslefree implementation of
Simultaneous Perturbation Stochastic Approximation (SPSA), using constant sensitivity parameters. It is
worth noting that our implementation `decouples' the sensitivity parameters and stepsizes.
We will also present experimental results in support of our theory. In the third part of this talk, we will
discuss stochastic recursive inclusions with twotimescales. We use our framework to develop a two
timescale algorithm to solve the constrained Lagrangian dual optimization problem. Due to the generality of
our framework, the class of objective and constraint functions is enlarged, when
compared to previous literature. In the final part of this talk, we will discuss a framework for stability
and convergence of stochastic approximations with ‘controlled Markov processes’. Using this framework we
present a relaxation of the assumptions for the analysis of temporal difference learning algorithms (an
important policy evaluation scheme in reinforcement learning). It may be noted that our assumptions for
stability (of temporal difference learning) are compatible with hitherto present frameworks. Further it may be
noted that the conditions are weakened twofold: (a) the Markov process is no longer required to evolve in a
finite state space and (b) the state process is not required to be ergodic under a given stationary policy.
 Series: Department Seminar Title: Concentration Bounds for Stochastic Approximation with Applications to Reinforcement Learning  Speaker: Mr. Gugan Thoppe
 Date and Time: Thursday, November 23, 2017, 3:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Stochastic Approximation (SA) is useful when the aim is to find optimal points, or zeros of a function, given only its noisy estimates. In this talk, we will review our recent advances in techniques for SA analysis. This talk has four major parts. In the first part, we will see a motivating application of SA to network tomography. Also, we shall discuss the convergence of a novel stochastic Kaczmarz method. In the second part, we shall discuss a novel tool based on the Alekseev's formula to obtain the rate of convergence of a nonlinear SA to a specific solution, given that there are multiple locally stable solutions. In the third part, we shall extend the previous tool to the two timescale but linear SA setting. We shall also discuss how this tool applies to gradient Temporal Difference (TD) methods such as GTD(0), GTD2, and TDC used in reinforcement learning. For the analyses in the second and third parts to hold, the initial step size must be chosen sufficiently small, depending on unknown problemdependent parameters. This is often impractical. In the fourth part, we shall discuss a trick to obviate this in context of the one timescale, linear TD(0) method. We strongly believe that this trick is generalizable. We also provide here a novel expectation bound. We shall end with some future directions.
Speaker Bio: Gugan Thoppe did his Ph.D. in Systems Science under Prof. Vivek Borkar at TIFR, Mumbai, INDIA. His work won the TAASasken best thesis award for 2017. He is also a two time recipient of the IBM Ph.D. fellowship award (2013–14) and (201415). He recently finished a two year postdoc position with Prof. Robert Adler at the Technion, Haifa, ISRAEL. From December, he will starting another postdoc with Prof. Sayan Mukherjee at Duke University, North Carolina, USA. His research interests include stochastic approximation and its applications to learning algorithms, and stochastic algebraic topology.
Host Faculty: Prof. Shalabh Bhatnagar
 Series: Department Seminar Title: Accountability for Social Values in DataDriven Systems  Speaker: Prof. Anupam Datta
Carnegie Mellon University
USA  Date and Time: Wednesday, November 22, 2017, 11:00 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Our vision is to enable datadriven systems to be accountable for social values, such as privacy
and fairness. We use the term “accountable” to refer to computational mechanisms that can be
used to “account for” behaviors of systems to support detection of privacy and fairness
violations, as well as explain how they came about. We then leverage this understanding to
repair systems and carefully account for the absence of violations.
As an illustration of this paradigm, I will introduce a notion of proxy nondiscrimination and
methods for making machine learning models accountable for this property. A key building block
for these notions is Quantitative Input Influence  a form of explanation for decisions of machine
learning models. This work is motivated by recent discoveries of unfairness or bias in widely
used datadriven systems, including our own work that discovered gender bias in the targeting
of jobrelated ads in the Google advertising ecosystem.
The talk is based on results with colleagues at CMU published at the 2016 IEEE Symposium on
Security and Privacy and the 2017 ACM Conference on Computer and Communications Security.
Speaker Bio: Anupam Datta is an Associate Professor (with tenure) at Carnegie Mellon University where he holds a primary appointment in the Electrical and Computer Engineering Department and a courtesy appointment in the Computer Science Department. His research area is security and privacy, with an emphasis on bridging theory and practice.
Datta's current focus is on information accountability: foundations and tools that can be used to provide oversight of complex information processing ecosystems (including big data systems) to examine whether they respect privacy, and other desirable values in the personal data protection area, such as fairness and transparency. His research group produced the first complete logical specification and audit of all disclosurerelated clauses of the HIPAA Privacy Rule for healthcare privacy. His group's work with Microsoft Research produced the first automated privacy compliance analysis of the production code of an Internetscale system  the big data analytics pipeline for Bing, Microsoft's search engine.
Datta has also made significant contributions to the research area of compositional security. Specifically, his work led to new principles for securely composing cryptographic protocols and their application to several protocol standards, most notably to the IEEE 802.11i standard for wireless authentication and to attestation protocols for trusted computing. Datta has authored a book and over 50 other publications on these topics.
He serves as an EditorinChief of Foundations and Trends in Privacy and Security, an Associate Editor of the Journal of Computer Security and the Journal of Computer and System Sciences, as well as the 201314 Program CoChair of the IEEE Computer Security Foundations Symposium. Datta obtained Ph.D. (2005) and M.S. (2002) degrees from Stanford University and a B.Tech. (2000) from IIT Kharagpur, all in Computer Science.
Host Faculty: Prof. Vinod Ganapathy
 Series: M.Sc. (Engg) Colloquium Title: Checking Observational Purity of Procedures  Speaker: Himanshu Arora
 Faculty Advisor: K. V. Raghavan
 Date and Time: Monday, November 20, 2017, 4:00 PM
 Venue: CSA Conference Room (Room No. 225, First Floor)
Abstract We provide two static analysis (using theorem proving) that check if a given (recursive) pro
cedure behaves as if it were stateless, even when it maintains state in global variables. In
other words, we check if the given procedure behaves like a mathematical function. In order to
eliminate the need for manual annotations, we define a syntactic invariant that represents the reachable global states in all runs of the program. This syntactic invariant makes use of function
symbols, which aids in automated construction of the invariant. The two static analysis are
an existential checker and an impurity witness checker. The impurity witness checker outputs
a formula whose unsatisfiability implies that the
procedure is observationally pure. Whereas, the existential checker outputs a formula that constrains the definition of the function that the given procedure may implement. Satisfiability
of the formula generated by the existential checker implies that the given procedure is observationally pure. The impurity witness approach works better (empirically) with SMT solvers,
whereas the existential approach is more precise on paper. We illustrate our work on examples such as
matrix chain multiplication. Examples such as these are not addressable by related techniques in the literature.
The closest work to our is by Barnett et al.; this work cannot handle procedures
with self recursion. We prove both our approaches to be sound. We have implemented the
two static analyses using the Boogie framework and the Z3 SMT solver, and have evaluated our implementation on a number of examples.
 Series: M.Sc. (Engg) Thesis Defense Title: Feature Selectio n under Multicollinearity
&
Causal Inference on Ti me Series  Speaker: Mr. Indranil Bhattacharya
M.Sc. student
Dept. of CSA  Faculty Advisor: Dr. Arnab Bhattacharyya
 Date and Time: Monday, November 20, 2017, 2:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract In this work, we study and extend algorithms for Sparse Regression and Causal Inference problems. Both
the problems are fundamental in the area of Data Science.
The goal of regression problem is to find out the “best” relationship between an output variable and
input variables, given samples of the input and output values. We consider sparse regression under a
highdimensional linear model with strongly correlated variables, situations which cannot be handled well using
many existing model selection algorithms. We study the performance of the popular feature selection
algorithms such as LASSO, Elastic Net, BoLasso, Clustered Lasso as well as Projected Gradient Descent
algorithms under this setting in terms of their running time, stability and consistency in recovering the
true support. We also propose a new feature selection algorithm, BoPGD, which cluster the features
first based on their sample correlation and do subsequent sparse estimation using a bootstrapped variant
of the projected gradient descent method with projection on the nonconvex L 0 ball. We attempt to
characterize the efficiency and consistency of our algorithm by performing a host of experiments on both
synthetic and real world datasets.
Discovering causal relationships, beyond mere correlation, is widely recognized as a fundamental
problem. The Causal Inference problems use observations to infer the underlying causal structure of the
data generating process. The input to these problems is either a multivariate time series or i.i.d sequences
and the output is a Feature Causal Graph where the nodes correspond to the variables and edges capture
the direction of causality. For high dimensional datasets, determining the causal relationships becomes a
challenging task because of the curse of dimensionality. Graphical modeling of temporal data based on the
concept of “Granger Causality” has gained much attention in this context. The blend of Granger methods
along with model selection techniques, such as LASSO, enables efficient discovery of a “sparse” subset
of causal variables in high dimensional settings. However, these temporal causal methods use an input
parameter, L, the maximum time lag. This parameter is the maximum gap in time between the occurrence
of the output phenomenon and the causal input stimulus. However, in many situations of interest, the
maximum time lag is not known, and indeed, finding the range of causal effects is an important problem.
In this work, we propose and evaluate a datadriven and computationally efficient method for Granger
causality inference in the Vector Auto Regressive (VAR) model without foreknowledge of the maximum
time lag. We present two algorithms Lasso Granger++ and Group Lasso Granger++ which not only
constructs the hypothesis feature causal graph, but also simultaneously estimates a value of maxlag ( Lˆ )
for each variable by balancing the tradeoff between “goodness of fit” and “model complexity".
 Series: M.Sc. (Engg) Thesis Defense Title: Large Scale Graph Processing in a Distributed Environment  Speaker: Mr.Nitesh Chandra Upadhyay
M.Sc. (Engg) Student
Dept of CSA
IISc  Faculty Advisor: Prof. Y.N. Srikant
 Date and Time: Monday, November 20, 2017, 12:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Graph algorithms are ubiquitously used across domains. They exhibit parallelism,
which can be exploited on parallel architectures, such as, multicore processors
and accelerators. However, real world graphs are massive in size and cannot fit
into the memory of a single machine. Such large graphs are partitioned and
processed in a distributed cluster environment which consist of multiple GPUs
and CPUs.
Existing frameworks that facilitate large scale graph processing in the distributed
cluster have their own style of programming and require extensive involvement by
the user in communication and synchronization aspects. Adaptation of these
frameworks appears to be an overhead for a programmer. Furthermore, these frameworks
have been developed to target only CPU clusters and lack the ability to harness the
GPU architecture.
We provide a backend framework to the graph Domain Specific Language, Falcon,
for large scale graph processing on CPU and GPU clusters. The Motivation behind
choosing this DSL as a frontend is its sharedmemory based imperative programmability
feature. Our framework generates Giraph code for CPU clusters. Giraph code runs
on the Hadoop cluster and is known for scalable and faulttolerant graph processing.
For GPU cluster, Our framework applies a set of optimizations to reduce computation
and communication latency, and generates efficient CUDA code coupled with MPI.
Experimental evaluations show the scalability and performance of our framework for
both CPU and GPU clusters. The performance of the framework generated code is
comparable to the manual implementations of various algorithms in distributed
environments


PAST SEMINARS 

Series: Department Seminar Title: Actively Secure Garbled Circuits with Constant Communication Overhead in the Plain Model  Speaker: Dr. Carmit Hazay
Senior Lecturer
Computer Engineering Department
BarIlan University
Israel  Date and Time: Wednesday, November 15, 2017, 11:00 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract We consider the problem of constantround secure twoparty computation in the presence of active
(malicious) adversaries. We present the first protocol that has only a constant
multiplicative communication overhead compared to Yao's protocol for passive adversaries and can be
implemented in the plain model by only making a blackbox use of (parallel) oblivious transfer and a pseudo
random generator. This improves over the polylogarithmic overhead of the previous best protocol. A
similar result could previously be obtained only in an amortized setting, using preprocessing, or by
assuming bitoblivioustransfer as an ideal primitive that has a constant cost.
We present two variants of this result, one which is aimed at minimizing the number of oblivious
transfers and another which is aimed at optimizing concrete efficiency. Our protocols are based on a
novel combination of previous techniques together with a new efficient protocol to certify that pairs
of strings transmitted via oblivious transfer satisfy a global relation. The communication complexity
of the second variant of our protocol can beat the best previous protocols even for realistic values of
the circuit size and the security parameter. This variant is particularly attractive in the offlineonline
setting, where the online cost is dominated by a single evaluation of an authenticated garbled circuit,
and can also be made noninteractive using the FiatShamir heuristic.
This is a joint work with Yuval Ishai and Muthuramakrishnan Venkitasubramaniam.
Speaker Bio: Carmit Hazay is a Senior Lecturer in the Computer Engineering Department, BarIlan University, Israel. In 2009 she completed her Ph.D. studies at BarIlan University and started her postdoctoral training at Weizmann Institute of Science and IDC (20092010) and at Aarhus University, Denmark (20102012). She joined the Faculty of Engineering at BarIlan University in October 2012.
Host Faculty: Dr. Arpita Patra
 Series: Ph.D. Colloquium Title: Developing Software Tools using Dynamic Program Analysis  Speaker: Ms.Monika Dhok
Ph.D student
Dept. of CSA
IISc  Faculty Advisor: Prof. K Gopinath
 Date and Time: Tuesday, November 14, 2017, 4:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Software development process consists of many stages like design, implementation, and testing. Programmers'
intuition and expertise play a vital role in the success of these stages. Therefore, various tools have been
developed that assist programmers by automating their tasks. Program analysis, the process of analyzing
program behavior by examining its source code or execution, forms the basis of such software tools. We identify
and address following three research gaps in the area of program analysis.
Typeawareness in concolic testing
Software testing is a widely used dynamic program analysis technique. Various automated test generation
techniques have been proposed as manually writing effective test suite is challenging. Concolic testing is
one such technique that outputs a test suite for the given program with the intent of maximizing code coverage.
This technique is very effective for statically typed languages. We show that applying concolic testing to
dynamically typed JS programs causes generation of a large number of test cases that explore paths and types
of the variables repeatedly. We propose an effective approach that scales concolic testing by incorporating
typeawareness. Our experimental results show that adapting typeaware concolic testing is as effective as
conventional concolic testing in detecting bugs and achieving coverage, even with a small percentage of test cases.
Test synthesis to detect redundant traversal bugs
Test generation techniques like concolic testing focus on verifying the functional correctness of the program.
Performance testing, on the other hand, verifies the software efficiency. Our second work focuses on automated
performance testing in the context of redundant traversal bugs. Such bugs occur when program fragment performs
repetitive computations across loop iterations. Various static and dynamic analysis techniques have been proposed
to detect such bugs automatically. However, while the effectiveness of dynamic analyses is dependent on input test
cases, static analyses are less useful in validating the presence of this problem. We propose an approach to generate
tests for exposing redundant traversal of loops automatically. Our experiments reveal the effectiveness of our
approach in generating 224 tests that reveal 46 bugs across seven Java libraries, including 34 previously unknown bugs.
Performance hints for stable multithreaded systems
Assuring correctness and efficiency of sequential programs is easier as compared to multithreaded programs. This
is mainly because the execution of multithreaded programs depends not only on the input but also on thread
interleavings. Stable multithreaded systems restrict the set of possible schedules such that schedule remains
unaffected for the given input. This eases the process of bug reproduction and thereby guaranteeing correctness.
However, the determinism imposed in these systems can serialize the schedule resulting into performance degradation.
Our third work focuses on automatically deriving performance hints so that such serialization can be avoided. Our
experimental results demonstrate that we are able to reduce the overall execution time of programs by up to 34%
when compared to the execution time where performance hints are inserted manually.
 Series: Department Seminar Title: Approximation Algorithms for Stochastic kTSP  Speaker: Dr. Rishi Saket
Researcher
IMB Research
Bangalore  Date and Time: Friday, October 27, 2017, 5:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract This paper studies the Stochastic kTSP problem: the stochastic variant of the
classical kTSP problem where rewards at the vertices are independent random
variables which are instantiated upon the tour's visit. The objective is to
minimize the expected length of a tour that collects reward at least k. The
solution is a policy describing the tour which may (adaptive) or may not
(nonadaptive) depend on the observed rewards. Our work presents an adaptive
O(log k)approximation algorithm for Stochastic kTSP, along with a nonadaptive
O(log^2 k)approximation algorithm which also upper bounds the adaptivity gap by
O(log^2 k). We also show that the adaptivity gap of Stochastic kTSP is at
least e, even in the special case of stochastic knapsack cover.
The talk shall give an overview of the main results and focus mostly on
describing the adaptive algorithm.
Joint work with Alina Ene (Boston University) and Viswanath Nagarajan
(University of Michigan)
Host Faculty: Dr. Anand Louis
 Series: M.Sc. (Engg) Thesis Defense Title: Generalizations of Hitting, Covering and Packing Problems on Intervals  Speaker: Mr. Datta Krupa R
M.Sc. Student
Dept. of CSA  Faculty Advisor: Prof. Sathish Govindarajan
 Date and Time: Friday, October 27, 2017, 10:00 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Interval graphs are wellstudied structures. Intervals can represent
resources like jobs to be scheduled. Finding maximum independent set in
interval graphs would correspond to scheduling maximum number of
nonconflicting jobs on the computer. Most optimization problems on
interval graphs like the independent set, vertex cover, dominating set,
maximum clique, etc can be solved efficiently using combinatorial algorithms
in polynomial time. Hitting, Covering and Packing problems have been
extensively studied in the last few decades and have applications in
diverse areas. While they are NPhard for most settings, they are
polynomial solvable for intervals. In this thesis, we consider the
generalizations of hitting, covering and packing problems for intervals.
For the general setting, we model the problems as mincost flow problems
using nontrivial reduction and solve it using standard flow algorithms.
Demandhitting problem which is a generalization of hitting problem is
defined as follows: Given n intervals, a positive integer demand for every
interval, m points, a real weight for every point, select a subset of
points H, such that every interval contains at least its demand many points
from H and sum of the weight of points in H minimized. When demands of
intervals are one we give dynamic programming based O(m+n) time algorithm
assuming that intervals and points are sorted. When demands are same, (say
k), we give O(m^2*n) time flowbased algorithm. For the general case, we
make an assumption that no interval is contained in another interval.
Under this assumption, we give O(m^2*n) time flowbased algorithm.
Demandcovering problem which is a generalization of covering problem is
defined as follows: Given n intervals, a real weight for every interval, m
points, a positive integer demand for every point, select a subset of
intervals C, such that every point is contained in at least its demand many
intervals from C and sum of the weight of intervals in C minimized. When
demand of points are one, we give dynamic programming based O(m+n log n)
time algorithm. When demands are same, (say k) we give O(m*n^2) time flow
based algorithm. For the general case, we give O(m*n^2) time flow based
algorithm.
kpack points problem which is a generalization of packing problem is
defined as follows: Given n intervals, an integer k, m points, a real
weight for every point, select a subset of points Y, such that every
interval contains at most k points from Y and sum of the weight of points
in Y is maximized. For kpack points problem, we give O(m^2 log m) time flow
based algorithm to solve it assuming intervals and points are sorted.
 Series: CSA Distinguished Lecture Title: Beating Floating Point at its Own Game: Posit Arithmetic  Speaker: Prof. John L. Gustafson
National University of Singapore  Date and Time: Thursday, October 26, 2017, 4:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract A new data type called "posit" is designed as a direct dropin
replacement for IEEE Standard 754 floatingpoint numbers (floats).
Unlike earlier forms of universal number (unum) arithmetic, posits do
not require interval arithmetic or variable size operands; like
floats, they round if an answer is inexact. However, they provide
compelling advantages over floats, including larger dynamic range,
higher accuracy, better closure, bitwise identical results across
systems, simpler hardware, and simpler exception handling. Posits
never overflow to infinity or underflow to zero, and NotaNumber
(NaN) indicates an action instead of a bit pattern. A posit
processing unit takes less circuitry than an IEEE float FPU. With
lower power use and smaller silicon footprint, the posit operations
per second (POPS) supported by a chip can be significantly higher
than the FLOPS using similar hardware resources. GPU accelerators and
Deep Learning processors, in particular, can do more per watt and per
dollar with posits, yet deliver superior answer quality.
A comprehensive series of benchmarks compares floats and posits for
decimals of accuracy produced for a set precision. Low precision
posits provide a better solution than approximate computing methods
that try to tolerate decreased answer quality. High precision posits
provide more correct decimals than floats of the same size; in some
cases, a 32bit posit may safely replace a 64bit float. In other
words, posits beat floats at their own game.
Speaker Bio: Dr. John L. Gustafson is an applied physicist and mathematician who
is a Visiting Scientist at ASTAR and Professor at NUS. He is a former
Director at Intel Labs and former Chief Product Architect at AMD. A
pioneer in highperformance computing, he introduced cluster
computing in 1985 and first demonstrated scalable massively parallel
performance on real applications in 1988. This became known as
Gustafson's Law, for which he won the inaugural ACM Gordon Bell
Prize. He is also a recipient of the IEEE Computer Society's Golden Core
Award.
Host Faculty: Prof. R. Govindarajan
 Series: Mathematical Foundations of Data Science Title: Lectures on Mathematical Foundations of Data Science  Speaker: Prof. Ravi Kannan
 Date and Time: Monday, October 23, 2017, 3:30 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract This is a series of 12 tutorial lectures spread over 4 weeks
on Mathematical Foundations of Data Science. The lectures will primarily focus on
1) High Dimensional geometry
2) Best fit subspaces and SVD
Who should attend: PhD students, 2nd year MTech students
Lecture Days: Monday WednesdayFriday
Time: 3:304:30
Venue: 254 CSA Dept
Start Date: 23rd Oct.
The material will be based on a textbook currently being coauthored by Ravi Kannan, Avrim Blum and John Hopfcroft, copies will be made available.
Speaker Bio: Ravindran Kannan is a Principal Researcher at Microsoft Research India, where he leads the algorithms research group. He is also the first adjunct faculty of Computer Science and Automation Department of Indian Institute of Science.
https://en.wikipedia.org/wiki/Ravindran_Kannan
Host Faculty: Chiranjib Bhattacharyya
 Series: Department Seminar Title: Evidence of nonGaussianity in the Cosmic Microwave Background & Visualizing Cosmic Structures  Speaker: Dr. Pratyush Pranav
Technion, Israel  Date and Time: Monday, October 09, 2017, 11:30 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract The standard cosmological paradigm asserts that the Universe underwent a phase of rapid inflation
moments after it's birth. In the simplest form, inflationary theories predict the spectrum of
the fluctuation of matter distribution to be Gaussian distributed. Consequently, deviations from Gaussianity, if found,
will point to novel physics driving the early phase of the Universe. In this talk, I will present an
evidence of nonGaussianity in the CMB, through new topological methods.
In a related aspect, as the universe evolves, the initial small perturbations in the matter distribution in the
Universe give rise to the structures like galaxies and groups of galaxies, woven into a three dimensional web
like network. Understanding the properties of this Cosmic Web is crucial to understanding the nature of the
matter distribution. Visualizing these cosmic structures plays a crucial role in this effort. In an ongoing
collaboration with Prof. Natarajan's visualization lab, we have developed visualization software based on
topological methods. I will briefly describe the methodology and some results, with a view to develop this further.
Speaker Bio: PP obtained his B.Sc. at St. Stephens college Delhi University, and the M.S. degree at IISc. There after he moved to the Kapteyn Astronomical Institute, Groningen , the Netherlands, to obtain a PhD. Currently he is in a transition, finishing his postdoctoral at Technion, Israel and starting the second one at Ecole Normale Superiure in Lyon, France.
Host Faculty: Prof. Vijay Natarajan
 Series: Ph.D. Thesis Defense Title: Optimization Algorithms for Deterministic, Stochastic and Reinforcement Learning Settings  Speaker: Mr. Ajin George Joseph
 Faculty Advisor: Prof. Shalabh Bhatnagar
 Date and Time: Thursday, October 05, 2017, 2:30 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Optimization is a very important field with diverse applications in physical, social and biological sciences and in various areas of engineering. It appears widely in machine learning, information retrieval, regression, estimation, operations research and a wide variety of computing domains. The subject is being deeply studied both theoretically and experimentally and several algorithms are available in the literature. These algorithms which can be executed (sequentially or concurrently) on a computing machine explore the space of input parameters to seek high quality solutions to the optimization problem with the search mostly guided by certain structural properties of the objective function. In certain situations, the setting might additionally demand for ``absolute optimum'' or solutions close to it, which makes the task even more challenging.
In this thesis, we propose an optimization algorithm which is ``gradientfree'', i.e., does not employ any knowledge of the gradient or higher order derivatives of the objective function, rather utilizes objective function values themselves to steer the search. The proposed algorithm is particularly effective in a blackbox setting, where a closedform expression of the objective function is unavailable and gradient or higherorder derivatives are hard to compute or estimate. Our algorithm is inspired by the well known cross entropy (CE) method. The CE method is a model based search method to solve continuous/discrete multiextremal optimization problems, where the objective function has minimal structure. The proposed method seeks, in the statistical manifold of the parameters which identify the probability distribution/model defined over the input space to find the degenerate distribution concentrated on the global optima (assumed to be finite in quantity). In the early part of the thesis, we propose a novel stochastic approximation version of the CE method to the unconstrained optimization problem, where the objective function is realvalued and deterministic. The basis of the algorithm is a stochastic process of model parameters which is probabilistically dependent on the past history, where we reuse all the previous samples obtained in the process till the current instant based on discounted averaging. This approach can save the overall computational and storage cost. Our algorithm is incremental in nature and possesses attractive features such as stability, computational and storage efficiency and better accuracy. We further investigate, both theoretically and empirically, the asymptotic behaviour of the algorithm and find that the proposed algorithm exhibits global optimum convergence for a particular class of objective functions.
Further, we extend the algorithm to solve the simulation/stochastic optimization problem. In stochastic optimization, the objective function possesses a stochastic characteristic, where the underlying probability distribution in most cases is hard to comprehend and quantify. This begets a more challenging optimization problem, where the ostentatious nature is primarily due to the hardness in computing the objective function values for various input parameters with absolute certainty. In this case, one can only hope to obtain noise corrupted objective function values for various input parameters. Settings of this kind can be found in scenarios where the objective function is evaluated using a continuously evolving dynamical system or through a simulation. We propose a multitimescale stochastic approximation algorithm, where we integrate an additional timescale to accommodate the noisy measurements and decimate the effects of the gratuitous noise asymptotically. We found that if the objective function and the noise involved in the measurements are well behaved and the timescales are compatible, then our algorithm can generate high quality solutions.
In the later part of the thesis, we propose algorithms for reinforcement learning/Markov decision processes using the optimization techniques we developed in the early stage. MDP can be considered as a generalized framework for modeling planning under uncertainty. We provide a novel algorithm for the problem of prediction in reinforcement learning, emph{i.e.}, estimating the value function of a given stationary policy of a model free MDP (with large state and action spaces) using the linear function approximation architecture. Here, the value function is defined as the longrun average of the discounted transition costs. The resource requirement of the proposed method in terms of computational and storage cost scales quadratically in the size of the feature set. The algorithm is an adaptation of the multitimescale variant of the CE method proposed in the earlier part of the thesis for simulation optimization. We also provide both theoretical and empirical evidence to corroborate the credibility and effectiveness of the approach.
In the final part of the thesis, we consider a modified version of the control problem in a model free MDP with large state and action spaces. The control problem most commonly addressed in the literature is to find an optimal policy which maximizes the value function, i.e., the longrun average of the discounted transition payoffs. The contemporary methods also presume access to a generative model/simulator of the MDP with the hidden premise that observations of the system behaviour in the form of sample trajectories can be obtained with ease from the model. In this thesis, we consider a modified version, where the cost function to be optimized is a realvalued performance function (possibly nonconvex) of the value function. Additionally, one has to seek the optimal policy without presuming access to the generative model. In this thesis, we propose a stochastic approximation algorithm for this peculiar control problem. The only information, we presuppose, available to the algorithm is the sample trajectory generated using a priori chosen behaviour policy. The algorithm is data (sample trajectory) efficient, stable, robust as well as computationally and storage efficient. We provide a proof of convergence of our algorithm to a high performing policy relative to the behaviour policy.
 Series: Department Seminar Title: Reachability for dynamic parametric processes  Speaker: Prof. Helmut Seidl,
Technical University of Munich  Date and Time: Wednesday, September 27, 2017, 3:30 PM
 Venue: CSA Lecture Hall (Room No. 117, Ground Floor)
Abstract In a dynamic parametric process every subprocess may spawn
arbitrarily many, identical child processes, that may communicate either over
global variables, or over local variables that are shared with their parent.
We show that reachability for dynamic parametric processes is
decidable under mild assumptions. These assumptions are met if
individual processes are realized by pushdown systems, or even
higherorder pushdown systems. We also provide algorithms for
subclasses of pushdown dynamic parametric processes, with complexity
ranging between NP and DEXPTIME.
These results are based on joint work with Anca Muscholl and Igor
Walukiewicz.
Speaker Bio: Helmut Seidl is a Professor at the Institute for
Informatics, at the Technical University of Munich, Germany. His
research interests include Program Analysis, SemiStructured Data, and
Tree Automata.
Host Faculty: Prof. Deepak D Souza
 Series: Ph.D. Colloquium Title: Deep Learning with Minimal Supervision  Speaker: Mr. Gaurav Pandey
Ph.D student
Dept. of CSA  Faculty Advisor: Prof. Ambedkar Dukkipati
 Date and Time: Tuesday, September 26, 2017, 12:00 PM
 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 some deep neural network 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
task, whereas realvalued feature vectors are fed as input to simple classifiers for auxiliary
supervised discrimination tasks. 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: Department Seminar Title: SOPER : Discovering the Influence of Fashion and the Many Faces of User from
Session Logs using Stick Breaking Process  Speaker: Ms. Lucky Dhakad
Flipkart  Date and Time: Monday, September 25, 2017, 2:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Recommending lifestyle articles is of immediate interest to the ecommerce industry
and is beginning to attract research attention. Often followed strategies, such as
recommending popular items are inadequate for this vertical because of two reasons.
Firstly, users have their own personal preference over items, referred to as personal
styles, which lead to the longtail phenomenon. Secondly, each user displays multiple
personas, each persona has a preference over items which could be dictated by a
particular occasion, e.g. dressing for a party would be different from dressing to
go to office. Recommendation in this vertical is crucially dependent on discovering
styles for each of the multiple personas. There is no literature which addresses this problem.
We posit a generative model which describes each user by a Simplex Over PERsona, SOPER,
where a persona is described as the individuals preferences over prevailing styles
modeled as topics over items. The choice of simplex and the longtail nature
necessitates the use of stickbreaking process. The main technical contribution is an
efficient collapsed Gibbs sampling based algorithm for solving the attendant inference problem.
Trained on largescale interaction logs spanning more than halfamillion sessions collected
from an ecommerce portal, SOPER outperforms previous baselines by a large margin of 35%
in identifying persona. Consequently it outperforms several competitive baselines
comprehensively on the task of recommending from a catalogue of roughly 150 thousand
lifestyle articles, by improving the recommendation quality as measured by AUC by a
staggering 12.23%, in addition to aiding the interpretability of uncovered personal and
fashionable styles thus advancing our precise understanding of the underlying phenomena.
Speaker Bio: Lucky Dhakad completed her ME from CSA, IISc in 2016 and is presently working with Flipkart.
*This is a practice talk for CIKM 2017*
Host Faculty: Prof. Chiranjib Bhattacharyya
 Series: M.Sc. (Engg) Thesis Defense Title: A Study of Thompson Sampling Approach for Sleeping
MultiArmed Bandit Problems  Speaker: Mr. Aritra Chatterjee
M.Sc. (Engg) Student
Dept of CSA
IISc  Faculty Advisor: Prof. Y. Narahari
 Date and Time: Monday, September 25, 2017, 11:30 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract The Multiarmed bandit (MAB) problem provides a
convenient abstraction for many online learning problems
arising in modern applications including Internet advertising,
crowdsourcing, online procurement, smart grids, etc. Several
variants of the MAB problem have been proposed to extend
the basic model to a variety of practical and general settings.
The sleeping multiarmed (SMAB) problem is one such
variant where the subset of available arms varies with time.
This study is focused on analyzing the efficacy of the
Thompson Sampling algorithm for solving the SMAB problem.
Any algorithm for the classical MAB problem is expected to
choose one of K available arms (actions) in each of T
consecutive rounds. Each choice of an arm generates a
stochastic reward from an unknown but fixed distribution.
The goal of the algorithm is to maximize the expected sum of
rewards over the T rounds (or equivalently minimize the
expected total regret), relative to the bestfixed action in
hindsight. In many of these settings, however, not all arms
may be available in any given round. For example, in Internet
advertising, some advertisers might choose to stay away from
the auction due to budget constraints; in crowdsourcing,
some workers may not be available at a given time due to
timezone difference, etc. This implies that the algorithm
needs to work only with the set of available arms. Further,
unlike in the classical setting, the performance of an algorithm
can no longer be evaluated relative to the bestfixed arm in
hindsight; the regret is now to be measured relative to the
best "available" arm in hindsight. One possible way is to
compute the overall regret as the worstcase regret over all
possible sample paths of availabilities (that is, under
adversarial selection of available arms).
In the literature, upper confidence bound (UCB)based
approaches have been proposed and investigated for the
SMAB problem. Our contribution is to investigate a
Thompson samplingbased approach. Our key finding is to
establish a logarithmic regret bound, which nontrivially
generalizes a similar bound known for this approach in the
classical MAB setting. Our bound also matches (up to
constants) the bestknown lower bound for the SMAB
problem. And, we show via detailed simulations, that the
Thompson Sampling approach, in fact, outperforms the
known algorithms for the SMAB problem.
 Series: Department Seminar Title: Maliciously Secure Oblivious Linear Function Evaluation with Constant Overhead  Speaker: Mr. Satrajit Ghosh
PhD Student
Cryptography and Security Group
Aarhus University
Denmark  Date and Time: Thursday, September 21, 2017, 3:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract In this work we consider the problem of oblivious linear function evaluation (OLE). OLE is a
special case of oblivious polynomial evaluation (OPE) and deals with the oblivious evaluation
of a linear function $f(x)=ax+b$. This problem is nontrivial in the sense that the sender
chooses $a,b$ and the receiver $x$, but the receiver may only learn $f(x)$. We present a highly
efficient and UCsecure construction of OLE in the OThybrid model that requires only $O(1)$ OTs
per OLE. The construction is based on noisy encodings introduced by Naor and Pinkas (STOC'99) and
used for passive secure OLE's by Ishai, Prabhakaran and Sahai (TCC'09). A result asymptotically
similar to ours is known by applying the IPS compiler to the mentioned passive secure OLE protocol,
but our protocol provides better constants and would be considerably simpler to implement. Concretely
we use only $16$ OTs to generate one active secure OLE, and our protocol achieves active security
by adding fairly simple checks to the passive secure protocol. We therefore believe our protocol
takes an important step towards basing practical activesecure arithmetic computations on OLEs.
Our result requires novel techniques that might be of independent interest. As an application we
present the currently most efficient OPE construction.
Speaker Bio: Satrajit Ghosh is doing his PhD at Cryptography and Security Group, Aarhus University, Denmark
under supervision of Jesper Buus Nielsen and Claudio Orlandi. He did his Masters from the Computer Science and Engineering Department, IIT Kharagpur under the guidance of
Dr. Abhijit Das. Prior to that, he did his B.Tech in Computer Science and Engineering and B.Sc (Honors)
in Physics from University of Calcutta.
Before joining Aarhus University, he also worked as researcher at the R. C. Bose Centre of
Cryptology and Security, Indian Statistical Institute, Kolkata and in Saarland University, Germany.
Host Faculty: Dr. Arpita Patra

