Events 

Seminars 

Golden Jubilee Frontier Lectures 

Prof. I. G. Sarma Memorial Lecture Series 

Prof. Priti Shankar Memorial Seminar Series 

Multimedia Archive 



UPCOMING SEMINARS 

Series: Ph.D. Colloquium Title: Neural Graph Embedding methods for Natural Language Processing  Speaker: Mr. Shikhar Vashishth
PhD Student
Dept. of CSA  Faculty Advisor: Dr. Partha Pratim Talukdar & Prof. Chiranjib Bhattacharyya
 Date and Time: Thursday, October 31, 2019, 3:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Graphs are all around us, ranging from citation and social networks to Knowledge Graphs (KGs). They are one of the most expressive data structures which have been used to model a variety of problems. Knowledge graphs are structured representations of facts in a graph, where nodes represent entities and edges represent relationships between them. Recent research has resulted in the development of several large KGs; examples include DBpedia, YAGO, NELL, and Freebase. However, all of them tend to be sparse with very few facts per entity. For instance, NELL KG consists of only 1.34 facts per entity. In the first part of the thesis, we propose three solutions to alleviate this problem: (1) KG Canonicalization, i.e., identifying and merging duplicate entities in a KG, (2) Relation Extraction which involves automating the process of extracting semantic relationships between entities from unstructured text, and (3) Link prediction which includes inferring missing facts based on the known facts in a KG. For KG Canonicalization, we propose CESI (Canonicalization using Embeddings and Side Information), a novel approach that performs canonicalization over learned embeddings of Open KGs. The method extends recent advances in KG embedding by incorporating relevant NP and relation phrase side information in a principled manner. For relation extraction, we propose RESIDE, a distantlysupervised neural relation extraction method which utilizes additional side information from KGs for improved relation extraction. Finally, for link prediction, we propose InteractE which extends ConvE, a convolutional neural networkbased link prediction method, by increasing the number of feature interaction through three key ideas – feature permutation, a novel feature reshaping, and circular convolution. Through extensive experiments on multiple datasets, we demonstrate the effectiveness of our proposed methods.
Traditional Neural Networks like Convolutional Networks and Recurrent Neural Networks are constrained to handle Euclidean data. However, graphs in Natural Language Processing (NLP) are prominent. Recently, Graph Convolutional Networks (GCNs) have been proposed to address this shortcoming and have been successfully applied for several problems. In the second part of the thesis, we utilize GCNs for Document Timestamping problem, which forms an essential component of tasks like document retrieval, and summarization.
For this, we propose NeuralDater which leverages GCNs for jointly exploiting syntactic and temporal graph structures of document for obtaining stateoftheart performance on the problem. We also propose SynGCN, a flexible Graph Convolution based method for learning word embeddings which utilize dependency context of a word instead of linear context for learning more meaningful word embeddings. In this third part of the thesis, we address two limitations of existing GCN models, i.e., (1) The standard neighborhood aggregation scheme puts no constraints on the number of nodes that can influence the representation of a target node. This leads to a noisy representation of hubnodes which coves almost the entire graph in a few hops. To address this shortcoming, we propose ConfGCN (Confidencebased GCN) which estimates confidences to determine the importance of a node on another during aggregation, thus restricting its influence neighborhood. (2) Most of the existing GCN models are limited to handle undirected graphs. However, a more general and pervasive class of graphs are relational graphs where each edge has a label and direction associated with it. Existing approaches to handle such graphs suffer from overparameterization and are restricted to learning representation of nodes only. We propose CompGCN, a novel Graph Convolutional framework which jointly embeds entity and relations in a relational graph. CompGCN is parameter efficient and scales with the number of relations. It leverages a variety of entityrelation composition operations from KG Embedding techniques and achieves demonstrably superior results on node classification, link prediction, and graph classification tasks.
 Series: Department Seminar Title: Recent Progress in Code Obfuscation  Speaker: Dr Venkata Koppula,
Postdoctoral Research Fellow, Weizmann Institute  Date and Time: Friday, October 25, 2019, 11:00 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Code obfuscation has been one of the main focal points of cryptographic research over the last few years. A code obfuscator is a compiler that hides the implementation of programs while preserving functionality. Barak et al showed that the most desirable definition of code obfuscation  virtual black box (VBB) obfuscation  is impossible for general functions. Therefore, we must either restrict our attention to weaker notions of obfuscation, or study obfuscation for restricted classes of functions. In this talk, I will first discuss one such weaker notion of obfuscation (called indistinguishability obfuscation) and its tremendous impact on cryptography.
Next, I will present a VBB obfuscation scheme for a restricted but useful function class. We call this notion `lockable obfuscation'. Our obfuscation scheme's security is based on standard cryptographic assumptions. At the same time, it has a number of applications, for upgrading security of encryption schemes as well as showing separations between different security notions. I will present one such application, followed by a brief discussion of how research related to indistinguishability obfuscation led to this result.
Based on joint work with Rishab Goyal and Brent Waters, and no prior background on obfuscation/crypto will be needed.
Speaker Bio: Venkata Koppula is a postdoctoral researcher at the Weizmann Institute of Science, hosted by Zvika Brakerski. Prior to this, he was a graduate student at the University of Texas at Austin, where his advisor was Brent Waters. He is interested in the theoretical aspects of cryptography.
Host Faculty: Prof. Matthew Jacob
 Series: Department Seminar Title: Does PD Control Always Work for Robotic Systems?  Speaker: Dr Shishir N Y Kolathaya,
INSPIRE Faculty Fellow, RBCCPS, IISc  Date and Time: Tuesday, October 22, 2019, 11:00 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract In 2015, a committee created by the International Federation of Automatic Control (IFAC) surveyed its members to obtain their views on the impact of advanced control in industries. PID control was first with a 100% highimpact rating, and nonlinear control was tenth with a 22% rating. Clearly, despite great advances in the theory of nonlinear controls,PD and PID tracking control laws continue to be the most popular choice. This is true even for robotic systems. Therefore, the goal of the talk is to understand some of the stability guarantees provided by PD control laws in the context of robotic systems.
The talk is divided into two parts. First, we will discuss existing stability results for PD controlled robotic systems. Some of these results were established as early as the 1980's. Second, we will extend these stability properties to underactuated and hybrid robotic systems i.e., by introducing additional assumptions on the unactuated coordinates of the robot. We will demonstrate these results on bipedal walking robots, which are known to be textbook examples for hybrid robotic systems. Bipedal robots have the legswing as the continuous event, and the footstrike as the discrete event, and these events alternate during walking. In addition, bipeds largely have underactuations due to the interactions between feet and ground. For each continuous event, we establish that the convergence rate of the tracking error can be regulated via appropriate tuning of the PD gains, and for each discrete event, we establish that this convergence rate sufficiently overcomes the nonlinear impacts by assumptions on the hybrid zero dynamics. Towards the end, we will validate these results on a 5link bipedal walker in simulation.
Speaker Bio: Shishir is an INSPIRE Faculty fellow in the Robert Bosch Center for Cyber Physical Systems (RBCCPS) in IISc Bangalore. He received his Ph.D. degree in Mechanical Engineering (2016) from the Georgia Institute of Technology, M.S. degree in Electrical Engineering (2012) from Texas A&M University, and B.Tech degree in Electrical & Electronics Engineering (2008) from National Institute of Technology Karnataka. His primary focus as a Ph.D. student was on stability and control of walking robots. Shishir is currently interested in safetycritical control, stability of hybrid systems, and deep reinforcement learning for all kinds of robotic platforms.
Host Faculty: Prof. Matthew Jacob
 Series: Department Seminar Title: FaultTolerant Reachability and Strongconnectivity Structures  Speaker: Dr Keerti Choudhary
 Date and Time: Friday, October 18, 2019, 11:00 AM
 Venue: CSA Lecture Hall (Room No. 117, Ground Floor)
Abstract Reachability and strongconnectivity are some of the fundamental graph problems. In the static setting, both problems can be solved in O(m+n) time for any directed graph G with n vertices and m edges. However, most realworld networks are prone to failures. The failures are transient and occur for a small duration of time. Under such a setting, we would like to preprocess the graph to compute datastructures that can achieve robustness by being functional even after the occurrence of failures. In recent years, researchers have studied various questions pertaining to connectivity, distances, routing, mincuts, etc. in the domain of fault tolerance networks.
In this talk, I will discuss the following questions:
1. Can we compute a reachability tree in just linear time, after the occurrence of a small number of failures?
2. How fast can we compute the strongly connected components, again on the occurrence of failures?
3. Does there exist a sparse certificate for these structures that remains valid even after a bounded number of failures?
The solutions to these problems employ extremely basic tools like maxflows, mincuts, and heavypathdecomposition.
Speaker Bio: Keerti Choudhary is a postdoctoral fellow in the Computer Science department at Tel Aviv University, where she is hosted by Shiri Chechik. Prior to this, she was a postdoctoral fellow at the Weizmann Institute of Sciences (Oct 2017  Sept 2019), where her host was David Peleg. Keerti completed her Ph.D. in Computer Science from IIT Kanpur in August 2017, where she was advised by Surender Baswana. She is also a 2013 graduate from the Mathematics department at IIT Kanpur.
https://sites.google.com/view/keerti/
Host Faculty: Prof. Matthew Jacob


PAST SEMINARS 

Series: CSA Faculty Colloquium Title: Abstract Interpretation  a framework for verifying correctness of programs  Speaker: Prof. K. V. Raghavan
Associate Professor
Dept. of CSA
IISc  Date and Time: Friday, October 04, 2019, 4:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Abstract Interpretation is a technique for static analysis of
programs. The objective of any static analysis technique is to identify
whether a property of interest holds across all executions of a program
without running the program at all. Abstract interpretation has certain
unique advantages: (1) It is a framework, in that it can be customized by a
user to analyze any property of interest. (2) It is safe, in that it
declares a property as holding only if it provably holds in all possible
runs of the program. (3) Implementations of it are provided by many tools,
for various prevalent programming languages. (4) It is efficient in
practice, even on very large programs. In this talk we will explore
abstract interpretation by going over some examples involving it, by
taking a look at the mathematical theory underlying it, and by looking at
its usage in practical settings.
Speaker Bio: K. V. Raghavan is an Associate Professor at the Department of Computer
Science and Automation, Indian Institute of Science, Bangalore.
His areas of interest are program analysis and
verification, programming tools, and formal methods in software engineering.
Host Faculty: Prof. Sunil L Chandran & Prof. Shalabh Bhatnagar
 Series: Department Seminar Title: Static Analysis for Detecting HighLevel Races in RTOS Kernels  Speaker: Rekha Pai
 Date and Time: Monday, September 30, 2019, 4:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract We propose a static analysis based approach for detecting
highlevel races in RTOS kernels popularly used in safetycritical
embedded software. HighLevel races are indicators of atomicity violations
and can lead to erroneous software behaviour with serious consequences.
Hitherto techniques for detecting highlevel races have relied on model
checking approaches, which are inefficient and apriori unsound. In contrast
we propose a technique based on static analysis that is both efficient
and sound. The technique is based on the notion of disjoint blocks recently
introduced in Chopra et al. We evaluate our technique on three
popular RTOS kernels and show that it is effective in detecting races,
many of them harmful, with a high rate of precision.
This is joint work with Abhishek Singh (IIIT Bangalore), Deepak D'Souza (IISc),
and Meenakshi D'Souza (IIIT Bangalore). The work will be presented at the Formal
Methods Symposium in Porto, Portugal, next month.
Speaker Bio: Rekha Pai is a Kothari PostDoctoral Fellow at the Computer Science and Automation department, IISc, Bangalore. Her interests are in Code Transformation and Static Race Detection.
Host Faculty: Deepak D'Souza
 Series: Department Seminar Title: Program Synthesis meets Machine Learning  Speaker: Sriram Rajamani
 Date and Time: Friday, September 20, 2019, 4:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract We give a tutorial overview of program synthesis, from its first formulation by Church in 1957, through its pragmatic evolution through sketching and programingbyexamples, and compare program synthesis with supervised machine learning. We then present our recent efforts (together with colleagues) in combining program synthesis and machine learning techniques to solve the problem of synthesizing extractors from heterogeneous data, as well as in solving NLP problems. Finally, we explore several opportunities at the intersection of program synthesis (and more broadly the PL community) and machine learning, such as pruning and ranking programs during synthesis, neural program synthesis and automatic differentiation. Towards the end, we will briefly outline plans for a course we are planning with Prof. Deepak D’Souza and Prof. Chiranjib Bhattacharyya in the Jan 2020 semester on this broad topic.
Speaker Bio: Sriram Rajamani is Distinguished Scientist and Managing Director of Microsoft Research India. His research interests are in designing, building and analyzing computer systems in a principled manner. Over the years he has worked on various topics including Hardware and Software Verification, Type Systems, Language Design, Distributed Systems, Security and Privacy. His current research interest is in combining Program Synthesis and Machine Learning.
Host Faculty: Deepak D'Souza
 Series: Department Seminar Title: Term modal logic  Speaker: Anantha Padmanabha
 Date and Time: Thursday, September 19, 2019, 12:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Modal logic has been ubiquitously used in many fields of computer
science including verification, epistemic logic etc. Typically we have
two modal operators "Box" and "Diamond" which in a broad sense refers
to "necessity" and "possibility" respectively. For instance, (Box_i
alpha) in an epistemic setting means that "Reasoner i knows that
alpha". Similarly, (Diamond_i alpha) in the context of a system of
processes is interpreted as "Process i can possibly change the system
configuration to a state where alpha holds". These reasoners or
process index are referred to as agents in general.
Classically, the number of agents is assumed to be fixed and finite.
But in many settings like multiprocess systems / clientserver
systems, we cannot fix the agent set beforehand. The active agents
change not only from one model to the other but also from one state to
the other in the same model. For instance, in multiprocess systems,
when the system configuration changes, some processes may be
terminated and some new ones may be created.
Term modal logic introduced by Fitting et.al is suitable to study such
settings, where we can state properties like "exists x Box_x alpha"
which means "there exists some process x such that any state update by
process x necessarily leads to a state where alpha holds".
In this talk we will look at term modal logic in some detail. This is
a joint work with R. Ramanujam
Speaker Bio: Anantha Padmanabha has recently submitted his PhD thesis in the Institute of Mathematical Sciences, Chennai.
Host Faculty: Deepak D'Souza
 Series: Theory Seminar Series Title: Breaking the $2^n$ Barrier in Secret Sharing  Speaker: Professor Vinod Vaikuntanathan
Associate Professor at MIT EECS
and CoFounder of Duality Technologies  Date and Time: Friday, September 13, 2019, 1:00 PM
 Venue: CSA Lecture Hall (Room No. 117, Ground Floor)
Abstract Informationtheoretic cryptography is full of open problems with a communicationcomplexity flavor. One such problem arises in the context of secret sharing for general access structures where there is a huge (exponential) gap between the best known upper and lower bounds. We will describe some recent progress on resolving some of these longstanding gaps in the context of secret sharing, CDS and PSM.
Based on work with Tianren Liu and Hoeteck Wee, at Crypto 2017, Eurocrypt 2017 and STOC 2018.
Speaker Bio: Professor Vinod Vaikuntanathan is an associate professor of computer science at MIT and the chief cryptographer at Duality Technologies. Vinod is the coinventor of most modern fully homomorphic encryption systems and many other latticebased (postquantum secure) cryptographic primitives. His work has been recognized with a George M. Sprowls PhD thesis award (2009), an IBM Josef Raviv Fellowship (2008), a Sloan Faculty Fellowship (2013), a Microsoft Faculty Fellowship (2014), an NSF CAREER Award (2014), a DARPA Young Faculty Award (2018), and a Harold E. Edgerton Faculty Award (2018). He holds SM and PhD degrees from MIT and a BTech degree from the Indian Institute of Technology Madras.
Host Faculty: Dr. Anand Louis
 Series: CSA Faculty Colloquium Title: Distributed algorithms for prototype selection and multilabel classification  Speaker: Dr. V. Susheela Devi
Principal Research Scientist
Dept. of CSA  Date and Time: Friday, September 06, 2019, 4:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract The Modified Condensed Nearest Neighbour (MCNN) algorithm is an
algorithm for prototype selection which gives good performance but the time
requirement is much higher than algorithms like Condensed Nearest Neighbour
(CNN) algorithm. A distributed approach called Parallel MCNN (pMCNN) is
proposed which cuts down the time required drastically. pMCNN has been used
for prototype selection on large and streaming data and results are presented
which shows good performance with saving in time.
The second part of the talk describes an algorithm for multilabel classification
for discrete data. Two improvements are carried out to reduce the complexity.
The first is feature selection which reduces both space and time complexity.
The second is to use a distributed approach to this problem.
Results show good performance as compared to standard techniques like MLKNN
(Multi label kNN). The use of feature selection and the distributed approach give
saving in the time required which is helpful when the data sizes are large.
Speaker Bio: V. Susheela Devi works in the Intelligent Systems group in the department.
Her areas of interest include pattern recognition, machine learning and soft
computing. She is the coordinator of the Pattern Analysis and Machine Intelligence
lab. She has handled courses such as Pattern Recognition, Data Mining,
Data Structures and Algorithms, Computational Methods of Optimization,
Artificial Intelligence and Soft Computing.
Host Faculty: Prof. Sunil L Chandran & Prof. Shalabh Bhatnagar
 Series: M.Tech (Research) Thesis Defense Title: Optimum Policy Adaptation Learning for uSD cards  Speaker: Mr. Abhinav Anand
M.Tech (Research)Student
Dept. of CSA  Faculty Advisor: Prof. Chiranjib Bhattacharyya
 Date and Time: Thursday, September 05, 2019, 10:00 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Machine Learning(ML) for Systems is a new and promising research area where performance of computer systems is optimized using machine learning methods. ML for Systems has outperformed traditional heuristics methods in various areas like learning memory access patterns in microarchitecture (Hashemi et. al), generating optimization heuristics using deep learning in compilers (Cummins et. al), avoiding unnecessary writes by efficient SSD caching using machine learning in storage systems (Wang et. al) etc. Systems for ML is another research area which is different from ML for Systems. In Systems for ML, focus is on designing specialized hardware for increasing computing capability for deep learning networks.
In this work, we apply machine learning to improve the performance and reliability of NAND flash based microSD(uSD) cards. In present scenario, NAND settings in uSD card are set heuristically to achieve desired performance. However manually tuning these configurations is very hard because of complex interactions between them and changing one can have a large and unexpected effect on another. This is where machine learning in storage systems is useful: manually it may not be possible to optimize thousands of NAND settings in uSD, but it's the type of exercise that machine learning systems excel at. However small storage devices like uSD cards are resource constrained. Therefore using ML algorithms on uSD card with low memory and computation power is in itself a challenge.
In comparison to SSDs, no workload characterization studies has been done for uSD cards. Thus we have no knowledge of existence of new patterns which in turn limits our understanding of policy space. Lot of research has been done to make SSDs firmware adaptive but current uSD firmware is nonadaptive in nature i.e it services all workloads using single policy. Another major issue is that uSD card is constrained on internal RAM and microprocessor, which restricts the use of computationally expensive ML algorithms.
To tackle these problem, we have proposed a machine learning based framework Optimum Policy Adaptation Learning(OPAL) to identify novel patterns and formulate targeted policies. The machine learning model in the controller of NAND flash will identify the incoming workload and map it to optimal policy thus making it adaptive for the incoming workloads. To the best our knowledge we are the first to collect workload data for uSD cards, categorize workloads into patterns, and design a computationally efficient adaptive firmware. Using OPAL we have achieved significant improvements in real world scenarios like 44 % reduction in file copy time and 54 % increase in the lifetime of card.
 Series: M.Tech (Research) Thesis Defense Title: Efficient and Secure Search over Encrypted Data  Speaker: Mr.Shah Akash Amritlal Rupa
M.Tech. (Research) Student
Dept. of CSA
IISc  Faculty Advisor: Prof. Sanjit Chatterjee
 Date and Time: Friday, August 30, 2019, 4:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Due to a variety of crucial benefits, enterprises outsource their data to cloud resident storage. The outsourced data needs to be stored in encrypted form on remote untrusted servers to preserve privacy. However, if the client has to retrieve the entire data and decrypt it in order to get results for a search query then that will defeat the purpose of outsourcing. A solution to this problem is Searchable Encryption that provides a reasonable tradeoff between security and efficiency.
Our first contribution is in the context of Dynamic Searchable Symmetric Encryption (DSSE). DSSE schemes, apart from providing support for search operation, allows a client to perform update operations on outsourced database efficiently. Two security properties, viz., forward privacy and backward privacy are desirable from a DSSE scheme. The former captures that the newly updated entries cannot be related to previous search queries and the latter ensures that search queries should not leak matching entries after they have been deleted. These security properties are formalized in terms of the information leakage that can be incurred by the respective constructions. Existing backward private constructions either have a nonoptimal communication overhead or they make use of heavy cryptographic primitives. This work makes two contributions: (i) propose alternative formulations of information leakage for backward privacy after revisiting the existing ones [Bost et al. CCS'17], (ii) construct three efficient backward private schemes that aim to achieve practical efficiency by using light weight symmetric cryptographic components only. Our first construction Π_BPprime achieves a stronger notion of backward privacy whereas our next two constructions Π_BP and Π_WBP achieve optimal communication complexity at the cost of some additional leakage. The prototype implementations of our schemes depict the practicability of the proposed constructions and indicate that the cost of achieving backward privacy over forward privacy is substantially small.
Certain applications require some type of fuzzy searches like wildcard and editdistance based search over encrypted data. In our second work, we investigate the problem of secure wildcard search over encrypted data in Outsourced Symmetric Private Information Retrieval (OSPIR) setting. The setting comprises of three entities, viz., the data owner, the server and the client. The data owner outsources the encrypted data to the server, who obliviously services the clients' queries. We propose two schemes, viz., Π_BS and Π_OTE to support secure wildcard search over encrypted data. Construction Π_BS reduces the problem of secure wildcard search to that of Boolean search. Π_BS is a sublinear wildcard search protocol but it allows false positives. Our second construction Π_OTE utilizes Oblivious Transfer Extension protocols to obtain linear time wildcard search protocol with no false positives. Π_BS and Π_OTE can then be combined to obtain an efficient sublinear solution with no false positives. We provide performance analysis based on our prototype implementation to depict the feasibility of our proposed constructions.
 Series: Theory Seminar Series Title: Guarding Polygons via CSP  Speaker: Dr. Akanksha Agrawal
Postdoctoral Researcher
Department of Computer Science
BenGurion University of the Negev
Israel  Date and Time: Friday, August 30, 2019, 1:00 PM
 Venue: CSA Lecture Hall (Room No. 117, Ground Floor)
Abstract The Art Gallery problem is a fundamental visibility problem in Computational Geometry, introduced by Klee in 1973. The input consists of a simple polygon P, (possibly infinite) sets X and Y of points within P, and an integer k, and the objective is to decide whether at most k guards can be placed on points in X so that every point in Y is visible to at least one guard. In the classic formulation of Art Gallery, X and Y consist of all the points within P. Other wellknown variants restrict X and Y to consist either of all the points on the boundary of P or of all the vertices of P. The above mentioned variants of Art Gallery are all W[1]hard with respect to k [Bonnet and Miltzow, ESA'16]. Given the above result, the following question was posed by Giannopoulos [Lorentz Center Workshop, 2016].
``Is Art Gallery FPT with respect to the number of reflex vertices?''
In this talk, we will obtain a positive answer to the above question, for some variants of the Art Gallery problem. By utilising the structural properties of ``almost convex polygons'', we design a twostage reduction from (Vertex,Vertex)Art Gallery to a new CSP problem where constraints have arity two and involve monotone functions. For the above special version of CSP, we obtain a polynomial time algorithm. Sieving these results, we obtain an FPT algorithm for (Vertex,Vertex)Art Gallery, when parameterized by the number of reflex vertices. We note that our approach also extends to (Vertex,Boundary)Art Gallery and (Boundary,Vertex)Art Gallery.
Speaker Bio: I am a postdoctoral researcher at the Department of Computer Science, BenGurion University of the Negev, Israel, where I work in the group of Prof. Meirav Zehavi. Before moving to Israel, I was a postdoctoral researcher at the Institute for Computer Science and Control, Hungarian Academy of Sciences, Hungary. I did my Ph.D at the Department of Informatics, University of Bergen, Norway, under the guidance of Prof. Saket Saurabh and Prof. Daniel Lokshtanov. My research interests include Parameterized Complexity, Computational Geometry, Exact Algorithms, and Fine Grained Complexity.
Host Faculty: Dr. Anand Louis
 Series: Ph.D. Colloquium Title: On Certain Learning and Lower Bound Problems Related to Iterated Matrix Multiplication Polynomial  Speaker: Mr. Vineet Nair
 Faculty Advisor: Prof. Chandan Saha
 Date and Time: Friday, August 23, 2019, 3:00 PM
 Venue: CSA Lecture Hall (Room No. 117, Ground Floor)
Abstract The iterated matrix multiplication polynomial (IMM) of width w and length d is the 1x1 entry in the product of d square matrices of size w. The w2d entries in the d matrices are distinct variables. In this thesis, we study certain learning and lower bound problems related to IMM.
Our first work gives a polynomial time randomized algorithm for equivalence testing of IMM. At its core, the equivalence testing algorithm exploits a connection between the irreducible invariant subspaces of the Lie algebra of the group of symmetries of a polynomial f that is equivalent to IMM and the layer spaces of a fullrank algebraic branching program computing f. This connection also helps determine the group of symmetries of IMM and show that IMM is characterized by its group of symmetries.
Our second work is related to learning affine projections of IMM, which is believed to be a very hard problem as it is equivalent to reconstructing a powerful model to compute polynomials called algebraic branching programs (ABP). Equivalence test for IMM can be viewed as reconstructing ABPs in the averagecase, when the width of the ABP is at most (n/d)0.5, where n and d are the number of variables and the degree of the polynomial computed by the ABP respectively. Our second work improves this by first considering a related problem called `linear matrix factorization’ (LMF) which is a natural generalization of the polynomial factorization problem. We give a polynomial time randomized algorithm for averagecase LMF for matrix products of width at most 0.5n0.5. In fact, we give a polynomial time randomized algorithm that solves (worstcase) LMF problem when the input matrix product is nondegenerate or pure product a notion we define in this work. Using our algorithm for LMF, we give a nontrivial averagecase reconstruction algorithm for ABPs of width at most 0.5n0.5, which is interesting in the context of the Ω(n0.5) width lower bound known for homogeneous ABPs.
Our last work gives lower bounds on interesting restrictions of arithmetic formulas computing IMM. We prove a wΩ(d) lower bound on the size of multilinear depth three formulas computing IMM of width w and length d. The lower bound is proved by introducing a novel variant of the partial derivatives measure called skewed partial derivatives, which found applications in other subsequent works. Improving this result to wΩ(log d) size lower bound on multilinear formulas computing IMM would imply a superpolynomial separation between ABPs and arithmetic formulas. We also show an exponential separation between multilinear depth three and multilinear depth four formulas which was an improvement over the quasipolynomial separation already known. We also consider a restriction of multilinear formulas, called interval setmultilinear formulas computing IMM. Proving a superpolynomial size lower bound on interval setmultilinear formulas computing IMM would imply a superpolynomial separation between algebraic branching programs and homogeneous formulas in the noncommutative world. We make progress in this direction by giving a superpolynomial size lower bound on an interesting restriction of the interval setmultilinear formula computing IMM.
 Series: Ph.D. Colloquium Title: Constantrate Nonmalleable Codes and their Applications  Speaker: MS.Sai Lakshmi Bhavana Obbattu
CSA Department  Faculty Advisor: Dr. Bhavana Kanukurthi
 Date and Time: Friday, August 23, 2019, 10:00 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Nonmalleable codes (NMCs) introduced by Dziembowski, Pietrzak and Wichs in ITCS 2010, provide powerful security guarantees where standard errorcorrecting codes can not provide any guarantee: a decoded message is either the same or completely independent of the underlying message. NMCs have found applications to various aspects of cryptography such as CCA secure encryption, tamper and leakage resilient cryptography, nonmalleable commitments, nonmalleable secret sharing schemes and so on.
In this talk, we present the first explicit construction of a constant rate, constant state nonmalleable code. Next, we will present an application of NMCs to the fascinating problem of "Privacy Amplification". In the problem of privacy amplification, two parties, Alice and Bob, who apriori share a weak secret, to agree on a uniform secret key, in the presence of a computationally unbounded adversary Eve. Building privacy amplification protocols with constant "entropy loss" and constant "round complexity" was open since 1988 (and recently closed in an independent work of Li [CCC '19]). In this talk, we will show how to construct such a privacy amplification protocol under the existence of nonmalleable code with certain strong security guarantees.
This talk is based on joint works with Eshan Chattopadhyay, Bhavana Kanukurthi and Sruthi Sekar.
References:
[1] Bhavana Kanukurthi, Sai Lakshmi Bhavana Obbattu, and Sruthi Sekar. Fourstate nonmalleable codes with explicit constant rate. In Theory of Cryptography Conference, TCC 2017.
Invited to Journal of Cryptology.
[2] Eshan Chattopadhyay, Bhavana Kanukurthi, Sai Lakshmi Bhavana Obbattu, and Sruthi Sekar. Privacy amplification from nonmalleable codes. In submission.
 Series: CSA Golden Jubilee Frontier Lecture Series Title: Shuffling Chromosomes, Chasing Kangaroos and Other Mathematical Curiosities  Speaker: Prof. Prasad Tetali
Regents’ Professor,
School of Mathematics and School of Computer Science,
Georgia Institute of Technology, Atlanta, USA  Date and Time: Thursday, August 22, 2019, 4:00 PM
 Venue: Faculty Hall, Indian Institute of Science
Abstract This popularlevel lecture will focus on some modern applications of the classical topic of Markov chains. The mixing time of a Markov chain measures the time to get close to the equilibrium distribution of the chain. After introducing the topic briefly, the speaker will address a few surprising applications of Markov chain mixing times. These range from cracking ciphers and modelling chromosomal mutations to solving the discrete logarithm problem (using Pollard’s kangaroos), of particular relevance to digital security. The lecture is expected to be selfcontained.
Speaker Bio: Prof. Prasad Tetali is a Regents’ Professor in the School of Mathematics and the School of Computer Science at Georgia Institute of Technology. Dr. Tetali obtained his Ph.D. (1991) from the Courant Institute of Mathematical Sciences (NYU) after earning an M.S. (1987) from the School of Automation at IISc. His research interests lie in probability, discrete mathematics, algorithms and optimization and he has published more than 110 research articles. He is recognized as a SIAM Fellow (2009) and an AMS Fellow (2012). Dr. Tetali is a former director and a current member of the steering committee of Georgia Tech’s Algorithms and Randomness Center Think Tank (ARC) and has been on the coordinating committee of Georgia Tech’s renowned interdisciplinary Ph.D. program in Algorithms, Combinatorics and Optimization (ACO) for the past two decades. He served as the interim Chair of the School of Mathematics at Georgia Tech during CY 20152016. He is currently on the leadership team of the NSFfunded Transdisciplinary Research Institute for Advancing Data Science (TRIAD) at Georgia Tech.
Host Faculty: Prof. Shalabh Bhatnagar
 Series: Department Seminar Title: Data Viz in a Box  Speaker: Christopher Arnold
Wells Fargo  Date and Time: Wednesday, August 21, 2019, 3:30 PM
 Venue: CSA Lecture Hall (Room No. 112, Ground Floor)
Abstract Data Viz in a box is an hourlong, interactive, and entertaining exploration of some of the key principles in data graphic design. This particular lecture focuses on the concept of Data/Ink ratio and how to eliminate unnecessary and “spend” helpful ink so that the reader can better interpret the data graphic. The session is highly interactive and infused with humour to engage and encourage students to put themselves in the place of the person trying to interpret their work.
The course objective is to fundamentally change the students’ concept of data graphics.
The instructor will bring a single page of paper for each student. The only materials required for the instructor are a whiteboard and three (working) darkcoloured markers. For large classes, a head microphone is preferred, but handheld can also work. This class can also be taught remotely through a sharing session on Skype or Zoom.
Speaker Bio: Chris Arnold (popularly known as the Data Whisperer) has been making data talk
since the age of mainframes. Spanning quantitative and qualitative analysis, he
has built high functioning quant teams and data mart solutions across
pharmaceutical, automotive, and financial services industries; within risk,
operations, and marketing domains. He has also conducted ethnographic research
in the Amazon basin. He currently leads Wells Fargo’s offshore analytics
practice, with teams in India and the Philippines. He guest lectures at
universities and has been a Lecturer of Data Visualization at UC Berkeley’s
Master’s in Data Science program. Chris has an interdisciplinary master’s
degree from UC Santa Barbara, where he additionally completed the National
Center for Geographic Information & Analysis program.
Chris speaks passionately about data visualization, intuitive use of complex
analytics, and the alleged intelligence of socalled business intelligence
tools. Warning: if you don't have an hour to waste, don't ask him about pie
charts.
Chris is a surfer, fly fisherman, and photographer, although not particularly
proficient in any one.
He is based in Namma Bengaluru.
Host Faculty: Prof. Vijay Natarajan
 Series: Theory Seminar Series Title: Inapproximability of Clustering in L_p metrics  Speaker: Mr. Karthik C.S
Postdoctoral fellow
Weizmann Institute of Science  Date and Time: Friday, August 16, 2019, 1:00 PM
 Venue: CSA Lecture Hall (Room No. 117, Ground Floor)
Abstract The two most popular objectives optimized in clustering algorithms are kmeans and kmedian. The kmeans (resp. kmedian) problem in the L_pmetric is specified by n points as input and the goal is to classify the input pointset into k clusters such that the kmeans (resp. kmedian) objective is minimized. The bestknown inapproximability factor in literature for these NPhard problems in L_pmetrics were wellbelow 1.01. In this talk, we take a significant step to improve the hardness of approximating these problems in various L_pmetrics. Our techniques are inspired by the tools and perspectives developed in finegrained complexity in the last couple of years.
The talk is based on a joint work with Vincent CohenAddad.
Speaker Bio: Karthik C.S. is a postdoctoral fellow in Weizmann Institute of Science. He is interested in Hardness of Approximation in FineGrained and FixedParameter Complexity, Probabilistically Checkable Proofs, and Communication Complexity. He received his PhD from Weizmann Institute of Science and Master's from École Normale Supérieure de Lyon.
Host Faculty: Dr. Arindam Khan
 Series: Ph.D. Thesis Defense Title: On Representations and Spectral Inequalities for NonUniform Hypergraphs  Speaker: Mr. Ashwin Guha
 Faculty Advisor: Prof. Ambedkar Dukkipati
 Date and Time: Tuesday, August 13, 2019, 11:30 AM
 Venue: CSA Seminar Hall (Room No. 254, First 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 and simplicial complexes as well as 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 the 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: CSA Golden Jubilee Frontier Lecture Series Title: The Multiarmed Bandit Problem Revisited  Speaker: Prof. P.R.Kumar
Professor and College of Engineering Chair in Computer Engineering
Texas A&M University, USA  Date and Time: Thursday, August 08, 2019, 4:00 PM
 Venue: Faculty Hall, Indian Institute of Science
Abstract We address the classical multiarmed bandit problem, and.
exhibit a family of scheduling policies that appear to have the best
empirical performance compared to those known in the literature,
as well as low complexity. We also establish regret bounds,
both in expectation and on sample paths.
[Joint work with Xi Liu, PingChun Hsieh and Anirban Bhattacharya].
Speaker Bio: P. R. Kumar obtained his B.Tech. degree in Electrical Engineering (Electronics) from I.I.T. Madras in 1973, and the M.S. and D.Sc. degrees in Systems Science and Mathematics from Washington University, St. Louis in 1975 and 1977, respectively. From 197784, he was a faculty member in the Department of Mathematics at the University of Maryland Baltimore County. From 19852011, he was a faculty member in the Department of Electrical and Computer Engineering and the Coordinated Science Laboratory at the University of Illinois. Currently he is at Texas A&M University where he is a University Distinguished Professor, Regents Professor, and holds the College of Engineering Chair in Computer Engineering.
Kumar has worked on problems in game theory, adaptive control, stochastic systems, simulated annealing, neural networks, machine learning, queueing networks, manufacturing systems, scheduling, wafer fabrication plants and information theory. His current research focus includes renewable energy, smart grid, security, privacy, automated transportation, unmanned aerial vehicle traffic management, wireless networks, 5G, cyberphysical systems, control theory, information theory, stochastic systems, and operations research.
Kumar is a member of the National Academy of Engineering of the USA, the World Academy of Sciences, and the Indian National Academy of Engineering. He was awarded an honorary doctorate by the Swiss Federal Institute of Technology (Eidgenossische Technische Hochschule) in Zurich. He received the IEEE Field Award for Control Systems, the Donald Eckman Award of American Automatic Control Council, the Fred Ellersick Prize of IEEE Communications Society, the Outstanding Contribution Award of ACM SIGMOBILE, the Infocom Achievement Award, and a SIGMOBILE TestofTime Paper Award. He is an ACM Fellow and a Fellow of IEEE. He was a Guest Chair Professor and Leader of the Guest Chair Professor Group on Wireless Communication and Networking at Tsinghua University, Beijing, China. He is an Honorary Professor at IIT Hyderabad. He is a D. J. Gandhi Distinguished Visiting Professor at IIT Bombay. He was awarded the Distinguished Alumnus Award from IIT Madras, the Alumni Achievement Award from Washington University in St. Louis, and the Daniel C. Drucker Eminent Faculty Award from the College of Engineering at the University of Illinois.
Host Faculty: Dr. Shalabh Bhatnagar

