Events 

Seminars 

Golden Jubilee Frontier Lectures 

Prof. I. G. Sarma Memorial Lecture Series 

Prof. Priti Shankar Memorial Seminar Series 

Multimedia Archive 



UPCOMING SEMINARS 

Series: CSA Faculty Colloquium Title: 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: 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


PAST SEMINARS 

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
 Series: Department Seminar Title: AI: towards Ambient Intelligence  Speaker: 1. Professor Yossi Matias
Tel Aviv University and Google Israel Research and Engineering,
2. Anand Rangarajan
Google Research, Bangalore  Date and Time: Tuesday, August 06, 2019, 4:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Speaker Bio: 1. Yossi is Vice President, Engineering, at Google. He is leading efforts in Search (Google
Autocomplete, Search Live Results, Google Trends, Search Console), Conversational AI
(Google Duplex, Call Screen, Listening to the web), and other Research initiatives (from
foundations to applications in Health). He is the global lead of Crisis Response (SOS Alerts,
Public Alerts, Flood Forecasting), and is on the steering committee for the AI for Social Good
initiative.
Yossi is the founding Head of Google's R&D Center in Israel (which he grew to over 1000 on
staff). He is also the founding executive lead of Google for Startup Campus Tel Aviv, and of
Launchpad and other global entrepreneurship programs.
In addition to his experience as an executive and entrepreneur, Yossi has a rich record of
scientific research as a Computer Science professor at Tel Aviv University, and previously a
Research Scientist at Bell Labs and visiting professor at Stanford. He published extensively, has
dozens of patents on his name, and pioneered some of the early technologies for the effective
analysis of big data, internet privacy, and contextual search. Yossi is a recipient of the Godel
Prize and is an ACM Fellow.
2. Anand is the Site Lead for Google Bangalore, and an Engineering Director in Search. He joined
Google in California in 2008 and worked in Enterprise, Gmail Ads and YouTube in Mountain View
before moving to Bangalore in Aug 2013. In prior life, he has invested ~10 years in designing, coding,
and managing teams working in various aspects of Computer Networking. He fondly remembers the
day when his startup Sahasra Networks was acquired by Cypress Semiconductor. He treasures the
company of his B.Tech classmates from IIT Madras and Masters friends from Stanford University. He
enjoys playing chess, running, word puzzles, sanskrit and listening to indian classical music. His
cofounder and he enjoy nurturing their 2 startups aged 11 and 8.
Host Faculty: Prof. Shalabh Bhatnagar
 Series: Department Seminar Title: Formal Methods in Network Games  Speaker: Dr Shibashis Guha
Universite Libre de Bruxelles
Belgium  Date and Time: Tuesday, August 06, 2019, 11:00 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Network games (NGs) are played on directed graphs and are extensively used in network design and analysis. In the classical model, each player selects a path connecting her source and target vertices. The cost of traversing an edge depends on the load; namely, number of players that traverse it. NGs abstract the fact that different users may use a resource at different times and for different durations; time plays an important role in determining the costs of the users in reality. For example, when transmitting packets in a communication network, routing traffic in a road network, or processing a task in a production system, actual sharing and congestion of resources crucially depends on time. In the first part of the talk, we will discuss timed network games (TNGs), which add a time component to network games. The time in our model is continuous and cannot be discretized. In particular, players have uncountably many strategies, and a game may have uncountably many pure Nash equilibria. We will also mention how different reductions to a formal model called timed automata help in reasoning about TNGs.
In the second part of the talk, we consider search problems for NGs that include finding special strategy profiles such as a Nash equilibrium and a globally optimal solution. The networks modeled by NGs may be huge. In formal verification, abstraction has proven to be an extremely effective technique for reasoning about systems with big and even infinite state space. We describe an abstractionrefinement methodology for reasoning about NGs.
Based on joint works with Guy Avni and Orna Kupferman.
Host Faculty: Prof. Matthew Jacob Thazhuthaveetil
 Series: Department Seminar Title: Asymptotically Optimal Threshold Policies for Appointment Scheduling and Stochastic Knapsacks.  Speaker: Dr. Harsha Honnappa
School of Industrial Engineering
Purdue University  Date and Time: Monday, July 29, 2019, 4:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract We revisit a classic appointment scheduling (AS) problem wherein a finite pool of jobs must be scheduled at a single server queue over a finite fixed time horizon. Jobs once scheduled may not show up (or ‘no show’) with fixed probability, and will take a random amount of time in the server. The AS problem seeks an arrangement of the jobs over the finite horizon such that the cumulative wait times of jobs that turn up are balanced against overage costs. In general, the AS integer program is quite hard to solve, and we seek nonadaptive optimal threshold policies that can be easily implemented. In this work, we prove by construction the existence of an asymptotically optimal sequence of heuristic policies as the number of jobs/items increases to infinity, both in a fluid and diffusion scale. In fact, our policy shows that asymptotically it is optimal to keep the system critically loaded. We also quantify the ’stochasticity gap’ of using the heuristic policies against the best offline/oracle policy where all the stochasticity is unveiled ahead of time. Our results also point to an equivalence between an online version of the AS problem and dynamic and stochastic knapsack problems (DSKPs). In the latter, items of random sizes are presented (one after another) over a finite time horizon to a decisionmaker who seeks to pack a fixed capacity ‘knapsack’ with a minimal number of items while maximizing a cumulative reward. This is joint work with Mor Armony (NYU) and Rami Atar (Technion).
Speaker Bio: Harsha Honnappa is an Assistant Professor in the School of Industrial Engineering at Purdue University. His research group at the Stochastic Systems Lab works on the theory of stochastic models and stochastic optimization, with a particular interest in system design. His works is supported by the National Science Foundation and the Purdue Research Foundation.
Host Faculty: Dr. Siddharth Barman
 Series: CSA Faculty Colloquium Title: Connections between Computational Geometry and Combinatorial Geometry  Speaker: Prof. Sathish Govindarajan
Associate Professor
Dept. of CSA  Date and Time: Friday, July 26, 2019, 4:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Given a collection of geometric objects, the area of Computational Geometry looks at algorithmic questions on them and the area of Combinatorial Geometry looks at structural/combinatorial questions on them. In this talk, we will explore connections between these two areas.
Specifically, we will look at geometric optimization problems like independent set, hitting set and set cover on geometric objects. The talk will survey and describe various methods of designing approximation algorithms for these problems using techniques and results in Combinatorial Geometry.
Speaker Bio: Sathish Govindarajan is an Associate Professor in the Department of Computer Science and Automation at IISc. He received his B.E degree from BITS, Pilani and Ph.D degree from Duke University. His research interests are broadly in the areas of Combinatorial Geometry and Computational Geometry. In current work, he is interested in solving geometric optimization problems using techniques and results from Combinatorial Geometry.
Host Faculty: Prof. Sunil L Chandran & Prof. Shalabh Bhatnagar
 Series: Department Seminar Title: Resource Management for Efficient, Scalable and Resilient Network Function Chains  Speaker: Dr Sameer G Kulkarni
University of California, Riverside  Date and Time: Thursday, July 25, 2019, 11:00 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Networks, the basis of the modern connected world, have evolved beyond the connectivity services. Network Functions (NFs) or traditionally the middleboxes are the basis of realizing different types of innetwork services such as security, optimization functions, and valueadded services. Typically, multiple NFs are chained together (also known as Service Function Chaining) to realize distinct network services, which are pivotal in providing policy enforcement and performance in networks. Network Function Virtualization (NFV) is becoming more prevalent and enabling the softwarized NFs to fast replace the traditional dedicated hardwarebased middleboxes in Communication Service Provider (CSP) networks. However, Virtualized Network Function (VNF) chains posit several systems and network level resource management and failure resiliency challenges: to ensure optimal resource utilization and performance at the system level; and at the networklevel to address optimal NF placement and routing for service chains, traffic engineering, and load balancing the traffic across Virtualized Network Function Instances (VNFIs); and to provide High Availability (HA), Fault Tolerance (FT) and Disaster Recovery (DR) guarantees.
This talk presents an NFV resource management framework to realize efficient, scalable and resilient network service chaining. The presented solutions enable to improve scalability, performance, resourceutilization efficiency, and resiliency of deploying the NF chains in SDN/NFV ecosystem and are based on the standardized ETSI MANO NFV reference architecture. We address systemlevel NF resource utilization, performance, and scale challenges by designing a userspace NF scheduling framework for service function chains. We present a novel ratecost proportional scheduler and chainaware backpressure mechanisms to optimize the resource utilization through judicious Central Processing Unit (CPU) allocation to the NFs and improve on the chainwide performance. We address networklevel challenges i.e. orchestration and management of NF chains through a semidistributed resource management framework that can efficiently instantiate, place and relocate the network functions and to distribute traffic across the active NF instances to optimize both the utilization of network links and NFs. We address HA and FT for NF chains through a novel NF state replication strategy and distinct mechanisms to provide
timely detection of NFs, hardware node (Virtualized Network Function Manager), and network link failures. We exploit the concept of external synchrony and rollback recovery to address non determinism and significantly reduce the amount of state transfer required to maintain consistent chainwide state updates. We provide distinct failover mechanisms for individual NF failures and global service chainwide failures with strict correctness guarantees.
Host Faculty: Matthew Jacob

