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

PAST SEMINARS

Series: Department Seminar
Title: Ludic design for Accessibility

  • Speaker: Dr. Manohar Swaminathan (Swami Manohar)
                   Principal Researcher
                   Microsoft Research India
  • Date and Time: Tuesday, September 15, 2020, 3:00 PM
  • Venue: On-Line (Microsoft Teams)

Abstract
Technology solutions for accessibility have long been created using a narrow utilitarian lens, especially in the global south due to the multi-dimensional challenges and resource constraints. We propose an alternate design methodology called the Ludic Design for Accessibility (LDA) that puts play and playfulness at the center of all assistive technology design and use. We have been exploring the application of this methodology in developing solutions for diverse disabilities using a range of technologies. In this talk I will focus on the application of this methodology to the following challenge and the lessons being learnt: introducing digital skills and computational thinking to children in schools for the blind in India starting at grade 2.

Speaker Bio:
Manohar Swaminathan (Swami Manohar) is a Principal researcher at Microsoft Research India, where he is part of the Technologies for Emerging Markets group. Manohar is an academic-turned technology entrepreneur-turned researcher with a driving passion to build and deploy technology for positive social impact. He has a PhD in CS from Brown University, was a Professor at the Indian Institute of Science, and has co-founded, managed, advised, and angel-funded several technology startups in India. He has guided over 40 graduate students and has more than 50 refereed publications. His current research interests are broadly in technologies for the global south and in particular, ludic design for accessibility. The latter covers a broad set of interdisciplinary research topics, and is being applied to computational thinking for children who are blind, video games for the vision impaired, and gaze-tracked interfaces for children with sensory motor impairments. Microsoft Teams link : https://teams.microsoft.com/l/team/19%3a68daf29425434a608aff44016c558a16%40thread.tacv2/conversations?groupId=157bca6a-0bb7-4769-81fb-685bab1009b8&tenantId=6f15cd97-f6a7-41e3-b2c5-ad4193976476

Host Faculty: Prof. Chiranjib Bhattacharyya

Video Archive Go Top

 

Series: Ph.D (Engg.)Thesis Defence -ON-LINE
Title: Algorithms for Social Good in Online Platforms with Guarantees on Honest Participation and Fairness

  • Speaker: Mr. Ganesh Sambhaji Ghalme
                   Ph.D Student
                   Dept. of CSA
  • Faculty Advisor: Prof. Y. Narahari
  • Date and Time: Tuesday, September 01, 2020, 2:00 PM
  • Venue: Microsoft Teams - ON-LINE

Abstract
Recent decades have seen a revolution in the way people communicate, buy products, learn new things, and share life experiences. This has spurred the growth of online platforms that enable users from all over the globe to buy/review/recommend products and services, ask questions and provide responses, participate in online learning, etc.

There are certain crucial requirements that are required to be satisfied by the online forums for ensuring their trustworthiness and sustainability. In this thesis, we are concerned with three of these requirements: social welfare maximization, honest participation by the users, and fairness in decision making. In particular, we address three contemporary problems in online platforms and obtain principled solutions that achieve social welfare maximization while satisfying honest participation and fairness of allocation. The three problems considered are set in the context of three different platforms: online review or Q&A forums, online discussion forums, and online search platforms. In each case, we develop an abstraction of the problem and solve it in its generality.

Ballooning Multi-armed Bandits

In our first problem, we consider online platforms where the users are shown user generated content such as reviews on an e-commerce platform or answers on a Q&A platform. The number of reviews/answers increases over time. We seek to design an algorithm that quickly learns the best review/best answer and displays it prominently. We model this problem as a novel multi-armed bandit formulation (which we call ballooning bandits) in which the set of arms expands over time. We first show that when the number of arms grows linearly with time, one cannot achieve sub-linear regret. In a realistic special case, where the best answer is likely to arrive early enough, we prove that we can achieve optimal sublinear regret guarantee. We prove our results for best answer arrival time distributions that have sub-exponetal or sub-Pareto tails.



Strategy-proof Allocation of Indivisible Goods with Fairness Guarantees

Second, we consider the problem of fairness in online search platforms. We view the sponsored ad-slots on these platforms as indivisible goods to be allocated in a fair manner among competing advertisers. We use envy-freeness up to one good (EF1) and maximin fair share (MMS) allocation as the fairness notions. The problem is to maximize the overall social welfare subject to these fairness constraints. We first prove under a single parameter setting that the problem of social welfare maximization under EF1 is NP-hard. We complement this result by showing that any EF1 allocation satisfies an 1/2-approximation guarantee and present an algorithm with a (1, 1/2) bi-criteria approximation guarantee. We finally show in a strategic setting that one can design a truthful mechanism with the proposed fair allocation.

Coalition Resistant Credit Score Functions

In the third problem, we study manipulation in online discussion forums. We consider a specific but a common form of manipulation namely manipulation by coalition formation. We design a manipulation resistant credit scoring rule that assigns to each user a score such that forming a coalition is discouraged. In particular, we study the graph generated by the interactions on the platform and use community detection algorithms. We show that the community scores given by community detection algorithms that maximize modularity lead to a coalition resistant credit scoring rule. This in turn leads to sustainable discussion forums with honest participation from users, devoid of any coalitional manipulation.

Microsoft Teams Meeting:

https://teams.microsoft.com/l/meetup-join/19%3ameeting_OGM2MGIyZGQtZjZkMi00YTAyLTg5MGItYTRiMGFkZjZmNmRm%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%2269dfbf19-0e41-447f-b7d4-700f9629e40e%22%7d

Video Archive Go Top

 

Series: Ph.D (Engg.) Thesis Defence - ON-LINE
Title: Scalable and Effective Polyhedral Auto-transformation Without using Integer Linear Programming

  • Speaker: Mr. Aravind Acharya
                   Ph.D Student
                   Dept. of CSA
                   IISc
  • Faculty Advisor: Prof. Uday Kumar Reddy B
  • Date and Time: Friday, August 28, 2020, 9:00 AM
  • Venue: On Google Meet

Abstract
In recent years, polyhedral auto-transformation frameworks have gained significant interest in general-purpose compilation, because of their ability to find and compose complex loop transformations that extract high performance from modern architectures. These frameworks automatically find loop transformations that either enhance locality, parallelism and minimize latency or a combination of these. Recently, focus has also shifting on developing intermediate representations, like MLIR, where complex loop transformations and data-layout optimizations can be incorporated efficiently in a single common infrastructure.

Polyhedral auto-transformation frameworks typically rely on complex Integer Linear Programming (ILP) formulations to find affine loop transformations. However, construction and solving these ILP problems is time consuming which increases compilation time significantly. Secondly, loop fusion heuristics in these auto-transformation frameworks are ad hoc, and modeling loop fusion efficiently would further degrade compilation time.

In this thesis, we first relax the ILP formulation in the Pluto algorithm. We show that even though LP relaxation reduces the time complexity of the problem, it does not reduce the compilation time significantly because of the complex construction of constraints. We also observe that due to relaxation, sub-optimal loop transformations that result in significant performance degradation may be obtained. Hence, we propose a new polyhedral auto-transformation framework, called Pluto-lp-dfp, that finds efficient affine loop transformations quickly, while relying on Plutos cost function. The framework decouples auto-transformation into three components: (1) loop fusion and permutation (2) loop scaling and shifting and (3) loop skewing components. In each phase, we solve a Linear Programming (LP) formulation instead of an ILP, thereby resulting in a polynomial time affine transformation algorithm. We propose a data structure, called fusion conflict graph, that allows us to model loop fusion to work in tandem with loop permutations, loop scaling and loop shifting transformations. We describe three greedy fusion heuristics, namely, max-fuse, typed-fuse and hybrid-fuse, of which, the hybrid-fuse and typed-fuse models incorporate parallelism preserving fusion heuristic without significant compilation time overhead. We also provide a characterization of time-iterated stencils that have tile-wise concurrent start and employ a different fusion heuristic in such programs. In our experiments, we demonstrate that Pluto-lp-dfp framework not only finds loop transformations quickly, resulting in significant improvements in compilation time, but also outperforms state-of-the-art polyhedral auto-parallelizers in terms of execution time of the transformed program. We observe that Pluto-lp-dfp is faster than PoCC and Pluto by a geomean factor of 461x and 2.2x in terms of compilation time. On larger NAS benchmarks, Pluto-lp-dfp was faster than Pluto by 246x. PoCC failed to find a transformation in a reasonable amount of time in these cases. In terms of execution time, the hybrid-fuse variant in Pluto-lp-dfp outperforms PoCC by a geomean factor 1.8x, with over 3x improvements in some cases. We also observe that Pluto-lp-dfp is faster than an improved version of Pluto by a factor of 7%, with a maximum performance improvement of 2x.

Link to join online on Google Meet: https://meet.google.com/ioe-tjuw-ijo

Please note that the meeting will be recorded as per Institute requirements. By joining the link you are giving your consent to the recording.

Speaker Bio:
Aravind Acharya submitted his PhD thesis under the supervision of Prof. Uday Kumar Reddy B at the Dept of CSA. He obtained his Masters degree from the same department. Prior to that, he obtained his BE in Computer Science from Sri Jayachamarajendra College of Engineering (SJCE), Mysore. He is current a post-doctoral researcher at NVIDIA, Redmond, USA. His research interests are in the development of optimizing compliers and domain-specific languages for high performance.

Video Archive Go Top

 

Series: Ph.D (Engg.) Colloquium - ON-LINE
Title: Towards Secure and Efficient Realization of Pairing-Based Signatures from Static Assumptions

  • Speaker: Mr. R. Kabaleeshwaran
                   Ph.D (Engg.) Student
                   Dept. of CSA
                   IISc
  • Faculty Advisor: Prof. Sanjit Chatterjee
  • Date and Time: Friday, August 28, 2020, 4:00 PM
  • Venue: On Microsoft Teams

Abstract
Bilinear pairing defined over elliptic curve group was first used to design novel cryptosystem in 2000. Since then a large number of cryptosystems has been proposed in pairing-based cryptography (PBC). The main tool for all such cryptosystems is the pairing map which can be defined on either composite or prime-order groups. Security of a public key cryptosystem is typically proved under some computational hardness assumption. PBC has witnessed a plenty of parameterized/interactive assumptions. However, it is well-known that such assumptions have several limitations. In this thesis we explore the question of security and efficiency of pairing-based signature schemes based on static assumptions. We have investigated the efficacy of the following approaches towards this goal: (i). frameworks for converting cryptosystems from composite to prime-order bilinear pairing setting, (ii). DejaQ framework, for removing dependency on parameterized assumption and (iii). dual-form signature (DFS) technique, for removing dependency on parameterized/interactive assumption.

First, we focus on the conversion framework. In 2005, Boneh et al. introduced a novel homomorphic encryption scheme using composite-order pairing setting. From then there are plenty of cryptosystems constructed in the composite-order pairing setting. However, it is well known that a composite-order pairing is significantly slower than its prime-order counterpart. This motivated Freeman to propose his conversion framework that converts some cryptographic protocols to the prime-order pairing setting. He formally defined certain properties called projecting and canceling, which are used in the protocol construction and/or in the security argument. Since then several frameworks have been proposed for conversion purpose. We revisit all the projecting frameworks and establish that Freemans framework is still optimal in the asymmetric pairing setting. We also present an alternative security proof for Seo-Cheons projecting and canceling framework under the static symmetric external Diffie-Hellman (SXDH) assumption, instead of the original tailor-made assumption. Next, we formalize the full-decomposition notion in the existing projecting frameworks and show that this notion is sufficient instead of the so-called translating property. Then, we abstract an unbalanced projecting framework in the asymmetric pairing setting that allows the pairing source groups to have different orders. As application, we convert the following schemes to the prime-order asymmetric pairing setting: Shacham-Waters ring signature, Boyen-Waters group signature and Meiklejohn et als round optimal blind signature. In their original construction, security of the above schemes requires both projecting and canceling properties in the composite-order symmetric pairing setting. We show that the framework for projecting and canceling is not necessary to instantiate these schemes.

Next, we focus on a set of parameterized assumptions called the BTA family. Such parameterized assumptions play a crucial role in the security of many novel pairing-based cryptosystems. However, they have some negative impact on efficiency at a concrete security level. A prominent approach to remove the dependency on parameterized assumption is the DejaQ framework of Chase et al. The DejaQ framework aims to establish that certain parameterized assumptions are implied by the subgroup hiding assumption in the composite-order pairing setting. Applying DejaQ framework to a family of assumptions is an important question, as it covers several parameterized assumptions which in turn cover more cryptographic protocols. However, the existing DejaQ framework could cover only Boyens Uber assumption family. Recently Ghadafi and Groth introduced the bilinear target assumption (BTA) family, that covers more parameterized assumptions including the Uber assumption family. We show that the parameterized assumptions that belong to the BTA family are reducible from the subgroup hiding assumption. In the process, we first suitably extend a property called parameter-hiding and then adapt the DejaQ proof technique on the parameterized assumptions that belong to the BTA family.

Finally, we focus on the applicability of the dual-form signature (DFS) technique on some pairing-based signatures. The DejaQ framework does not address the question of how to remove the dependency on interactive assumption. The DFS technique can be used for this purpose and it is applied directly in the security argument of the protocol. We use the DFS technique to prove the security of Abe et als structure-preserving signature, Boyen-Waters group signature and Pointcheval-Sanders rerandomizable signature (RRS) under some static assumptions. We also present an efficient construction of RRS scheme in the prime-order setting. Then, we use the proposed RRS scheme as a building block to construct a sequential aggregate signature (SeqAS) scheme with constant-size public key under the SXDH assumption. The performance of the proposed schemes is comparable to that of previous proposals based on some non-standard interactive assumptions.

Link to join Microsoft Teams:

https://teams.microsoft.com/l/channel/19%3aa24e8f8dbe724c0486b5239881d7674c%40thread.tacv2/General?groupId=57f6f230-1dd8-4280-85ed-de7a55a7d936&tenantId=6f15cd97-f6a7-41e3-b2c5-ad4193976476

Video Archive Go Top

 

Series: Department Seminar
Title: On building interactive and secure smart spaces

  • Speaker: Dr. Swadhin Pradhan
                   The University of Texas at Austin
  • Date and Time: Thursday, August 27, 2020, 10:30 AM
  • Venue: On MS Teams

Abstract
Please click on the following URL to join the talk. https://teams.microsoft.com/l/meetup-join/19%3ameeting_YmU3ZGQzMzMtY2Q1MC00NzY0LWE2MzAtZGQ3NTIxNjgwZjFm%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

Absract:

The future of Internet-of-Things (IoT) demands seamless interaction between users and devices, where sensing interfaces blend into everyday objects. Toward realizing the vision of making sensing interfaces truly ubiquitous, we also need to make the future smart spaces secure. In this talk, I will present two of my works, which concern with these critical issues. Firstly, I will present RIO, a novel battery-free touch-sensing user interface (UI) primitive. With RIO, any surface can be turned into a touch-aware interactive surface by directly attaching RFID tags. RIO is built using impedance tracking: when a human finger touches the surface of an RFID tag, the impedance of the antenna changes. This change manifests as a variation in the phase of the RFID backscattered signal and is used by RIO to track fine-grained touch movement, over both off-the-shelf and custom-built tags. Secondly, I will present REVOLT, an end-to-end system to detect replay attacks on voice-first devices (e.g., Amazon Echo, Google Home, etc.) without requiring a user to wear any wearable device. This system has several distinct features: (i) it intelligently exploits the inherent differences between the spectral characteristics of the original and replayed voice signals, (ii) it exploits both acoustic and WiFi channels in tandem, (iii) it utilizes unique breathing rate extracted from WiFi signal while speaking to test the liveness of human voice. This novel technique of combining WiFi and voice modality yields low false positive and false negative when evaluated against a range of voice replay attacks.

Speaker Bio:
Swadhin Pradhan is a recent Ph.D. graduate in the Department of Computer Science at UT Austin. His research is focused on mobile computing and internet-of-things (IoT) systems. He has designed, built, and deployed systems that deliver ubiquitous sensing, enhanced communication capabilities, and new human-computer interfaces. His works have been published in the top-tier conferences like MobiCom, CHI, UbiComp, Infocom, etc. and featured in the popular press like BBC, MIT Tech Review, Boston Globe, The Guardian, etc. He is a recipient of the UT Austin Graduate Fellowship and the University Gold Medal at Jadavpur University, Kolkata.

Host Faculty: Arkaprava Basu

Video Archive Go Top

 

Series: Ph.D (Engg.) Thesis Defence - ON-LINE
Title: Verification of a Generative Separation Kernel

  • Speaker: Mr. Inzemamul Haque
                   Ph.D Student
                   Dept. of CSA
  • Faculty Advisor: Prof. Deepak D Souza
  • Date and Time: Thursday, August 20, 2020, 2:30 PM
  • Venue: On Google Meet

Abstract
In this thesis we present a technique to formally verify the functional correctness of template-based generative systems. A generative system is one in which a specialised system is generated for each given input specification. In a template-based generative system, the generated systems have a common template code, and the components of this template are generated based on the given input specification. Many safety-critical systems today are of this nature, with an important class being that of separation kernels. A separation kernel is a small specialized microkernel that provides a sand-boxed execution environment for a given set of processes called "subjects", and are commonly used in aerospace and defence applications.

The verification goal in the context of generative systems is to show that for every valid input specification the generated system refines an abstract specification that is generated according to the input specification.

The key stepping stone in our theory is the notion of a parametric Abstract Data Type or "machine". These are similar to classical machines except that they have parameters on which the behaviour of the machine depends. We propose a notion of refinement for such machines, which we call conditional parametric refinement, which essentially says that whenever the parameter values of the abstract and concrete parametric machines satisfy a given condition, the resulting machines enjoy a refinement relation. We define refinement conditions for this notion of refinement and show that they are sound and complete for total and deterministic machines. The refinement conditions are similar in structure to the classical case and can be discharged using standard Floyd-Hoare logic in a programmatic setting.

We use this framework to propose a two-step verification approach for template-based generative systems. Such a system naturally corresponds to a parametric machine, where the template corresponds to the definition of operations of the machine and generated components correspond to values for the parameters of the machine. In a similar way we construct an abstract parametric machine whose parameter values are generated based on the input specification. The first step of our approach is independent of the input specification and checks that the that the concrete parametric machine conditionally refines the abstract parametric machine, subject to a condition C on the parameter values generated. In the second step, which is input-specific, we check that for a given input specification, the generated abstract and concrete parameter values actually satisfy the condition C. Whenever this check passes for a given input specification, we can say that the generated system refines the abstract system. This gives us an effective verification technique for verifying generative systems that lies somewhere between verifying the generator and translation validation.

We demonstrate the effectiveness of our technique by applying it to verify the Muen Separation Kernel. Muen is an open-source template-based generative separation kernel which uses hardware support for virtualization to implement separation of subjects. We chose to model the virtualization layer (in this case Intel's VT-x layer) along with the rest of the hardware components like registers and memory, programmatically in software. Using the templates which Muen generator utilizes we constructed a parametric machine and carried out the first step of conditional parametric refinement for Muen, using the Spark Ada verification tool. This was a substantial effort involving about 20K lines of source code and annotation. We have also implemented a tool that automatically and efficiently performs the Step 2 check for a given separation kernel configuration. The tool is effective in proving the assumptions, leading to machine-checked proofs of correctness for 16 different input configurations, as well as in detecting issues like undeclared sharing of memory components in some seeded faulty configurations.



Details for joining online on Google Meet:

Link: https://meet.google.com/xkj-bugw-cxf

Please note that the meeting will be recorded as per Institute requirements. By joining the link you are giving your consent to the recording.

Video Archive Go Top

 

Series: Ph.D (Engg.) (Colloquium) -ONLINE
Title: Hypergraph Network Models: Learning, Prediction, and Representation in the Presence of Higher-Order Relations

  • Speaker: Mr. Govind Sharma
                   Ph.D (Engg.) Student
                   Dept. of CSA
  • Faculty Advisor: Prof. M. Narasimha Murty
  • Date and Time: Wednesday, July 22, 2020, 12:00 PM
  • Venue: Microsoft Teams Meeting Link: Details follows.

Abstract
The very thought about relating objects makes us assume the relation would be pairwise, and not of a higher-order -- involving possibly more than two of them at a time. Yet in reality, higher-order relations do exist and are spread across multiple domains: medical science (e.g., co-existing diseases/symptoms), pharmacology (e.g., reacting chemicals), bibliometrics (e.g., collaborating researchers), the film industry (e.g., cast/crew), human resource (e.g., a team), social sciences (e.g., negotiating/conflicting nations), and so on. Since a collection of intersecting higher-order relations lose context when represented by a graph, "hypergraphs" -- graph-like structures that allow edges (called hyperedges/hyperlinks) spanning possibly more than two nodes -- capture them better. In a quest to better understand such relations, in this thesis we focus on solving a few network-science oriented problems involving hypergraphs. "Hypergraphs and Pairwise Links": In the first of three broad parts, we study the behavior of usual graph-oriented networks that have an otherwise-ignored hypergraph underpinning. We particularly establish the skewness a hypergraph introduces into its induced graphs, and the effect of these biases on the structure and evaluation of the well-known problem of link prediction in networks. We find that an underlying hypergraph structure makes popular heuristics such as common-neighbors overestimate their ability to predict links. Gathering enough evidence -- both theoretical and empirical -- to support the need to reestablish the evaluations of link prediction algorithms on hypergraph-derived networks, we propose adjustments that essentially undo the undesired effects of hypergraphs in performance scores. Motivated by this observation, we extend graph-based structural node similarity measures to cater to hypergraphs (although still, for similarity between pairs of nodes). To be specific, we first establish mathematical transformations that could transfer any graph-structure-based notion of similarity between node pairs to a hypergraph-structure-based one. Using exhaustive combinations of the newly established scores with the existing ones, we could show improvements in the performance of both structural as well as temporal link prediction. "Predicting Higher-order Relations": For the second part of our thesis, we turn our attention towards a more central problem in hypergraphs -- the hyperlink/hyperedge prediction problem. It simply refers to developing models to predict the occurrence of missing or future hyperedges. We first study the effect of negative sampling (sampling the negative class) -- an exercise performed due to the extreme intractability of the set of all non-hyperlinks, also known as the class imbalance problem -- on hyperlink prediction, which has never been studied in the past. Since we observe hyperlink prediction algorithms performing differently under different negative sampling techniques, our experiments help the seemingly unimportant procedure gain some significance. Moreover, we contribute towards two benchmark negative sampling algorithms that would help standardize the step. Moving on from the negative sampling problem to predicting hyperlinks themselves, we work on two different approaches: a clique-closure based approach, and a sub-higher-order oriented one. While in the former, we develop and successfully test the clique-closure hypothesis -- that hyperlinks mostly form from cliques or near-cliques -- and are able to utilize it for hyperlink prediction via matrix completion (C3MM), the latter approach works on a novel information flow model in hypergraphs. More precisely, we introduce the concept of sub-hyperedges to capture the sub-higher-order notion in relations, and utilize an attention-based neural network model called SHONeN focusing on sub-hyperedges of a hyperedge. Owing to SHONeN's computational complexity, we propose a sub-optimal heuristic that is able to perform better than its baselines on the downstream task of predicting hyperedges. "Higher-order Bipartite Relations": The third and final part of our thesis is dedicated exclusively to "bipartite hypergraphs": structures that are used to capture higher-order relations between two disjoint node sets, e.g., a patient's diagnosis (possibly multiple diseases and symptoms), a movie project (multiple actors and crew members), etc. We first capture the structure of real-world such networks using per-fixed bipartite hypergraphs (those where the set of left and right hyperedges is fixed beforehand), and then focus on the bipartite hyperlink prediction problem. Since existing self-attention based approaches meant for usual hypergraphs do not work for bipartite hypergraphs -- a fact that our experiments validate, we propose a cross-attention model for the same, and use the notion of set-matching over collections of sets to solve for bipartite hyperlink prediction. As a result, we develop a neural network architecture called CATSETMAT that performs way better than any of the other approaches meant to solve the bipartite hyperlink prediction problem. Last but not least, we also explain how, owing to an observation we call the positive-negative dilemma, existing state-of-the-art algorithms fail on bipartite hypergraphs.

Microsoft Teams Meeting Link:

https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZWQyMTY2OTMtMmI4MC00ZThiLThiN2QtNGU1M2FlYTExZDRi%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227cc8bd44-135e-4281-b033-80d7f9df42fd%22%7d

Video Archive Go Top

 

Series: M.Tech (Research) Thesis Defence - Online
Title: Equivalence test for the trace iterated matrix multiplication polynomial

  • Speaker: Ms. Janaky Murthy
                   M.Tech (Research) student
                   Dept. of CSA, IISc
  • Faculty Advisor: Prof. Chandan Saha
  • Date and Time: Tuesday, July 21, 2020, 2:30 PM
  • Venue: Please fill form before 19/07/20 - link details below

Abstract
An m-variate polynomial f is affine equivalent to an n-variate polynomial g if m > n and there is a full rank n * m matrix A and a n-dimensional vector b such that f(x) = g(Ax + b). Given blackbox access to f and g (i.e membership query access) the affine equivalence test problem is to determine whether f is affine equivalent to g, and if yes then output a rank n matrix A and a vector b such that f(x) = g(Ax + b). This problem is at least as hard as graph isomorphism and algebra isomorphism even when the coefficients of f and g are given explicitly (Agarwal and Saxena, STACS 2006), and has been studied in literature by fixing g to be some interesting family of polynomials. In this work, we fix g to be the trace of the product of d, w * w symbolic matrices. We call this polynomial 'Trace Iterated Matrix Multiplication' polynomial (Tr-IMM). Kayal, Nair, Saha and Tavenas (CCC 2017) gave an efficient (i.e polynomial in m,w,d) randomized algorithm for the affine equivalence test of the 'Iterated Matrix Multiplication' polynomial (IMM), which is the (1,1)-th entry of the product of these symbolic matrices. Although the definitions of IMM and Tr-IMM are closely related and their circuit complexities are very similar, it is not clear whether an efficient affine equivalence test algorithm for IMM implies the same for Tr-IMM. In this thesis, we take a step towards showing that equivalence test for IMM and Tr-IMM have different complexity. We show that equivalence test for Tr-IMM reduces in randomized polynomial time to equivalence test for the determinant polynomial (Det), under mild conditions on the underlying field. If the converse is also true then equivalence tests for Tr-IMM and Det are randomized polynomial time equivalent. It would then follow from the work of Gupta, Garg, Kayal and Saha (ICALP 2019) that equivalence test for Tr-IMM over rationals is at least as hard as Integer Factoring. This would then be in sharp contrast with the complexity of equivalence test for Tr-IMM over rationals which can be solved efficiently in randomized polynomial time (by Kayal, Nair, Saha and Tavenas (CCC 2017)). Recent Update: Soon after the thesis is written, we (together with Vineet Nair) have succeeded in showing the converse direction. So, the above conclusion is indeed true! This work has been accepted at the 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020).

Please fill out this form by July 19, 2020 to receive the Google Meet link: https://docs.google.com/forms/d/e/1FAIpQLSfWTKc-z5v_dpOpfzb8JwZKFJVl5UN6aUR5Pw2yIwK22QCqww/viewform?usp=sf_link

Video Archive Go Top

 

Series: M.Tech (Research) Thesis Defence - ONLINE
Title: Modern Combinatorial Optimization Problems: Balanced Clustering and Fair Knapsack

  • Speaker: Mr. Deval Patel
                   M.Tech (Research) student
                   Dept. of CSA
  • Faculty Advisor: Dr. Anand Louis
  • Date and Time: Friday, July 17, 2020, 11:00 AM
  • Venue: Microsoft Teams - ON-LINE

Abstract
In many classical optimization problems, it is desirable to have an output that is equitable in some sense. The property equitability could be defined differently for different optimization problems. We study this property in two classical optimization problems, clustering and knapsack. In the clustering problem, we desire to have a cost of the clustering evenly distributed among the clusters. We study this problem under the name cost-balanced k-clustering. In the knapsack problem, we desire to have a packing which is fair in some sense. We study this problem under the name fair knapsack. In most of the clustering objectives like k-median or k-center, the cost of assigning a client to the cluster is considered to be borne by client. Algorithms optimizing such objectives might output a solution where few clusters have very large cost and few clusters have very small cost. Cost-balanced k-clustering problem aims to obtain the clustering which is cost balanced. We consider the objective of minimizing the maximum cost of each cluster, where the cost of a cluster is the sum of distances of all the points in that cluster from the center of that cluster. We define the notion of γ-stability, for γ > 1, for the problem and give a poly time algorithm for 1.5-stable instances of the problem. The algorithm requires an optimal value as an input. We also modify this algorithm for 1.5+eps, eps>0, stable instance that does not require an optimal value as an input. We also define the more general version of the problem and name it "lp" cost-balanced k-clustering. Given a black-box algorithm which gives constant factor approximation to the "lp" cost k-clustering problem, we show a procedure that runs in poly time and gives bi-criteria approximation to the "lp" cost-balanced k-clustering problem. In this work, we also consider the notion of group fairness in the knapsack problems. In this setting, each item belongs to some category, and our goal is to compute a subset of items such that each category is fairly represented, in addition to the total weight of the subset not exceeding the capacity, and the total value of the subset being maximized. We study various notions of group fairness, such as the number of items from each category, the total value of items from each category, and the total weight of items from each category. We give algorithms and hardness results for these problems.

Microsoft Teams link:

https://teams.microsoft.com/l/team/19%3abcdacd2f9b9b4f4e8534f288b0598817%40thread.tacv2/conversations?groupId=d79f4d99-3e9e-4035-a301-09c28012be9e&tenantId=6f15cd97-f6a7-41e3-b2c5-ad4193976476

Video Archive Go Top

 

Series: M.Tech (Research) Colloquium- ONLINE
Title: Embedding Networks: Node and Graph Level Representations

  • Speaker: Ms. Manasvi Aggarwal
                   M.Tech (Research) Student
                   Dept. of CSA
  • Faculty Advisor: Prof. M. Narasimha Murty
  • Date and Time: Wednesday, June 24, 2020, 1:00 PM
  • Venue: Microsoft Teams - ONLINE

Abstract
Network representation learning is important to carry out various network analysis downstream tasks. Graphs are the most suitable structures to represent relational data such as social networks and molecular structures. In this thesis work, we focus on learning representations of the nodes as well as of the entire graphs. Graph neural networks got significant importance for graph representation. Recently, attention mechanisms on graphs show promising results for classification tasks. Most of the attention mechanisms developed in graph literature use attention to derive the importance of a node or a pair of nodes for different tasks. But in the real world situation, calculating importance up to a pair of nodes is not adequate.

To address this problem, we introduce a novel GNN based approach, subgraph attention, to classify the nodes of a graph. On the other hand, the hierarchical graph pooling is promising in the recent literature. But, not all the hierarchies of a graph play an equal role for graph classification. Towards this end, we propose an algorithm called SubGattPool to find the important nodes in a hierarchy and the importance of individual hierarchies in a graph for embedding and classifying the graphs given a collection of graphs. Moreover, existing pooling approaches do not consider both the region based as well as the graph level importance of the nodes together. In the next research work, we solve this issue by proposing a novel pooling layer named R2pool which retains the most informative nodes for the next coarser version of the graph. Further, we integrate R2pool with our branch training strategy to learn coarse to fine representations and improve the model's capability for graph classification by exploiting multi-level prediction strategy. Thorough experimentation on both the real world and synthetic graphs shows the merit of the proposed algorithms over the state-of-the-art.

Microsoft Teams link: https://teams.microsoft.com/l/team/19%3a35aa9398569340ed9061a35f0589ffe2%40thread.tacv2/conversations?groupId=d9e50dc5-3600-46c1-8888-998889fcedb8&tenantId=6f15cd97-f6a7-41e3-b2c5-ad4193976476

Video Archive Go Top

 

Series: M.Tech (Research) - Thesis Defence (ON-LINE)
Title: Privacy Preserving Machine Learning via Multi-party Computation

  • Speaker: Mr. Chaudhari Harsh Mangesh Suchita
                   M.Tech (Research) student
                   Dept. of CSA
  • Faculty Advisor: Dr. Arpita Patra
  • Date and Time: Monday, June 15, 2020, 11:00 AM
  • Venue: ON-LINE

Abstract
Privacy-preserving machine learning (PPML) via Secure Multi-party Computation (MPC) has gained momen-tum in the recent past. Assuming a minimal network of pair-wise private channels, we propose an efficient four-party PPML framework over rings, FLASH, the first of its kind in the regime of PPML framework, that achieves the strongest security notion of Guaranteed Output Delivery (all parties obtain the output irrespective of adversary's behaviour). The state of the art ML frameworks such as ABY3 by Mohassel et.al (ACM CCS'18) and SecureNN by Wagh et.al (PETS'19) operate in the setting of 3 parties with one malicious corruption but achieve the weaker security guarantee of abort. We demonstrate PPML with real-time efficiency, using the following custom-made tools that overcome the limitations of the aforementioned state-of-the-art-- (a) dot prod-uct, which is independent of the vector size unlike the state-of-the-art ABY3, SecureNN and ASTRA by Chaudhari et.al (ACM CCSW'19), all of which have linear dependence on the vector size. (b) Truncation which is constant round and free of circuits like Ripple Carry Adder (RCA), unlike ABY3 which uses these circuits and has round complexity of the order of depth of these circuits. We then exhibit the application of our FLASH framework in the secure server-aided prediction of vital algorithms: Linear Regression, Logistic Regression, Deep Neural Networks, and Binarized Neural Networks. We substantiate our theoretical claims through im-provement in benchmarks of the aforementioned algorithms when compared with the current best framework ABY3. All the protocols are implemented over a 64-bit ring in LAN and WAN. Our experiments demonstrate that, for MNIST dataset, the improvement (in terms of throughput) ranges from 11x to 1390x over Local Area Network (LAN) and Wide Area Network (WAN) together.

Online link to join Microsoft meeting:

https://teams.microsoft.com/_#/pre-join-calling/19:meeting_MmMxMDZkNmItZWZkOS00ZGJhLTgyYzYtNjlhODZiYjk5NzNj@thread.v2

Video Archive Go Top

 

Series: Seminar
Title: Learning-Based Controlled Concurrency Testing

  • Speaker: Suvam Mukherjee
  • Faculty Advisor: Deepak D'Souza
  • Date and Time: Monday, June 01, 2020, 11:00 AM
  • Venue: ON-LINE

Abstract
Concurrency bugs are notoriously hard to detect and reproduce. Controlled concurrency testing (CCT) techniques aim to offer a solution, where a scheduler explores the space of possible interleavings of a concurrent program looking for bugs. Since the set of possible interleavings is typically very large, these schedulers employ heuristics that prioritize the search to "interesting" subspaces. However, current heuristics are typically tuned to specific bug patterns, which limits their effectiveness in practice.

In this work, we present QL, a learning-based CCT framework where the likelihood of an action being selected by the scheduler is influenced by earlier explorations. We leverage the classical Q-learning algorithm to explore the space of possible interleavings, allowing the exploration to adapt to the program under test, unlike previous techniques. We have implemented and evaluated QL on a set of microbenchmarks, complex protocols, as well as production cloud services. In our experiments, we found QL to consistently outperform the state-of-the-art in CCT.

This is joint work with Pantazis Deligiannis (Microsoft Research), Arpita Biswas (Indian Institute of Science) and Akash Lal (Microsoft Research).

Microsoft Teams Meeting Link:

https://teams.microsoft.com/l/meetup-join/19%3ameeting_YjIwMzU5NDItM2Q2ZC00Zjg5LTkzYTYtMDVkODg2M2I0OGYw%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%224e94f9c8-085e-46c8-b31f-468b334d3138%22%7d

Speaker Bio:
Suvam Mukherjee is a postdoctoral researcher at Microsoft Research India (MSRI). His research interests lie in the areas of programming languages, verification and model-checking. At MSRI, he has been working on several projects in Microsoft Coyote, an open-source framework used by several teams in Microsoft Azure to write reliable and efficient cloud services. Prior to joining MSRI, Suvam obtained his PhD from the Indian Institute of Science, where his thesis focused on developing efficient static analyses for multithreaded programs. For a part of his work, he won the Radhia Cousot Young Researcher Best Paper Award at the 24th Static Analysis Symposium 2017, New York City.

Host Faculty: Deepak D'Souza

Video Archive Go Top

 

Series: Ph.D (Engg.) - Thesis Defence (Skype)
Title: Constant-rate Non-malleable Codes and their Applications

  • Speaker: Ms. Sai Lakshmi Bhavana Obbattu
                   Ph.D (Engg.)
                   Dept. of CSA
  • Faculty Advisor: Dr. Bhavana Kanukurthi
  • Date and Time: Friday, May 29, 2020, 3:30 PM
  • Venue: Skype

Abstract
Non-malleable codes (NMCs) introduced by Dziembowski, Pietrzak and Wichs in ITCS 2010, provide powerful security guarantees where standard error-correcting codes can not provide any guarantee: a decoded message is either the same or completely independent of the underlying message. NMCs have found applications to various aspects of cryptography such as CCA secure encryption, tamper and leakage resilient cryptography, non-malleable commitments, non-malleable secret sharing schemes and so on. In this talk, we present an application of NMCs to the fascinating problem of "Privacy Amplification". In the problem of privacy amplification, two parties, Alice and Bob, who a-priori share a weak secret, to agree on a uniform secret key, in the presence of a computationally unbounded adversary Eve. Building privacy amplification protocols with constant "entropy loss" and constant "round complexity" was open since 1988 (and recently closed in an independent work of Li [CCC '19]). In this talk, we will show how to construct such a privacy amplification protocol under the existence of non-malleable code with certain strong security guarantees. Next, we will also discuss the first explicit construction of a constant rate, constant state non-malleable code.

This talk is based on joint works with Eshan Chattopadhyay, Bhavana Kanukurthi and Sruthi Sekar.

References: [1] Bhavana Kanukurthi, Sai Lakshmi Bhavana Obbattu, and Sruthi Sekar. Four-state non-malleable codes with explicit constant rate. In Theory of Cryptography Conference, TCC 2017. Invited to Journal of Cryptology.

[2] Eshan Chattopadhyay, Bhavana Kanukurthi, Sai Lakshmi Bhavana Obbattu, and Sruthi Sekar. Privacy amplification from non-malleable codes. In Indocrypt 2019.



Please fill this form: https://docs.google.com/forms/d/e/1FAIpQLSdYuJUadeb9EU60_G_-dm8iy7Y0GjBqzaE8JWr-UL8G9KgTqA/viewform?usp=sf_link by 28 May to be added to the conversation

Video Archive Go Top

 

Series: Ph.D (Engg.) Colloquium (ON-LINE)
Title: Representing Networks: Centrality, Node Embeddings, Community Outliers and Graph Representation

  • Speaker: Mr. Sambaran Bandyopadhyay
                   Ph.D (Engg.) ERP Student
                   Dept. of CSA
  • Faculty Advisor: Prof. M Narasimha Murty & Dr. Ramasuri Narayanam Organizational guide, IBM Research
  • Date and Time: Friday, May 29, 2020, 2:00 PM
  • Venue: Microsoft Teams

Abstract
We start our technical work in this thesis by exploring the classical concept of node centrality (also known as influence measure) in information network. Like clustering, node centrality is also an ill-posed problem. There exist several heuristics and algorithms to compute the centrality of a node in a graph, but there is no formal definition of centrality available in the network science literature. Lately, researchers have proposed axiomatic frameworks for the centrality of a node in a network. However, these existing formal frameworks are not generic in nature in terms of characterizing the space of influence measures in complex networks. In this work, we propose a set of six axioms in order to capture most of the intrinsic properties that any influence measure ideally should satisfy. We also characterize existing measures of centrality with respect to this framework.

Next, we focus more on the representation learning on networks. Network embedding is required as real life networks are large, extremely sparse and discrete in nature. We investigate the problem of unsupervised node representation in attributed networks through informative random walk. Edges are also useful for various downstream network mining tasks, but most of the existing homogeneous network representation learning approaches focus on embedding the nodes of a graph. So, we propose a novel unsupervised algorithm to embed the edges of a network, through the application of the classical concept of line graph of a network. The optimization framework of edge embedding connects to the concept of node centrality in the representation learning framework. Finally, we also conduct research on attributed hypergraphs. We propose a novel graph neural network to represent and classify hypernodes.

Outlier analysis (or anomaly detection) is another important problem for the network science community. All the real-world networks contain outlier nodes to some extent. Empirically we have shown that outliers can affect the quality of network embedding if not handled properly. So, we integrate the process of network embedding and outlier detection into a single framework. In this research thread, we first propose a matrix factorization based approach which minimizes the effect of outlier nodes in the framework of attributed network embedding. Next, we propose two neural network architectures, based on L2 regularization and adversarial training respectively, to minimize the effect of outliers on node embedding of an attributed network. Further, extending the concept of support vector data description, we propose a novel algorithm which integrates node embedding, community detection and outlier detection into a single optimization framework by exploiting the link structure of a graph.

So far, we have conducted research only on the individual components of a graph, i.e., on nodes and edges. In the last part of the thesis, we focus on graph level representation and tasks. First, we propose a supervised graph neural network based algorithm with hierarchical pooling strategy to classify a graph from a set of graphs. Next, we propose a novel GNN based algorithm for the unsupervised representation of a graph from a set of graphs, so that similar graphs are represented closely in the embedding space and dissimilar graphs are separated away.



Microsoft Teams link:

https://teams.microsoft.com/l/team/19%3ad5d87af5b08d4f14b81c06c903932960%40thread.tacv2/conversations?groupId=ef37e047-58df-4367-b37e-9bb717bb42bc&tenantId=6f15cd97-f6a7-41e3-b2c5-ad4193976476

Video Archive Go Top

 

Series: M.Tech (Research) Thesis Defence (ON-LINE)
Title: Fault Aware Read-Copy-Update

  • Speaker: Mr. Abhishek Dubey
                   M.Tech (Research) Student
                   Dept. of CSA
  • Faculty Advisor: Prof. K Gopinath
  • Date and Time: Thursday, May 28, 2020, 2:30 PM
  • Venue: ON-LINE

Abstract
Deferred freeing is the fundamental technique used in Read-Copy-Update (RCU) synchronization technique where reclamation of resources is deferred until the completion of all active RCU read-side critical sections. We observe that faults inside an RCU read-side critical section can indefinitely block writers that are waiting for the completion of RCU readers and also lead to system failures by preventing the reclamation of deferred resources. We show that the impact of such faults in the Linux kernel is global; a fault in one subsystem can propagate and exhaust critical resources in other unrelated subsystems opening a window of opportunity for DoS-based attacks. For example, a fault in a filesystem can exhaust the process ulimit resulting in fork failures. Since, guaranteeing the absence of faults is practically impossible, it is imperative to harden RCU to tolerate faults. We first study the impact of mitigating lockup by termination of the faulty thread, as thread termination is standard approach used by Linux as recovery strategy. Whereas, another solution is stack based and do not require termination of faulty thread. We demonstrate the impact of faults in RCU read-side critical sections and present RCU recovery techniques that use novel approaches to detect and isolate effect of such faults. We also discuss system consistency once the fault is handled by our approaches. Timely recovery results in a usable system, preserving the user application state and increasing the system’s availability. Our evaluation in the Linux kernel shows that our solution can prevent resource exhaustion in the presence of faults with no additional overhead in the absence of faults.

Teams Meeting Link: https://teams.microsoft.com/dl/launcher/launcher.html?url=%2f_%23%2fl%2fmeetup-join%2f19%3ameeting_Nzk2YTg2ZDEtOWRhYy00OGYyLThmZTYtZWI5NTZiMGY0YzRl%40thread.v2%2f0%3fcontext%3d%257b%2522Tid%2522%253a%25226f15cd97-f6a7-41e3-b2c5-ad4193976476%2522%252c%2522Oid%2522%253a%252247d9ed45-e131-49b4-9b89-ac82d3c3da13%2522%257d%26anon%3dtrue&type=meetup-join&deeplinkId=d862ca07-3513-4597-8b62-e5bea2346d12&directDl=true&msLaunch=true&enableMobilePage=true&suppressPrompt=true

Video Archive Go Top

 

Series: Ph.D Colloquium (ON-LINE)
Title: Online Learning from Relative Subsetwise Preferences

  • Speaker: Ms. Aadirupa Saha
                   Ph.D student
                   Dept. of CSA
  • Faculty Advisor: Prof. Chiranjib Bhattacharyya & Prof. Aditya Gopalan
  • Date and Time: Friday, May 15, 2020, 9:00 AM
  • Venue: ON-LINE

Abstract
The elicitation and aggregation of preferences is often the key to making better decisions. Be it a perfume company wanting to relaunch their 5 most popular fragrances, a movie recommender system trying to rank the most favoured movies, or a pharmaceutical company testing the relative efficacies of a set of drugs, learning from preference feedback is a widely applicable problem to solve. One can model the sequential version of this problem using the classical multiarmed-bandit (MAB) (e.g., Auer, 2002) by representing each decision choice as one bandit-arm, or more appropriately as a Dueling-Bandit (DB) problem (Yue and Joachims, 2009). Although DB is similar to MAB in that it is an online decision making framework, DB is different in that it specifically models learning from pairwise preferences. In practice, it is often much easier to elicit information, especially when humans are in the loop, through relative preferences: `Item A is better than item B' is easier to elicit than its absolute counterpart: `Item A is worth 7 and B is worth 4'.

However, instead of pairwise preferences, a more general subset-wise preference model is more relevant in various practical scenarios, e.g. recommender systems, search engines, crowd-sourcing, e-learning platforms, design of surveys, ranking in multiplayer games. Subset-wise preference elicitation is not only more budget friendly, but also flexible in conveying several types of feedback. For example, with subset-wise preferences, the learner could elicit the best item, a partial preference of the top 5 items, or even an entire rank ordering of a subset of items, whereas all these boil down to the same feedback over pairs (subsets of size 2). The problem of how to learn adaptively with subset-wise preferences, however, remains largely unexplored; this is primarily due to the computational burden of maintaining a combinatorially large, O(n^k), size of preference information in general.

We take a step in the above direction by proposing "Battling Bandits (BB)"---a new online learning framework to learn a set of optimal ('good') items by sequentially, and adaptively, querying subsets of items of size up to k (k>=2). The preference feedback from a subset is assumed to arise from an underlying parametric discrete choice model, such as the well-known Plackett-Luce model, or more generally any random utility (RUM) based model. It is this structure that we leverage to design efficient algorithms for various problems of interest, e.g. identifying the best item, set of top-k items, full ranking etc., for both in PAC and regret minimization setting. We propose computationally efficient and (near-) optimal algorithms for above objectives along with matching lower bound guarantees. Interestingly this leads us to finding answers to some basic questions about the value of subset-wise preferences: Does playing a general k-set really help in faster information aggregation, i.e. is there a tradeoff between subsetsize-k vs the learning rate? Under what type of feedback models? How do the performance limits (performance lower bounds) vary over different combinations of feedback and choice models? And above all, what more can we achieve through BB where DB fails?

We proceed to analyse the BB problem in the contextual scenario – this is relevant in settings where items have known attributes, and allows for potentially infinite decision spaces. This is more general and of practical interest than the finite-arm case, but, naturally, on the other hand more challenging. Moreover, none of the existing online learning algorithms extend straightforwardly to the continuous case, even for the most simple Dueling Bandit setup (i.e. when k=2). Towards this, we formulate the problem of "Contextual Battling Bandits (C-BB)" under utility based subsetwise-preference feedback, and design provably optimal algorithms for the regret minimization problem. Our regret bounds are also accompanied by matching lower bound guarantees showing optimality of our proposed methods. All our theoretical guarantees are corroborated with empirical evaluations.

Lastly, it goes without saying, that there are still many open threads to explore based on BB. These include studying different choice-feedback model combinations, performance objectives, or even extending BB to other useful frameworks like assortment selection, revenue maximization, budget-constrained bandits etc. Towards the end we will also discuss some interesting combinations of the BB framework with other, well-known, problems, e.g. Sleeping / Rotting Bandits, Preference based Reinforcement Learning, Learning on Graphs, Preferential Bandit-Convex-Optimization etc.



Microsoft Teams link:

https://teams.microsoft.com/l/meetup-join/19%3ameeting_YzFmNTdmODYtYjhhZi00Yjc4LTg3NWItNmEyNzc5NzlkMzQ1%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%22620fb6db-36c5-4f95-ba45-6ed8e824aa28%22%7d

Video Archive Go Top

 

Series: Ph.D Colloquium (Online)
Title: Decision Making under Uncertainty : Reinforcement Learning Algorithms and Applications in Cloud Computing, Crowdsourcing and Predictive Analytics

  • Speaker: Ms. Indu John
                   Ph.D Student
                   Dept. of CSA
  • Faculty Advisor: Prof. Shalabh Bhatnagar
  • Date and Time: Friday, May 15, 2020, 3:00 PM
  • Venue: Microsoft Teams meeting : https://teams.microsoft.com/l/meetup-join/19%3a8dbfbf39c4464817a8333f18b16a8aec%40thread.tacv2/1588649977138?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%2286976192-e64f-4e50-ae9f-8a79b451c8f8%22%7d

Abstract
In this thesis, we study both theoretical and practical aspects of decision making, with a focus on reinforcement learning based methods. Reinforcement learning (RL) is a form of semi-supervised learning in which the agent learns the decision making strategy by interacting with its environment. We develop novel reinforcement learning algorithms and study decision problems in the domains of cloud computing, crowdsourcing and predictive analytics.

In the first part of the thesis, we develop a model free reinforcement learning algorithm with faster convergence named Generalized Speedy Q-learning and analyze its finite time performance. This algorithm integrates ideas from the well-known Speedy Q-learning algorithm and the generalized Bellman equation to derive a simple and efficient update rule such that its finite time bound is better than that of Speedy Q-learning for MDPs with a special structure. Further, we extend our algorithm to deal with large state and action spaces by using function approximation.

Extending the idea in the above algorithm, we develop a novel Deep Reinforcement Learning algorithm by combining the technique of successive over-relaxation with Deep Q-networks. The new algorithm, named SOR-DQN, uses modified targets in the DQN framework with the aim of accelerating training. We study the application of SOR-DQN in the problem of auto-scaling resources for cloud applications, for which existing algorithms suffer from issues such as slow convergence, poor performance during the training phase and non-scalability.

Next, we consider an interesting research problem in the domain of crowdsourcing - that of efficiently allocating a fixed budget among a set of tasks with varying difficulty levels. Further, the assignment of tasks to workers with different skill levels is tackled. This problem is modeled in the RL framework and an approximate solution is proposed to deal with the exploding state space.

We also study the following problem in predictive analytics : predicting the future values of system parameters well in advance for a large-scale software or industrial system, which is important for avoiding disruptions. An equally challenging and useful exercise is to identify the "important" parameters and optimize them in order to attain good system performance. In addition to devising an end-to-end solution for the problem, we present a case study on a large-scale enterprise system to validate the effectiveness of the proposed approach.

Video Archive Go Top

 

Series: M.Tech (Research) Colloquium
Title: Model Extraction defense using Modified Variational Autoencoder

  • Speaker: Mr. Yash Gupta
                   M.Tech. (Research) Student
                   Dept. of CSA
  • Faculty Advisor: Prof. Aditya Kanade and Prof. Shirish K Shevade
  • Date and Time: Tuesday, May 05, 2020, 09:30 AM
  • Venue: The defense will be conducted online. Please fill the following form before 4th May 5 PM to receive the Microsoft Teams meeting invite. https://forms.gle/Bw4Lj36uFuugZZFY7

Abstract
Machine Learning as a Service (MLaaS) exposes machine learning (ML) models that are trained on confidential datasets to users in the form of an Application Programming Interface (API). Since the MLaaS models are deployed for commercial purposes the API is available as a pay-per-query service. A malicious user or attacker can exploit these APIs to extract a close approximation of the MLaaS model by training a substitute model using only black-box query access to the API, in a process called model extraction. The attacker is restricted to extract the MLaaS model using a limited query budget because of the paid service. The model extraction attack is invoked by firing queries that belong to a substitute dataset that consists of either (i) Synthetic Non-Problem Domain (SNPD), (ii) Synthetic Problem Domain (SPD), or (iii) Natural Non-Problem Domain (NNPD) dataset.

In this work, we propose a novel defense framework against model extraction, using a hybrid anomaly detector composed of an encoder and a detector. In particular we propose a modified Variational Autoencoder, VarDefend, which uses a loss function, specially designed, to separate the encodings of queries fired by malicious users from those by benign users. We consider two scenarios: (i) stateful defense where an MLaaS provider stores the queries made by each client for discovering any malicious pattern, (ii) stateless defense where individual queries are discarded if they are flagged as out-of-distribution. Treating encoded queries from benign users as normal, one can use outlier detection models to identify encoded queries from malicious users in the stateless approach. For the stateful approach, a statistical test known as Maximum Mean Discrepancy (MMD) is used to match the distribution of the encodings of the malicious queries with those of the in-distribution encoded samples. In our experiments, we observed that our stateful defense mechanism can completely block one representative attack for each of the three types of substitute datasets, without raising a single false alarm against queries made by a benign user. The number of queries required to block an attack is much smaller than those required by the current state-of-the-art model extraction defense PRADA. Further, our proposed approach can block NNPD queries that cannot be blocked by PRADA. Our stateless defense mechanism is useful against a group of colluding attackers without significantly impacting benign users. Our experiments demonstrate that, for MNIST and FashionMNIST dataset, proposed stateless defense rejects more than 98% of the queries made by an attacker belonging to either SNPD, SPD or NNPD datasets while rejecting only about 0.05% of all the queries made by a benign user. Our experiments also demonstrate that the proposed stateless approach makes the MLaaS model significantly more robust to adversarial examples crafted using the substitute model by blocking transferability.

Video Archive Go Top

 

Series: Theory Seminar Series
Title: Fair Rent Division

  • Speaker: Ms. Nidhi Rathi
                   IntPh.D Student
                   Dept. of Mathematics
  • Date and Time: Friday, March 13, 2020, 1:00 PM
  • Venue: CSA Lecture Hall (Room No. 117, Ground Floor)

Abstract
The theory of fair division addresses the fundamental problem of allocating resources among agents with equal entitlements but distinct preferences.

In this talk, I will focus on the classic problem of fair rent division that entails splitting the rent (money) and allocating the rooms (indivisible resources) of an apartment among roommates (agents) in a fair manner. Here, a distribution of the rent and an accompanying allocation is said to be fair if it is envy free, i.e., under the imposed rents, no agent has a strictly stronger preference (utility) for any other agent’s room. While envy-free solutions are guaranteed to exist under reasonably general utility functions, efficient algorithms for finding them were known only for quasilinear utilities. Our work addresses this notable gap and develops approximation algorithms for fair rent division with minimal assumptions on the utility functions.

Specifically, we show that if the agents have continuous, monotone decreasing, and piecewise- linear utilities, then the fair rent division problem admits a fully polynomial-time approximation scheme (FPTAS). We complement the algorithmic results by proving that the fair rent division problem (under continuous, monotone decreasing, and piecewise-linear utilities) lies in the intersection of the complexity classes PPAD and PLS. This talk is based on a joint work with Eshwar Arunachaleswaran and Siddharth Barman that appeared in SODA 2019.

Host Faculty: Dr. Anand Louis

Video Archive Go Top

 

Series: M.Tech (Research) Thesis Defense
Title: Optimizing the Linear Fascicle Evaluation Algorithm for Multi-Core and Many-Core Systems

  • Speaker: Mr. Karan Aggarwal
                   M.Tech (Research) student
                   Dept. of CSA
  • Faculty Advisor: Prof. Uday Kumar Reddy B
  • Date and Time: Thursday, March 05, 2020, 2:30 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Sparse matrix-vector multiplication (SpMV) operations are commonly used in various scientific and engineering applications. The performance of the SpMV operation often depends on exploiting regularity patterns in the matrix. Various new representations and optimization techniques have been proposed to minimize the memory bandwidth bottleneck arising from the irregular memory access pattern. Among recent representation techniques, tensor decomposition is a popular one used for very large but sparse matrices. Post sparse-tensor decomposition, the new representation involves indirect accesses, making it challenging to optimize for multi-core architectures and even more demanding for the massively parallel architectures, such as on GPUs.

Computational neuroscience algorithms often involve sparse datasets while still performing compute-intensive operations. The Linear Fascicle Evaluation (LiFE) application is a popular neuroscience algorithm used for pruning brain connectivity graphs. The datasets employed herein involve the Sparse Tucker Decomposition (STD) - a widely used tensor decomposition method. Using this decomposition leads to multiple irregular array references, making it very difficult to optimize for multi-cores and GPUs. Recent implementations of the LiFE algorithm show that its SpMV operations are the key bottleneck for performance and scaling. In this work, we first propose target-independent techniques such as (1) data restructuring techniques to minimize the effects of irregular accesses, and (2) simple compiler optimizations. Then we apply target-specific optimizations to exploit the resources provided by the architecture. The CPU-specific optimizations that we incorporated are loop tiling, loop parallelization and utilizing BLAS calls to exploit data reuse, coarse-grained parallelism and fine-grained parallelism respectively. We extend the PolyMage domain-specific language, embedded in Python, to automate the CPU-based optimizations developed for this algorithm. Next, we propose various GPU-specific optimizations to optimally map threads at the granularity of warps, thread blocks and grid, and methods to split the computation among thread blocks to obtain fine-grained parallelism and data reuse. Our highly optimized and parallelized CPU implementation obtain a reduction in execution time from 225 min to 8.2 min over the original sequential approach running on 16-core Intel Xeon Silver (Skylake-based) system. Our optimized GPU implementation achieves a speedup of 5.2x over a reference optimized GPU code version on NVIDIA's GeForce RTX 2080 Ti GPU, and a speedup of 9.7x over our highly optimized and parallelized CPU implementation.

Video Archive Go Top

 

 

 

 

 

 

 

 

 

 

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