Events 

Seminars 

Prof. I. G. Sarma Memorial Lecture Series 

Prof. Priti Shankar Memorial Seminar Series 

Multimedia Archive 



UPCOMING SEMINARS 

Series: Department Seminar Title: Inferring Insertion Times in Bloom Filters  Speaker: Prof. C V Ravishankar, UC Riverside
 Date and Time: Tuesday, August 21, 2018, 11:30 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Bloom filters are extremely useful in dealing with streaming data, but are easy to misuse.
We first illustrate pitfalls in using Bloom Filters, and show how to generalize our techniques
to infer insertion times. We introduce inferential filters, which integrate priors and information
latent in filters to make optimal queryspecific decisions.
We illustrate our approach on TimeDecaying Bloom Filters, which are probabilistic structures to
test membership on recently inserted items. As new items are inserted, memory of older items decays.
Incorrect query responses, however, will penalize the application using the filter. Current filters
may only be tuned to static penalties, and ignore much information latent in the filter. While our
methods are general, we focus here on inferential timedecaying filters, and show how to support
novel query types and sliding window queries with varying error penalties.
We have developed inferential versions of the existing Timing Bloom Filter and Generalized Bloom Filter.
Our experiments on real and synthetic datasets show that when penalties are dynamic and prior
probabilities are known, these filters reduce penalties for incorrect responses to slidingwindow
queries by up to 70%.
Speaker Bio: Chinya V Ravishankar is Professor of Computer Science at the Marlan and Rosemary Bourns College of Engineering at UC Riverside. Ravishankar’s current research and teaching focus is in the fields of Data Management as well as Computer Security. In the past, he has worked and taught in a wide range of areas, including Distributed Systems, Networking, and Programming Languages.
Prof. Ravishankar has served as Associate Dean for at the Marlan and Rosemary Bourns College of Engineering for the past 14 years. His current portfolio covers Research and Graduate Education. His earlier previous portfolio covered Undergraduate Education.
Before moving to UCR in 1999, Prof. Ravishankar was on the faculty of the EECS Department at the University of Michigan, Ann Arbor, between 1986—1999. He holds a PhD in Computer Sciences from the University of Wisconsin—Madison, and a bachelor’s degree in Chemical Engineering from the Indian Institute of Technology (IIT) Bombay.
Host Faculty: Prof. Jayant Haritsa


PAST SEMINARS 

Series: Ph.D. Thesis Defense Title: Typestates and Beyond: Verifying Rich Behavioral Properties Over Complex Programs  Speaker: Ashish Mishra
Ph.D Student, CSA Department  Faculty Advisor: Y.N. Srikant
 Date and Time: Friday, August 17, 2018, 10:00 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Statically verifying behavioral/dynamic properties of programs is an important
and challenging research problem. Typestates are the most prevalently used, static,
light‐weight verification systems for verifying program properties. In our work
we present both theoretical and practical contributions towards static analysis
and verification of Typestate defined properties. We dicuss two major challenges
in statically verifying typestate properties over programs.
The first challenge may be attributed to the ``complexity of programs'' being
analyzed. The state‐of‐the‐art static typestate analysis works cannot handle
formidably rich programming features like asynchrony, library calls and callbacks,
concurrency, etc. The second challenge may be attributed to ``complexity of the
property'' being verified. Classical typestates can only verify a property defined
through a finite state machine, and are inadequate to verify richer non‐regular
program properties. Currently, these rich behavioral properties are mostly
verified/enforced at runtime via explicit checks either by the programmer or the
compiler. Unfortunately, these runtime checks are costly, error‐prone, and lay an
extra burden on the programmer.
In this thesis we take small steps towards tackling both these challenges.
Addressing complex program features, we present an asynchrony‐aware static analysis
framework, taking Android applications as our use case. We use this framework to
develop a static typestate analysis to capture Android resource API usage protocol
violations. We present a set of benchmark applications for different resource types,
and empirically compare our typestate analysis with the state‐of‐the‐art synchronous
static analyses for Android applications.
Addressing the challenges associated with increasing complexity of properties, we
present an expressive notion of typestates called, Presburger definable typestates
or p‐typestates. p‐typestates associate an extra Pressburger definable property
along with the states of regular typestates. This allows p‐typestates to express many
useful non‐regular properties. We present a dependent type system for p‐typestates
and present a simple typestate‐oriented language incorporating p‐typestates called
Decidable Rich Interface Programming (DRIP) language. Further, typechecking such
rich p‐typestate properties requires a programmer to provide invariants for loops
and recursive structures. Unfortunately, providing these invariants is a non‐trivial
task even for expert programmers. To solve this problem, we present a simple and
novel loop invariant calculation approach for Pressburger definable systems. We
encode a number of real world programs in our dependently‐typed language to verify
several rich and non‐regular properties.
Finally we discuss several possible extensions of our thesis along both these directions.
Speaker Bio: Mr.Ashish Mishra is a Ph.D student in the CSA department. After submitting his thesis, he has been working as a postdoctoral research at North Eastern University, USA. His areas of interest are programming language theory, program analysis and verification, and semantics of programming languages.
Host Faculty: Y N Srikant
 Series: Department Seminar Title: On Complexity of Closest Pair Problem  Speaker: Mr. Karthik C.S.
Ph.D Student
Weizmann Institute of Science
Israel  Date and Time: Monday, August 13, 2018, 10:00 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Closest Pair is a fundamental problem in Computational Geometry, where we are given a set of n points in R^d and we would like to find the closest pair of points in the set. In this talk we will see that assuming the Strong Exponential Time Hypothesis for SAT, Closest Pair cannot be solved in subquadratic (in n) time when d=omega(log n) for all L_p metrics.
Based on two joint works  first one with Roee David and Bundit Laekhanukit and second one with Pasin Manurangsi.
Host Faculty: Dr. Arnab Bhattacharyya
 Series: CSA Faculty Colloquium Title: How to securely snapshot memory  Speaker: Prof. Vinod Ganapathy
Associate Professor
Dept. of CSA
IISc  Date and Time: Friday, August 10, 2018, 4:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Computer systems security has historically been a game of cat and mouse between attackers and defenders. Attackers develop novel techniques to bypass proposed defenses, while defenders must think ahead and foresee novel attacks. In this setting, how can the defender get the upper hand? This talk will make the case for security from the hardware up. We will consider the problem of securely obtaining snapshots of a computer system's memory. Snapshots play a key role in computer forensics, and it is therefore key to ensure that a machine can be snapshot free from an adversary's tampering. We will describe how adversaries have subverted these techniques in the past, and how stateoftheart approaches to obtaining snapshots fail. We will then propose a hardwarebased mechanism to obtain snapshots and show that it offers attractive benefits.
Speaker Bio: Vinod Ganapathy is an associate professor in the CSA department working on computer systems security.
Host Faculty: Prof. Sunil L Chandran & Prof. Shalabh Bhatnagar
 Series: Department Seminar Title: Interactive Visual Analysis of Large Urban Data using Urbane  Speaker: Dr. Harish Doraiswamy
Research Scientist
New York University  Date and Time: Thursday, August 02, 2018, 11:00 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract The recent explosion in the number and size of spatiotemporal data sets from urban environments and social sensors creates new opportunities for datadriven approaches to understand and improve cities. Visualization and visual analytics systems have been successfully used at enabling users to obtain insight: welldesigned visualizations substitute perception for cognition, freeing up limited cognitive/memory resources for higherlevel problems. Supporting the interactive response times these systems require is challenging as they often rely on computationally expensive spatial and spatiotemporal queries involving polygonal constraints of arbitrary shapes and sizes. This problem is further compounded as data set sizes increase.
In this talk I will first give an overview of Urbane, a multiresolution visual analytics framework that enables a datadriven analysis of cities. I will then present techniques that use GPUs to obtain real time performance for spatial aggregation queries and are at least two orders of magnitude faster than existing database systems.
Speaker Bio: Harish Doraiswamy is a Research Scientist at the NYU Center for Data Science and a Research Assistant Professor of Computer Science and Engineering at New York University. He received his Ph.D. in Computer Science and Engineering from the Department of Computer Science and Automation at Indian Institute of Science, Bangalore. His research lies in the intersection of computational topology, big data visualization, and databases. His recent research focuses on the visual analyses of large spatiotemporal datasets from urban environments.
Host Faculty: Prof. Vijay Natarajan
 Series: Research Student Colloquium Title: Data Races and Static Analysis for InterruptDriven Kernels  Speaker: Ms.Nikita Chopra
M.Sc.(Engg.) student
Dept. of CSA  Date and Time: Friday, July 27, 2018, 4:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Embedded software is widespread and increasingly employed in safetycritical applications in
medical, automobile, and aerospace domains.
In this work, we consider a class of interruptdriven programs that model the kernel API libraries of some popular realtime embedded operating systems and the synchronization mechanisms they use. We define a natural notion of data races and a happensbefore ordering for such programs. The key insight is the notion of disjoint blocks to define the synchronizeswith relation. This notion also suggests an efficient and effective lockset based analysis for race detection. It also enables us to define efficient "syncCFG" based static analyses for such programs, which exploit datarace freedom. We use this theory to carry out static analysis on the FreeRTOS kernel library to detect races and to infer simple relational invariants on key kernel variables and datastructures.
Speaker Bio: Nikita Chopra is an M.Sc.(Engg.) student in the CSA department. She is working in Programming Languages Lab under the supervision of Prof. Deepak D'Souza. Her broad research interests lie in the area of static program analysis.
Host Faculty: Prof. Sunil L Chandran & Prof. Shalabh Bhatnagar
 Series: Department Seminar Title: Foundations for Natural Proofs and Quantifier Instantiation  Speaker: Madhusudan Parthasarathy
 Date and Time: Friday, July 27, 2018, 11:30 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract The logics required to support program verification are much more
expressive than the class of decidable logics available today, and
beyond the quantifierfree logics supported by SMT solvers. In
particular, when dealing with unbounded structures such as arrays or
dynamically manipulated heaps, the current support for automated
reasoning falls short of what we desire. The typical ways of dealing
with such logics have been through heuristics, and in particular
quantifier instantiation heuristics to deal with quantified logics and
the socalled natural proof heuristics that employ recursionunfolding
tactics to deal with recursively defined datatypes.
We give foundational results that explain the efficacy of heuristics
used for dealing with quantified formulas and recursive
definitions. We develop a framework for first order logic (FOL) over
an uninterpreted combination of background theories. Our central
technical result is that systematic term instantiation is *complete*
for a fragment of FOL that we call safe. Coupled with the fact that
unfolding recursive definitions is essentially term instantiation and
with the observation that heap verification engines generate
verification conditions in the safe fragment explains the efficacy of
verification engines like natural proofs that resort to such
heuristics. Furthermore, we study FOL with recursive definitions that
have least fix point semantics and show that though they are not
amenable to complete procedures, we can systematically introduce
induction principles that in practice bridge the divide between FOL
and FOL with recursive definitions.
Speaker Bio: Madhusudan Parthasarathy is a Professor in the Computer Science Department of the University of Illinois at UrbanaChampaign, USA. His interests are in Software Verification, Security, Program Synthesis and Machine Learning, and Logic and Automata Theory.
Host Faculty: Deepak D'Souza
 Series: Ph.D. Colloquium Title: Design of a LargeScale Distributed File System for PeertoPeer Networks  Speaker: Mr. Hrishikesh Dewan
PhD(ERP)  Faculty Advisor: Prof. R. C. Hansdah and Dr. Girish Suryanarayana(Orgn)
 Date and Time: Wednesday, July 25, 2018, 3:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract We present, in this thesis, a distributed file storage system called Julunga. Julunga is designed
for peertopeer systems supporting federated data centre environments such as cloud computing centres as well
as individual nodes. In Julunga, the metadata, the namespace and the data blocks of the files are entirely
distributed with no hard limits on the number of files that can be accommodated in a single directory. Also,
there is no physical limit on the size of a file. Junlunga supports file of exabytes size with ease along
with the number of concurrent users updating, reading and writing to the same file or a directory. The
location of the data blocks of a file is determined by using functions, thus expunging the need for file
allocation tables. Many new data structures and algorithms were designed where locality and preferences
of users are considered to provide optimal storage locations for files and file system metadata. Julunga
is designed on top of a new overlay network design named 'Afuronto' that is suited for largescale
peertopeer networks requiring fast message transmission, and we use different operators as found in
evolutionary computing to emulate a semistructured network. We present the network structure and the
various algorithms required for essential communication and maintenance. We also study the proposed
network by simulation and compare its performance with existing overlay networks. The simulated results
show that, on the average, there are at most six hops required for a message originated at any node in
the network to be transferred to any other node in the network. The network so designed is scalable,
resilient to failures, and can include a node of arbitrary size in processing capacity, network bandwidth,
and storage.
Reaching consensus is an essential problem in the design of distributed systems. To date, many algorithms
for achieving consensus in a distributed system have been proposed. However, only a few of them works
under practical implementation. For Julnga, we have designed and used a new consensus algorithm called
Majuli. Majuli is designed such that it easier to understand for system developers and resembles natural
techniques of reaching agreement when acting cooperatively. We show the safety and the liveness
property of the proposed consensus algorithm and demonstrate its usefulness in a few distributed
algorithms used in Julunga that require agreement or consensus for their correct operations.
Finally, we describe a new data structure called HashTrie Tree that we have developed to parse
and locate REST based services. The implementation of the overlay network and the file system are
exposed as RESTbased services on top of HTTP(s) protocol. HashTrie Tree is used in our custom
HTTP server designed in C# that has optimum performance when compared with other RESTbased HTTP
servers such as Windows Communication Foundation, Jersey. We show how our implementation supports
REST based service declarations, organizes the various methods in an optimized way for faster
access and scale to support thousands of concurrent users.
 Series: M.Tech (Research) Colloquium Title: Guarding Terrain Using k Watchtowers  Speaker: Nitesh Tripathi
Dept. of CSA  Faculty Advisor: Prof. Sunil L. Chandran
 Date and Time: Tuesday, July 24, 2018, 4:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract The discrete kwatchtower problem for a polyhedral terrain T in 3D with n vertices is to
find k vertical segments, called watchtowers, of smallest height, whose bottom endpoints
(bases) lie on some vertices of T , and every point of T is visible from the top endpoint
(tip) of at least one of those watchtowers. In other words, we have to find k watchtowers
whose bottom endpoints (bases) lie on some vertices of T, such that every point of T is
visible from the tip of at least one watchtower and the maximum height among these k
watchtowers is minimized. Zhu gave an algorithm for this problem when k = 1
with running time O(n log n). Agrawal et al. proposed a polynomial time
algorithm using parametric search technique for this problem with k = 2. Surprisingly,
no result is known for the problem when k > 2. In this talk, we discuss our proposed algorithm to solve kwatchtower problem for a fixed constant k. Our algorithm does not use parametric search and it’s running
time is polynomial in n.
Speaker Bio: Nitesh is a Masters student in CSA department, working in Theory Lab. He is advised by Prof. Sunil L. Chandran.
 Series: Department Seminar Title: Learning discrete Markov Random Fields with nearly optimal runtime and sample complexity.  Speaker: Prof. Raghu Meka
Associate Professor
Department of Computer Science
UCLA  Date and Time: Monday, July 23, 2018, 5:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract We give an algorithm for learning the structure of an undirected graphical model that has essentially optimal sample complexity and running time. We make no assumptions on the structure of the graphical model. For Ising models, this subsumes and improves on all prior work. For general twise MRFs, these are the first results of their kind.
Our approach is new and uses a multiplicativeweight update algorithm. Our algorithm Sparsitron is easy to implement (has only one parameter) and holds in the online setting. It also gives the first provably efficient solution to the problem of learning sparse Generalized Linear Models (GLMs).
Joint work with Adam Klivans.
Speaker Bio: Raghu Meka is an Associate Professor in the CS department at UCLA. He is broadly interested in complexity theory, learning and probability theory. He got his PhD at UT Austin under the (wise) guidance of David Zuckerman. After that, he spent two years in Princeton as a postdoctoral fellow at the Institute for Advanced Study with Avi Wigderson, and at DIMACS, at Rutgers. And after that, he spent an enjoyable year as a researcher at the Microsoft Research Silicon Valley Lab.
Host Faculty: Dr. Arnab Bhattacharyya
 Series: Department Seminar Title: On Randomization and Combinatorics in Computational Geometry,Discrete Mathematics, and Combinatorial Representation Theory.  Speaker: Dr. Kunal Dutta
Postdoc Researcher
Data Shape group
Inria Sophia
France  Date and Time: Monday, July 23, 2018, 3:30 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract In this talk we shall see three very different areas of
applications of combinatorics in computer science and mathematics,
illustrating different flavours of combinatorial reasoning.
First, we consider lower bounds on the maximum size of an
independent set, as well as the number of independent sets, in kuniform
hypergraphs, together with an extension to the maximum size of a subgraph
of bounded degeneracy in a hypergraph. Joint works with C. R. Subramanian
(IMSc, Chennai), Dhruv Mubayi (UIC, Chicago) and Jeff Cooper (UIC,
Chicago) and Arijit Ghosh (IMSc Chennai).
Next, we shall look at Haussler's Packing Lemma from Computational
Geometry and Machine Learning, for set systems of bounded VC dimension. We
shall go through its generalization to the Shallow Packing Lemma for
systems of shallow cell complexity, and see how it can be used to prove
the existence of small representations of set systems, such as epsilon
nets, Mnets, etc. Joint works with Arijit Ghosh (IMSc, Chennai), Nabil
Mustafa (ESIEE Paris), Bruno Jartoux (ESIEE Paris) and Esther Ezra
(Georgia Inst. Tech., Atlanta).
The last problem is on the decomposition, into irreducible
representations, of the Weil representation of the full symplectic group
associated to a finite module of odd order over a Dedekind domain. We
shall discuss how a poset structure defined on the orbits of finite
abelian pgroups under automorphisms can be used to show the decomposition
of the Weil representation is multiplicityfree, as well as parametrize
the irreducible subrepresentations, compute their dimensions in terms of
p, etc. Joint works with Amritanshu Prasad (IMSc, Chennai).
Host Faculty: Prof. Sunil L Chandran
 Series: Ph.D. Colloquium Title: Problems on bendnumber, circular separation dimension and maximum edge 2colouring  Speaker: Mr. Abhiruk Lahiri
Ph.D Student
Dept. of CSA  Faculty Advisor: Prof. Sunil L Chandran
 Date and Time: Monday, July 23, 2018, 11:00 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Representation of graphs as the intersection graphs of geometric objects has a long history. The objective is to a find a collection of “simple” sets S such that a given graph G is its intersection graph. We are interested in two types of intersection representations motivated by VLSI circuit layout problem. In these models, vertices are represented by polygonal paths with alternating horizontal and vertical segments. The measure of the complexity of a path is defined by the number of bends it has. The objective is to minimise the maximum number of bends used by any path in a representation. This minimum number (over all possible representations) is called the bend number of the graph.
In the first model, two vertices share an edge if and only if corresponding paths intersect. A graph that can be represented in such a way is called a VPG graph. We study a subclass of the planar graphs on this model. In the second model, two vertices of the graph share an edge if and only if corresponding paths overlap on a nonzero length segment. A graph that can be represented in such a way is called an EPG graph. We study Halin graphs which is a subclass of the planar graphs, fully subdivided graphs and minimally 2connected graphs for this model. Using one of these results, we show optimization problems such as maximum independent set, minimum dominating set are APXhard on 1bend EPG graphs and its subclass which is called LEPG graphs. We devise a constant factor approximation algorithm for the maximum independent set problem on 1bend EPG graphs which guarantees an approximation ratio of 3, which improves the previously known approximation ratio of 4.
In the second part, we study the notion of circular separation dimension which was introduced recently by Douglas West. Formally, a pair of nonadjacent edges is said to be separated in a circular ordering of vertices if the endpoints of the two edges do not alternate in the ordering. The circular separation dimension (CSD) of a graph G is the minimum number of circular orderings of the vertices of G such that every pair of nonadjacent edges is separated in at least one of the circular orderings. We establish a new upper bound for CSD in terms of the chromatic number of the graph. We further study this question for special graph classes such as seriesparallel graph and twoouterplanar graph.
In the final part, we study maximum edge 2colouring problem. For a graph G, the maximum edge 2colouring problem seeks the maximum possible colours that can be used to colour the edges of the graph such that edges incident on a vertex span at most two distinct colours. The problem is well studied in combinatorics, in the context of the antiRamsey number. Algorithmically, the problem is known to be NPhard. It is also known that no polynomial time algorithm can approximate to a factor less than 3/2 assuming the unique game conjecture. The obvious but the only known algorithm issues different colours to the edges of a maximum matching and different colours to remaining connected components. We establish an improved approximation bound of 8/5 for the algorithm, for trianglefree graphs with perfect matching.
 Series: CSA Faculty Colloquium Title: Efficient Algorithms for Structured Prediction Problems  Speaker: Prof. Shirish K Shevade.
 Date and Time: Friday, July 20, 2018, 4:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract In many realworld prediction problems, the output is a structured object like
a sequence or a tree or a graph. Such problems are referred to as structured prediction
problems. Support vector machines (SVMs) have shown promise for solving these problems.
Learning structural SVMs amounts to solving a convex quadratic program with a huge number of
constraints. The number of constraints is typically exponential, which makes the problem intractable
by general purpose optimization methods. In this talk, we discuss a fast sequential dual method for training structural SVMs. We also discuss a simple and efficient algorithm for solving a nonconvex optimization problem for structured prediction in a semisupervised setting.
Speaker Bio: Shirish Shevade received his Ph.D. from the Indian Institute of Science, Bangalore, India, in 2002. He is currently an Associate Professor in the Department of Computer Science and Automation at the Indian Institute of Science. His research interests span many areas of Machine Learning such as Support Vector Machines, Gaussian Processes and semisupervised learning. He is a Senior Member of IEEE.
Host Faculty: Prof. Sunil Chandran & Prof. Shalabh Bhatnagar
 Series: M.Tech (Research) Thesis Defense Title: Design of Trusted Market Platforms using Permissioned Blockchains and Game Theory  Speaker: Ms. Shivika Narang
M.Tech. (Research) Student
Dept. of CSA
IISc  Faculty Advisor: Prof. Y. Narahari
 Date and Time: Thursday, July 19, 2018, 4:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract The blockchain concept forms the backbone of a new wave technology that promises to be deployed extensively in a wide variety of industrial and societal applications. Governments, financial institutions, banks, industrial supply chains, service companies, and even educational institutions and hospitals are investing in a substantial manner in the hope of improving business efficiency and operational robustness through deployment of blockchain technology. This thesis work is concerned with designing trustworthy businesstobusiness (B2B) market platforms drawing upon blockchain technology and game theory.
The proposed platform is built upon three key ideas. First, we use permissioned blockchains with smart contracts as a technically sound approach for building the B2B platform. The blockchain deploys smart contracts that govern the interactions of enterprise buyers and sellers. Second, the smart contracts are designed using a rigorous analysis of a repeated game model of the strategic interactions between buyers and sellers. We show that such smart contracts induce honest behavior from buyers and sellers. Third, we embed cryptographic regulation protocols into the permissioned blockchain to ensure that business sensitive information is not revealed to the competitors. We believe our work is an important step in the direction of building a powerful B2B platform that maximizes social welfare and enables trusted collaboration between strategic enterprise agents.
 Series: CSA Distinguished Lecture Title: A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics  Speaker: Professor Moses Charikar
Donald E. Knuth Professor Computer Science
Stanford University  Date and Time: Tuesday, July 17, 2018, 11:30 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract We study the Stochastic Gradient Langevin Dynamics (SGLD) algorithm for nonconvex optimization. The algorithm performs stochastic gradient descent, where in each step it injects appropriately scaled Gaussian noise to the update. We analyze the algorithm’s hitting time to an arbitrary subset of the parameter space. Two results follow from our general theory: First, we prove that for empirical risk minimization, if the empirical risk is pointwise close to the (smooth) population risk, then the algorithm finds an approximate local minimum of the population risk in polynomial time, escaping suboptimal local minima that only exist in the empirical risk. Second, we show that SGLD gives an alternate approach and an improvement for learning linear classifiers under zeroone loss.
Joint work with Yuchen Zhang and Percy Liang. (COLT '17)
Speaker Bio: Moses Charikar is the Donald E. Knuth professor of Computer Science at Stanford University. He obtained his PhD from Stanford in 2000, spent a year in the research group at Google, and was on the faculty at Princeton from 20012015. He is broadly interested in the design and analysis of algorithms with an emphasis on approximation algorithms for hard problems, metric embeddings and algorithmic techniques for big data. He won the best paper award at FOCS 2003 for his work on the impossibility of dimension reduction, the best paper award at COLT 2017 and the 10 year best paper award at VLDB 2017. He was jointly awarded the 2012 Paris Kanellakis Theory and Practice Award for his work on locality sensitive hashing, and was named a Simons Investigator in theoretical computer science in 2014.
Host Faculty: Dr. Anand Louis
 Series: Department Seminar Title: A Case for (Limited) Explicit Dataflow Graph Execution  Speaker: Dr. Gagan Gupta
Computer Architecture Researcher
Microsoft Research
USA  Date and Time: Tuesday, July 17, 2018, 10:00 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract As Moore’s law slows down, we must find new ways of scaling processor performance. Von Neumann ISAs have been successful because they provide a clean conceptual target to software while running the complete gamut of algorithms reasonably well. We badly need clean new abstractions that utilize finegrain parallelism and run energy efficiently. Prior work (such as the UTAustin TRIPS EDGE ISA and others) showed how to form blocks of computation containing limitedscope dataflow graphs, which can be thought of as small structures (DAGs) mapped to silicon. In this presentation I describe some postTRIPS work that addresses the limitations of the original ISA, and how those extensions can provide energyefficient execution for single threads compared to a conventional outoforder superscalar design. I will also describe a specific microarchitecture based on these extensions, and show early results. Finally, I will describe how this notion of “structured computation” can be extended to form accelerators dynamically with minor changes to the CPU, or extended to synthesize efficient accelerators that are specialized to a specific workload.
Speaker Bio: Gagan Gupta has worked in the semiconductor industry for over two decades. Presently he is a computer architecture researcher at Microsoft Research. He has led engineering and marketing teams to launch commercially successful processors at LSI Logic, Huawei, and ARC International, and influenced R&D strategies in the industry (e.g., at Intel and Sandisk). Gagan has a Ph.D. in Computer Sciences from the University of WisconsinMadison. His work has been recognized with awards at multiple industrial and academic fora, and is regularly cited in trade publications.
Host Faculty: Dr. Arkaprava Basu
 Series: M.Sc. (Engg) Colloquium Title: Optimizing Matrix Computations with PolyMage  Speaker: Ms. Kumudha K N
 Faculty Advisor: Prof. Uday Kumar Reddy
 Date and Time: Friday, July 13, 2018, 11:00 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Linear algebra computations and other arbitrary affine accesses are ubiquitous in
applications from domains like scientific computing and digital signal processing
(DSP). Libraries such as OpenBLAS, MKL, and FFTW
provide efficient handoptimized implementations for matrix and vector
primitives used in these domains for various architectures. Applications are
then built upon these standard library routines to obtain high performance.
These libraries do not perform well for all matrix sizes and obtain suboptimal
performance for small matrices. The interface of these libraries can also be
fairly complex requiring several input parameters. Thus, an even higher level
of abstraction is often desired to improve productivity. Further, by using
these libraries the opportunity to optimize across different library calls is
lost and traditional programming to exploit this locality using library
functions becomes complex.
The work in this thesis proposes (i) a tile size selection model which works for any
arbitrary affine access and eschews autotuning, (ii) a simple heuristic to
determine profitability of library call mapping and falling back to generated
code otherwise, (iii) an intratile optimization technique to expose innerloop
parallelism thus enabling general purpose compiler's vectorizer to generate vector
instructions, (iv) a DSL approach with high level primitives and
functions to allow expressing computations efficiently. The optimizations
proposed are implemented in the PolyMage DSL, a domain specific language (DSL)
for image processing pipelines. Its optimizer is able to perform optimizations like
fusion, tiling, and loop optimizations for image processing pipelines. We
extend PolyMage's compiler to support the above optimizations.It is thus able to optimize
computations from additional domains including dense linear algebra and certain
DSP computations.
We experimentally evaluates these optimizations on modern
multicore systems using representative benchmarks from PolyBench, digital
signal processing, image processing and neural networks. The results are
compared to stateoftheart optimization approaches and frameworks in each
domain. Experiments on DSP benchmarks show that our optimizations has a mean
speed up of 7.7x over existing PolyMage optimizer, 5.1x over
numpy and 1.9x over MATLAB toolboxes with parallel computing support. On
linear algebra computations from PolyBench benchmark suite show that we obtain
a speedup of 7.5x over existing PolyMage optimizer, 3.6x over
Pluto and 4.1x over PPCG.
 Series: M.Sc. (Engg) Colloquium Title: Active Learning for Efficient Testing of Student Programs  Speaker: Mr. Ishan Rastogi
M.Sc (Engg)Student
Dept. of CSA  Faculty Advisor: Prof. Shirish Shevade and Prof. Aditya Kanade
 Date and Time: Friday, July 13, 2018, 10:00 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Automated evaluation of student programs is an important problem since it eases instructor's burden by reducing or altogether eliminating the time required for program evaluation. A solution to this problem would also make it possible to scale up courses having computer programming content to a larger audience, such as to a massive online open courses setting. The problem is, however, inherently difficult as students can make a variety of mistakes spanning the entire gamut  from shallow syntactic errors to more involved semantic ones. Among these, identifying whether a program has a logical error is perhaps the most challenging, since the error may only surface in a subset of all valid test cases. Additionally, unlike syntax errors, logical errors are task specific and hence require an additional input from the instructor (for example, in the form of a set of quality test cases) for every new task introduced into the system.
In this talk, we will discuss our work, Automated Testing using Active learning and Symbolicexecution (ATAS), an algorithm designed to identify whether a student program is logically incorrect in an online setting. This algorithm builds upon the recent advances in both symbolic execution and active learning. Symbolic execution is a program analysis technique which can generate test cases through symbolic constraint solving. Our method makes use of a reference implementation of the task as its sole input. We compare our method with a symbolic executionbased baseline on six programming tasks retrieved from CodeForces comprising of about 23000 student submissions. We demonstrate an average improvement of over $2.5$x over the baseline in terms of runtime (thus making it more suitable for online evaluation), without significant degradation in evaluation accuracy.
Speaker Bio: Ishan is a masters student at the CSA department, working in Intelligent Systems Lab. He is advised by Prof. Shirish Shevade and Prof. Aditya Kanade.
 Series: Department Seminar Title: Leveraging Data and AI for Early Warning of Social and Economic Disruption  Speaker: Prof. Rohini Srihari
Professor,
Dept. of Computer Science and Engineering
State University of New York, Buffalo.  Date and Time: Thursday, July 12, 2018, 11:30 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract According to the Institute of Economics and Peace, conflict costs the world 13.3% of its GDP, or $13.6 trillion per year. And these numbers don’t even begin to tell the story of the human costs of violence, which disproportionately affects women and youth.
This talk focuses on the design and development of a software platform, groundTruth, for early warning of social and economic disruption in emerging markets and fragile states. This initiative leverages the following developments: (i) major advances in artificial intelligence, (ii) widespread adoption of mobile devices and the internet in emerging countries, and (iii) the availability of an unprecedented amount of data, including social media and sensor data. A taxonomy of risk drivers, types of disruptions, and key indicators useful in predicting disruptions will be presented. Predictive analytics algorithms based on machine learning models (including deep learning models} will be discussed along with initial results. These have been trained and tested on rich, manually curated, global event databases. A demo of the current system will be presented along with plans for further development.
Speaker Bio: Rohini Srihari is an educator, entrepreneur and computer scientist. She is a Professor in the Dept. of Computer Science and Engineering at the State University of New York, Buffalo. Her research has focused on various aspects of multilingual text mining and natural language processing and has been funded by agencies such as DARPA and the National Science Foundation. She has founded and led language technology companies, delivering content analytics solutions and services to enterprise customers across multiple industries. She is currently serving as the Chief Data Scientist with PeaceTech Lab based in Washington, DC where she is overseeing data and technology programs with the potential for major societal impact. She received a B. Math. from the University of Waterloo, Canada and a PhD in Computer Science from the University at Buffalo.
Host Faculty: Prof. M Narasimha Murty
 Series: Ph.D. Colloquium Title: Recommendations in Complex Networks: Unifying Structure into Random Walk.  Speaker: Sharad Kumar Nandanwar
 Faculty Advisor: Prof. M. Narasimha Murty
 Date and Time: Thursday, July 12, 2018, 10:00 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Making recommendations or predicting links which are likely to exist in the future is one of the central problems in network science and graph mining. In spite of modern stateoftheart approaches for link prediction, the traditional approaches like Resource Allocation Index, Adamic Adar still find heavy use, because of their simplistic nature yet competitive performance. Our preliminary investigation reveals that a major fraction of missing links which are observed in the near future, are the links which are between onehop distant nodes. Current "friend of friend is a friend" based approaches, provide a mechanism for aggregating the effect of triangles getting closed by inclusion of an edge. In this work we look beyond these triangles, and hunt for higher order structures in common neighborhood. However, with an idealistic choice of cliques as higher order structures, the problem easily gets out of hand, even for common egonetworks involving 50100 nodes. In wake of this, we define a dense structure ksupport, as an approximation to the clique. Further, for a given k value, we propose a goodness measure to capture the contribution of the common neighborhood w.r.t. ksupport, towards the link strength. The proposed goodness measure with different k values is then exploited in learning a supervised model.
We next take a multiclass classification view to the recommendation problem. This is suited for the cases where cardinality of the set of target objects is reasonably small. Classification of entities based on the underlying network structure is an important problem and has been studied extensively in literature. Networks encountered in practice are sparse and have many missing and noisy links. Statistical learning techniques have been used in intranetwork classification; however, they typically exploit only the local neighborhood, so may not perform well. We propose a novel structural neighborhoodbased classifier learning using a random walk, where we label a node based on how nodes in the respective k^{th}level neighborhood are labeled. We observe that random walks of short length are helpful in classification, while emphasizing role of longer random walks may cause the underlying Markov chain to converge to a stationary distribution. Considering this, we take a lazy random walk based approach with variable termination probability for each node, based on the node's structural properties including its degree.
Further, we observe that conventional loss functions penalize a node based on a function of its predicted label and target label. Such loss functions underperform while learning on a network having overlapping classes. In relational setting, even though the ground truth is not known for the unlabeled nodes, some evidence is present in the form of labeling acquired by the nodes in their neighborhood. Considering this, we propose a structural loss function for learning in networks based on the hypothesis that loss is induced when a node fails to acquire a label that is consistent with the labels of the majority of the nodes in its neighborhood. We further combine this with a novel semantic regularizer, which we call homophily regularizer, to capture the smooth transition of discriminatory power and behavior of semantically similar nodes.
Hybrid recommender systems have shown the power of exploiting relationships amongst objects which directly or indirectly effect the recommendation task. However, the effect of all relations is not equal, and choosing their right balance for a recommendation problem at hand is nontrivial. We model these interactions using a Heterogeneous Information Network, and propose a systematic framework for learning their influence weights for a given recommendation task. We address the issue of redundant results, which is very much prevalent in recommender systems. To alleviate redundancy in recommendations we use Vertex Reinforced Random Walk (a nonMarkovian random walk) over a heterogeneous graph. It works by boosting the transitions to the influential nodes, while simultaneously shrinking the weights of others. This helps in discouraging recommendation of multiple influential nodes which lie in close proximity of each other, thus ensuring diversity.

