Events 

Seminars 

Golden Jubilee Frontier Lectures 

Prof. I. G. Sarma Memorial Lecture Series 

Prof. Priti Shankar Memorial Seminar Series 

Multimedia Archive 



UPCOMING SEMINARS 

Series: Theory Seminar Title: Algorithmic advances on metric and graph clustering (Part 2)  Speaker: Dr. Vincent Viallat CohenAddad,
Research Scientist,
Google Zürich  Date and Time: Monday, October 18, 2021, 4:00 PM
 Venue: Microsoft Teams  ONLINE
Abstract Clustering algorithms are at the core of unsupervised machine learning and data analysis techniques.
Given a set of data elements, the goal of a clustering is to partition a dataset in such a way that
data elements in the same part are more similar to each other than data elements in different parts.
Clustering problems arise in large variety of applications ranging from bioinformatics to computer vision
and as such are very basic problems.
In these two talks, we will present both metric clustering (Part 1) and graph clustering (Part 2) problems.
We will first illustrate some recent advances in the complexity of the classic kmedian and kmeans problems,
two popular objective functions for metric clustering, via some recent developments on the fixedparameter
tractability of the objectives and hardness of approximation. We will then describe new approximation algorithms
for metric hierarchical clustering.
In the second part of the talks, we will present a new perspective on the classic correlation clustering
objective that leads to new efficient distributed algorithms for the problem, together with a beyondtheworstcase
analysis of the Louvain algorithm for finding the maximum modularity graphs clustering.
Microsoft Teams Link:
https://teams.microsoft.com/l/meetupjoin/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97f6a741e3b2c5ad4193976476%22%2c%22Oid%22%3a%227c84465ec38b4d7a9a9dff0dfa3638b3%22%7d
The first part of this talk is uploaded on CSA’s YouTube channel: https://www.youtube.com/watch?v=7vKYZFjGwo8
For more details about the seminar please visit the website at https://www.csa.iisc.ac.in/iiscmsrseminar/
Host Faculty: Dr. Arindam Khan


PAST SEMINARS 

Series: M.Tech (Research)Thesis Defence ONLINE Title: A TrustedHardware Backed Secure Payments Platform for Android  Speaker: Rounak Agarwal,
M.Tech (Research) student,
Dept. of CSA  Faculty Advisor: Prof. Vinod Ganapathy, CSA
 Date and Time: Thursday, October 14, 2021, 9:30 AM
 Venue: Microsoft Teams  ONLINE
Abstract Digital payments using personal electronic devices have been steadily gaining in popularity for the last few years. While digital payments using smartphones are very convenient, they are also more susceptible to security vulnerabilities. Unlike devices dedicated to the purpose of payments (e.g. POS terminals), modern smartphones provide a large attack surface due to the presence of so many apps for various use cases and a complex featurerich smartphone OS.
Because it is the most popular smartphone OS by a huge margin, Android is the primary target of attackers. Although the security guarantees provided by the Android platform have improved significantly with each new release, we still see new vulnerabilities being reported ever month. Vulnerabilities in the underlying Linux kernel are particularly dangerous because of their severe impact on app security. To protect against a compromised kernel, some critical functions of the Android platform such as cryptography and local user authentication have been moved to a Trusted Execution Environment (TEE) in the last few releases. But the Android platform doesn't yet provide a way to protect a user's confidential input meant for a remote server, from a compromised kernel. Our work aims to address this gap in Android's use of TEEs for app security. We have designed a framework that leverages a TEE for protecting user's confidential input and we have shown how this framework can be used to improve the security of digital payments,
Microsoft teams link: https://teams.microsoft.com/l/meetupjoin/19%3ameeting_OTVlNGMzNzAtOWU3MC00ODA5LTk0MTAtNDNhZDc5YjNlMGFm%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97f6a741e3b2c5ad4193976476%22%2c%22Oid%22%3a%220432f3a0d225405cb0f4ff1ffaf4f1fd%22%7d
 Series: Theory Seminar Title: Algorithmic advances on metric and graph clustering (Part 1)  Speaker: Dr. Vincent Viallat CohenAddad
Research Scientist
Google Zürich  Date and Time: Friday, October 08, 2021, 4:00 PM
 Venue: Microsoft Teams  ONLINE
Abstract Clustering algorithms are at the core of unsupervised machine learning and data analysis techniques.
Given a set of data elements, the goal of a clustering is to partition a dataset in such a way that
data elements in the same part are more similar to each other than data elements in different parts.
Clustering problems arise in large variety of applications ranging from bioinformatics to computer vision
and as such are very basic problems.
In these two talks, we will present both metric clustering (Part 1) and graph clustering (Part 2) problems.
We will first illustrate some recent advances in the complexity of the classic kmedian and kmeans problems,
two popular objective functions for metric clustering, via some recent developments on the fixedparameter
tractability of the objectives and hardness of approximation. We will then describe new approximation algorithms
for metric hierarchical clustering.
In the second part of the talks, we will present a new perspective on the classic correlation clustering
objective that leads to new efficient distributed algorithms for the problem, together with a beyondtheworstcase
analysis of the Louvain algorithm for finding the maximum modularity graphs clustering.
Microsoft Teams Link:
https://teams.microsoft.com/l/meetupjoin/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97f6a741e3b2c5ad4193976476%22%2c%22Oid%22%3a%227c84465ec38b4d7a9a9dff0dfa3638b3%22%7d
For more details about the seminar please visit the website at https://www.csa.iisc.ac.in/iiscmsrseminar/
Host Faculty: Dr. Arindam Khan
 Series: M.Tech (Research)Thesis Defence ONLINE Title: A MultiPolicy Reinforcement Learning Framework for Autonomous Navigation  Speaker: Mr. Rajarshi Banerjee
M.Tech (Research) student
Dept. of CSA  Faculty Advisor: Prof. Ambedkar Dukkipati
 Date and Time: Friday, October 08, 2021, 10:00 AM
 Venue: Microsoft Teams  ONLINE
Abstract Reinforcement Learning (RL) is the process of training an agent to take a sequence of actions with the prime objective of maximizing rewards it obtains from an environment. Deep RL is simply using the same approach where a deep neural network parameterizes the policy. Temporal abstraction in RL is learning useful and generalizable skills, which are often necessary for solving complex tasks in various environments of practical interest. One such domain is the longstanding problem of autonomous vehicle navigation. In this work, we focus on learning complex skills in such environments where the agent has to learn a highlevel policy by leveraging multiple skills inside an environment that presents various challenges.
Multipolicy reinforcement learning algorithms like the Options Critic Framework require an exorbitant amount of time for converging to policies. Even when they do, there is a broad tendency for the policy over options to choose a single subpolicy exclusively, thus rendering the other policies moot. In contrast, our approach combines an iterative approach to complement previously learned policies.
To conduct the experiments, a custom simulated 3D navigation environment was developed where the agent is a vehicle that has to learn a policy by which it can avoid a collision. This is complicated because, in some scenarios, the agent needs to infer certain abstract meaning from the environment to make sense of it while learning from a reward signal that becomes increasingly sparse.
In this thesis, we introduce the `Stay Alive` approach to learn such skills by sequentially adding them into an overall set without using an overarching hierarchical policy where the agents objective is to prolong the episode for as long as possible. The general idea behind our approach comes from the fact that both animals and human beings learn meaningful skills in previously acquired skills to better adapt to their respective environments.
We compare and report our results on the navigation environment and the Atari Riverraid environment with stateoftheart RL algorithms and show that our approach outperforms the prior methods.
Microsoft teams link:
https://teams.microsoft.com/l/meetupjoin/19%3ameeting_NTM0NzExMWMtNmFmYi00OWZjLTliM2EtNTNjYTQyNzg4OTVm%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97f6a741e3b2c5ad4193976476%22%2c%22Oid%22%3a%229d60e18526004b28b2d52d47a54928f3%22%7d
 Series: M.Tech (Research)Thesis Defence ONLINE Title: A Framework for PrivacyCompliant Delivery Drones  Speaker: Mr. Rakesh Rajan Beck
M.Tech (Research) student
Dept. of CSA  Faculty Advisor: Prof. Vinod Ganapathy
 Date and Time: Tuesday, October 05, 2021, 9:00 AM
 Venue: Microsoft Teams  ONLINE
Abstract This thesis presents Privaros, a framework to enforce privacy policies on drones. Privaros is designed for commercial delivery drones, such as the ones that will likely be used by Amazon Prime Air. Such drones visit various host airspaces, each of which may have different privacy requirements. Privaros uses mandatory access control to enforce the policies of these hosts on guest delivery drones. Privaros is tailored for ROS, a middleware popular in many drone platforms. This thesis presents the design and implementation of Privaross policyenforcement mechanisms, describes how policies are specified, and shows that policy specification can be integrated with Indias Digital Sky portal. This thesis presents an evaluation of Privaros that shows that a drone running Privaros can robustly enforce various privacy policies specified by hosts, and that its core mechanisms only marginally increase communication latency and power consumption.
Microsoft Teams link:
https://teams.microsoft.com/l/meetupjoin/19%3ameeting_MWNhNDA3ODYtNWI3NC00Zjg3LWJjM2YtYzBiNTQwOTI2ZTBk%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97f6a741e3b2c5ad4193976476%22%2c%22Oid%22%3a%220432f3a0d225405cb0f4ff1ffaf4f1fd%22%7d
 Series: Theory Seminar Title: Improved (exponential time) algorithms: A case study for Subset Sum and Bin Packing  Speaker: Dr. Jesper Nederlof
Associate Professor
Algorithms and Complexity group
Utrecht University  Date and Time: Friday, October 01, 2021, 4:00 PM
 Venue: Microsoft Teams  ONLINE
Abstract Given an algorithm for a computational problem, a natural question is: Can its time or space efficiency be improved? We study this question for some natural and/or old algorithms for NPcomplete problems.
Specifically, we survey some of the modern techniques to design such improved algorithms, with a focus on the Subset Sum and Bin Packing problems:
The algorithm by Schroeppel and Shamir (FOCS'79) solving Subset Sum on instances with n items in O(2^{n/2}) time and O(2^{n/4}) space can be improved to an algorithm using the same time and O(2^{0.249999n}) space. The trivial O(2^n) time and poly(n) space algorithm for Subset Sum can be improved to an O(2^{0.86n}) time poly(n) space algorithm, assuming random readonly access to random bits. The standard algorithm solving Bin Packing with n items in O(2^n) can be improved to an algorithm running in time O((2−ε_b)^n), where n denotes the number of items and ε_b is a positive number that only depends on the number of bins b available in the instance.
Two key modern techniques we will discuss are (1) a new method based on anticoncentration of subset sums (along with structural new insights in additive combinatorics) and (2) the representation method by Joux and HowgraveGraham (EUROCRYPT'10) to navigate through the search space in an improved way,
We will discuss parts of the following works:
Jesper Nederlof, Jakub Pawlewicz, Céline M. F. Swennenhuis, Karol Wegrzycki: A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics. SODA 2021: 16821701.
Jesper Nederlof, Karol Wegrzycki: Improving Schroeppel and Shamir's algorithm for subset sum via orthogonal vectors. STOC 2021: 16701683
Nikhil Bansal, Shashwat Garg, Jesper Nederlof, Nikhil Vyas: Faster spaceefficient algorithms for subset sum and ksum. STOC 2017: 198209
Per Austrin, Petteri Kaski, Mikko Koivisto, Jesper Nederlof: Dense Subset Sum May Be the Hardest. STACS 2016: 13:113:14
Microsoft Teams Link:
https://teams.microsoft.com/l/meetupjoin/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97f6a741e3b2c5ad4193976476%22%2c%22Oid%22%3a%227c84465ec38b4d7a9a9dff0dfa3638b3%22%7d
For more details about the seminar please visit the website at https://www.csa.iisc.ac.in/iiscmsrseminar/
Host Faculty: Dr. Arindam Khan
 Series: Theory Seminar Title: Monotone Arithmetic Lower Bounds Via Communication Complexity.  Speaker: Dr. Arkadev Chattopadhyay
Associate Professor
School of Technology and Computer Science
TIFR Mumbai  Date and Time: Friday, September 24, 2021, 4:00 PM
 Venue: Microsoft Teams  ONLINE
Abstract How much power does negation or cancellation provide to computation?
This is a fundamental question in theoretical computer science that
appears in various parts: in Boolean circuits, Arithmetic circuits and
also in communication complexity. I will talk about some new connections
between the latter two fields and their applications to extend two
classical results from four decades ago: Valiant (1979) showed that
monotone arithmetic circuits are exponentially weaker than general
circuits for computing monotone polynomials. Our first result gives a
qualitatively more powerful separation by showing an exponential
separation between general monotone circuits and constantdepth
multilinear formulas. Neither such a separation between general
formulas and monotone circuits, nor a separation between multilinear
circuits and monotone circuits were known before. Our result uses the
recent counterexample to the LogApproximateRank Conjecture in
communication complexity.
Jerrum and Snir (1982) also obtained a separation between the powers of
general circuits and monotone ones via a different polynomial, i.e. the
spanning tree polynomial (STP), a polynomial that is well known to be in
VP, using nonmultilinear cancellations of determinantal computation.
We provide the first extension of this result to show that the STP
remains `robustly hard` for monotone circuits in the sense of Hrubes
recent notion of epsilonsensitivity. The latter result is proved via
formulating a discrepancy method for monotone arithmetic circuits that
seems independently interesting.
We will discuss several open problems arising from these results.
(These are based on joint works with Rajit Datta, Utsab Ghosal and
Partha Mukhopadhyay).
Microsoft Teams Link:
https://teams.microsoft.com/l/meetupjoin/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97f6a741e3b2c5ad4193976476%22%2c%22Oid%22%3a%227c84465ec38b4d7a9a9dff0dfa3638b3%22%7d
For more details about the seminar please visit the website at https://www.csa.iisc.ac.in/iiscmsrseminar/
Host Faculty: Dr. Anand Louis
 Series: Department Seminar Title: Vertex Coloring Problem with Some Domination Properties  Speaker: Dr. Sayani Das
Department of Mathematics
Indian Institute of Technology Madras
Chennai  Date and Time: Thursday, September 23, 2021, 4:00 PM
 Venue: Microsoft Teams  ONLINE
Abstract Coloring and Dominating Set are two well known and well studied problems in Graph Theory. Here we consider a vertex coloring problem by imposing some domination property on it. Given a simple graph G = (V,E), in domination coloring, we need to find a vertex coloring of V such that each vertex v in V dominates some color class and each color class is dominated by some vertex v in V. The domination chromatic number of G, is the minimum number of colors used in a domination coloring of G. In minimum domination coloring we need to compute a domination coloring with minimum number of colors. We prove that, this problem is as hard as minimum vertex coloring problem. We also show that, it cannot be approximated within a factor of O(ln n), even when restricted to weakly chordal graphs. We also consider node deletion problems associated with domination coloring. Given a graph G and a positive integer q, in Minimum qDomination Partization, it is required to find a vertex set S of minimum size such that the remaining graph is domination colorable with at most q colors. We only consider qdomination partization problem for q = 2 and q =3. We prove that Minimum 2Domination Partization is APXcomplete. It is approximable within a factor of 2 and this approximation factor is the best possible approximation factor. Then we have given the characterizations for 3domination colorable graphs. Finally, we prove that Minimum 3Domination Partization is APXhard, it is equivalent to minimum odd cycle transversal and design approximation algorithm for it.
Speaker Bio: Ph.D. Scholar, Department of Mathematics, IIT Madras.
Microsoft teams link:
https://teams.microsoft.com/l/meetupjoin/19%3ameeting_YzI4MTA2NGQtZDAwZS00MGU4LWI4MzktM2YyYzVjMjE0ZmYx%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97f6a741e3b2c5ad4193976476%22%2c%22Oid%22%3a%222671ab71955e4e4e9268ebb188b00539%22%7d
Host Faculty: Dr. Arindam Khan
 Series: Department Seminar Title: Designing Secure Cryptographic Systems: Journey from Theory to Practice  Speaker: Dr. Sikhar Patranabis, Visa Research
 Date and Time: Wednesday, September 22, 2021, 8:00 AM
 Venue: ONLINE
Abstract The study of cryptography is aimed at keeping information secure in an increasingly digitized world. Modern cryptography uses theoretical frameworks to prove the security of cryptographic primitives against precisely modeled attacks. However, translating cryptographic primitives from provably secure algorithms into secure deployable systems remains a massive challenge. In particular, existing theoretical models do not account for potential weaknesses inherent to practical cryptographic implementations. Hence, provable security guarantees often collapse in the face of attacks that exploit implementationlevel weaknesses to devastating effect.
In this talk, I will give an overview of my journey so far in attempting to bridge the wonderfully multifaceted aspects of cryptography, with the aim of designing, analyzing and securely implementing cryptographic solutions to realworld problems while relying on as minimal a set of assumptions as possible. In the process, I will summarize my past research works spanning theoretical cryptographic foundations, applied cryptography and secure cryptographic implementations.
I will begin with an overview of my foundational research into enabling a variety of functionally rich and provably secure cryptographic applications based on Minicrypt (the world of “symmetrickey” cryptoprimitives), and some additional algebraic structure. I will then discuss my research efforts towards enabling a specific cryptographic application  searchable symmetric encryption (SSE)  that supports a wide class of Boolean queries over encrypted relational databases at scale while relying on purely symmetrickey primitives. Finally, I will showcase that despite the theoretical security guarantees afforded by standardized symmetrickey cryptographic algorithms such as AES128, practical implementations of SSE schemes remain vulnerable to “faultinjection attacks'' – a special class of implementationlevel attacks powerful enough to reduce the keyspace for AES128 from 2^{128} to a single key while relying on a single faultinjection. In particular, I will describe my recent work (appeared at Eurocrypt 2020) on a “fault propagation”based keyrecovery attack that completely breaks the security of an AES128 implementation, even when equipped with dedicated protections against standard implementationlevel attacks.
No prior background on cryptography will be needed.
Speaker Bio: Sikhar Patranabis is a staff research scientist at Visa Research USA. His research focuses on cryptographic foundations, postquantum cryptography, database encryption, and cryptographic hardware security. Prior to joining Visa Research, he was a postdoctoral researcher at ETH Zurich, Switzerland. He received his PhD and B.Tech in Computer Science and Engineering from IIT Kharagpur. His research has appeared in reputed international conferences and journals, including IACR Crypto, IACR Eurocrypt, IACR Asiacrypt, ACM CCS, NDSS, IEEE TC and IEEE TIFS. He has delivered invited talks at many prestigious international forums, including an invited tutorial at IACR CHES 2015. He is the recipient of an IBM PhD fellowship, a Qualcomm Innovation Fellowship and the President of India gold medal from IIT Kharagpur.
This seminar will be given via Teams Meeting: https://teams.microsoft.com/l/meetupjoin/19%3ameeting_MzlkOTZhMmMtYmJjOC00MTJiLTg4OGYtZjg4ZjNkZTVmNTVj%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97f6a741e3b2c5ad4193976476%22%2c%22Oid%22%3a%224bcd3d56e4054b0699fb27742262f261%22%7d
Host Faculty: R. Govindarajan
 Series: Theory Seminar Title: Efficient Intervention Design for Learning Causal DAGs  Speaker: Dr. Karthikeyan Shanmugam
Research Staff Member
IBM Research AI group
New York  Date and Time: Friday, September 17, 2021, 4:00 PM
 Venue: Microsoft Teams  ONLINE
Abstract Network of cause effect relationships between measured variables is modeled as a causal DAG (Directed Acyclic Graph). In this talk, we focus on efficient adaptive intervention design for learning a causal DAG, with no latent confounders, given the observational equivalence class it belongs to as an input. We first consider equivalence class inputs whose skeleton is a tree. We consider a Bayesian framework where a prior over all directed trees is updated based on the outcome of every single node intervention each of which is adaptively designed based on current posterior. We provide an efficient algorithm that requires interventions that is within a factor of 2 from the best adaptive algorithm. We also show that information greedy approaches are exponentially suboptimal in terms of the optimal number of interventions required. The main technical tool is a simple greedy algorithm that myopically optimizes a centrality measure on the skeleton of the true causal tree.
We generalize and extend the above approach for adaptive interventional design to learn an arbitrary causal DAGs given its equivalence class. We show that the half the maximum clique size is an instance specific fundamental lower bound for any algorithm to even verify the DAG structure through interventions given the equivalence class. Under mild assumptions on the equivalence class, we provide an adaptive algorithm inspired by the algorithm on causal trees that requires interventions that matches the optimal number of interventions up to a multiplicative logarithmic factor in the number of maximal cliques.
Microsoft Teams Link:
https://teams.microsoft.com/l/meetupjoin/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97f6a741e3b2c5ad4193976476%22%2c%22Oid%22%3a%227c84465ec38b4d7a9a9dff0dfa3638b3%22%7d
For more details about the seminar please visit the website at https://www.csa.iisc.ac.in/iiscmsrseminar/
Host Faculty: Dr. Rahul Saladi
 Series: M.Tech (Research) Colloquium ONLINE Title: Security of PostQuantum Multivariate Blind Signature Scheme: Revisited and Improved  Speaker: Ms. Aalo Majumdar
M.Tech (Research) student
Dept. of CSA  Faculty Advisor: Prof. Sanjit Chatterjee
 Date and Time: Thursday, September 16, 2021, 4:00 PM
 Venue: Microsoft teams  ONLINE
Abstract Current ubiquitous cryptosystems face an imminent threat from quantum algorithms like Shors and Grovers, leading us to a future of postquantum cryptography. Multivariate signatures are prominent in postquantum cryptography due to their fast, lowcost implementations and shorter signatures. Blind signatures are a special category of digital signatures with two security notions: blindness and onemore unforgeability (OMF). Our work primarily focuses on the multivariate blind signature scheme (MBSS) proposed by Petzoldt et al. We construct a formal proof along the lines of the heuristic sketch given by the authors of MBSS based on the proposed universal onemore unforgeability (UOMF) model, a weaker variant of OMF. The construction of this proof led us to identify the various issues in the security argument  mainly the difficulty in simulating the response to the blind signature queries without knowing the secret key of the underlying Rainbow scheme used. Since our investigation revealed the difficulty in reducing the UOMF security to the hardness assumption used by the authors, therefore we design a new class of hardness assumptions: (1) Single Target Inversion Problem, PRSTI (2) Modified version of Single Target Inversion Problem, PRmSTI (3) Chosen Target Inversion Problem, PRCTI. Armed with the new class of computational problems, we reduce the UOMF and OMF security of MBSS to these problems. We begin by giving an improved security argument of MBSS in the UOMF security model using the PRmSTI assumption. We employ the general forking algorithm in this security reduction. However, we cannot apply the forking algorithm directly owing to the wrapper algorithm being split and the presence of the blind signature oracle. We thus suitably modify the algorithm and then derive the corresponding forking probability. To argue the security of MBSS in the standard security model, i.e., in the OMF model, we try using the PRCTI assumption. The PRCTI problem demands computing the solution for more than one target. With the high cost of forking, a significant degradation factor appears in the success probability. So, instead, we reduce the OMF security of MBSS to the PRmSTI assumption (in a restricted setting) and give a comparative analysis between the security argument in the UOMF and OMF models.
Microsoft Teams link:
https://teams.microsoft.com/l/meetupjoin/19%3ameeting_NzFiMjNmODEtN2ZkZi00OGU4LWEzOGEtZTdjMjM5OWI0ZWZl%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97f6a741e3b2c5ad4193976476%22%2c%22Oid%22%3a%22f24581ee935045bbb76b26beecd9d45f%22%7d
 Series: M.Tech (Research) Thesis Defense Title: GPM: Exploring GPUs with Persistent Memory  Speaker: Shweta Pandey
 Faculty Advisor: Arkaprava Basu
 Date and Time: Monday, September 13, 2021, 11:00 AM
 Venue: https://teams.microsoft.com/l/meetupjoin/19%3a13ca80f16f7948a2a87ac38e29410e0a%40thread.tacv2/1630390106337?context=%7b%22Tid%22%3a%226f15cd97f6a741e3b2c5ad4193976476%22%2c%22Oid%22%3a%2282f39501c5b24bfb87c3f17ca74c00b6%22%7d
Abstract GPUs are a key computing platform for many application domains. While the emergence of nonvolatile memory has brought the promise of finegrain byteaddressable persistence (a.k.a., persistent memory, or PM) to CPU applications, the same unfortunately is beyond the reach of GPU programs.
This work takes three steps toward enabling GPU programs to directly access PM. First, we show how various existing software and hardware technologies can be put together to enable direct access to PM from within a GPU kernel. Next, we created a workload suite of 10 GPUaccelerated applications to demonstrate how GPUs can benefit from PM. We then created a GPU library to support logging, checkpointing, and primitives for native persistence to enable GPU programmers to easily leverage PM.
Speaker Bio: Shweta Pandey is an MTech (Research) student in the Department of Computer Science and Automation. She is advised by Prof. Arkaprava Basu. She is interested in building systems that use heterogeneous computing and are heterogeneous memory aware.
Host Faculty: Arkaprava Basu
 Series: Theory Seminar Title: BetterThan2 Approximations for Weighted Tree Augmentation  Speaker: Dr. Vera Traub
Postdoctoral Researcher
ETH Zurich (Switzerland)  Date and Time: Friday, September 10, 2021, 4:00 PM
 Venue: Microsoft Teams  ONLINE
Abstract The Weighted Tree Augmentation Problem (WTAP) is one of the most basic connectivity augmentation problems. It asks how to increase the edgeconnectivity of a given graph from 1 to 2 in the cheapest possible way by adding some additional edges from a given set. There are many standard techniques that lead to a 2approximation for WTAP, but despite much progress on special cases, the factor 2 remained unbeaten for several decades.
In this talk we present two algorithms for WTAP that improve on this longstanding approximation ratio of 2. The first algorithm is a relative greedy algorithm, which starts with a simple, though weak, solution and iteratively replaces parts of this starting solution by stronger components.
This algorithm achieves an approximation ratio of
(1+ln(2)+ϵ)<1.7. Second, we present a local search algorithm that achieves an approximation ratio of 1.5+ϵ (for any constant ϵ>0).
This is joint work with Rico Zenklusen.
Microsoft Teams Link:
https://teams.microsoft.com/l/meetupjoin/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97f6a741e3b2c5ad4193976476%22%2c%22Oid%22%3a%227c84465ec38b4d7a9a9dff0dfa3638b3%22%7d
For more details about the seminar please visit the website at https://www.csa.iisc.ac.in/iiscmsrseminar/
Host Faculty: Dr. Arindam Khan
 Series: Theory Seminar Title: A (2 + ϵ)approximation algorithm for preemptive weighted flow time on a single machine  Speaker: Dr. Lars Rohwedder
Postdoctoral Researcher
Theoretical Computer Science
EPFL, Lausanne (Switzerland)  Date and Time: Friday, September 03, 2021, 4:00 PM
 Venue: Microsoft Teams  ONLINE
Abstract In a recent breakthrough in scheduling, Batra, Garg, and Kumar gave the first constant approximation algorithm for minimizing the sum of weighted flow times. Wiese and I (STOC 21) managed to improve this large unspecified constant to 2+ϵ. I will give a very graphic presentation of the algorithmic techniques behind this.
Microsoft Teams Link:
https://teams.microsoft.com/l/meetupjoin/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97f6a741e3b2c5ad4193976476%22%2c%22Oid%22%3a%227c84465ec38b4d7a9a9dff0dfa3638b3%22%7d
For more details about the seminar please visit the website at https://www.csa.iisc.ac.in/iiscmsrseminar/
Host Faculty: Dr. Arindam Khan
 Series: M.Tech (Research) Colloquium ONLINE Title: A Syntactic Neural Model for Question Decomposition  Speaker: Ms. Suman Gupta
M.Tech (Research) student
Dept. of CSA  Faculty Advisor: Prof. Shirish K Shevade
 Date and Time: Friday, September 03, 2021, 2:00 PM
 Venue: Microsoft Teams  ONLINE
Abstract Question decomposition along with singlehop Question Answering (QA) system serve as useful modules in developing multihop Question Answering systems, mainly because the resulting QA system is interpretable and has been demonstrated to exhibit better performance. The problem of Question Decomposition can be posed as a machine translation problem and it can be solved using any sequencetosequence neural architecture. Using this approach, it is difficult to capture the innate hierarchical structure of the decomposition. Inspired by database query languages a pseudoformalism for capturing the meaning of questions, called Question Decomposition Meaning Representation (QDMR) was recently introduced. In this approach, a complex question is decomposed into simple queries which are mapped into a small set of formal operations. This method does not utilize the underlying syntax information of QDMR to generate the decomposition.
In the area of programming language code generation, methods that use syntax information as a prior knowledge have been demonstrated to perform better. Moreover, the syntaxaware models are usually interpretable.
Motivated by the success of syntaxaware models, we propose a new syntactic neural model for question decomposition in this thesis.
In particular, we encode the underlying syntax of the QDMR structures into a grammar model as a sequence of actions.
This is done using a deterministic framework which uses Abstract Syntax Trees (AST) and Parse Trees. The proposed
approach can be thought of as an encoderdecoder method for QDMR structures where a sequence of possible actions is a latent representation of the QDMR structure. The advantage of using this latent representation is that it is interpretable. Experimental results on a realworld dataset demonstrate that the proposed approach outperforms the stateoftheart approach especially in scenarios where training data is limited. Some heuristics to further improve the performance of the proposed approach are also suggested in this work.
Microsoft teams link:
https://teams.microsoft.com/l/meetupjoin/19%3ameeting_YTQ3YzdhOWMtMDBiYy00ODQxLWJmMDItMzlmY2MwNjFjYjY5%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97f6a741e3b2c5ad4193976476%22%2c%22Oid%22%3a%229c3e2bfe1b0f4d7ba589832878069dc6%22%7d
 Series: Ph.D. (Engg.) Colloquium ONLINE Title: Neural Models for Personalized Recommendation Systems with External Information  Speaker: Mr. Vijaikumar M
Ph.D student
Dept. of CSA  Faculty Advisor: Prof. Shirish K Shevade & Prof. M Narasimha Murty
 Date and Time: Thursday, August 26, 2021, 2:00 PM
 Venue: Microsoft Teams  ONLINE
Abstract Personalized recommendation systems use the data generated by useritem interactions (for example, in the form of ratings) to predict different users interests in available items and recommend a set of items or products to the users. The sparsity of data, cold start, and scalability are some of the important challenges faced by the developers of recommendation systems. These problems are alleviated by using external information, which can be in the form of a social network or a heterogeneous information network, or crossdomain knowledge. This thesis develops novel neural network models for designing personalized recommendation systems using the available external information.
The first part of the thesis studies the topN item recommendation setting where the external information is available in the form of a social network or heterogeneous information network. Unlike a simple recommendation setting, capturing complex relationships amongst entities (users, items, and connected objects) becomes essential when a social and heterogeneous information network is available. In a social network, all socially connected users do not have equal influence on each other. Further, estimating the quantum of influence among entities in a useritem interaction network is important when only implicit ratings are available. We address these challenges by proposing a novel neural network model, SoRecGAT, which employs a multihead and multilayer graph attention mechanism. The attention mechanism helps the model learn the influence of entities on each other more accurately. Further, we exploit heterogeneous information networks (HIN) to gather multiple views for the items. A novel neural network model  GAMMA (Graph and Multiview Memory Attention mechanism) is proposed to extract relevant information from HINs. The proposed model is an endtoend model which eliminates the need for learning a similarity matrix offline using some manually selected metapaths before optimizing the desired objective function.
In the second part of the thesis, we focus on topN bundle recommendation and list continuation setting. Bundle recommendation is the task of recommending a group of products instead of individual products to users. We study two interesting challenges  (1) how to personalize and recommend existing bundles to users and (2) how to generate personalized novel bundles targeting specific users. We propose GRAMSMOT  a graph attentionbased framework that considers higherorder relationships among the users, items, and bundles and the relative influence of items present in the bundles. For efficiently learning the embeddings of the entities, we define a loss function based on the metriclearning approach. A strategy that leverages submodular optimization ideas is used to generate novel bundles.
We also study the problem of topN personalized list continuation where the task is to curate the next items to usergenerated lists (ordered sequence of items) in a personalized way by using the sequential information of the items in the list. The main challenge in this task is understanding the ternary relationships among the users, items, and lists. We propose HyperTeNet  a selfattention hypergraph and Transformerbased neural network architecture for the personalized list continuation task. Here, graph convolutions are used to learn the multihop relationship among entities of the same type. A selfattentionbased hypergraph neural network is proposed to learn the ternary relationships among the interacting entities via hyperlink prediction in a 3uniform hypergraph. Further, the entity embeddings are shared with a Transformerbased architecture and are learned through an alternating optimization procedure.
The final part of the thesis focuses on the personalized rating prediction setting where external information is available in the form of crossdomain knowledge. We propose an endtoend neural network model, NeuCDCF, that provides a way to alleviate data sparsity problems by exploiting the information from related domains. NeuCDCF is based on a wide and deep framework and learns the representations jointly using matrix factorization and deep neural networks. We study the challenges involved in handling diversity between domains and learning complex nonlinear relationships among entities within and across domains.
We conduct extensive experiments in each of these settings using several realworld datasets and demonstrate the efficacy of the proposed models.
Microsoft teams link:
https://teams.microsoft.com/l/meetupjoin/19%3ameeting_MWVhYWRkODUtZGI4OC00ZDZmLTk2NGMtZmViNTNiZmFmM2E3%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97f6a741e3b2c5ad4193976476%22%2c%22Oid%22%3a%229c3e2bfe1b0f4d7ba589832878069dc6%22%7d
 Series: Department Seminar Title: The Story of Arjun Guha, or: the Arc of a Research Project  Speaker: Shriram Krishnamurthi
Vice President for Programming Languages
Brown University
Providence, RI, USA  Date and Time: Saturday, August 21, 2021, 5:30 PM
 Venue: Online on Zoom: https://brown.zoom.us/j/94769764745 Meeting ID: 947 6976 4745 at 5:30pm IST
Abstract There are many ways to do research successfully, so you should take
all advice with a pinch of salt. That said, I will try to describe
some of the attributes that have worked well for my students and
me. To make it concrete, I will use my former student, Arjun Guha, as
a case study. I will strip away most of the technical detail while
trying to retain the essential ideas, so people from any area of
computer science will be able to follow almost all of it. Questions
are welcome at any time. The talk will be followed by plenty of time
for Q&A.
Speaker Bio: Shriram is the Vice President for Programming Languages at Brown
University in Providence, RI, USA. He is not, really, but thats what
it says on his business card. At heart, he is a person of illrepute: a
Schemer, Racketeer, and Pyreteer. He believes tropical fruit are
superior to all other kinds. He is terrified of success, because he
may be forced to buy a suit. He is known to interrogate his audiences
to ensure they are paying attention. So, be alert. You can read email
later.
On a more serious note: Shriram Krishnamurthi is a Professor in the
Computer Science at Brown University. Shrirams research has cut
across multiple disciplines ranging from Security, Networking, Formal
Methods, and HCI, but always rooted firmly in programming language
theory. Shriram has also made significant contributions to Computer
Science education and outreach. Shriram is a recipient of SIGPLANs
Robin Milner Young Researcher Award (2012), SIGSOFTs Influential
Educator Award (2018), SIGPLANs Software Award (jointly in 2018), and
Brown Universitys Wriston Fellowship.
COMMUNICATIONS
https://brown.zoom.us/j/94769764745
Meeting ID: 947 6976 4745
A few Zoom protocol recommendations:
You are welcome to share video; the more people that do, the more it
feels like we have a group of people rather than a sterile set of
boxes. On the other hand, you are welcome to not share video for
whatever reason (privacy, poor connection, etc.), which you dont have
to explain or justify.
Questions are WELCOME! However, I want to make sure everyone gets a
fair chance to ask them. Therefore, to ask questions, please use the
Raise Hand feature, and I will call on you.
Please keep yourself muted, especially if you are in a noisy
environment, unless you are asking a question. If you cant use audio,
you are welcome to type questions.
I will NOT be looking at the chat. Therefore, if you ask questions
unbidden in chat, I wont see them. Please only type questions into
chat once you ave been called on to ask (at which point I will look to
see if there is one in chat). You can always type your questions
offline and keep them handy to paste into chat.
Host Faculty: Prof. Deepak DSouza
 Series: Theory Seminar Title: A 3Approximation Algorithm for Maximum Independent Set of Rectangles  Speaker: Dr. Arindam Khan
Assistant Professor
Department of Computer Science & Automation
Indian Institute of Science
Bengaluru, India.  Date and Time: Friday, August 20, 2021, 4:00 PM
 Venue: Microsoft Teams  ONLINE
Abstract We study the Maximum Independent Set of Rectangles (MISR) problem, where we are given a set of axisparallel rectangles in the plane and the goal is to select a subset of nonoverlapping rectangles of maximum cardinality. In a recent breakthrough, Mitchell [2021] obtained the first constantfactor approximation algorithm for MISR. His algorithm achieves an approximation ratio of 10 and it is based on a dynamic program that intuitively recursively partitions the input plane into special polygons called cornerclipped rectangles, without intersecting certain special horizontal line segments called fences.
In this work, we present a 3approximation algorithm for MISR which is based on a similar recursive partitioning scheme. First, we use a partition into a more general class of axisparallel polygons with constant complexity each, which allows us to provide an arguably simpler analysis and at the same time already improves the approximation ratio to 6. Then, using a more elaborate charging scheme and a recursive partitioning into general axisparallel polygons with constant complexity, we improve our approximation ratio to 3. In particular, our partitioning uses more general fences that can be sequences of up to O(1) line segments each. This and our other new ideas may be useful for future work towards a PTAS for MISR.
For more details about the seminar please visit the website at https://www.csa.iisc.ac.in/iiscmsrseminar/
Microsoft Teams Link:
https://teams.microsoft.com/l/meetupjoin/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97f6a741e3b2c5ad4193976476%22%2c%22Oid%22%3a%227c84465ec38b4d7a9a9dff0dfa3638b3%22%7d
Host Faculty: Dr. Rahul Saladi
 Series: M.Tech (Research) Thesis Defense Title: nuKSM: NUMAaware Memory Deduplication for Multisocket Servers  Speaker: Akash Panda
 Faculty Advisor: Arkaprava Basu
 Date and Time: Tuesday, August 17, 2021, 2:30 PM
 Venue: https://teams.microsoft.com/l/meetupjoin/19%3ameeting_MzE5OGJmM2YtOWVhZC00YTM3LWJmMTEtZGZlZWM5YjFkZWE5%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97f6a741e3b2c5ad4193976476%22%2c%22Oid%22%3a%2282f39501c5b24bfb87c3f17ca74c00b6%22%7d
Abstract Teams meeting link: shorturl.at/jsAR9
Memory management is one of the most critical pieces in an operating system's design.
It has several responsibilities ranging from ensuring quick access to data by applications to enabling memory consolidation. For example, judicious placement of pages in multisocket NUMA (nonuniform memory access) servers could determine the access latencies experienced by an application. Similarly, memory deduplication can play a pivotal role in memory consolidation and overcommitment.
Different responsibilities of memory management can conflict with each other. This often happens when different subsystems of an OS are responsible for different memory management goals, and each works in its silo.
In this work, we report one such conflict that appears between memory deduplication and NUMA management. Linux's memory deduplication subsystem, namely KSM, is NUMA unaware. We demonstrate that memory deduplication can have unintended consequences to NUMA overheads experienced by applications running on multisocket servers. Linux's memory deduplication subsystem, namely KSM, is NUMA unaware.
Consequently, while deduplicating pages across NUMA nodes, it can place deduplicated pages in a manner that can lead to significant performance variations, unfairness, and subvert process priority.
We introduce NUMAaware KSM, a.k.a., nuKSM, that makes judicious decisions about the placement of deduplicated pages to reduce the impact of NUMA and unfairness in execution. nuKSM also enables users to avoid priority subversion. Finally, independent of the NUMA effect, we observed that KSM fails to scale well to large memory systems due to its centralized design. We thus extended nuKSM to adopt a decentralized design to scale to larger memory.
Speaker Bio: Akash Panda is an M.Tech (Research) student who worked in the area of operating system's memory management for this thesis under the supervision of Arkaprava Basu.Currently, he is working in the Server Performance Group in AMD, Bangalore.
Host Faculty: Arkaprava Basu
 Series: Theory Seminar Title: Recent progress in online matching  Some open problems in online advertising  Speaker: Dr. Zhiyi Huang
Associate Professor
Department of Computer Science
University of Hong Kong  Date and Time: Friday, August 13, 2021, 11:00 AM
 Venue: Microsoft Teams  ONLINE
Abstract Originated from the seminal work by Karp, Vazirani, and Vazirani (1990), online matching has been established as one of the most fundamental topics in the literature of online algorithms.
This is the second of two talks which presents the basics of online matching. The first talk focussed on General arrival models and todays talk will be looking at some Open problems in online advertising.
Open problems in online advertising:
AdWords and Display Ads are generalizations of the online bipartite matching problem by Karp et al. These problems capture online advertising which generates tens of billions of US dollars annually. This year, we introduce a new technique called online correlated selection, and design the first online algorithms for the general cases of AdWords and Display Ads outperforming greedy, which has remained the state of the art for more than 10 years, despite many attempts to find better alternatives.
For more details about the seminar please visit the website at https://www.csa.iisc.ac.in/iiscmsrseminar/
Microsoft Teams Link:
https://teams.microsoft.com/l/meetupjoin/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97f6a741e3b2c5ad4193976476%22%2c%22Oid%22%3a%227c84465ec38b4d7a9a9dff0dfa3638b3%22%7d
Host Faculty: Dr. Arindam Khan

