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: M.Tech (Research) Colloquium
Title: Modeling and verification of database-accessing applications

  • Speaker: Geetam Chawla
  • Faculty Advisor: Komondoor V. Raghavan
  • Date and Time: Monday, June 21, 2021, 12:00 PM
  • Venue: Online

Abstract
Databases are central to the functioning of most IT-enabled processes and services. In many domains, databases are accessed and updated via applications written in general-purpose languages, as such applications need to contain the business logic and workflows that are key to the organization. Therefore, automated tools are required not only for creation and testing of database schemas and queries, etc., but also for analysis, testing, and verification of database-accessing applications. In this work we describe a novel approach for modeling, analysis and verification of database-accessing applications. We target applications that use Object Relational Mapping (ORM), which is the common database-access paradigm in most Model-View Controller (MVC) based application development frameworks. In contrast with other approaches that try to directly analyze and prove properties of complex database accessing ORM-based code, our approach infers a relational algebra specification of each controller in the application. This specification can then be fed into any off-the-shelf relational algebra solver to check properties (or assertions) given by a developer.

We have implemented this approach as a tool that works for "Spring" based MVC applications. The tool was evaluated on a set of 58 specifications. The tool found 35 of these to be satisfied; of the rest, upon manual analysis, we found that two were genuinely violated, while the remaining 21 "unsatisfied" warnings were actually false positives. This preliminary evaluation reveals that the approach is scalable and quite precise.

Teams meeting link: https://teams.microsoft.com/l/meetup-join/19%3ameeting_MDA2MDgxNGYtYTZkNy00YzA4LTlkOWUtOGJlZDQ5NDA3OWVl%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%22cd42250e-1d66-4966-a431-6a8d7d5235ba%22%7d

Host Faculty: Komondoor V. Raghavan

Video Archive Go Top

 

Series: Ph.D. (Engg.) Colloquium- ONLINE
Title: MPCLeague: Robust MPC Platform for Privacy-Preserving Machine Learning

  • Speaker: Mr. Ajith S
                   Ph.D. Student
                   Dept. of CSA
  • Faculty Advisor: Prof. Arpita Patra
  • Date and Time: Wednesday, June 16, 2021, 11:00 AM
  • Venue: Microsoft Teams – ONLINE - https://teams.microsoft.com/l/meetup-join/19%3ameeting_NGExMzk4NWEtMmY3My00OTViLWFlMDQtMmNlMTNhMmI2NmRj%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%22a787cc01-57cc-4fc1-b7e1-4e9d51923f6d%22%7d

Abstract
In the modern era of computing, machine learning tools have demonstrated their potential in vital sectors, such as healthcare and finance, to derive proper inferences. The sensitive and confidential nature of the data in such sectors raises genuine concerns for data privacy. This motivated the area of Privacy-preserving Machine Learning (PPML), where privacy of data is guaranteed. Typically, machine learning techniques require significant computing power, which leads clients with limited infrastructure to rely on the method of Secure Outsourced Computation (SOC). In the SOC setting, the computation is outsourced to a set of specialized and powerful cloud servers and the service is availed on a pay-per-use basis. In this thesis, we design an efficient platform, MPCLeague, for PPML in the SOC setting using Secure Multi-party Computation (MPC) techniques.

MPC, the holy-grail problem of secure distributed computing, enables a set of n mutually distrusting parties to perform joint computation on their private inputs in a way that no coalition of t parties can learn more information than the output (privacy) or affect the true output of the computation (correctness). While MPC, in general, has been a subject of extensive research, the area of MPC with a small number of parties has drawn popularity of late mainly due to its application to real-time scenarios, efficiency and simplicity. This thesis focuses on designing efficient MPC frameworks for 2, 3 and 4 parties, with at most one corruption and supports ring structures.

Our platform aims at achieving the most substantial security notion of robustness, where the honest parties are guaranteed to obtain the output irrespective of the behaviour of the corrupt parties. A robust protocol prevents the corrupt parties from repeatedly causing the computations to rerun, thereby upholding the trust in the system. While on the roadmap to attain robustness, our frameworks also demonstrate constructions with improved performance that achieve relaxed notions of security: security with abort and fairness. A fair protocol enforces the restriction that either all parties or none of them receive the output.

The general structure of the computation involves the execution of the protocol steps once the participating parties have supplied their inputs. Finally, the output is distributed to all the parties. However, to enhance practical efficiency, many recent works resort to the preprocessing paradigm, which splits the computation into two phases; a preprocessing phase where input-independent (but function-dependent), computationally heavy tasks can be computed, followed by a fast online phase. Since the same functions in ML are evaluated several times, this paradigm naturally fits the case of PPML, where the ML algorithm is known beforehand.

At the heart of this thesis are four frameworks - ASTRA, SWIFT, Tetrad, ABY2.0 - catered to different settings.

- ASTRA: We begin with the setting of 3 parties (3PC), which forms the base case for honest majority. If a majority of the participating parties are honest, then the setting is deemed an honest majority setting. In the set of 3 parties, at most one party can be corrupt, and this framework tackles semi-honest corruption, where the corrupt party follows the protocol steps but tries to glean more information from the computation. ASTRA acts as a stepping stone towards achieving a stronger security guarantee against active corruption. Our protocol requires communication of 2 ring elements per multiplication gate during the online phase, attaining a per-party cost of less than one element. This is achieved for the first time in the regime of 3PC.

- SWIFT: Designed for 3 parties, this framework tackles one active corruption where the corrupt party can arbitrarily deviate from the computation. Building on ASTRA, SWIFT provides a multiplication that improves the communication by at least 3x over state of the art, besides improving security from abort to robustness. In the regime of malicious 3PC, SWIFT is the first robust and efficient PPML framework. It achieves a dot product protocol with communication independent of the vector size for the first time.

- Tetrad: Designed for 4 parties in the honest majority, the fair multiplication protocol in Tetrad requires communication of only 5 ring elements instead of 6 in the state-of-the-art. The fair framework is then extended to provide robustness without inflating the costs. A notable contribution is the design of the multiplication protocol that supports on-demand applications where the function to be computed is not known in advance.

- ABY2.0: Moving on to the stronger corruption model where a majority of the parties can be corrupt, we explore the base case of 2 parties (2PC). Since we aim to achieve robustness which is proven to be impossible in active corruption, we restrict ourselves to semi-honest corruption. The prime contribution of this framework is the scalar product for which the online communication is two ring elements irrespective of the vector dimension. This is a feature achieved for the first time in the 2PC literature. Along with PPML, we showcase our frameworks practicality with three relevant applications in the 2PC setting: i) AES S-box, ii) Circuit-based Private Set Intersection, iii) Biometric Matching.

Our frameworks provide the following contributions in addition to the ones mentioned above. First, we support multi-input multiplication for arithmetic and boolean worlds, improving the online phase in rounds and communication. Second, all our frameworks except SWIFT, incorporate truncation without incurring any overhead. Finally, we introduce efficient instantiation of garbled-world, tailor-made for the mixed-protocol framework for the first time. The mixed-protocol approach, combining arithmetic, boolean and garbled style computations, has demonstrated its potential in several practical use-cases like PPML. To facilitate the computation, we also provide the conversion mechanisms to switch between the computation styles.

The practicality of our framework is argued through improvements in the benchmarking of widely used ML algorithms -- Linear Regression, Logistic Regression, Neural Networks, and Support Vector Machines. One variant of our frameworks aims at minimizing the execution time, while the other focuses on the monetary cost.

The concrete efficiency gains of our frameworks coupled with the stronger security guarantee of robustness make our platform an ideal choice for a real-time deployment of privacy-preserving machine learning techniques.

References: [1] Harsh Chaudhari, Ashish Choudhury, Arpita Patra, Ajith Suresh. ASTRA: High Throughput 3PC over Rings with Application to Secure Prediction. ACM CCSW,19

[2] Arpita Patra, Ajith Suresh. BLAZE: Blazing Fast Privacy-Preserving Machine Learning. NDSS,20

[3] Harsh Chaudhari, Rahul Rachuri , Ajith Suresh. Trident: Efficient 4PC Framework for Privacy Preserving Machine Learning. NDSS20

[4] Nishat Koti, Mahak Pancholi, Arpita Patra, Ajith Suresh. SWIFT: Super-fast and Robust Privacy-Preserving Machine Learning. USENIX Security,21

[5] Arpita Patra, Thomas Schneider, Ajith Suresh, Hossein Yalame. ABY2.0: Improved Mixed-Protocol Secure Two-Party Computation. USENIX Security,21

[6] Nishat Koti, Arpita Patra, Rahul Rachuri, Ajith Suresh. Tetrad: Fair and Robust 4PC Framework for Privacy-Preserving Machine Learning. Under Submission.

Microsoft Teams Link:

https://teams.microsoft.com/l/meetup-join/19%3ameeting_NGExMzk4NWEtMmY3My00OTViLWFlMDQtMmNlMTNhMmI2NmRj%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%22a787cc01-57cc-4fc1-b7e1-4e9d51923f6d%22%7d

Video Archive Go Top

 

PAST SEMINARS

Series: M.Tech (Research)Thesis Defence -ONLINE
Title: Revisiting Statistical Techniques for Result Cardinality Estimation

  • Speaker: Mr. Dhrumilkumar Shah
                   M.Tech (Research) student
                   Dept. of CSA
  • Faculty Advisor: Prof. Jayant R. Haritsa
  • Date and Time: Thursday, June 10, 2021, 12:00 PM
  • Venue: Microsoft Teams - ONLINE

Abstract
The Relational Database Management Systems (RDBMS) constitute the backbone of today's information-rich society, providing a congenial environment for handling enterprise data during its entire life cycle of generation, storage, maintenance, and processing. The Structured Query Language (SQL) is the standard interface to query the information present in RDBMS-based storage. Knowing the expected size of the SQL query result, measured in terms of the output row-cardinality, prior to execution can benefit both the RDBMS system and the user in several ways. The use-cases include assessing query feasibility, approximate query answering, query progress monitoring, and resource allocation strategies. In the context of our work, we define cardinality estimation as the estimation of the result size (number of rows in the output) of the given SQL query.

Unfortunately, the histogram and sampling-based techniques commonly used in industrial database engines for cardinality estimation are often woefully inaccurate in practice. This lacuna has motivated a recent slew of papers advocating the use of machine-learning/deep-learning techniques for cardinality estimation. However, these new approaches have their own limitations regarding significant training effort, inability to handle dynamic data-updates, and generalization to unseen queries.

In this work, we take a relook at the traditional random sampling and investigate whether they can be made to work satisfactorily when augmented with lightweight data structures. Specifically, we present GridSam – a Grid-based Dynamic Sampling technique, which essentially augments random sampling with histograms, incorporating both algorithmic and platform innovations.

From the algorithmic perspective, GridSam first creates a multi-dimensional grid overlay by partitioning the data-space on “critical” attributes, and then performs dynamic sampling from the confined query-specific region of the grid to capture correlations. A greedy methodology targeted towards reducing the Zero Sample Problem occurrence is used to determine the set of “critical” attributes as the grid dimensions. Further, insights from the Index-based Join Sampling (IBJS) technique are leveraged to direct the sampling in multi-table queries. Finally, learned-indexes are incorporated to reduce the index-probing cost for join sampling during the estimation process.

From the platform perspective, GridSam leverages the massive parallelism offered by current GPU architectures to provide fast grid setup times. This parallelism is also extended to the run-time estimation process.

A detailed performance study on benchmark environments indicates that GridSam computes cardinality estimates with accuracies competitive to contemporary learning-based techniques. Moreover, it does so while achieving an orders-of-magnitude reduction in setup time. Further, the estimation time is in the same ballpark as both traditional and learning-based techniques. Finally, a collateral benefit of GridSam's simple and highly parallelizable design is that, unlike learned estimators, it is amenable to dynamic data environments with frequent data-updates.

Microsoft Teams Link:

https://teams.microsoft.com/l/channel/19%3ahnmvZ5nGAP1ZF26uEVJEq8xHNmslkLLM1laDUK5iHVk1%40thread.tacv2/General?groupId=b3316384-7d8e-441d-80c8-fd1d1a5250c6&tenantId=6f15cd97-f6a7-41e3-b2c5-ad4193976476

Video Archive Go Top

 

Series: M.Tech (Research)Thesis Defence -ONLINE
Title: Design, Implementation, and Analysis of a TLB-based Covert Channel on GPUs

  • Speaker: Mr. Ajay Nayak
                   M.Tech(Research) Student
                   Dept. of CSA
  • Faculty Advisor: Prof. Vinod Ganapathy
  • Date and Time: Wednesday, June 09, 2021, 11:00 AM
  • Venue: Microsoft Teams - ONLINE - https://teams.microsoft.com/l/meetup-join/19%3ameeting_YjJhMWJjYTYtNGRlZi00ODFmLWI3OTQtZTIyOGVmZDc5NzA2%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

Abstract
GPUs are now commonly available in most modern computing platforms. They are increasingly being adopted in cloud platforms and data centers due to their immense computing capability. In response to this growth in usage, manufacturers are continuously trying to improve GPU hardware by adding new features. However, this increase in usage and the addition of utility-improving features can create new, unexpected attack channels. In this thesis, we show that two such features—unified virtual memory (UVM) and multi-process service (MPS)—primarily introduced to improve the programmability and efficiency of GPU kernels have an unexpected consequence—that of creating a novel covert timing channel via the GPUs translation lookaside buffer (TLB) hierarchy. To enable this covert channel, we first perform experiments to understand the characteristics of TLBs present on a GPU. The use of UVM allows fine-grained management of translations, and helps us discover several idiosyncrasies of the TLB hierarchy, such as three-levels of TLB, coalesced entries. We use this newly-acquired understanding to demonstrate a novel covert channel via the shared TLB. We then leverage MPS to increase the bandwidth of this channel by 40×. Finally, we demonstrate the channels utility by leaking data from a GPU-accelerated database application.

Microsoft Teams - ONLINE https://teams.microsoft.com/l/meetup-join/19%3ameeting_YjJhMWJjYTYtNGRlZi00ODFmLWI3OTQtZTIyOGVmZDc5NzA2%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: Ph.D. (Engg.) Colloquium- ONLINE
Title: Analysis and Methods for Knowledge Graph Embeddings

  • Speaker: Mr. Chandrahas
                   Ph.D. (Engg.) Student
                   Dept. of CSA
  • Faculty Advisor: Prof. Partha Pratim Talukdar
  • Date and Time: Friday, June 04, 2021, 4:00 PM
  • Venue: Microsoft Teams - ONLINE

Abstract
Knowledge Graphs (KGs) are multi-relational graphs where nodes represent entities, and typed edges represent relationships among entities. These graphs store real-world facts such as (Lionel Messi, plays-for-team, Barcelona) as edges, called triples. KGs such as NELL, YAGO, Freebase, and WikiData have been very popular and support many AI applications such as Web Search, Query Recommendation, and Question Answering. Although popular, these KGs suffer from incompleteness. Learning Knowledge Graph Embeddings (KGE) is a popular approach for predicting missing edges (i.e., link prediction) and representing entities and relations in downstream tasks. While numerous KGE methods have been proposed in the past decade, our understanding and analysis of such embeddings have been limited. Further, such methods only work well with ontological KGs. In this thesis, we address these gaps.

Firstly, we study various KGE methods and present an extensive analysis of these methods, resulting in interesting insights. Next, we address an under-explored problem of link prediction in Open Knowledge Graphs (OpenKGs) and present a novel approach that improves the type compatibility of predicted edges. Lastly, we present an adaptive interaction framework for learning KG embeddings that generalizes many existing methods.

Analysis of KGE Embeddings In the first part, we present a macro and a micro analysis of embeddings learned by various KGE methods.

Despite the popularity and effectiveness of KG embeddings, their geometric understanding (i.e., arrangement of entity and relation vectors in vector space) is unexplored. We initiate a study to analyze the geometry of KG embeddings and correlate it with task performance and other hyper-parameters. Firstly, we present a set of metrics (e.g., Conicity, ATM) to analyze the geometry of a group of vectors. Using these metrics, we find sharp differences between the geometry of embeddings learned by different classes of KGE methods. The vectors learned by a multiplicative model lie in a narrow cone, unlike additive models where the vectors are spread out in the space. This behavior of multiplicative models is amplified by increasing the number of negative samples used for training. Further, a very high Conicity value is negatively correlated with the performance on the link prediction task.

We also study the problem of understanding KG embeddings semantics and propose an approach to learn more coherent dimensions. A dimension is coherent if the top entities have similar types (e.g., person). In this work, we formalize the notion of coherence using entity co-occurrence statistics and propose a regularizer term that maximizes coherence while learning KG embeddings. The proposed approach significantly improves coherence while having a comparable performance with baseline in the link prediction and triple classification tasks. Further, based on the human evaluation, we demonstrate that the proposed approach learns more coherent dimensions than the baseline.

A method for OpenKG Embedding In the second part, we address the problem of learning KG embeddings for Open Knowledge Graphs (OpenKGs), focusing on improving link prediction. An OpenKG refers to a set of (head noun phrase, relation phrase, tail noun phrase) triples such as (tesla, return to, new york) extracted from a text corpus using OpenIE tools. While OpenKGs are easy to bootstrap for a domain, they are very sparse. Therefore, link prediction becomes an important step while using these graphs in downstream tasks. Learning OpenKG embeddings is one approach for link prediction that has received some attention lately. However, on careful examination, we find that current algorithms often predict noun phrases (NPs) with incompatible types for given noun and relation phrases. We address this problem and propose OKGIT that improves OpenKG link prediction using novel type compatibility score and type regularization. With extensive experiments on multiple datasets, we show that the proposed method achieves state-of-the-art performance while producing type compatible NPs in the link prediction task.

An Adaptive Framework for KG Embeddings In the third part, we address the problem of improving the KGE models.

Firstly, we show that the performance of existing approaches varies across different datasets, and a simple neural network-based method can consistently achieve better performance on these datasets. Upon analysis, we find that KGE models depend on fixed sets of interactions among the dimensions of entity and relation vectors. Therefore, we investigate ways to learn such interactions automatically during training. We propose an adaptive interaction framework for learning KG embeddings, which can learn appropriate interactions while training. We show that some of the existing models could be seen as special cases of the proposed framework. Based on this framework, we also present two new models, which outperform the baseline models on the link prediction task. Further analysis demonstrates that the proposed approach can adapt to different datasets by learning appropriate interactions.

Microsoft Teams Link: https://teams.microsoft.com/l/meetup-join/19%3ameeting_MDdmNzk0ZTMtZGRjOS00ZmExLTgwZjQtZmI1YmNlZDk3OWVm%40thread.v2/0?context=%7b"Tid"%3a"6f15cd97-f6a7-41e3-b2c5-ad4193976476","Oid"%3a"f43791af-6a7d-4204-a02a-956254a32597"%7d

Video Archive Go Top

 

Series: M.Tech (Research) Colloquium- ONLINE
Title: A Trusted-Hardware Backed Secure Payments Platform for Android

  • Speaker: Mr. Rounak Agarwal
                   M.Tech(Research) Student
                   Dept. of CSA
  • Faculty Advisor: Prof. Vinod Ganapathy
  • Date and Time: Friday, June 04, 2021, 11:00 AM
  • Venue: Microsoft Teams - ONLINE - https://teams.microsoft.com/l/meetup-join/19%3ameeting_OGU1ZmRjNWUtM2Q2ZC00NzcwLTlhZWQtMDJhMDlkYWIzNzcy%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

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 signifi cantly 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 con fidential 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 confi dential 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_OGU1ZmRjNWUtM2Q2ZC00NzcwLTlhZWQtMDJhMDlkYWIzNzcy%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: ICRA Conference practice talk
Title: Can Non-Humanoid Social Robots Reduce Workload of Special Educators : An Online and In-Premises Field Study (Joint work with Academy for severe handicaps and Autism)

  • Speaker: Ms. Nabanita Paul
                   Ph.D (Engg.) student
                   Dept. of CSA
                   
                   (This is a practice talk for a paper to be presented next week at ICRA conference)
  • Faculty Advisor: Prof. Chiranjib Bhattacharyya
  • Date and Time: Friday, May 28, 2021, 4:00 PM
  • Venue: Microsoft Teams - ONLINE

Abstract
Socially Assistive Robotics have been used in Autism Spectrum Disorder (ASD) interventions, such studies often exclude Special Educators (SEs) and often use expensive humanoid robots. In this paper, we investigate whether non-humanoid toy robots can act as teaching aids in ASD Education, in particular, can they reduce the workload of SEs. We target two most common yet divergent problems from Individualized Education Plans (IEPs) of ASD children - communication and gross motor skills. We present results from three studies a) toy robot Cozmo assists SEs in verbal lessons in school premises, b) mini drone Tello helps SEs in exercise lessons in school premises, and c) Cozmo, SEs, and ASD children connect remotely, as mandated due to the Covid-19 pandemic, for verbal lessons. All three studies showed improvement in learning outcomes and reduction in prompts from the SEs, denoting reduced workload. The effect of a robots virtual presence in online ASD interventions has not been studied before. However, our results show that children spent more time on lessons in online intervention with Cozmo, suggesting that using robots should also be considered when designing online interventions. Furthermore, the roles of Cozmo were analyzed, and we found children showed increased spontaneous interaction when Cozmo acts as a Co-Instructor. Thus, preliminary results indicate toy robots, as opposed to expensive humanoids, may have significant potential in aiding SEs in Autism education.

Speaker Bio:
Nabanita is a PhD student in Machine learning lab under Prof. Chiranjib Bhattacharya in CSA dept., IISc . Her current interest is creating behaviour models for Social Robots to be used in autism education, and in general, other neuro-developmental disorders. Microsoft teams link: https://teams.microsoft.com/l/meetup-join/19%3ameeting_Zjc0ZGQ3YjItYzFhNC00YmQ2LWE5MjEtMGE5MmQyM2RmZWRm%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%22974825d6-8ace-42c2-98fe-f29247120077%22%7d

Host Faculty: Prof. Chiranjib Bhattacharyya

Video Archive Go Top

 

Series: Ph.D (Engg.)Thesis Defence -ON-LINE
Title: New Algorithmic and Hardness results in Learning, Error Correcting Codes, and Constraint Satisfaction Problems

  • Speaker: Mr. Suprovat Ghoshal
                   Ph.D (Engg) student
                   Dept. of CSA
  • Faculty Advisor: Prof. Arnab Bhattacharyya and Prof. Siddharth Barman
  • Date and Time: Tuesday, May 11, 2021, 4:00 PM
  • Venue: Microsoft Teams - ONLINE

Abstract
Approximation algorithms are a natural way to deal with the intractability barrier that is inherent in many naturally arising computational problems. However, it is often the case that the task of solving the approximation version of the problem is as hard as the exact version of the problem itself, which is the underlying philosophy driving the study of hardness of approximation. While the last couple of decades has seen significant progress in terms of tight inapproximability results for many important problems, there are still several fundamental problems for which best known lower bounds in terms of the hardness of approximation is still quite far off from their best known upper bounds achievable using efficient algorithms. In this thesis, we investigate this phenomenon in the context of several fundamental com- putational problems in Learning Theory, Error Correcting Codes and Constraint Satisfaction Problems (CSPs), along the following themes:

1. Hardness of Learning using Thresholds: Improper learning – i.e., learning a concept class with a different and potentially easier to deal with hypothesis class – is often used as natural relaxation when the exact (proper) learning problem is intractable. In this thesis, we show the NP-Hardness of (improperly) learning natural concept classes such as Halfspaces and Disjunctive Normal Forms using threshold functions. Our results are tight with respect to efficiently achievable approximation factors for learning using arbitrary functions of thresholds.

2. Parameterized Complexity of Finding Sparse Solutions: Many natural problems such as k-VectorSum and k-EvenSet can be modeled as finding a sparse solution to a system of equations over finite fields. We study these problems in the framework of parameterized complexity and give new (and often tight) lower bounds for exact and approximation versions of these problems under various hypotheses. We also use these results to establish new hardness results for learning sparse parities.

3. Vertex Deletion CSPs: We study Vertex deletion CSPs, which are a variant of CSPs where the objective is to delete the least number of vertices to recover a fully satisfi- able sub-instance. In particular, we give new algorithmic and hardness results for the StrongUniqueGames problem which is the vertex deletion variant of UniqueGames, establishing a connection with small-set-vertex-expansion en route. We also give new algo- rithmic results for vertex deletion CSPs such as OddCycleTransversal, Balanced- VertexSeparator, Partial-3-Coloring in more tractable settings such as when the underlying constraint graph has low threshold rank or is sampled semi-randomly.

4. Testing Sparsity: We also investigate the following question: can one design efficient algorithms for testing a property for which the search/optimization version is intractable? We study this question in the form of testing sparsity, where one simply wishes to check whether a matrix admits a sparse factorization. While the optimization of the problem (Dictionary Learning) is intractable without distributional assumptions, we design an efficient algorithm for the property testing formulation of this problem. We also extend our results to the noise tolerant setting and settings where the basis of representation is known.

Microsoft Teams link:

https://teams.microsoft.com/l/meetup-join/19%3ameeting_OGQzZDlkODItZDBmNi00M2JmLWJjYmEtZmRjYWJkOTU4NWQy%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%22497b6b67-f9b1-41bc-a3fb-f22b0fd477ef%22%7d

Video Archive Go Top

 

Series: M.Tech (Research)Thesis Defence -ON-LINE
Title: Robust Algorithms for recovering planted structures in Semi-random instances

  • Speaker: Mr. Yash Khanna
                   M.Tech (Research) student
                   Dept. of CSA
  • Faculty Advisor: Dr. Anand Louis
  • Date and Time: Monday, May 03, 2021, 11:00 AM
  • Venue: Microsoft Teams - ONLINE

Abstract
In this work, we design algorithms for two fundamentally important and classical graph problems in the planted setting. Both of these problems are NP-hard and the bounds known from the algorithmic front are either not fully understood, or not much progress can be made because of tight lower bounds. Thus it is natural to consider semi-random models for these problems. These models are inspired from the seminal paper of Feige and Killian [FK01] and have been studied in numerous follow-up works with the latest ones by Steinhardt, and McKenzie et al. [Ste17, MMT20]. The construction of our instance starts with an empty graph, then an arbitrary set of vertices (S) is chosen and either a dense graph or a clique (or an independent set) is planted on it, the subgraph on S x VS is a random graph, while the subgraph on VS might be a random, arbitrary, or some special graph (depending on the model). Our algorithms are based on rounding semidefinite programs and our primary focus is on recovering (completely or partially) the planted structure (S) with high probability (over the randomness of the input). We give algorithms that exploit the geometry of the corresponding vectors (from the SDP) and are easy to design/analyse.

The two problems which we study are:

1) Densest k-Subgraph/k-Clique Given an undirected graph G, the Densest k-Subgraph problem (DkS) asks to compute a set S subseteq V of cardinality k such that the weight of edges inside S is maximized. This is a fundamental NP-hard problem whose approximability, in spite of many decades of research, is yet to be settled. There is a significant gap between the best known worst-case approximation factor of this problem [BCC+10] and the hardness of approximation for it (assuming the Exponential Time Hypothesis) [Man17]. We ask what are some "easier" instances of this problem? We propose some natural semi-random models of instances with a planted dense subgraph, and study approximation algorithms for computing the densest subgraph in them. There are many such random and semi-random models which have been studied in the literature [BCC+10, Ame15, HWX16, BA19 etc.].

2) Independent Set in Hypergraphs The independent set problem in graphs poses the following question: given a graph, and a subset of vertices such that any two vertices of the set do not have an edge between them. The maximization version of this problem features as one of the Karp's original twenty-one NP-complete problems ([Kar72], the clique problem instead of its complement, the independent set problem). The independent set problem is relatively well understood and by the famous result of Håstad [Hås99], the lower and upper bounds of this problem are tight. Hypergraphs are a natural extension of graphs, where each edge is formed across a tuple of distinct vertices. For a graph, each tuple has a size, two. To the best of our knowledge, semi-random models on hypergraphs have not been studied so far. Studying classical problems like these on hypergraphs is naturally of theoretical as well as practical interest. We study the algorithmic problems studied in McKenzie et al. [MMT20] and develop algorithms for them in the case of hypergraphs.

References:

[1] Yash Khanna and Anand Louis. Planted Models for the Densest k-Subgraph Problem. In FSTTCS, 2020. [2] Yash Khanna, Anand Louis, and Rameesh Paul. Independent Sets in Semi-random Hypergraphs. In WADS, 2021. [3] Yash Khanna. Exact recovery of Planted Cliques in Semi-random graphs. In Submission.

Note: All the above e-prints are available online on arXiv.

Speaker Bio:
Yash Khanna is a third (and final) year M.Tech (Research) student in the Department of Computer Science and Automation in the Theory group. He previously graduated from BITS Pilani. His research interests include Algorithms and Complexity. Link to Microsoft Teams: https://teams.microsoft.com/l/meetup-join/19%3ameeting_YThmNzFjMzAtY2FkMy00ZmNkLTk0NGEtYTllOTViNGE2M2Zl%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%22a57dc80f-813f-4a35-aa24-34fdc7026ee7%22%7d

Video Archive Go Top

 

Series: M.Tech (Research) Thesis 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: Wednesday, April 28, 2021, 11:00 AM
  • 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_ODk1OTI2YjEtNTg5NS00NGQ2LWExYjUtZjVkNDc5ODNhOTZm%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: M.Tech (Research) Thesis Colloquium: ON-LINE
Title: A Novel Neural Network Architecture for Sentiment-oriented Aspect-Opinion Pair Extraction

  • Speaker: Mr. Kapil Jayesh Pathak
                   M.Tech (Research) student
                   Dept. of CSA
  • Faculty Advisor: Prof. Shirish K Shevade
  • Date and Time: Wednesday, April 28, 2021, 10:00 AM
  • Venue: Microsoft Teams - ON-LINE

Abstract
Over the years, fine-grained opinion mining in online reviews has received great attention from the NLP research community. It involves different tasks such as Aspect Term Extraction (ATE), Opinion Term Extraction (OTE), etc. Opinion Term Extraction (OTE) aims to detect different opinion expressions which convey certain attitude in the review while Aspect Term Extraction (ATE) aims to identify the entities or proposition from the review at which the attitude is directed. Recently, the NLP research community got attracted to aspect-opinion relation modeling. Such modeling would be helpful for aspect-opinion pair extraction that would be used for downstream tasks such as aspect-based sentiment analysis, opinion summarization, etc.

As online reviews may contain different sentiment polarities for different aspects of the products, it would help companies find all aspects for which the customers gave positive or negative feedback. In this thesis, we propose a new opinion mining task called Sentiment-oriented Aspect-Opinion Pair Extraction (SAOPE), which aims to find all aspect-opinion pairs from customer reviews given that these pairs convey the specified sentiment polarity.

We present a novel neural network architecture for the SAOPE task. In the proposed approach, aspect-opinion co-extraction is performed first and then the aspect-opinion pairs are generated through relation modeling. The aspect and the corresponding opinion words are closely related in the dependency trees. Hence, we explore graph neural networks to utilize syntactic information generated from the dependency tree of the reviews to model the relationship between the aspects and corresponding opinion words. We design a modified graph attention network (GAT) called Graph Co-attention Network (GCAT) and compare its performance with Graph Convolution Network (GCN) and Graph Attention Network (GAT) for the aspect-opinion co-extraction and the relation detection. For the SAOPE task, we evaluate our model on SemEval Challenge datasets and show that GCAT and GAT perform better than the baseline model with GCN for aspect-opinion co-extraction. We demonstrate that the proposed Graph Co-attention Network (GCAT) performs better than other graph neural networks for aspect-opinion relation detection on the publicly available benchmark datasets.

Microsoft Teams link:

https://teams.microsoft.com/l/meetup-join/19%3ameeting_OWMzMGM4NzItYTliNC00NmIzLWIxZDQtNTkzNTU5OGFiZTI3%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 Thesis Colloquium- ON-LINE
Title: Novel First-order Algorithms for Non-smooth Optimization Problems in Machine Learning

  • Speaker: Mr. Achintya Kundu
                   Ph.D (Engg.) student
                   Dept. of CSA
  • Faculty Advisor: Prof. Chiranjib Bhattacharyya
  • Date and Time: Tuesday, April 27, 2021, 9:30 AM
  • Venue: Microsoft Teams - ON-LINE

Abstract
This thesis is devoted to the design of efficient optimization algorithms for machine learning (ML) problems where the underlying objective function to be optimized is convex but not necessarily differentiable. Such non-smooth objective functions are ubiquitous in ML mainly due to the use of one or more of the following: (a) non-differentiable loss functions, (b) sparsity promoting regularization terms, (c) constraint sets to induce specific structure on the parameters to be learned. Motivated by a wide range of learning problems that can be cast as optimization of a non-smooth convex objective, we focus on developing first-order algorithms with non-asymptotic convergence rate guarantees to solve such problems in large-scale settings. Based on shortcomings of the existing research in this domain, we address the following specific issues in this thesis.

First, we consider the problem of learning a kernel matrix from m similarity matrices under a general convex loss. The existing algorithms do not apply if one employs arbitrary loss functions and often can not handle m>1 case. Based on the Mirror Descent (MD) framework, we present several provably convergent iterative algorithms that exploit the availability of off-the-shelf support vector machine (SVM) solvers. One of the significant contributions involves an extension of the well-known MD algorithm for simplex to handle the Cartesian product of positive semidefinite (PSD) matrices leading to a novel algorithm called Entropic Multiple Kernel Learning. We also show simulation results on protein structure classification involving several similarity matrices to demonstrate the proposed algorithms efficacy.

Next, we focus on minimizing a convex function over a feasible set given by the intersection of finitely many simple sets, each of which is equipped with a projection oracle. Examples of constraint sets that possess such structure include the set of doubly stochastic matrices, elliptope, the intersection of PSD cone with an L1-norm ball, etc. The main difficulty lies in computing the projection of a point onto the feasible set. Exploiting the intersecting sets linear regularity property, we present an exact penalty approach that leads to first-order algorithms with explicit guarantees on the approximate solutions distance from the feasible set. Further, we show improved iteration-complexity when the objective possesses structural smoothness / strong convexity. This is achieved through a saddle-point reformulation where the proximal operators required by the primal-dual algorithms can be computed in closed form. We illustrate the benefits of our approach on a graph transduction problem and on graph matching.

Third, we consider convex-concave saddle point problems with bilinear interaction structure. This class of problems encompasses most convex optimization problems arising in ML and includes minimizing the sum of many simple non-smooth convex functions as a special case; thereby, it subsumes learning problems involving complex regularization terms such as total-variation based image denoising, overlapping group lasso, isotonic regression, etc. We first propose a primal-dual algorithm for this general class of problems that can achieve the O(1/T) convergence rate guarantee on the non-ergodic primal-dual iterate pair. Further, assuming strong convexity in the primal domain, we show an improved non-ergodic convergence rate of O(1/T^2). In contrast, the existing primal-dual algorithms achieve such convergence rate only in the ergodic or semi-ergodic setting.

Finally, we consider the classical setting of minimizing the sum of two convex functions: a smooth one (possessing Lipschitz continuous gradient) and a simple non-smooth one with easy to compute proximal operator. The well-known FISTA algorithm (also Nesterovs accelerated gradient method) achieves the optimal O(1/T^2) non-ergodic convergence rate for this problem. One of the drawbacks of these fast gradient methods is that they require computing gradients of the smooth function at points different from those on which the convergence rate guarantee applies. Inspired by the use of past gradients as momentum in training deep nets, we propose an accelerated gradient algorithm to rectify this drawback keeping the convergence rate intact. We achieve this through a judicious choice of momentum in both primal and dual space. To the best of our knowledge, this is the first accelerated gradient algorithm that achieves an O(1/T^2) convergence rate guarantee on the iterates at which gradients are evaluated. This fills a significant research gap as Polyaks Heavy Ball method guarantees accelerated convergence rate through gradient momentum only for a restrictive class of twice differentiable and strongly convex objective functions.

The Microsoft Teams link:

https://teams.microsoft.com/l/meetup-join/19%3ameeting_NmFmY2Q2ZmYtYTEwZC00YmZkLWE3NDMtNGNkMTdlNzEwY2Fk%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%22f9260723-90fc-447a-9c09-fe900a1e6645%22%7d

Video Archive Go Top

 

Series: M.Tech (Research) Thesis Colloquium- ON-LINE
Title: Scaling Blockchains Using Coding Theory and Verifiable Computing

  • Speaker: Mr. Nilesh Rathi
                   M.Tech (Research) student
                   Dept. of CSA
  • Faculty Advisor: Prof. K. Gopinath
  • Date and Time: Monday, April 26, 2021, 4:00 PM
  • Venue: Microsoft Teams - ON-LINE

Abstract
The issue of scalability has been restricting blockchains from their widespread adoption. The current transaction rate of bitcoin is around seven transactions/second while the blockchain size has crossed the 300 GB mark. Although many different approaches have been proposed to scale blockchains, e.g., sharding, lightning network, etc., we focus our analysis on methods utilizing ideas from coding theory and verifiable computing. We first consider SeF, a blockchain archiving architecture utilizing LT codes to reduce storage constraints per node up to 1000x. SeF enables full nodes to store only a small number of encoded blocks or droplets instead of an entire blockchain. Although efficient in the average case, the architecture sometimes requires large bandwidth (many droplets) to reconstruct blockchain. While other rate-less coding strategies utilizing two encoding levels are proven better than LT codes, we investigate their suitability in the proposed architecture. We propose and simulate three techniques about how to incorporate these coding strategies. The results show that precode-based rate-less coding schemes provide similar storage savings with reduced bandwidth variance for recovery. The other work we examine is PolyShard, which introduces the notion of coded-sharding. Coded sharding exports block verification of sub-ledger to the whole network instead of nodes handling that sub-ledger, making sharding resilient even to an adaptive adversary, i.e., adversary having the power to corrupt nodes after their assignment to shards. However innovative, PolyShard requires decoding of Reed-Solomon codes over large fields for block verification in real-world settings, making it computationally intensive and less practical. We propose replacing the decoding phase with verifiable computing, which reduces the bottleneck and makes the system practical for light verification functions.

Microsoft Teams link:

https://teams.microsoft.com/l/channel/19%3a90c3a6855afe407d9a0516f42cff8e4c%40thread.tacv2/General?groupId=ae7f9d05-a7e4-423b-8bf4-800e78978105&tenantId=6f15cd97-f6a7-41e3-b2c5-ad4193976476

Video Archive Go Top

 

Series: M.Tech (Research) Colloquium- ON-LINE
Title: A Trusted-Hardware Backed Secure Payments Platform for Android

  • Speaker: Mr. Rounak Agarwal
                   M.Tech (Research) student
                   Dept. of CSA
  • Faculty Advisor: Prof. Vinod Ganapathy
  • Date and Time: Friday, April 23, 2021, 3:00 PM
  • Venue: Microsoft Teams - ON-LINE: https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZWQ3YzBmODUtMzFlZS00NDgzLTk0NTEtZjAyOGFjNWUwNTMw%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

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 signifi cantly 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 con fidential 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 confi dential 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_ZWQ3YzBmODUtMzFlZS00NDgzLTk0NTEtZjAyOGFjNWUwNTMw%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: M.Tech (Research) Colloquium- 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: Wednesday, April 07, 2021, 11: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 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 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 agent's 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 Meeting Link : https://teams.microsoft.com/l/meetup-join/19%3ameeting_YTI5M2MzOWMtMDEwNS00MzU4LTgyN2MtNWZmNGYzMTk0YjQ0%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%22c90a12b8-df95-4e40-88fd-ee979f2b42ba%22%7d

Video Archive Go Top

 

Series: M.Tech (Research) Colloquium- ONLINE
Title: Approximation Algorithms for Geometric Packing Problems

  • Speaker: Mr. Eklavya Sharma
                   M.Tech (Research)
                   Dept.of CSA
  • Faculty Advisor: Dr. Arindam Khan
  • Date and Time: Tuesday, March 30, 2021, 4:00 PM
  • Venue: Microsoft Teams - ONLINE

Abstract
We study approximation algorithms for the geometric bin packing problem and its variants. In the two-dimensional geometric bin packing problem (2D GBP), we are given n rectangular items and we have to compute an axis-parallel non-overlapping packing of the items into the minimum number of square bins of side length 1. 2D GBP is an important problem in computer science and operations research arising in logistics, resource allocation, and scheduling.

We first study an extension of 2D GBP called the generalized multidimensional bin packing problem (GVBP). Here each item i additionally has d nonnegative weights v_1(i), v_2(i), …, v_d(i) associated with it. Our goal is to compute an axis-parallel non-overlapping packing of the items into bins so that for all j ∈ [d], the sum of the jth weight of items in each bin is at most 1. Despite being well studied in practice, surprisingly, approximation algorithms for this problem have rarely been explored. We first obtain two simple algorithms for GVBP having asymptotic approximation ratios (AARs) 6(d+1) and 3(1 + ln(d+1) + ε). We then extend the Round-and-Approx (R&A) framework [Bansal-Khan, SODA 14] to wider classes of algorithms, and show how it can be adapted to GVBP. Using more sophisticated techniques, we obtain algorithms for GVBP having an AAR of 2(1+ln((d+4)/2))+ε, which improves to 2.919+ε for the special case of d=1.

Next, we explore approximation algorithms for the d-dimensional geometric bin packing problem (dD GBP). Caprara (MOR 2008) gave a harmonic-based algorithm for dD GBP having an AAR of 1.69104^(d-1). However, their algorithm doesnt allow items to be rotated. This is in contrast to some common applications of dBP, like packing boxes into shipping containers. We give approximation algorithms for dD GBP when items can be orthogonally rotated about all or a subset of axes. We first give a fast and simple harmonic-based algorithm, called fullh_k, having an AAR of 1.69104^d. We next give a more sophisticated harmonic-based algorithm, which we call hgap_k, having an AAR of (1+eps)1.69104^(d-1). This gives an AAR of roughly 2.860 + ε for 3BP with rotations, which improves upon the best-known AAR of 4.5. In addition, we study the multiple-choice bin packing problem that generalizes the rotational case. Here we are given n sets of d-dimensional cuboidal items and we have to choose exactly one item from each set and then pack the chosen items. Our algorithms fullh_k and hgap_k also work for the multiple-choice bin packing problem. We also give fast and simple approximation algorithms for the multiple-choice versions of dD strip packing and dD geometric knapsack. These algorithms have AARs 1.69104^(d-1) and (1-ε)3^(-d), respectively.

A rectangle is said to be δ-thin if it has width at most δ or height at most δ. When δ is a small constant (i.e., close to 0), we give an APTAS for 2D GBP when all rectangles are δ-thin. On the other hand, general 2D GBP is APX-hard. This shows that hard instances arise due to items that are large in both dimensions.

A packing of rectangles into a bin is said to be guillotine-separable iff we can use a sequence of end-to-end cuts to separate the items from each other. The asymptotic price of guillotinability (APoG) is the maximum value of opt_G(I)/opt(I) for large opt(I), where opt(I) and opt_G(I) are the minimum number of bins and the minimum number of guillotine-separable bins, respectively, needed to pack I. Computing lower and upper bounds on APoG is an important problem, since proving an upper bound smaller than 1.5 would beat the state-of-the-art algorithm for 2D GBP. The best-known upper bound is 1.69104 and the best-known lower bound is 4/3. We analyze this problem for the special case of δ-thin rectangles, where δ is a small constant (i.e., close to 0). We give a roughly 4/3-asymptotic-approximate algorithm for 2D GBP for this case, which proves an upper-bound of roughly 4/3 on APoG for δ-thin rectangles. We also prove a matching lower-bound of 4/3. This shows that hard examples for upper-bounding APoG include items that are large in both dimensions.

Mocrosoft Teams link:

https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZWE5NDlkMDgtNzBiNi00YzYyLWJjNzAtM2QxMzZiOTQ1Mzhi%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%22cd1ddf68-b75e-4337-87f3-ded65154fa20%22%7d

Video Archive Go Top

 

Series: M.Tech (Research) Colloquium
Title: GPM - Exploring GPUs with Persistent Memory

  • Speaker: Shweta Pandey
  • Faculty Advisor: Arkaprava Basu
  • Date and Time: Thursday, March 25, 2021, 3:00 PM
  • Venue: https://teams.microsoft.com/l/channel/19%3a13ca80f16f7948a2a87ac38e29410e0a%40thread.tacv2/General?groupId=e8b8b189-9c66-4a15-a4d0-2f2555b5724d&tenantId=6f15cd97-f6a7-41e3-b2c5-ad4193976476

Abstract
Non-volatile memory (NVM) technologies promise to blur the long-held distinction between memory and storage by enabling durability at latencies comparable to DRAM at byte granularity. Persistent Memory (PM) is defined as NVM accessed via load/store instructions at a fine grain. Due to decade-long research into CPU's software and hardware stack for PM, and with the recent commercialization of NVM under the aegis of Intel Optane, PM's promise of revolutionizing computing seems closer to reality than it has ever been before. Unfortunately, while a significant portion of computation today happens on Graphics Processing Units (GPUs), they are deprived of leveraging PM. We find that there exist GPU-accelerated applications that could benefit from fine-grain persistence. Our key goal is to expose byte-grain persistent memory to GPU kernels. For this, we propose a design for GPU with fine-grained access to PM, a.k.a. GPM which combines commercially available GPUs and NVM through software. We find important use-cases to leverage GPM and create a workload suite called GPMBench. GPMBench consists of 11 GPU-accelerated workloads modified to leverage PM. Finally, we demonstrate the benefits of our proposed design, GPM, over conventional methods of persisting from GPU.

Speaker Bio:
Shweta Pandey is an MTech Research student in the Department of Computer Science and Automation at IISC, Bangalore. She is currently advised by Prof. Arkaprava Basu. Her research interests lie in the field of High-Performance Computing. She is currently looking into improving GPU hardware systems for emerging needs.

Host Faculty: Arkaprava Basu

Video Archive Go Top

 

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

  • Speaker: Akash Panda
  • Faculty Advisor: Arkaprava Basu
  • Date and Time: Thursday, March 25, 2021, 2:00 PM
  • Venue: https://teams.microsoft.com/l/channel/19%3aee36253808914fffb930888369bed27e%40thread.tacv2/General?groupId=18b6fde4-c906-4143-b1ea-d5d66e19462d&tenantId=6f15cd97-f6a7-41e3-b2c5-ad4193976476

Abstract
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 de-centralized design to scale to larger memory.

Speaker Bio:
Akash Panda is an MTech Research student in the Department of Computer Science and Automation at IISC, Bangalore. He is advised by Prof. Arkaprava Basu and is interested in memory management and Linux's virtual memory subsystem.

Host Faculty: Arkaprava Basu

Video Archive Go Top

 

Series: Ph.D (Engg.)Thesis Defence -ON-LINE
Title: Algorithms for Challenges to Practical Reinforcement Learning

  • Speaker: Ms. Sindhu P R
                   Ph.D (Engg.) Student
                   Dept. of CSA
  • Faculty Advisor: Prof. Shalabh Bhatnagar
  • Date and Time: Wednesday, March 24, 2021, 4:00 PM
  • Venue: Microsoft Teams - ON-LINE

Abstract
Reinforcement learning (RL) in real world applications faces major hurdles - the foremost being safety of the physical system controlled by the learning agent and the varying environment conditions in which the autonomous agent functions. A RL agent learns to control a system by exploring available actions. In some operating states, when the RL agent exercises an exploratory action, the system may enter unsafe operation, which can lead to safety hazards both for the system as well as for humans supervising the system. RL algorithms thus need to respect these safety constraints and must do so with limited available information. Additionally, RL autonomous agents learn optimal decisions in the presence of a stationary environment. However, the stationary assumption on the environment is very restrictive. In many real world problems like traffic signal control, robotic applications, etc., one often encounters situations with non-stationary environments, and in these scenarios, RL algorithms yield sub-optimal decisions.

We describe algorithmic solutions to the challenges of safety and non-stationary environmental conditions in RL. In order to handle safety restrictions and facilitate safe exploration during learning, we propose a cross-entropy method based sample efficient learning algorithm. This algorithm is developed based on constrained optimization framework and utilizes limited information for the learning of feasible policies. Also, during the learning iterations, the exploration is guided in a manner that minimizes safety violations. The goal of the second algorithm is to find a good policy for control when the latent model of the environment changes with time. To achieve this, the algorithm leverages a change point detection algorithm to monitor change in the statistics of the environment. The results from this statistical algorithm are used to reset learning of policies and efficiently control an underlying system.

In the second part of talk, we describe the application of RL to obstacle avoidance problem in UAV quadrotor. Obstacle avoidance in quadrotor aerial vehicle navigation brings in additional challenges in comparison to ground vehicles. Our proposed method utilizes the relevant temporal information available from the ambient surroundings for this problem and adapts attention based deep Q networks combined with generative adversarial networks for this application.

Microsoft Teams Link: https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZjIwYjI3YTEtNzU0OC00MDQxLTk1YjAtMzZiMTkzNDY5ZTgz%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%221b0586c2-1488-4f8f-ab3c-d2e61940254c%22%7d

Video Archive Go Top

 

Series: M.Tech (Research) Thesis Colloquium- ON-LINE
Title: Revisiting Statistical Techniques for Cardinality Estimation in RDBMS

  • Speaker: Mr. Dhrumilkumar Shah
                   M. Tech (Research) student
                   Department of Computer Science and Automation
  • Faculty Advisor: Prof. Jayant R. Haritsa
  • Date and Time: Monday, March 22, 2021, 2:00 PM
  • Venue: Microsoft Teams - ON-LINE

Abstract
Relational Database Management Systems (RDBMS) constitute the backbone of today's information-rich society, providing a congenial environment for handling enterprise data during its entire life cycle of generation, storage, maintenance, and processing. The Structured Query Language (SQL) is the standard interface to query the information present in RDBMS-based storage. Because of the declarative nature of SQL, the query optimizer inside the database engine needs to come up with an efficient execution plan for a given query. To do so, database query optimizers are critically dependent on accurate row-cardinality estimates of the intermediate results generated on the edges of the execution plan tree.

Unfortunately, the histogram and sampling-based techniques commonly used in industrial database engines for cardinality estimation are often woefully inaccurate in practice. As a result, query optimizers produce sub-optimal query execution plans, leading to inflated query response times. This lacuna has motivated a recent slew of papers advocating the use of machine-learning techniques for cardinality estimation. However, these new approaches have their own limitations regarding training overheads, output explainability, incorporating dynamic updates, handling of workload drift, and generalization to unseen queries.

In this work, we take a relook at the traditional techniques and investigate whether they can be made to work satisfactorily when augmented with light-weight data structures. Specifically, we present GridSam, which essentially combines histograms and sampling in a potent partnership incorporating both algorithmic and platform innovations.

From the algorithmic perspective, GridSam first creates a multi-dimensional grid overlay structure by partitioning the data-space on "critical" attributes (Histogram), and then performs dynamic sampling from query-specific regions of the grid to capture correlations (Sampling). A heuristic-based methodology is used to determine the critical grid dimensions. Further, insights from Index-based Join Sampling (IBJS) technique are leveraged to direct the sampling in multi-table queries. Finally, learned-indexes are incorporated to reduce the index-probing cost for join sampling during the estimation process.

From the platform perspective, GridSam leverages the massive parallelism offered by current GPU architectures to provide fast grid setup times. This parallelism is also extended to the run-time estimation process.

A detailed performance study on benchmark environments indicates that GridSam computes cardinality estimates with accuracies competitive to contemporary learning-based techniques. Moreover, it does so while achieving orders-of-magnitude reduction in setup time. Further, the estimation time is in the same ballpark as both traditional and learning-based techniques. Finally, a collateral benefit of GridSam’s simple design is that, unlike learned estimators, it is natively amenable to dynamic data environments.

Microsoft Teams Link:

https://teams.microsoft.com/l/channel/19%3aff37417a25ea41889bb3521f22d917be%40thread.tacv2/General?groupId=cf375c71-892f-441a-ab57-27cbe3049dd4&tenantId=6f15cd97-f6a7-41e3-b2c5-ad4193976476

Video Archive Go Top

 

 

 

 

 

 

 

 

 

 

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