Events 

Seminars 

Prof. I. G. Sarma Memorial Lecture Series 

Prof. Priti Shankar Memorial Seminar Series 

Multimedia Archive 



UPCOMING SEMINARS 

Series: Department Seminar Title: Problem of Induction: East and West  Speaker: Prof. Kisor Kumar Chakrabarti
President
Institute for Cross Cultural Studies and Academic Exchange
NC, USA  Date and Time: Thursday, January 03, 2019, 4:30 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Hume argued that any induction presupposes uniformity of nature that itself is an induction and hence induction is circular. More recently Goodman has argued that the same inductive evidence yields conflicting predictions. I shall try to show that various contemporary attempts to solve these problems are unsatisfactory. I shall also try to show that these problems were anticipated in Indian philosophies and that a Nyaya solution has more promise.
Speaker Bio: Kisor Kumar Chakrabarti is a former Distinguished Professor of Philosophy and Religious Studies of the Davis and Elkins College (where he has served as the Vice President of Academic Affairs), the Bethany College, the Ferrum College, etc. He has also taught at the University of California at Berkeley, the University of Maine at Orono and the University of Calcutta. He has held Fellowships at the University of Oxford, Institute for Advanced Study, Princeton, the Indian Institute for Advanced Study, Shimla, the University of Pittsburgh and the Australian National University and received numerous honors and awards. He is fluent in Sanskrit, studied for decades original Sanskrit works of Indian Philosophical Schools under the guidance of eminent pundits and is a leading authority on Indian and comparative philosophy and religion. He is also devoted to the study of Greek philosophy from original Greek sources and has taught modern and contemporary philosophy in India and the USA for more than forty years and published substantially on all these areas. He has published eighty eight research papers and articles mainly dealing with topics of comparative logic, epistemology, metaphysics and ethics. He has also authored The Logic of Gotama (University of Hawaii Press, 1978), Definition and Induction (University of Hawaii Press, 1995), Classical Indian Philosophy of Mind (State University of New York Press, 1999) and Classical Indian Philosophy of Induction (Rowman and Littlefield, 2010).
Host Faculty: Prof. K Gopinath
 Series: CSA Distinguished Lecture Title: Lectures on Brain and Computation  Speaker: Prof. Christos Papadimitriou
Donoval Family Professor of Computer Science
Columbia University  Date and Time: Wednesday, December 26, 2018, 3:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Despite a deluge of exciting results in experimental and theoretical neuroscience over the past decades, some of the top researchers in the area agree that progress has been slow on the field’s overarching question: How does the Brain (molecules, neurons, synapses) give rise to the Mind (cognition, behavior, learning, thought)? This is arguably one of the hardest and most fundamental challenges in science today. Many expect that computation will be an important workhorse, conceptual framework, and metaphor of this epic interdisciplinary scientific effort. On another front, advances in machine learning have often been inspired by the Brain, albeit in a pointedly tentative way.
The purpose of this series of three lectures is to give the participants some of the necessary background for appreciating this fascinating interface between computation and neuroscience, and for making progress in it.
Note: Three lectures will be held starting from 26/12/2018, 27/12/2018, and 28/12/2018
Speaker Bio: Christos H. Papadimitriou is the Donoval Family Professor of Computer Science at Columbia University. Before joining Columbia this year, he taught at Harvard, MIT, NTU Athens, Stanford, UCSD, and at Berkeley since 1995. He has written many books and articles on the theory of algorithms and complexity, and its applications to optimization, databases, control, AI, robotics, economics and game theory, the Internet, evolution, and the brain. He holds a Phd from Princeton, and honorary doctorates from nine universities. He is a member of the National Academy of Sciences of the US, the American Academy of Arts and Sciences, and the National Academy of Engineering, and is a recipient of the Knuth prize, the Gödel prize, the Kalai prize for CS in Game Theory, the EATCS award, and the von Neumann medal. He has also written three novels: "Turing," " Logicomix," and his latest "Independence" (2017).
Host Faculty: Dr. Siddharth Barman
 Series: Department Seminar Title: Towards LowCost Memory Security  Speaker: Prof. Moinuddin Qureshi
Professor,
Electrical and Computer Engineering,
Georgia Institute of Technology, USA  Date and Time: Monday, December 17, 2018, 2:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Securing offchip main memory is essential for protection from adversaries with physical access to systems. Current securememory designs, such as Intel SGX, incur significant slowdown, mainly due to the extra accesses required to obtain the securityrelated metadata  counters for encryption, MAC for integrity check, and Merkletree counters for replay attack protection. To make secure memory solutions widespread, it is vital that the performance overhead of providing security is kept to a negligible amount, otherwise, such solutions will remain limited to only a narrow set of systems and applications.
In this talk, I will describe our recent works to reduce the overheads of secure memory. First, we avoid the bandwidth overhead of MAC accesses by colocating the data and the MAC on an ECC DIMM. This solution, called SYNERGY, not only provides higher performance for secure memory but also provides stronger reliability than ECC alone. Second, we reduce the bandwidth overhead of obtaining counters for encryption and MerkleTree by packing more counters per cache line. This solution, called Morphable Counter, can pack 2x more counters per line than stateoftheart by adapting the counter format to suit the application requirement. Finally, I will also briefly discuss our MICRO2018 work on protecting cache memories from evictionbased attacks. This solution, called CEASER, can tolerate years of attack, has a slowdown of ~1%, and incurs a storage overhead of only 24 bytes.
Speaker Bio: Moinuddin Qureshi is a Professor of Electrical and Computer Engineering at the Georgia Institute of Technology. His research interests include computer architecture, memory systems, hardware security, and quantum computing. He was a research staff member (20072011) at IBM T.J. Watson Research Center, where he investigated the caching algorithms for Power7 processors and won the Outstanding Technical Achievement (OTA) award for studying nonvolatile memories for servers. He holds more than twodozen U.S. patents. His publications have received more than 7500 citations, including two leadauthor papers with more than 1000 citations each. He served as the Program Chair for MICRO 2015 and as the selection committee cochair for IEEE MICRO Top Picks 2017. He is a member of the HallofFame of ISCA, HallofFame of MICRO, and HallofFame of HPCA. He is a recipient of the Intel Faculty Award, NetApp Faculty Fellowship, MICRO2018 best paper award, two IEEE MICRO TopPick awards, and two honorable mentions. He received his Ph.D. (2007) and M.S. (2003) from the University of Texas at Austin.
Host Faculty: Arkaprava Basu
 Series: Department Seminar Title: Breaking the Memory Wall in Current and Emerging Accelerators  Speaker: Prof. Adwait Jog
Assistant professor,
Computer Science at the College of William & Mary (W&M), Virginia, USA  Date and Time: Monday, December 17, 2018, 10:30 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract The famous memory wall has been a problem in computer systems for decades. In this talk, I will revisit this problem in light of accelerators, which are becoming an inevitable part of almost all systems. First, I will discuss the limited memory capacity problem faced by accelerators, especially in emerging inmemory automata processors, and discuss one of the ways to address it to achieve higher throughput. Next, I will discuss the limited bandwidth problem in Graphics Processing Units (GPUs) and show that existing memory coalescing solution to address this bandwidth problem can actually expose a security vulnerability. Time permitting, I will briefly discuss our solution that partially addresses this issue. The bulk of my talk is inspired by my research groupâ€™s two recent conference papers (MICRO'18 and HPCA'18), which can be accessed here: http://adwaitjog.github.io/pubs.html
Speaker Bio: Adwait Jog is an Assistant Professor of Computer Science at the College of William & Mary (W&M), Virginia, USA. He earned his Ph.D. from the Pennsylvania State University, University Park in 2015. His research interests lie in the broad area of computer architecture. Specifically, he is interested in designing capable, energyefficient, reliable, and secure generalpurpose Graphics Processing Units (GPUs) and other accelerators. He is the recipient of the NSF CAREER Award and Penn State Outstanding Graduate Research Assistant Award. More details can be found on Adwait's webpage: http://adwaitjog.github.io/
Host Faculty: Arkaprava Basu
 Series: Department Seminar Title: Improved Algorithms for MST and MetricTSP Interdiction  Speaker: Prof. Chaitanya Swamy
 Date and Time: Wednesday, December 12, 2018, 11:00 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Interdiction problems investigate the sensitivity of an underlying optimization problem with respect to removal of a limited set of underlying elements in order to identify vulnerable spots for possible reinforcement or disruption. We consider the MSTinterdiction problem: given a multigraph G with weights and interdiction costs on the edges, and an interdiction budget B, find a set R of edges of total interdiction cost at most B so as to maximize the weight of an MST of GR. Our main result is a 4approximation algorithm for this problem. This improves upon the previousbest 14approximation due to Zenklusen, and notably, our analysis is also significantly simpler and cleaner. Whereas Zenklusen uses a greedy algorithm with an involved analysis to extract a good interdiction set from an overbudget set, we utilize a generalization of knapsack called the tree knapsack problem that nicely captures the key combinatorial aspects of this "extraction problem." We prove a simple, yet strong, LPrelative approximation bound for tree knapsack, which leads to our improved guarantees for MST interdiction. Our algorithm and analysis are nearly tight, as we show that one cannot achieve an approximation ratio better than 3 relative to the upper bound used in our (and the prior) analysis. Our guarantee for MSTinterdiction yields an 8approximation for metricTSP interdiction. We also show that the maximumspanningtree interdiction problem is at least as hard to approximate as the minimization version of densestksubgraph. This is joint work with Andre Linhares.
Host Faculty: Dr. Siddharth Barman


PAST SEMINARS 

Series: Department Seminar Title: Adaptive Garbled Circuits with Near Optimal Online Complexity.  Speaker: Mr. Akshayaram Srinivasan, University of California, Berkeley
 Date and Time: Monday, December 10, 2018, 11:00 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Garbled circuits are fundamental cryptographic primitives. They have diverse applications such as designing secure multiparty computation protocols, in parallel cryptography, in constructing program obfuscation and more recently in constructing IBE schemes without pairings. The security of garbling schemes have been analyzed in two settings: the selective setting and the adaptive setting. In the selective setting, an adversary is forced to declare the input on which he wishes to evaluate the circuit before seeing the garbled circuit and in the adaptive setting, he is allowed to choose the input adaptively depending on the garbled circuit. Constructing adaptive garbled circuits where the size of the garbled input is small has been a major open problem in cryptography. In this talk, I will give a construction of adaptive garbled circuits where the size of the garbled input is (nearly) optimal.
Joint work with Sanjam Garg.
Speaker Bio: Akshayaram Srinivasan is a fourthyear PhD student in the theory group at UC Berkeley. His advisor is Prof. Sanjam Garg. He received his B.Tech in Computer Science and Engineering from IITMadras in 2015.
He is broadly interested in theoretical computer science and in particular, in the theory and applications of cryptography. He has published more than 12 research papers in top conferences in cryptography such as Foundations of Computer Science (FOCS), Crypto, Eurocrypt and TCC. His research has been recognized with a best paper award at Eurocrypt 2018. He is a recipient of the EECS department fellowship in 201516 in UC Berkeley, Computer age management prize for the best academic performance in computer science during his junior year in IITMadras, Singapore technologies fellowship during 201214 for outstanding academic achievement and the Kishore Vaigyanik Protsahan Yojana (KVPY) fellowship in 2010.
Host Faculty: Dr. Bhavana Kanukurthi
 Series: CSA Faculty Colloquium Title: Automating Deductive Verification using DecisionTree Based Learning  Speaker: Prof. Deepak D'Souza
Professor
Dept. of CSA  Date and Time: Friday, December 07, 2018, 4:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract The FloydHoare style of proving assertions in programs involves
coming up with logical annotations at different program points, that
are consistent with the semantics of the program statements and
adequate in that they are strong enough to imply the given
assertions. Proofs in this style have the potential to be a lot more
scalable than verification approaches like modelchecking that rely on
exhaustive search of the statespace of the program, given that complex
programs may often have simple proofs of the assertions in them. While
a large part of these proofs can be automated using a verification
engine that checks consistency and adequacy of given annotations with
the help of logical solvers in the backend, a critical input that a
user needs to supply manually are annotations at key points, like loop
invariants and function contracts. A possible way to address this
problem is to use learning techniques to find such candidate
invariants, making use of counterexamples provided by the verification
engine to previously conjectured invariants. In this talk we describe
a decisiontree based approach to doing this, and highlight some of
the challenges in adapting classical decisiontree learning algorithms
to handle samples that may, in general, take the form of Horn clauses.
Speaker Bio: Deepak D'Souza received his PhD from Chennai Mathematical Institute in
2000. Since 2003 he has been at the Department of Computer Science and
Automation of the Indian Institute of Science, Bangalore, where he is
currently a Professor. His areas of interest include program verification,
program analysis, and specification and analysis of realtime and hybrid
systems.
Host Faculty: Prof. Sunil L Chandran & Prof. Shalabh Bhatnagar
 Series: M.Sc. (Engg) Thesis Defense Title: IO Pattern Aware Methods to Improve the Performance and Lifetime of NAND SSD  Speaker: Mr. Arpith K
M.Sc (Engg)Student
Dept. of CSA  Faculty Advisor: Prof. K Gopinath
 Date and Time: Monday, December 03, 2018, 4:00 PM
 Venue: CSA Faculty Room, (Room No. 101, Ground floor)
Abstract Solid State Drives based on NAND flash use transistors to store information persistently. Data is stored as a threshold voltage in each flash cell. Due to its energy efficiency, small form factor and resilience to physical shock, they are the storage medium of choice in a variety of mobile devices. Internal parallelism facilitates SSDs to deliver a significantly higher IO performance when compared to traditional magnetic disks, and are hence used in data centers. Modern flash memories have transistors that allow it to store multiple bits, thus enabling the production of SSDs with higher capacities and a low costperbit. As of 2018, cells with an ability to store three bits are being widely used, with Intel and Micron just announcing even the availability of the first commercial SSD with quad level cells.
However, such highdensity SSDs suffer from longer latencies to program and read data, resulting in reduced throughputs, when compared to flash memories that store a single bit per cell. Also, they suffer from reduced reliability. Mechanisms to detect bit errors and prevent data loss add to performance overheads.
In the talk, we will discuss the two proposed systemlevel solutions, which with the knowledge of IO patterns of the workload can improve the performance and lifetime of NAND based solid state drives.
The first work proposes to combine various page types in a wordline to a single logical page called a MeldedPage. This improves the read performance of an SSD by mitigating the overheads involved in the read operation. Using this method, we achieve performance improvements of up to 44% on distributed workloads that use Hadoop Distributed File System (HDFS).
Second, to improve the write performance and lifetime of an SSD, we propose a modified programming scheme called Hot Page Aware Relaxed Program Sequence scheme. Experimental results show an average improvement of 56% in the performance of the SSD when compared to methods that use shadow program sequence scheme. We also observe a reduction in the number of pages backed up by an average of 85%. When compared to methods that use dynamic SLC caching, the proposed scheme can reduce the number of blockerases by an average of 61%.
Speaker Bio: Speaker’s bio: Arpith is a masters student at CSA department working in Computer Architecture and Systems Lab. He is advised by Prof. K. Gopinath.
 Series: Department Seminar Title: Classical lower bounds from quantum upper bounds  Speaker: Dr. Ankit Garg
MSR India  Date and Time: Friday, November 30, 2018, 11:00 AM
 Venue: CSA Faculty Room, (Room No. 101, Ground floor)
Abstract We prove lower bounds on complexity measures, such as the approximate degree of a Boolean function and the approximate rank of a Boolean matrix, using quantum arguments. We prove these lower bounds using a quantum query algorithm for the combinatorial group testing problem.
We show that for any function f, the approximate degree of computing the OR of n copies of f is at least square root of n times the approximate degree of f, which is optimal. No such general result was known prior to our work, and even the lower bound for the OR of ANDs function was only resolved in 2013.
We also prove analogous results in communication complexity as well as generalize the result by replacing OR with an arbitrary symmetric function. The talk will assume no quantum background and in fact won’t need to go into too much quantum details at all. Based on joint work with Shalev BenDavid, Adam Bouland and Robin Kothari.
Host Faculty: Dr. Anand Louis
 Series: Department Seminar Title: Betti Numbers of Gaussian Excursions in the Sparse Regime  Speaker: Dr. Gugan Thoppe
PostDoctoral Associate
Department of Statistical Science
Duke University
Durham
USA  Date and Time: Monday, November 26, 2018, 2:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract A function's excursion set is the subdomain where its value exceeds some threshold. Some key examples illustrating the central role that excursion sets play in different application areas are as follows. In medical imaging, in order to understand the brain parts involved in a particular task, analysts frequently look at the high blood flow level regions in the brain when the said task is being performed. In control theory, it is known that the viability and invariance properties of control systems can be expressed as superlevel sets of suitable value functions. In robotics, in order to plan its motion, a sensor robot may want to identify the subterrain where the accessibility probability is above some threshold. Often, functions whose excursions are of interest are either random themselves (for e.g., due to noise) or, while being deterministic, are too complicated and hence can be treated as being a sample of a random field. In this sense, studying the topology of random field excursions is vital. This work is the first detailed study of their Betti numbers (number of holes) in the socalled `sparse' regime. Specifically, we consider a piecewise constant Gaussian field whose covariance function is positive and satisfies some local, boundedness, and decay rate conditions. We model its excursion set via a Cech complex. For Betti numbers of this complex, we then prove various limit theorems as the window size and the excursion level together grow to infinity. Our results include asymptotic mean and variance estimates, a vanishing to nonvanishing phase transition with a precise estimate of the transition threshold, and a weak law in the nonvanishing regime. We further have a Poisson approximation and a central limit theorem close to the transition threshold. Our proofs combine extreme value theory and combinatorial topology tools.
This is joint work with Sunder Ram Krishnan.
Speaker Bio: Dr Gugan Thoppe is a PostDoctoral Associate in the Dept. of Statistical Science at Duke University, USA with Prof. Sayan Mukherjee. Earlier, he worked with Prof. Robert Adler as an ERC Senior Researcher (postdoc) at Technion, Israel. He has done his PhD and MS in Systems Science with Prof. Vivek Borkar at TIFR, India. His PhD work won the TAASasken best thesis award for 2017. He is also a twotime recipient of the IBM PhD fellowship award (2013–14 and 201415). His research interests include random topology and stochastic approximation. In random topology, he has looked at topological evolutions in dynamic ErdosRenyi graphs, the connections between persistence diagrams and minimal spanning acycles, and, recently, the behaviour of Betti numbers of Gaussian excursions. Presently, he is interested in exploring the topological behaviour of dynamic random fields, volatility in the topology of dynamic ErdosRenyi graphs, and on building online algorithms for minimal spanning acycles. In stochastic approximation, he has been focussing on building theoretical tools for deriving convergence rates for the class of one/ two timescale stochastic approximation algorithms in both linear and nonlinear settings. His main contributions have been the novel use of Alekseev's formula, a generalization of variation of constants formula, and a useful concentration inequality for a sum of martingale differences. Some of his results have direct applications in reinforcement learning.
Host Faculty: Prof. Shalabh Bhatnagar
 Series: Ph.D. Colloquium Title: Relation Schema Induction using Tensor Factorization and Algorithms for Lowrank Tensor Completion.  Speaker: Mr. Madhav Ram Nimishakavi
 Faculty Advisor: Prof. Partha Pratim Talukdar
 Date and Time: Thursday, November 22, 2018, 4:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract A lot of tasks in Machine Learning involve dealing with multidimensional data. Utilizing the underlying structure of this multidimensional data is useful in many applications. Tensors, which are multiway generalization of matrices, can be used to represent the multidimensional data. Tensor decomposition is extensively used for analyzing this type of data in various fields. In the first part of the thesis, we introduce two novel tensor decomposition based approaches for the problems of Relation Schema Induction (RSI) and Higherorder Relation Schema Induction (HRSI). RSI is the task of inducing schemata i.e., type signatures of arguments of relations from raw text. For example, capital_of(city, country) is a valid schema for the relation capital_of. This is an important first step in the construction of Knowledge Bases (or Knowledge Graphs) for a new domain. We propose a novel coupled MatrixTensor decomposition based approach called Schema Induction using Coupled Tensor Factorization (SICTF) for the task of RSI. Similarly, the task of HRSI is inducing type signatures of more arguments than just subject and object for relations. For this task, we propose a novel framework called Tensor Factorization with Backoff and Aggregation (TFBA). TFBA jointly factorizes multiple tensors as the first step and then performs aggregation for constructing higherorder (or nary) schemata. Through extensive experiments on multiple real world datasets, we demonstrate the effectiveness of SICTF and TFBA for the tasks of RSI and HRSI respectively.
Many real world multidimensional datasets are often incomplete and a lot of applications can benefit from predicting the missing values in these datasets. In this context, the problem of tensor completion is used, which is the task of predicting missing values in a partially observed tensor. A common assumption made for tensor completion is that the tensor is of lowrank. Two of the most popular approaches for lowrank tensor completion are trace norm based approaches and decomposition based approaches. In the second part of the thesis, we propose two novel frameworks for lowrank tensor completion. First, we consider the standard batch mode setting where the tensor data is static and does not change with time. The second setting we consider is the dynamic setting, where the tensor can grow dynamically with time. In the dynamic setting, we also incorporate additional side information matrices that can be available along different modes of the tensor.
For the first setting, we propose a trace norm based approach by proposing a novel regularizer based on the latent trace norm. This regularizer helps in learning a nonsparse combination of tensors, which helps in achieving better tensor completion results on multiple datasets. We propose two novel optimization formulations, which are shown to lie on a cartesian product of Riemannian spectrahedron manifolds. We propose Riemannian trust region algorithms for solving the formulations. For the second setting, we propose an inductive framework called Side Information infused Incremental Tensor Analysis (SIITA) for the problem of dynamic tensor completion. Most of the existing approaches for dynamic tensor completion make a restrictive assumption that the tensor grows only along one mode, but SIITA can handle the more general setting called multiaspect streaming setting where the tensor is allowed to grow in all modes. SIITA incorporates side information into dynamic tensor completion and can also model sparsity, first ever dynamic tensor completion algorithm to do so to the best of our knowledge. We also show how nonnegative constraints can be incorporated into SIITA which is essential for learning interesting clusters in an unsupervised setting. Through extensive experiments on multiple real world datasets across various tasks, we illustrate the efficacy of proposed lowrank tensor completion algorithms.
 Series: Department Seminar Title: Proofs of Replicated Storage Without Timing Assumptions  Speaker: Dr. Chaya Ganesh
Postdoctoral Researcher
Aarhus Crypto group
Department of Computer Science
Aarhus University
Denmark  Date and Time: Thursday, November 22, 2018, 11:00 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract In this work we provide a formal treatment of proof of replicated storage, a novel cryptographic primitive recently proposed in the context of a novel cryptocurrency, namely Filecoin.
In a nutshell, proofs of replicated storage is a solution to the following problem: A user stores a file m on n different servers to ensure that the file will be available even if some of the servers fail. Using proof of retrievability, the user could check that every server is indeed storing the file. However, what if the servers collude and, in order to save on resources, decide to only store one copy of the file? A proof of replicated storage guarantees that, unless the server is indeed storing n copies of the file, the user will not accept the proof.
While some candidate proofs of replicated storage have already been proposed, their soundness relies on timing assumptions, that is, the user must reject the proof if the prover does not reply within a certain timebound.
In this paper we provide the first construction of a proof of replication which does not rely on any timing assumptions.
This is joint work with Ivan Damgård and Claudio Orlandi.
Speaker Bio: Chaya Ganesh is a postdoctoral researcher at the Aarhus Crypto group. She graduated with a PhD from the Courant Institute of Mathematical Sciences, New York University under the supervision of Prof. Yevgeniy Dodis. Chaya has worked on zero knowledge proofs, secure computation and consensus protocols during doctoral studies. She is currently working on efficient ZK proofs, blockchain style consensus protocols and maintains broad interest in theoretical and applied Cryptography.
Host Faculty: Dr. Arpita Patra
 Series: Department Seminar Title: Orca: Differential Bug Localization in LargeScale Services  Speaker: Dr. Ranjita Bhagwan
Microsoft Research India  Date and Time: Friday, November 16, 2018, 2:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Today, we depend on numerous largescale services for basic operations such as email. These services are complex and extremely dynamic as developers continously commit code and introduce new features, fixes and, consequently, new bugs. Hundreds of commits may enter deployment simultaneously. Therefore one of the most timecritical, yet complex tasks towards mitigating service disruption is to localize the bug to the right commit.
This paper presents the concept of differential bug localization that uses a combination of differential code analysis and software provenance tracking to effectively pinpoint buggy commits. We have built Orca, a customized code searchengine that implements differential bug localization. Orca is actively being used by the OnCall Engineers (OCEs) of a large enterprise email and collaboration service to localize bugs to the appropriate buggy commits. Our evaluation shows that Orca correctly localizes 77% of bugs for which it has been used. We also show that it causes a 4x reduction in the work done by the OCE.
Speaker Bio: Ranjita Bhagwan is a researcher at Microsoft Research India. Previously, she was a research staff member at IBM T. J. Watson Research in Hawthorne, NY, USA. Prior to that, she completed my PhD in 2004 from the University of California at San Diego. She received my B. Tech in Computer Science and Engineering from IIT Kharagpur in 1998.
My interests are mainly in solving problems related to Networking and Distributed Systems. Most recently, she has been working on improving systems using machinelearning. She also work on Cloud securityrelated projects.
Host Faculty: Prof. Vinod Ganapathy
 Series: Ph.D. Colloquium Title: On Representations and Spectral Inequalities for NonUniform Hypergraphs  Speaker: Mr. Ashwin Guha
 Faculty Advisor: Prof. Ambedkar Dukkipati
 Date and Time: Friday, November 16, 2018, 12:00 PM
 Venue: CSA Faculty Room, (Room No. 101, Ground floor)
Abstract Spectral graph theory involves the study of the eigenvalues and eigenvectors of graph
connectivity matrices such as the adjacency matrix, Laplacian or the signless Laplacian.
Spectral methods have often proved to be efficient and are widely used in solving problems
where the underlying objects can be represented by graphs. While graph theory has a
variety of applications, it has often been observed in many realworld instances that the
pairwise relationships captured in graphs do not describe the data in its entirety. To
overcome this limitation, the notion of hypergraphs was introduced. Hypergraphs are a
general version of a graph, where an edge may span more than two nodes. They have been
studied extensively from a combinatorial perspective. Recently there has been renewed
interest in applying spectral methods to problems in hypergraphs, especially hypergraph
partitioning and community detection, which have applications in machine learning. In
order to employ spectral techniques, a crucial issue that needs to be addressed is the
appropriate representation of the hypergraphs.
In this work, we consider various representations of hypergraphs to study their spectral properties. These representations include some matrixbased representations such
as clique expansion, star expansion, simplicial complexes and tensor representations. We
present a comparative study of the representations and study how one can extend existing
results for 2graphs to hypergraphs, in particular, to nonuniform hypergraphs. We define
a Laplacian in each of the representation and study its spectrum. We also provide bounds
for the largest and the second smallest eigenvalue of the Laplacians in terms of each of
the representations.
One of the most important results in spectral graph theory is the Cheeger inequality, which
relates the isoperimetric number of a graph and the second smallest eigenvalue of the
graph Laplacian. We provide a generalized version of Cheeger inequality for nonuniform
hypergraphs using the weighted clique approach as well as using a tensor approach. This
is our main contribution of this work. We then compare these results with the existing
Cheeger inequality for simplicial complexes. In addition, we also provide a conjecture on
a generalized Mixing Lemma for simplicial complexes.
 Series: Ph.D. Thesis Defense Title: Stochastic Approximation With SetValued Maps And Markov Noise : Theoretical Foundations And Applications  Speaker: Mr. Vinayaka Ganapati Yaji
Ph.D student
Dept. of CSA  Faculty Advisor: Prof. Shalabh Bhatnagar
 Date and Time: Friday, November 16, 2018, 11:00 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Stochastic approximation algorithms produce estimates of a desired solution using noisy real world data. Introduced by Robbins and Monro, in 1951, stochastic approximation techniques have been instrumental in the asymptotic analysis of several adaptive algorithms in learning, signal processing and control. A popular method for the analysis of stochastic approximation schemes is the dynamical systems approach or the o. d. e. method introduced by Ljung and developed further extensively by Benaim and Hirsch. We build upon the works of Benaim et. al., and Bhatnagar et. al., and present the asymptotic analysis of stochastic approximation schemes with setvalued drift functions and nonadditive Markov noise. The frameworks studied by us are under the weakest set of assumptions and encompass a majority of the methods studied to date. We first present the asymptotic analysis of stochastic approximation schemes with setvalued drift function and nonadditive iteratedependent Markov noise. We show that a linearly interpolated trajectory of such a recursion is an asymptotic pseudo trajectory for the flow of a limiting differential inclusion obtained by averaging the setvalued
drift function of the recursion with respect to the stationary distributions of the Markov noise. The limit set theorem by Benaim is then used to characterize the limit sets of the recursion in terms of the dynamics of the limiting differential inclusion. The analysis presented allows us characterize the asymptotic behavior of controlled stochastic approximation, subgradient descent, approximate drift problem and analysis of discontinuous dynamics all in the presence of nonadditive iteratedependent Markov noise.
Next we present the asymptotic analysis of a stochastic approximation scheme on two timescales with setvalued drift functions and in the presence of nonadditive iteratedependent Markov noise. It is shown that the recursion on each timescale tracks the flow of a differential inclusion obtained by averaging the setvalued drift function in the recursion with respect to a set of measures which take into account both the averaging with respect to the stationary distributions of the Markov noise terms and the interdependence between the two recursions on different timescales.
Finally, we present the analysis of stochastic approximation schemes with setvalued maps in the absence of a stability guarantee. We prove that after a large number of iterations if the stochastic approximation process enters the domain of attraction of an attracting set it gets locked into the attracting set with high probability. We demonstrate that the above result is an effective instrument for analyzing stochastic approximation schemes in the absence of a stability guarantee, by using it to obtain an alternate criterion for convergence in the presence of a locally attracting set for the mean field and by using it to show that a feedback mechanism, which involves resetting the iterates at regular time intervals, stabilizes the scheme when the mean field possesses a globally attracting set, thereby guaranteeing convergence. Our results build on the works of Borkar, Andrieu et al., and Chen et al., by allowing for the presence of setvalued drift functions.
 Series: Department Seminar Title: LevioSA: Lightweight Secure Arithmetic Computation  Speaker: Prof. Muthuramakrishnan Venkitasubramaniam
Associate Professor
Department of Computer Science
University of Rochester
USA  Date and Time: Thursday, November 15, 2018, 4:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract We study the problem of secure twoparty computation of arithmetic circuits. This problem is motivated by privacypreserving numerical computations, such as ones arising in the context of machine learning training and classification. Recent works on the problem have mainly focused on passively secure protocols, whose security holds against passive (``semihonest'') parties but may completely break down in the presence of active (``malicious'') parties who can deviate from the protocol.
In this work, we design, optimize, and implement an actively secure protocol for secure twoparty arithmetic computation. A distinctive feature of our protocol is that it can make a fully modular blackbox use of any passively secure implementation of oblivious linear function evaluation (OLE). OLE is a commonly used primitive for secure arithmetic computation, analogously to the role of oblivious transfer in secure Boolean computation.
For typical circuits, our protocol requires roughly 4 invocations of passively secure OLE per multiplication gate. This significantly improves over the recent TinyOLE protocol (Döttling et al., ACM CCS 2017), which requires 22 invocations of actively secure OLE in general, or 44 invocations of a specific codebased passively secure OLE.
We showcase the efficiency of our protocol by applying it to standard benchmarks. Our protocol can be applied for a securely outsourcing neural network classification system. This is the first actively secure implementation of its kind, strengthening the passive security provided by recent related works (Mohassel and Zhang, IEEE S&P 2017; Juvekar et al., USENIX 2018).
This is joint work with Carmit Hazay, Yuval Ishai and Antonio Marcedone
Speaker Bio: Muthu Venkitasubramaniam is an Associate Professor at the University of Rochester. He received his BTech degree in computer science from the Indian Institute of Technology, Madras in 2004. He attended Cornell University, where he worked with Rafael Pass receiving his Ph.D. in computer science in 2011. Before arriving at the University of Rochester, he spent a year at the Courant Institute of Mathematical Sciences (NYU) as a postdoctoral researcher supported by the Computing Innovation Fellowship. Muthu's interests are in the theory and practice of Cryptography and Network Security. He is a recipient of the Google Faculty Research award and his work on "LDiversity: Privacy beyond KAnonymity" received the ICDE 2017 Influential Paper Award.
Host Faculty: Dr. Arpita Patra
 Series: Department Seminar Title: Systems Research for Deep Learning / AI  Speaker: Dr. Muthian Sivathanu
Microsoft Research India  Date and Time: Wednesday, November 14, 2018, 2:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract The remarkable success and popularity of deep learning over the last decade has been primarily enabled due to systems advances – the theory behind deep learning is several decades old. Future innovation in deep learning will also be gated on systems research, in terms of compute efficiency and scale.
In this talk, I will describe two systems we have built, that make significant improvements to the efficiency of the deep learning (DL) workflow, primarily focused on deep learning training. The first system is Gandiva, a cluster scheduler for efficiently running DL training jobs in a large cluster of GPUs. The second system is Astra, a compiler and optimizing runtime tailored to the characteristics of DL jobs, that improves the throughput of DL training. Both these systems adopt an approach of careful vertical codesign – by tailoring the infrastructure stack to the specific traits of the workload, they achieve significant efficiency improvements, both in cost and training time.
I will conclude with some brief thoughts on the critical role of systems research in today’s computing landscape.
Speaker Bio: Muthian Sivathanu is a principal researcher at Microsoft Research India, specializing in distributed systems, operating systems, blockchains, and systems for machine learning and information retrieval. Prior to joining Microsoft Research, he worked at Google for about 10 years, mostly focusing on building key infrastructure powering Google web search (in particular, the query engine for web search). Muthian obtained his PhD from UW Madison in 2005, and a BE from CEG Anna University in 2000.
Host Faculty: Arkaprava Basu
 Series: CSA Faculty Colloquium Title: Role of Centrality and Diversity in Search  Speaker: Prof. M. Narasimha Murty
Professor
Dept.of CSA  Date and Time: Friday, November 09, 2018, 4:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Centrality and diversity are two important notions that influence internet search and several machine learning tasks including clustering and classification. They are also important in analysing communities in social networks. In this talk the role of centrality and diversity in a variety of these tasks will be examined and a novel task of diverse grouping will be explored.
Speaker Bio: M Narasimha Murty is a Professor at the Indian Institute of Science. His area
of interest is pattern recognition. He received his PhD from the Indian
Institute of Science, Bangalore and he had joined the department of Computer Science and Automation as an assistant professor in 1984.
Host Faculty: Prof. Sunil L Chandran & Prof. Shalabh Bhatnagar
 Series: Research Student Colloquium Title: 1) An Approach for Finding Loop Permutations Quickly: Fusion and Dimension Matching
2) Inductive Framework for MultiAspect Streaming Tensor Completion with Side Information  Speaker: 1) Aravind Acharya N
2) Madhav Ram Nimishakavi  Date and Time: Friday, November 02, 2018, 4:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract 1) Polyhedral loop transformations have been proven to be powerful in the the
context of loop optimizations. Stateoftheart algorithms used in automatic
polyhedral transformation for parallelization and locality optimization
typically rely on Integer Linear Programming (ILP). This poses a scalability
issue when scaling to tens or hundreds of statements, and may be disconcerting
in production compiler settings. Plutolpdfp framework overcomes this issue by
(i) using Linear Programming instead of ILP and (ii) decoupling
autotransformation into loop fusion and permutation, loop scaling and shifting,
and loop skewing components.
The focus of this talk will be on finding loop fusion and permutations quickly.
We construct a fusion conflict graph (FCG), which models all possible fusion and
permutations that enable tiling. We propose a convex colouring heuristic that
enables us to infer permutations from the fusion conflict graph. We also observe
that various loop fusion models, for example typed fuse, can be effectively
implemented in using the FCG. Finally, with statement clustering heuristics, we
show that good polyhedral transformations can be found in polynomial time.
2) Low rank tensor completion is a well studied problem and has applications in various fields. However, in many real world applications the data is dynamic, i.e., new data arrives at different time intervals. As a result, the tensors used to represent the data grow in size. Besides the tensors, in many real world scenarios, side information is also available in the form of matrices which also grow in size with time. The problem of predicting missing values in the dynamically growing tensor is called dynamic tensor completion. Most of the previous work in dynamic tensor completion make an assumption that the tensor grows only in one mode. To the best of our Knowledge, there is no previous work which incorporates side information with dynamic tensor completion. We bridge this gap by proposing a dynamic tensor completion framework called Side Information infused Incremental Tensor Analysis (SIITA), which incorporates side information and works for general incremental tensors. We also show how nonnegative constraints can be incorporated with SIITA, which is essential for mining interpretable latent clusters. We carry out extensive experiments on multiple real world datasets to demonstrate the effectiveness of SIITA in various different settings.
Host Faculty: Prof. Sunil Chandran & Prof. Shalabh Bhatnagar
 Series: Department Seminar Title: Finding Minors in Sublinear time in Bounded degree graphs with (almost) optimal onesided query complexity  Speaker: Mr. Akash Kumar
Ph.D. student
Purdue University
USA  Date and Time: Monday, October 29, 2018, 11:00 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Let G be an undirected, bounded degree graph with n vertices. Fix a finite graph H, and suppose one must remove eps n edges from G to make it Hminor free (for some small constant eps > 0). We give an n^{1/2 + o(1)}time randomized procedure that, with high probability, finds an Hminor in such a graph. For an example application, suppose one must remove eps n edges from a bounded degree graph G to make it planar. This result implies an algorithm, with the same running time, that produces a K_3,3 or K_5 minor in G. No sublinear time bound was known for this problem, prior to this result.
By the graph minor theorem, we get an analogous result for any minorclosed property. Up to n^{o(1)} factors, this resolves a conjecture of BenjaminiSchrammShapira (STOC 2008) on the existence of onesided property testers for minorclosed properties. Furthermore, our algorithm is nearly optimal, by an Omega(sqrt n) lower bound of Czumaj et al (RSA 2014).
Prior to this work, the only graphs H for which nontrivial property testers were known for Hminor freeness are the following: H being a forest or a cycle (Czumaj et al, RSA 2014), K_2,k / the kby2grid / and the kcircus (Fichtenberger et al, Arxiv 2017).
Host Faculty: Dr. Anand Louis

