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

UPCOMING SEMINARS

Series: Theory Seminar
Title: Algorithmic advances on metric and graph clustering (Part 2)

  • Speaker: Dr. Vincent Viallat Cohen-Addad,
                   Research Scientist,
                   Google Zürich
  • Date and Time: Monday, October 18, 2021, 4:00 PM
  • Venue: Microsoft Teams - ON-LINE

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 k-median and k-means problems,

two popular objective functions for metric clustering, via some recent developments on the fixed-parameter

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 beyond-the-worst-case

analysis of the Louvain algorithm for finding the maximum modularity graphs clustering.

Microsoft Teams Link:

https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%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/iisc-msr-seminar/

Host Faculty: Dr. Arindam Khan

Video Archive Go Top

 

PAST SEMINARS

Series: M.Tech (Research)Thesis Defence -ONLINE
Title: A Trusted-Hardware 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 feature-rich 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/meetup-join/19%3ameeting_OTVlNGMzNzAtOWU3MC00ODA5LTk0MTAtNDNhZDc5YjNlMGFm%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%220432f3a0-d225-405c-b0f4-ff1ffaf4f1fd%22%7d

Video Archive Go Top

 

Series: Theory Seminar
Title: Algorithmic advances on metric and graph clustering (Part 1)

  • Speaker: Dr. Vincent Viallat Cohen-Addad
                   Research Scientist
                   Google Zürich
  • Date and Time: Friday, October 08, 2021, 4:00 PM
  • Venue: Microsoft Teams - ON-LINE

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 k-median and k-means problems,

two popular objective functions for metric clustering, via some recent developments on the fixed-parameter

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 beyond-the-worst-case

analysis of the Louvain algorithm for finding the maximum modularity graphs clustering.

Microsoft Teams Link:

https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d



For more details about the seminar please visit the website at https://www.csa.iisc.ac.in/iisc-msr-seminar/

Host Faculty: Dr. Arindam Khan

Video Archive Go Top

 

Series: M.Tech (Research)Thesis Defence -ONLINE
Title: A Multi-Policy 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 - ON-LINE

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 high-level policy by leveraging multiple skills inside an environment that presents various challenges.

Multi-policy 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 sub-policy 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 state-of-the-art RL algorithms and show that our approach outperforms the prior methods.

Microsoft teams link:

https://teams.microsoft.com/l/meetup-join/19%3ameeting_NTM0NzExMWMtNmFmYi00OWZjLTliM2EtNTNjYTQyNzg4OTVm%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%229d60e185-2600-4b28-b2d5-2d47a54928f3%22%7d

Video Archive Go Top

 

Series: M.Tech (Research)Thesis Defence -ONLINE
Title: A Framework for Privacy-Compliant 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 - ON-LINE

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 policy-enforcement 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/meetup-join/19%3ameeting_MWNhNDA3ODYtNWI3NC00Zjg3LWJjM2YtYzBiNTQwOTI2ZTBk%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%220432f3a0-d225-405c-b0f4-ff1ffaf4f1fd%22%7d

Video Archive Go Top

 

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 - ON-LINE

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 NP-complete 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 read-only 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 anti-concentration of subset sums (along with structural new insights in additive combinatorics) and (2) the representation method by Joux and Howgrave-Graham (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: 1682-1701.

Jesper Nederlof, Karol Wegrzycki: Improving Schroeppel and Shamir's algorithm for subset sum via orthogonal vectors. STOC 2021: 1670-1683

Nikhil Bansal, Shashwat Garg, Jesper Nederlof, Nikhil Vyas: Faster space-efficient algorithms for subset sum and k-sum. STOC 2017: 198-209

Per Austrin, Petteri Kaski, Mikko Koivisto, Jesper Nederlof: Dense Subset Sum May Be the Hardest. STACS 2016: 13:1-13:14



Microsoft Teams Link:

https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d

For more details about the seminar please visit the website at https://www.csa.iisc.ac.in/iisc-msr-seminar/

Host Faculty: Dr. Arindam Khan

Video Archive Go Top

 

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 - ON-LINE

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 constant-depth

multi-linear formulas. Neither such a separation between general

formulas and monotone circuits, nor a separation between multi-linear

circuits and monotone circuits were known before. Our result uses the

recent counter-example to the Log-Approximate-Rank 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 non-multi-linear 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 epsilon-sensitivity. 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/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d

For more details about the seminar please visit the website at https://www.csa.iisc.ac.in/iisc-msr-seminar/

Host Faculty: Dr. Anand Louis

Video Archive Go Top

 

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 - ON-LINE

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 q-Domination 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 q-domination partization problem for q = 2 and q =3. We prove that Minimum 2-Domination Partization is APX-complete. 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 3-domination colorable graphs. Finally, we prove that Minimum 3-Domination Partization is APX-hard, 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/meetup-join/19%3ameeting_YzI4MTA2NGQtZDAwZS00MGU4LWI4MzktM2YyYzVjMjE0ZmYx%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%222671ab71-955e-4e4e-9268-ebb188b00539%22%7d

Host Faculty: Dr. Arindam Khan

Video Archive Go Top

 

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 implementation-level weaknesses to devastating effect.

In this talk, I will give an overview of my journey so far in attempting to bridge the wonderfully multi-faceted aspects of cryptography, with the aim of designing, analyzing and securely implementing cryptographic solutions to real-world 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 “symmetric-key” 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 symmetric-key primitives. Finally, I will showcase that despite the theoretical security guarantees afforded by standardized symmetric-key cryptographic algorithms such as AES-128, practical implementations of SSE schemes remain vulnerable to “fault-injection attacks'' – a special class of implementation-level attacks powerful enough to reduce the keyspace for AES-128 from 2^{128} to a single key while relying on a single fault-injection. In particular, I will describe my recent work (appeared at Eurocrypt 2020) on a “fault propagation”-based key-recovery attack that completely breaks the security of an AES-128 implementation, even when equipped with dedicated protections against standard implementation-level 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, post-quantum 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/meetup-join/19%3ameeting_MzlkOTZhMmMtYmJjOC00MTJiLTg4OGYtZjg4ZjNkZTVmNTVj%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%224bcd3d56-e405-4b06-99fb-27742262f261%22%7d

Host Faculty: R. Govindarajan

Video Archive Go Top

 

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 - ON-LINE

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 sub-optimal 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/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d

For more details about the seminar please visit the website at https://www.csa.iisc.ac.in/iisc-msr-seminar/

Host Faculty: Dr. Rahul Saladi

Video Archive Go Top

 

Series: M.Tech (Research) Colloquium- ON-LINE
Title: Security of Post-Quantum 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 post-quantum cryptography. Multivariate signatures are prominent in post-quantum cryptography due to their fast, low-cost implementations and shorter signatures. Blind signatures are a special category of digital signatures with two security notions: blindness and one-more 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 one-more 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, PR-STI (2) Modified version of Single Target Inversion Problem, PR-mSTI (3) Chosen Target Inversion Problem, PR-CTI. 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 PR-mSTI 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 PR-CTI assumption. The PR-CTI 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 PR-mSTI 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/meetup-join/19%3ameeting_NzFiMjNmODEtN2ZkZi00OGU4LWEzOGEtZTdjMjM5OWI0ZWZl%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%22f24581ee-9350-45bb-b76b-26beecd9d45f%22%7d

Video Archive Go Top

 

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/meetup-join/19%3a13ca80f16f7948a2a87ac38e29410e0a%40thread.tacv2/1630390106337?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%2282f39501-c5b2-4bfb-87c3-f17ca74c00b6%22%7d

Abstract
GPUs are a key computing platform for many application domains. While the emergence of non-volatile memory has brought the promise of fi ne-grain byte-addressable 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 GPU-accelerated 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

Video Archive Go Top

 

Series: Theory Seminar
Title: Better-Than-2 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 - ON-LINE

Abstract
The Weighted Tree Augmentation Problem (WTAP) is one of the most basic connectivity augmentation problems. It asks how to increase the edge-connectivity 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 2-approximation 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/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d

For more details about the seminar please visit the website at https://www.csa.iisc.ac.in/iisc-msr-seminar/

Host Faculty: Dr. Arindam Khan

Video Archive Go Top

 

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 - ON-LINE

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/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d



For more details about the seminar please visit the website at https://www.csa.iisc.ac.in/iisc-msr-seminar/

Host Faculty: Dr. Arindam Khan

Video Archive Go Top

 

Series: M.Tech (Research) Colloquium- ON-LINE
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 - ON-LINE

Abstract
Question decomposition along with single-hop Question Answering (QA) system serve as useful modules in developing multi-hop 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 sequence-to-sequence neural architecture. Using this approach, it is difficult to capture the innate hierarchical structure of the decomposition. Inspired by database query languages a pseudo-formalism 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 syntax-aware models are usually interpretable. Motivated by the success of syntax-aware 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 encoder-decoder 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 real-world dataset demonstrate that the proposed approach outperforms the state-of-the-art 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/meetup-join/19%3ameeting_YTQ3YzdhOWMtMDBiYy00ODQxLWJmMDItMzlmY2MwNjFjYjY5%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%229c3e2bfe-1b0f-4d7b-a589-832878069dc6%22%7d

Video Archive Go Top

 

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 - ON-LINE

Abstract
Personalized recommendation systems use the data generated by user-item 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 cross-domain 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 top-N 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 user-item 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 multi-head and multi-layer 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 Multi-view Memory Attention mechanism) is proposed to extract relevant information from HINs. The proposed model is an end-to-end model which eliminates the need for learning a similarity matrix offline using some manually selected meta-paths before optimizing the desired objective function.

In the second part of the thesis, we focus on top-N 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 GRAM-SMOT -- a graph attention-based framework that considers higher-order 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 metric-learning approach. A strategy that leverages submodular optimization ideas is used to generate novel bundles.

We also study the problem of top-N personalized list continuation where the task is to curate the next items to user-generated 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 self-attention hypergraph and Transformer-based neural network architecture for the personalized list continuation task. Here, graph convolutions are used to learn the multi-hop relationship among entities of the same type. A self-attention-based hypergraph neural network is proposed to learn the ternary relationships among the interacting entities via hyperlink prediction in a 3-uniform hypergraph. Further, the entity embeddings are shared with a Transformer-based 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 cross-domain knowledge. We propose an end-to-end 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 non-linear relationships among entities within and across domains.

We conduct extensive experiments in each of these settings using several real-world datasets and demonstrate the efficacy of the proposed models.

Microsoft teams link: https://teams.microsoft.com/l/meetup-join/19%3ameeting_MWVhYWRkODUtZGI4OC00ZDZmLTk2NGMtZmViNTNiZmFmM2E3%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%229c3e2bfe-1b0f-4d7b-a589-832878069dc6%22%7d

Video Archive Go Top

 

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 ill-repute: 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

Video Archive Go Top

 

Series: Theory Seminar
Title: A 3-Approximation 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 - ON-LINE

Abstract
We study the Maximum Independent Set of Rectangles (MISR) problem, where we are given a set of axis-parallel rectangles in the plane and the goal is to select a subset of non-overlapping rectangles of maximum cardinality. In a recent breakthrough, Mitchell [2021] obtained the first constant-factor 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 corner-clipped rectangles, without intersecting certain special horizontal line segments called fences.

In this work, we present a 3-approximation algorithm for MISR which is based on a similar recursive partitioning scheme. First, we use a partition into a more general class of axis-parallel 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 axis-parallel 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/iisc-msr-seminar/

Microsoft Teams Link:

https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d

Host Faculty: Dr. Rahul Saladi

Video Archive Go Top

 

Series: M.Tech (Research) Thesis Defense
Title: nuKSM: NUMA-aware Memory De-duplication for Multi-socket Servers

  • Speaker: Akash Panda
  • Faculty Advisor: Arkaprava Basu
  • Date and Time: Tuesday, August 17, 2021, 2:30 PM
  • Venue: https://teams.microsoft.com/l/meetup-join/19%3ameeting_MzE5OGJmM2YtOWVhZC00YTM3LWJmMTEtZGZlZWM5YjFkZWE5%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%2282f39501-c5b2-4bfb-87c3-f17ca74c00b6%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 multi-socket NUMA (non-uniform memory access) servers could determine the access latencies experienced by an application. Similarly, memory de-duplication can play a pivotal role in memory consolidation and over-commitment.

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 de-duplication and NUMA management. Linux's memory de-duplication subsystem, namely KSM, is NUMA unaware. We demonstrate that memory de-duplication can have unintended consequences to NUMA overheads experienced by applications running on multi-socket servers. Linux's memory de-duplication subsystem, namely KSM, is NUMA unaware. Consequently, while de-duplicating pages across NUMA nodes, it can place de-duplicated pages in a manner that can lead to significant performance variations, unfairness, and subvert process priority.

We introduce NUMA-aware KSM, a.k.a., nuKSM, that makes judicious decisions about the placement of de-duplicated 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

Video Archive Go Top

 

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 - ON-LINE

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/iisc-msr-seminar/

Microsoft Teams Link:

https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d

Host Faculty: Dr. Arindam Khan

Video Archive Go Top

 

 

 

 

 

 

 

 

 

 

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