Events 

Seminars 

Golden Jubilee Frontier Lectures 

Prof. I. G. Sarma Memorial Lecture Series 

Prof. Priti Shankar Memorial Seminar Series 

Multimedia Archive 



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: OnLine (Microsoft Teams)
Abstract Technology solutions for accessibility have long been created using a narrow utilitarian lens, especially in the global south due to the multidimensional 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 academicturned technology entrepreneurturned 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 cofounded, managed, advised, and angelfunded 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 gazetracked interfaces for children with sensory motor impairments.
Microsoft Teams link : https://teams.microsoft.com/l/team/19%3a68daf29425434a608aff44016c558a16%40thread.tacv2/conversations?groupId=157bca6a0bb7476981fb685bab1009b8&tenantId=6f15cd97f6a741e3b2c5ad4193976476
Host Faculty: Prof. Chiranjib Bhattacharyya
 Series: Ph.D (Engg.)Thesis Defence ONLINE 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  ONLINE
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 Multiarmed Bandits
In our first problem, we consider online platforms where the users are shown user generated content such as reviews on an ecommerce 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 multiarmed 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 sublinear 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 subexponetal or subPareto tails.
Strategyproof Allocation of Indivisible Goods with Fairness Guarantees
Second, we consider the problem of fairness in online search platforms. We view the sponsored adslots on these platforms as indivisible goods to be allocated in a fair manner among competing advertisers. We use envyfreeness 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 NPhard. We complement this result by showing that any EF1 allocation satisfies an 1/2approximation guarantee and present an algorithm with a (1, 1/2) bicriteria 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/meetupjoin/19%3ameeting_OGM2MGIyZGQtZjZkMi00YTAyLTg5MGItYTRiMGFkZjZmNmRm%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97f6a741e3b2c5ad4193976476%22%2c%22Oid%22%3a%2269dfbf190e41447fb7d4700f9629e40e%22%7d
 Series: Ph.D (Engg.) Thesis Defence  ONLINE Title: Scalable and Effective Polyhedral Autotransformation 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 autotransformation frameworks have gained
significant interest in generalpurpose 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
datalayout optimizations can be incorporated efficiently in a single common
infrastructure.
Polyhedral autotransformation 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 autotransformation 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,
suboptimal loop transformations that result in significant performance degradation
may be obtained. Hence, we propose a new polyhedral autotransformation
framework, called Plutolpdfp, that finds efficient affine loop
transformations quickly, while relying on Plutos cost function. The framework
decouples autotransformation 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, maxfuse, typedfuse and hybridfuse, of which, the hybridfuse and
typedfuse models incorporate parallelism preserving fusion heuristic without
significant compilation time overhead. We also provide a characterization of
timeiterated stencils that have tilewise concurrent start and employ a
different fusion heuristic in such programs. In our experiments, we demonstrate
that Plutolpdfp framework not only finds loop transformations quickly,
resulting in significant improvements in compilation time, but also outperforms
stateoftheart polyhedral autoparallelizers in terms of execution time of
the transformed program. We observe that Plutolpdfp is faster than PoCC and
Pluto by a geomean factor of 461x and 2.2x in terms of compilation time. On
larger NAS benchmarks, Plutolpdfp 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 hybridfuse variant in Plutolpdfp outperforms
PoCC by a geomean factor 1.8x, with over 3x improvements in some cases. We
also observe that Plutolpdfp 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/ioetjuwijo
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 postdoctoral researcher at NVIDIA, Redmond, USA. His research interests are in the development of optimizing compliers and domainspecific languages for high performance.
 Series: Ph.D (Engg.) Colloquium  ONLINE Title: Towards Secure and Efficient Realization of PairingBased 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 pairingbased cryptography (PBC). The main tool for all such cryptosystems is the pairing map which can be defined on either composite or primeorder 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 wellknown that such assumptions have several limitations. In this thesis we explore the question of security and efficiency of pairingbased 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 primeorder bilinear pairing setting, (ii). DejaQ framework, for removing dependency on parameterized assumption and (iii). dualform 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 compositeorder pairing setting. From then there are plenty of cryptosystems constructed in the compositeorder pairing setting. However, it is well known that a compositeorder pairing is significantly slower than its primeorder counterpart. This motivated Freeman to propose his conversion framework that converts some cryptographic protocols to the primeorder 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 SeoCheons projecting and canceling framework under the static symmetric external DiffieHellman (SXDH) assumption, instead of the original tailormade assumption. Next, we formalize the fulldecomposition notion in the existing projecting frameworks and show that this notion is sufficient instead of the socalled 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 primeorder asymmetric pairing setting: ShachamWaters ring signature, BoyenWaters 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 compositeorder 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 pairingbased 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 compositeorder 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 parameterhiding 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 dualform signature (DFS) technique on some pairingbased 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 structurepreserving signature, BoyenWaters group signature and PointchevalSanders rerandomizable signature (RRS) under some static assumptions. We also present an efficient construction of RRS scheme in the primeorder setting. Then, we use the proposed RRS scheme as a building block to construct a sequential aggregate signature (SeqAS) scheme with constantsize public key under the SXDH assumption. The performance of the proposed schemes is comparable to that of previous proposals based on some nonstandard interactive assumptions.
Link to join Microsoft Teams:
https://teams.microsoft.com/l/channel/19%3aa24e8f8dbe724c0486b5239881d7674c%40thread.tacv2/General?groupId=57f6f2301dd8428085edde7a55a7d936&tenantId=6f15cd97f6a741e3b2c5ad4193976476
 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/meetupjoin/19%3ameeting_YmU3ZGQzMzMtY2Q1MC00NzY0LWE2MzAtZGQ3NTIxNjgwZjFm%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97f6a741e3b2c5ad4193976476%22%2c%22Oid%22%3a%2282f39501c5b24bfb87c3f17ca74c00b6%22%7d
Absract:
The future of InternetofThings (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 batteryfree touchsensing user interface (UI) primitive. With RIO, any surface can be turned into a touchaware 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 finegrained touch movement, over both offtheshelf and custombuilt tags.
Secondly, I will present REVOLT, an endtoend system to detect replay attacks on voicefirst 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 internetofthings (IoT) systems. He has designed, built, and deployed systems that deliver ubiquitous sensing, enhanced communication capabilities, and new humancomputer interfaces. His works have been published in the toptier 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
 Series: Ph.D (Engg.) Thesis Defence  ONLINE 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 templatebased generative systems. A
generative system is one in which a specialised system is generated
for each given input specification. In a templatebased 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 safetycritical 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
sandboxed 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 FloydHoare logic in a programmatic setting.
We use this framework to propose a twostep verification approach for
templatebased 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 inputspecific, 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 opensource
templatebased 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 VTx
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 machinechecked 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/xkjbugwcxf
Please note that the meeting will be recorded as per Institute
requirements. By joining the link you are giving your consent to the
recording.
 Series: Ph.D (Engg.) (Colloquium) ONLINE Title: Hypergraph Network Models: Learning, Prediction, and Representation in the Presence of HigherOrder 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 higherorder  involving possibly more than two of them at a time. Yet in reality, higherorder relations do exist and are spread across multiple domains: medical science (e.g., coexisting 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 higherorder relations lose context when represented by a graph, "hypergraphs"  graphlike 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 networkscience oriented problems involving hypergraphs.
"Hypergraphs and Pairwise Links": In the first of three broad parts, we study the behavior of usual graphoriented networks that have an otherwiseignored 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 wellknown problem of link prediction in networks. We find that an underlying hypergraph structure makes popular heuristics such as commonneighbors 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 hypergraphderived networks, we propose adjustments that essentially undo the undesired effects of hypergraphs in performance scores. Motivated by this observation, we extend graphbased 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 graphstructurebased notion of similarity between node pairs to a hypergraphstructurebased 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 Higherorder 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 nonhyperlinks, 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 cliqueclosure based approach, and a subhigherorder oriented one. While in the former, we develop and successfully test the cliqueclosure hypothesis  that hyperlinks mostly form from cliques or nearcliques  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 subhyperedges to capture the subhigherorder notion in relations, and utilize an attentionbased neural network model called SHONeN focusing on subhyperedges of a hyperedge. Owing to SHONeN's computational complexity, we propose a suboptimal heuristic that is able to perform better than its baselines on the downstream task of predicting hyperedges.
"Higherorder Bipartite Relations": The third and final part of our thesis is dedicated exclusively to "bipartite hypergraphs": structures that are used to capture higherorder 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 realworld such networks using perfixed 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 selfattention based approaches meant for usual hypergraphs do not work for bipartite hypergraphs  a fact that our experiments validate, we propose a crossattention model for the same, and use the notion of setmatching 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 positivenegative dilemma, existing stateoftheart algorithms fail on bipartite hypergraphs.
Microsoft Teams Meeting Link:
https://teams.microsoft.com/l/meetupjoin/19%3ameeting_ZWQyMTY2OTMtMmI4MC00ZThiLThiN2QtNGU1M2FlYTExZDRi%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97f6a741e3b2c5ad4193976476%22%2c%22Oid%22%3a%227cc8bd44135e4281b03380d7f9df42fd%22%7d
 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 mvariate polynomial f is affine equivalent to an nvariate polynomial g if m > n and there is a full rank n * m matrix A and a ndimensional 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 (TrIMM). 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 TrIMM 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 TrIMM. In this thesis, we take a step towards showing that equivalence test for IMM and TrIMM have different complexity. We show that equivalence test for TrIMM 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 TrIMM 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 TrIMM over rationals is at least as hard as Integer Factoring. This would then be in sharp contrast with the complexity of equivalence test for TrIMM 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/1FAIpQLSfWTKcz5v_dpOpfzb8JwZKFJVl5UN6aUR5Pw2yIwK22QCqww/viewform?usp=sf_link
 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  ONLINE
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 costbalanced kclustering. 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 kmedian or kcenter, 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. Costbalanced kclustering 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.5stable 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" costbalanced kclustering. Given a blackbox algorithm which gives constant factor approximation to the "lp" cost kclustering problem, we show a procedure that runs in poly time and gives bicriteria approximation to the "lp" costbalanced kclustering 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=d79f4d993e9e4035a30109c28012be9e&tenantId=6f15cd97f6a741e3b2c5ad4193976476
 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 multilevel prediction strategy. Thorough experimentation on both the real world and synthetic graphs shows the merit of the proposed algorithms over the stateoftheart.
Microsoft Teams link:
https://teams.microsoft.com/l/team/19%3a35aa9398569340ed9061a35f0589ffe2%40thread.tacv2/conversations?groupId=d9e50dc5360046c18888998889fcedb8&tenantId=6f15cd97f6a741e3b2c5ad4193976476
 Series: M.Tech (Research)  Thesis Defence (ONLINE) Title: Privacy Preserving Machine Learning via Multiparty 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: ONLINE
Abstract Privacypreserving machine learning (PPML) via Secure Multiparty Computation (MPC) has gained momentum in the recent past. Assuming a minimal network of pairwise private channels, we propose an efficient fourparty 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 realtime efficiency, using the following custommade tools that overcome the limitations of the aforementioned stateoftheart (a) dot product, which is independent of the vector size unlike the stateoftheart 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 serveraided prediction of vital algorithms: Linear Regression, Logistic Regression, Deep Neural Networks, and Binarized Neural Networks. We substantiate our theoretical claims through improvement in benchmarks of the aforementioned algorithms when compared with the current best framework ABY3. All the protocols are implemented over a 64bit 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/_#/prejoincalling/19:meeting_MmMxMDZkNmItZWZkOS00ZGJhLTgyYzYtNjlhODZiYjk5NzNj@thread.v2
 Series: Seminar Title: LearningBased Controlled Concurrency Testing  Speaker: Suvam Mukherjee
 Faculty Advisor: Deepak D'Souza
 Date and Time: Monday, June 01, 2020, 11:00 AM
 Venue: ONLINE
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 learningbased CCT framework where the likelihood of an action being selected by the scheduler is influenced by earlier explorations. We leverage the classical Qlearning 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 stateoftheart 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/meetupjoin/19%3ameeting_YjIwMzU5NDItM2Q2ZC00Zjg5LTkzYTYtMDVkODg2M2I0OGYw%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97f6a741e3b2c5ad4193976476%22%2c%22Oid%22%3a%224e94f9c8085e46c8b31f468b334d3138%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 modelchecking. At MSRI, he has been working on several projects in Microsoft Coyote, an opensource 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
 Series: Ph.D (Engg.)  Thesis Defence (Skype) Title: Constantrate Nonmalleable 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 Nonmalleable codes (NMCs) introduced by Dziembowski, Pietrzak and Wichs in ITCS 2010, provide powerful security guarantees where standard errorcorrecting codes can not provide any guarantee: a decoded message is either the same or completely independent of the underlying message. NMCs have found applications to various aspects of cryptography such as CCA secure encryption, tamper and leakage resilient cryptography, nonmalleable commitments, nonmalleable secret sharing schemes and so on.
In this talk, we present an application of NMCs to the fascinating problem of "Privacy Amplification". In the problem of privacy amplification, two parties, Alice and Bob, who apriori share a weak secret, to agree on a uniform secret key, in the presence of a computationally unbounded adversary Eve. Building privacy amplification protocols with constant "entropy loss" and constant "round complexity" was open since 1988 (and recently closed in an independent work of Li [CCC '19]). In this talk, we will show how to construct such a privacy amplification protocol under the existence of nonmalleable code with certain strong security guarantees.
Next, we will also discuss the first explicit construction of a constant rate, constant state nonmalleable 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. Fourstate nonmalleable codes with explicit constant rate. In Theory of Cryptography Conference, TCC 2017.
Invited to Journal of Cryptology.
[2] Eshan Chattopadhyay, Bhavana Kanukurthi, Sai Lakshmi Bhavana Obbattu, and Sruthi Sekar. Privacy amplification from nonmalleable codes. In Indocrypt 2019.
Please fill this form:
https://docs.google.com/forms/d/e/1FAIpQLSdYuJUadeb9EU60_G_dm8iy7Y0GjBqzaE8JWrUL8G9KgTqA/viewform?usp=sf_link
by 28 May to be added to the conversation
 Series: Ph.D (Engg.) Colloquium (ONLINE) 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 illposed 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 realworld 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=ef37e04758df4367b37e9bb717bb42bc&tenantId=6f15cd97f6a741e3b2c5ad4193976476
 Series: M.Tech (Research) Thesis Defence (ONLINE) Title: Fault Aware ReadCopyUpdate  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: ONLINE
Abstract Deferred freeing is the fundamental technique used in ReadCopyUpdate (RCU) synchronization technique where reclamation of resources is deferred until the completion of all active RCU readside critical sections. We observe that faults inside an RCU readside 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 DoSbased 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 readside 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%2fmeetupjoin%2f19%3ameeting_Nzk2YTg2ZDEtOWRhYy00OGYyLThmZTYtZWI5NTZiMGY0YzRl%40thread.v2%2f0%3fcontext%3d%257b%2522Tid%2522%253a%25226f15cd97f6a741e3b2c5ad4193976476%2522%252c%2522Oid%2522%253a%252247d9ed45e13149b49b89ac82d3c3da13%2522%257d%26anon%3dtrue&type=meetupjoin&deeplinkId=d862ca07351345978b62e5bea2346d12&directDl=true&msLaunch=true&enableMobilePage=true&suppressPrompt=true
 Series: Ph.D Colloquium (ONLINE) 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: ONLINE
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 multiarmedbandit (MAB) (e.g., Auer, 2002) by representing each decision choice as one banditarm, or more appropriately as a DuelingBandit (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 subsetwise preference model is more relevant in various practical scenarios, e.g. recommender systems, search engines, crowdsourcing, elearning platforms, design of surveys, ranking in multiplayer games. Subsetwise preference elicitation is not only more budget friendly, but also flexible in conveying several types of feedback. For example, with subsetwise 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 subsetwise 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 wellknown PlackettLuce 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 topk 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 subsetwise preferences: Does playing a general kset really help in faster information aggregation, i.e. is there a tradeoff between subsetsizek 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 finitearm 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 (CBB)" under utility based subsetwisepreference 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 choicefeedback model combinations, performance objectives, or even extending BB to other useful frameworks like assortment selection, revenue maximization, budgetconstrained bandits etc. Towards the end we will also discuss some interesting combinations of the BB framework with other, wellknown, problems, e.g. Sleeping / Rotting Bandits, Preference based Reinforcement Learning, Learning on Graphs, Preferential BanditConvexOptimization etc.
Microsoft Teams link:
https://teams.microsoft.com/l/meetupjoin/19%3ameeting_YzFmNTdmODYtYjhhZi00Yjc4LTg3NWItNmEyNzc5NzlkMzQ1%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97f6a741e3b2c5ad4193976476%22%2c%22Oid%22%3a%22620fb6db36c54f95ba456ed8e824aa28%22%7d
 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/meetupjoin/19%3a8dbfbf39c4464817a8333f18b16a8aec%40thread.tacv2/1588649977138?context=%7b%22Tid%22%3a%226f15cd97f6a741e3b2c5ad4193976476%22%2c%22Oid%22%3a%2286976192e64f4e50ae9f8a79b451c8f8%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 semisupervised 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 Qlearning and analyze its finite time performance. This algorithm integrates ideas from the wellknown Speedy Qlearning 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 Qlearning 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 overrelaxation with Deep Qnetworks. The new algorithm, named SORDQN, uses modified targets in the DQN framework with the aim of accelerating training. We study the application of SORDQN in the problem of autoscaling resources for cloud applications, for which existing algorithms suffer from issues such as slow convergence, poor performance during the training phase and nonscalability.
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 largescale 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 endtoend solution for the problem, we present a case study on a largescale enterprise system to validate the effectiveness of the proposed approach.
 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 payperquery 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 blackbox 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 NonProblem Domain (SNPD), (ii) Synthetic Problem Domain (SPD), or (iii) Natural NonProblem 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 outofdistribution. 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 indistribution 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 stateoftheart 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.
 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 envyfree 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 polynomialtime approximation scheme (FPTAS). We complement the algorithmic results by proving that the fair rent division problem (under continuous, monotone decreasing, and piecewiselinear 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
 Series: M.Tech (Research) Thesis Defense Title: Optimizing the Linear Fascicle Evaluation Algorithm for
MultiCore and ManyCore 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 matrixvector 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 sparsetensor decomposition, the new representation
involves indirect accesses, making it challenging to optimize for multicore architectures and
even more demanding for the massively parallel architectures, such as on GPUs.
Computational neuroscience algorithms often involve sparse datasets while still performing
computeintensive 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 multicores 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
targetindependent techniques such as (1) data restructuring techniques to minimize the effects of
irregular accesses, and (2) simple compiler optimizations. Then we apply targetspecific optimizations
to exploit the resources provided by the architecture. The CPUspecific optimizations that we
incorporated are loop tiling, loop parallelization and utilizing BLAS calls to exploit data reuse,
coarsegrained parallelism and finegrained parallelism respectively. We extend the PolyMage
domainspecific language, embedded in Python, to automate the CPUbased optimizations developed for
this algorithm. Next, we propose various GPUspecific 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 finegrained 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 16core Intel Xeon Silver (Skylakebased) 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.

