Department of Computer Science and Automation Department of Computer Science and Automation, IISc, Bangalore, India Indian Institute of Science
HOME | ABOUT US | PEOPLE | RESEARCH | ACADEMICS | FACILITIES | EVENTS / SEMINARS | NEWS | CONTACT US

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

Video Archive Go Top

 

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

Video Archive Go Top

 

Series: Department Seminar
Title: Towards Low-Cost 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 off-chip main memory is essential for protection from adversaries with physical access to systems. Current secure-memory designs, such as Intel SGX, incur significant slowdown, mainly due to the extra accesses required to obtain the security-related metadata -- counters for encryption, MAC for integrity check, and Merkle-tree 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 co-locating 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 Merkle-Tree by packing more counters per cache line. This solution, called Morphable Counter, can pack 2x more counters per line than state-of-the-art by adapting the counter format to suit the application requirement. Finally, I will also briefly discuss our MICRO-2018 work on protecting cache memories from eviction-based 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 (2007-2011) at IBM T.J. Watson Research Center, where he investigated the caching algorithms for Power-7 processors and won the Outstanding Technical Achievement (OTA) award for studying non-volatile memories for servers. He holds more than two-dozen U.S. patents. His publications have received more than 7500 citations, including two lead-author papers with more than 1000 citations each. He served as the Program Chair for MICRO 2015 and as the selection committee co-chair for IEEE MICRO Top Picks 2017. He is a member of the Hall-of-Fame of ISCA, Hall-of-Fame of MICRO, and Hall-of-Fame of HPCA. He is a recipient of the Intel Faculty Award, NetApp Faculty Fellowship, MICRO-2018 best paper award, two IEEE MICRO Top-Pick 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

Video Archive Go Top

 

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 in-memory 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, energy-efficient, reliable, and secure general-purpose 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

Video Archive Go Top

 

Series: Department Seminar
Title: Improved Algorithms for MST and Metric-TSP 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 MST-interdiction 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 G-R. Our main result is a 4-approximation algorithm for this problem. This improves upon the previous-best 14-approximation 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 over-budget 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, LP-relative 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 MST-interdiction yields an 8-approximation for metric-TSP interdiction. We also show that the maximum-spanning-tree interdiction problem is at least as hard to approximate as the minimization version of densest-k-subgraph. This is joint work with Andre Linhares.

Host Faculty: Dr. Siddharth Barman

Video Archive Go Top

 

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 fourth-year 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 IIT-Madras 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 2015-16 in UC Berkeley, Computer age management prize for the best academic performance in computer science during his junior year in IIT-Madras, Singapore technologies fellowship during 2012-14 for outstanding academic achievement and the Kishore Vaigyanik Protsahan Yojana (KVPY) fellowship in 2010.

Host Faculty: Dr. Bhavana Kanukurthi

Video Archive Go Top

 

Series: CSA Faculty Colloquium
Title: Automating Deductive Verification using Decision-Tree 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 Floyd-Hoare 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 model-checking that rely on exhaustive search of the state-space 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 counter-examples provided by the verification engine to previously conjectured invariants. In this talk we describe a decision-tree based approach to doing this, and highlight some of the challenges in adapting classical decision-tree 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 real-time and hybrid systems.

Host Faculty: Prof. Sunil L Chandran & Prof. Shalabh Bhatnagar

Video Archive Go Top

 

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 cost-per-bit. 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 high-density 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 system-level 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 Melded-Page. 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 block-erases 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.

Video Archive Go Top

 

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 Ben-David, Adam Bouland and Robin Kothari.

Host Faculty: Dr. Anand Louis

Video Archive Go Top

 

Series: Department Seminar
Title: Betti Numbers of Gaussian Excursions in the Sparse Regime

  • Speaker: Dr. Gugan Thoppe
                   Post-Doctoral 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 sub-domain 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 super-level sets of suitable value functions. In robotics, in order to plan its motion, a sensor robot may want to identify the sub-terrain 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 so-called `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 non-vanishing phase transition with a precise estimate of the transition threshold, and a weak law in the non-vanishing 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 Post-Doctoral 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 TAA-Sasken best thesis award for 2017. He is also a two-time recipient of the IBM PhD fellowship award (2013–14 and 2014-15). His research interests include random topology and stochastic approximation. In random topology, he has looked at topological evolutions in dynamic Erdos-Renyi 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 Erdos-Renyi 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 non-linear 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

Video Archive Go Top

 

Series: Ph.D. Colloquium
Title: Relation Schema Induction using Tensor Factorization and Algorithms for Low-rank 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 multi-way 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 Higher-order 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 Matrix-Tensor 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 Back-off and Aggregation (TFBA). TFBA jointly factorizes multiple tensors as the first step and then performs aggregation for constructing higher-order (or n-ary) 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 low-rank. Two of the most popular approaches for low-rank tensor completion are trace norm based approaches and decomposition based approaches. In the second part of the thesis, we propose two novel frameworks for low-rank 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 non-sparse 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 multi-aspect 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 non-negative 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 low-rank tensor completion algorithms.

Video Archive Go Top

 

Series: Department Seminar
Title: Proofs of Replicated Storage Without Timing Assumptions

  • Speaker: Dr. Chaya Ganesh
                   Post-doctoral 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 time-bound.

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 post-doctoral 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

Video Archive Go Top

 

Series: Department Seminar
Title: Orca: Differential Bug Localization in Large-Scale 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 large-scale 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 time-critical, 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 pin-point buggy commits. We have built Orca, a customized code search-engine that implements differential bug localization. Orca is actively being used by the On-Call 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 machine-learning. She also work on Cloud security-related projects.

Host Faculty: Prof. Vinod Ganapathy

Video Archive Go Top

 

Series: Ph.D. Colloquium
Title: On Representations and Spectral Inequalities for Non-Uniform 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 real-world instances that the pair-wise 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 matrix-based 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 2-graphs to hypergraphs, in particular, to non-uniform 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 non-uniform 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.

Video Archive Go Top

 

Series: Ph.D. Thesis Defense
Title: Stochastic Approximation With Set-Valued 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 set-valued drift functions and non-additive 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 set-valued drift function and non-additive iterate-dependent 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 set-valued 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 non-additive iterate-dependent Markov noise.

Next we present the asymptotic analysis of a stochastic approximation scheme on two timescales with set-valued drift functions and in the presence of non-additive iterate-dependent Markov noise. It is shown that the recursion on each timescale tracks the flow of a differential inclusion obtained by averaging the set-valued 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 set-valued 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 set-valued drift functions.

Video Archive Go Top

 

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 two-party computation of arithmetic circuits. This problem is motivated by privacy-preserving 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 (``semi-honest'') 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 two-party arithmetic computation. A distinctive feature of our protocol is that it can make a fully modular black-box 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 code-based 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 "L-Diversity: Privacy beyond K-Anonymity" received the ICDE 2017 Influential Paper Award.

Host Faculty: Dr. Arpita Patra

Video Archive Go Top

 

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 co-design – 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

Video Archive Go Top

 

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

Video Archive Go Top

 

Series: Research Student Colloquium
Title: 1) An Approach for Finding Loop Permutations Quickly: Fusion and Dimension Matching 2) Inductive Framework for Multi-Aspect 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. State-of-the-art 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. Pluto-lp-dfp framework overcomes this issue by (i) using Linear Programming instead of ILP and (ii) decoupling auto-transformation 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 non-negative 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

Video Archive Go Top

 

Series: Department Seminar
Title: Finding Minors in Sublinear time in Bounded degree graphs with (almost) optimal one-sided 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 H-minor free (for some small constant eps > 0). We give an n^{1/2 + o(1)}-time randomized procedure that, with high probability, finds an H-minor 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 minor-closed property. Up to n^{o(1)} factors, this resolves a conjecture of Benjamini-Schramm-Shapira (STOC 2008) on the existence of one-sided property testers for minor-closed 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 non-trivial property testers were known for H-minor freeness are the following: H being a forest or a cycle (Czumaj et al, RSA 2014), K_2,k / the k-by-2-grid / and the k-circus (Fichtenberger et al, Arxiv 2017).

Host Faculty: Dr. Anand Louis

Video Archive Go Top

 

 

 

 

 

 

 

 

 

 

Copyright: CSA, IISc 2018      Phone: +91-80-22932368          Fax: +91-80-23602911 Travel Blog    Feedback    Credits