Events 

Seminars 

Golden Jubilee Frontier Lectures 

Prof. I. G. Sarma Memorial Lecture Series 

Prof. Priti Shankar Memorial Seminar Series 

Multimedia Archive 



UPCOMING SEMINARS 

Series: Theory Seminar Title: Superpolynomial lower bounds against lowdepth algebraic circuits  Speaker: Dr. Nutan Limaye
Associate Professor
Department of Computer Science and Engineering
Indian Institute of Technology, Bombay  Date and Time: Friday, July 30, 2021, 4:00 PM
 Venue: Microsoft Teams  ONLINE
Abstract An algebraic circuit computes a polynomial using addition and multiplication operators. Understanding the power of algebraic circuits has close connections to understanding general computation. It is known that proving lower bounds for algebraic circuits can serve as a stepping stone towards proving general Boolean circuit lower bounds.
Despite this, not many lower bounds are known for even simple Sigma Pi Sigma (productdepth 1) circuits. Before our work, the best known lower bound for productdepth 1 circuit was (slightly less than) cubic. No lower bounds were known for general productdepth 2 circuits.
In this work, we show the first superpolynomial lower bound for lowproductdepth algebraic circuits.
In the talk, we discuss the main results and present the proof ideas used in the proof of the superpolynomial lower bound for productdepth 1 circuits.
This talk is based on joint work with Srikanth Srinivasan and Sébastien Tavenas.
Microsoft Teams Link:
https://teams.microsoft.com/l/meetupjoin/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97f6a741e3b2c5ad4193976476%22%2c%22Oid%22%3a%227c84465ec38b4d7a9a9dff0dfa3638b3%22%7d
Host Faculty: Dr. Anand Louis
 Series: Department Seminar Title: Network Anonymity, Privacy, (Anti) Censorship and the Whole Nine Yards.  Speaker: Dr. Sambuddho Chakravarty
Assistant Professor
Department of Computer Science and Engineering
Indraprastha Institute of Information Technology (IIIT Delhi)  Date and Time: Friday, July 30, 2021, 2:00 PM
 Venue: Microsoft teams  ONLINE: https://teams.microsoft.com/l/meetupjoin/19%3ameeting_NjA3ZmM1ZDYtZTdjYi00NTZjLTgzNDUtZjRhNjJmZmNiMDdl%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97f6a741e3b2c5ad4193976476%22%2c%22Oid%22%3a%220432f3a0d225405cb0f4ff1ffaf4f1fd%22%7d
Abstract In the second decade of the century (circa the Arab Springs of 2011), the Internet is the new battlefield where wars between politicians, media, (h)activists, lawyers and the military, shape the destiny of millions of people. Historically incepted as the ARPANET, it was engineered to serve as means of communication, even in the face of calamities and wars. Political will often plays antithetical to this very attribute. For instance, countries like China, Iran and UAE use (homebrewed) firewalling infrastructure to censor web traffic  sometimes with the pretext of preserving cultural and religious values, at other times to prevent political dissent. No wonder a large body of network censorship measurements focuses on these two countries. While such countries are inherently (constitutionally) undemocratic, free speech over the Internet is, in recent years, being regularly suppressed even in democracies like India. Such evolutions are positioned on concerns otherwise paramount to the preservation of human rights  e.g., policing child pornography. But state control of communication channels has been abuse to silence dissent, even in India where the supreme court deems freedom of speech on the Internet a fundamental right.
In this context, it is natural to ask how free and open is the Internet and how robust it is to censorship by countries like India, that in the recent years has evolved a sophisticated censorship infrastructure.
In this talk I present an overview our work over the years that has focussed on evolution of Indians Internet censorship infrastructure, how it censors traffic (and now apps.), how various ISPs implement it. Further, I also present some research efforts to evade censorship (and also Internet shutdowns/blackouts).
To begin with we consider the question of whether India might potentially follow the Chinese model and institute a single, governmentcontrolled filter. Our research shows that would not be difficult, as the Indian Internet is quite centralized already. A few key ASes (~ 1% of Indian ASes, i.e. less than 4) and routers (<5000) collectively intercept approximately 95% of paths to the censored sites and to all publiclyvisible DNS resolvers. Thereafter we conducted an extensive study (first of its kind) involving nine major ISPs of the country in terms of what kind of censorship techniques they use, what triggers them, their consistency and coverage, and how to evade them. Our results indicate a clear disparity among the ISPs, on how widely they install censorship infrastructure. As of 2021, we have extensively explored the evolution of web censorship (HTTPS) along with exactly how Chinese apps are being filtered in the country.
While existing solutions to evade censorship include proxies, VPNs, Tor have been designed primarily for web, while other applications like VoIP (realtime voice) are mostly ignored. As a part of our research we have extensively explored the feasibility of transporting realtime voice (mostly UDP) over Tor (that primarily supports TCP). Prior research deemed Tor to be unsuitable for such purposes. In our research we tried to identify how the interplay of network attributes (delay, jitter, bandwidth etc.) impact performance of VoIP. To our surprise the belief established from prior research seems unfounded.
However, all such solutions that rely on proxies are prone to being filtered by the ISPs, as these endpoints are easily discoverable. Futuristic solutions like Decoy Routing, that rely on routers that could double as “smart proxies”, are resilient to such filtering. They have hitherto relied mostly on commodity servers, and involve wide scale traffic observation, inadvertently posing a threat to the privacy of users who do not require such services. To that end, we devised a SDN based DR solution, SiegeBreaker, that not only performs at line rates (comparable to native TCP) but also does not require inspection of all network flows, thus preserving the privacy of oblivious users. However, the deployability of such solutions remains a challenge, as it requires support from major toptier ISPs.
A third alternative, combining the best of both the above solutions, involves tunnelling Internet traffic over that of various (semi)real time applications, e.g. Instant Messaging (IM). To that end, we designed and tested a scheme, Camoufler, that utilizes IM channels asis for transporting traffic. The scheme provides unobservability and good QoS, due to its inherent properties, such as lowlatency message transports. Moreover, unlike Decoy Routing, it does not pose new deployment challenges. Performance evaluation of Camoufler, implemented on five popular IM apps indicate that it provides sufficient QoS for web browsing. E.g., the median time to render the homepages of Alexa top1k sites was recorded to be about 3.6s, when using Camoufler implemented over Signal.
Finally, I would like to conclude the talk with our new system Dolphin, that emulates old school dialup modems, sans the ISP support, to relay Internet traffic especially in the face of Internet shutdowns. Dolphins protocol recovers from the losses and errors introduced by the cellular voice medium, while also assuring endtoend confidentiality. At low data rates (<=64bps), the errors are under 5% and suitable for supporting delaytolerant applications with acceptable latencies. E.g. a 280 character tweet can be posted in about a minute.
Speaker Bio: Sambuddho Chakravarty works as an Asst Prof. at the Department of Computer Science and Engineering Department of Indraprastha Institute of Information Technology (IIIT Delhi) since June 2014. He completed his PhD in Computer Science from Columbia University, New York, where he worked at the Network Security Lab (NSL) and was advised by Prof. Angelos D. Keromytis. His research is broadly related to network security and more specifically related to network anticensorship, countersurveillance, network anonymity and privacy (and all problems revolving around such systems e.g. network measurements, infrastructure etc.). He heads a small research lab at IIIT Delhi that involves ten students (mostly PhDs and B.tech students) and collaborates actively with other networks and systems security researchers in India and abroad.
Microsoft teams link
https://teams.microsoft.com/l/meetupjoin/19%3ameeting_NjA3ZmM1ZDYtZTdjYi00NTZjLTgzNDUtZjRhNjJmZmNiMDdl%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97f6a741e3b2c5ad4193976476%22%2c%22Oid%22%3a%220432f3a0d225405cb0f4ff1ffaf4f1fd%22%7d
Host Faculty: Prof. Vinod Ganapathy


PAST SEMINARS 

Series: M.Tech (Research) Colloquium ONLINE Title: Hadwigers conjecture and total coloring  Speaker: Mr. Ankur Naskar
M.Tech (Research) student
Dept. of CSA  Faculty Advisor: Prof. Sunil L Chandran
 Date and Time: Wednesday, July 28, 2021, 4:00 PM
 Venue: Microsoft Teams  ONLINE
Abstract Hadwigers conjecture is one of the most important and longstanding conjectures in graph theory.
It was established that proving Hadwigers conjecture is equivalent to proving the conjecture for the special class of graphs that can be expressed as the square of some other graph. However, it is difficult to prove Hadwigers conjecture even for the squares of highly specialised graph classes.
We decided to investigate the squares of subdivided graphs (a subdivided graph is a graph that can be obtained from another graph $H$ by replacing each edge $uv$ of $H$ by a path $uwv$, where $w$ is a new vertex).
It turns out that squares of subdivided graphs are exactly the class of total graphs, wellstudied in the context of the total coloring conjecture, another wellknown and longstanding conjecture in graph theory.
The total graph of $G$, denoted by $T(G)$, is defined on the vertex set $V(G)sqcup E(G)$ with $c_{1},c_{2}in V(G)sqcup E(G)$ adjacent whenever $c_{1}$ and $c_{2}$ are adjacent to or incident on each other in $G$.
The totalchromatic number $chi(G)$ of a graph $G$ is defined to be equal to the chromatic number of its total graph. That is, $chi(G)=chi(T(G))$.
The total coloring conjecture or textit{TCC} states that for every graph $G$, $chi(G)leqDelta(G)+2$.
Though Hadwigers conjecture was proved for the closely related class of line graphs 20 years ago itself, Hadwigers conjecture is not yet studied in the context of total graphs.
In this thesis, the following results are proved:
(i) There exists a constant $C$ such that, if the connectivity of $Ggeq C$, then Hadwigers conjecture is true for $T(G)$.
(ii) Let $mathcal{F}$ be a class of graphs that is closed under the operation of taking subgraphs. If a weaker version of the total coloring conjecture (weak textit{TCC}) namely, $chi(G)leqDelta(G)+3$, is true for the class $mathcal{F}$, then Hadwigers conjecture is true for the class ${T(G): Gin mathcal{F} }$.
The second statement motivates one to look for classes of graphs that satisfy weak textit{TCC}.
It may be noted that a complete proof of textit{TCC} for even $4$colorable graphs (in fact even for planar graphs) has remained elusive even after decades of effort; but weak textit{TCC} can be proved easily for $4$colorable graphs.
It was noticed that in spite of interest in studying $chi(G)$ in terms of $chi(G)$ right from the initial days, weak textit{TCC} is not proven to be true for $k$colorable graphs even for $k=5$.
In the latter half of the thesis, an important contribution to the total coloring literature is made by proving that $chi(G)leq Delta(G)+3$, for every $5$colorable graph $G$.
Being close to some of the well studied topics in total coloring, it seems that this is a longpending addition to the literature.
Microsoft teams link:
https://teams.microsoft.com/l/meetupjoin/19%3ameeting_ZGMzMDhiNTItM2IwNS00MDZhLWI4Y2ItMThhMjkwN2M4YjNi%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97f6a741e3b2c5ad4193976476%22%2c%22Oid%22%3a%22ed2e5ccdb870455c862e26e9ab1908be%22%7d
 Series: M.Tech (Research) Colloquium ONLINE Title: Algorithms for Fair Clustering  Speaker: Ms. Swati Allabadi
M.Tech (Research)
Dept. of CSA  Faculty Advisor: Prof. Anand Louis and Prof. Arindam Khan
 Date and Time: Wednesday, July 28, 2021, 3:30 PM
 Venue: Microsoft Teams  ONLINE
Abstract Many decisions today are taken by various machine learning algorithms, hence it is crucial to accommodate fairness in such algorithms to remove/reduce any kind of bias in the decision. We incorporate fairness in the problem of clustering. Clustering is a classical machine learning problem in which the task is to partition the data points into various groups such that the data points belonging to one group are more similar to each other than the data points belonging to some other group in the partition.
newline
In our model, each data point belongs to one or more number of categories. We define fairness in terms of two constraints, restricted dominance and minority protection. While ensuring fairness in the clustering, we consider each data point in only of the categories from the set of categories it belongs to.
Our model ensures that no category is either in minority or in dominance in any of the clusters. Representation of a category in a cluster is considered not in absolute terms but in proportion to its presence in the whole dataset.
We give bicriteria approximation for fair clustering whose objective is to minimise $L_p$norm where $p$ can take any integral value. We implement this algorithm and do experiments to compare it with the stateoftheart. For any $epsilon >0$, we give a randomized algorithm with approximation ratio of $(1 + epsilon)$ for fair clustering for points lying in Euclidean space whose objective is to minimise $L_1$norm (or $L_2$norm). For points lying in $mathbb{R}^d$, the run time of this algorithm for $L_2$norm is $Oleft(nd cdot 2^{tilde{O}(k/epsilon)}right) + poly(n) cdot 2^{tilde{O}(k/epsilon)}$, where $n$ represents the size of the dataset. For $L_1$norm, the run time of this algorithm is $Oleft(nd cdot 2^{tilde{O}(k/epsilon^{O(1)})}right) + poly(n) cdot 2^{tilde{O}(k/epsilon^{O(1)})} $. Given a $gamma$perturbation resilient instance of clustering in the metric space $(V,d)$, we also give a bicriteria approximation for the fair clustering of the same instance while changing its metric to $d $. Here, $d $ is any metric which is a $gamma$perturbation of $(V,d)$.
Microsoft teams link:
https://teams.microsoft.com/l/meetupjoin/19%3ameeting_YjZkYWU2MjEtMGYwZS00YmZlLWI1MGMtMzA3YjhiMGUyZjgy%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97f6a741e3b2c5ad4193976476%22%2c%22Oid%22%3a%220c3c2a6337e34ad6b0bdddfa9589e2d5%22%7d
 Series: M.Tech (Research)Thesis Defence ONLINE Title: Locally Reconstructable NonMalleable Secret Sharing  Speaker: Ms. Jenit Tomy
M.Tech (Research) student
Dept. of CSA  Faculty Advisor: Prof. Bhavana Kanukurthi
 Date and Time: Tuesday, July 27, 2021, 9:00 AM
 Venue: Microsoft Teams  ONLINE
Abstract Nonmalleable secret sharing (NMSS) schemes, introduced by Goyal and Kumar (STOC 2018), ensure that a secret m can be distributed into shares m1,...,mn (for some n), such that any t (a parameter <= n) shares can be reconstructed to recover the secret m, any t1 shares doesnt leak information about m and even if the shares that are used for reconstruction are tampered, it is guaranteed that the reconstruction of these tampered shares will either result in the original m or something independent of m. Since their introduction, nonmalleable secret sharing schemes sparked a very impressive line of research.
In this talk, we present a new feature of local reconstructablility in NMSS, which allows reconstruction of any portion of a secret by reading just a few locations of the shares. This is a useful feature, especially when the secret is long or when the shares are stored in a distributed manner on a communication network. In this talk, we give a compiler that takes in any nonmalleable secret sharing scheme and compiles it into a locally reconstructable nonmalleable secret sharing scheme. To secret share a message consisting of k blocks of length r each, our scheme would only require reading r + log k bits (in addition to a few more bits, whose quantity is independent of r and k) from each partys share (of a reconstruction set) to locally reconstruct a single block of the message.
Microsoft teams link:
https://teams.microsoft.com/l/meetupjoin/19%3ameeting_MzNjOGVkNzgtNTM5Zi00OWRlLWJkYWItYWNjMjI4ZGI1NzJi%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97f6a741e3b2c5ad4193976476%22%2c%22Oid%22%3a%225f3273b8883846b7b675b1e9eab4d8ef%22%7d
 Series: M.Tech (Research)Thesis Defence ONLINE Title: Approximation Algorithms for Geometric Packing Problems  Speaker: Mr. Eklavya Sharma
M.Tech (Research) student
Dept. of CSA  Faculty Advisor: Prof. Arindam Khan
 Date and Time: Monday, July 26, 2021, 11:00 AM
 Venue: Microsoft Teams  ONLINE
Abstract We study approximation algorithms for the geometric bin packing problem and its variants. In the twodimensional geometric bin packing problem (2D GBP), we are given n rectangular items and we have to compute an axisparallel nonoverlapping packing of the items into the minimum number of square bins of side length 1. 2D GBP is an important problem in computer science and operations research arising in logistics, resource allocation, and scheduling.
We first study an extension of 2D GBP called the generalized multidimensional bin packing problem (GVBP). Here each item i additionally has d nonnegative weights v_1(i), v_2(i), …, v_d(i) associated with it. Our goal is to compute an axisparallel nonoverlapping packing of the items into bins so that for all j ∈ [d], the sum of the jth weight of items in each bin is at most 1. Despite being well studied in practice, surprisingly, approximation algorithms for this problem have rarely been explored. We first obtain two simple algorithms for GVBP having asymptotic approximation ratios (AARs) 6(d+1) and 3(1 + ln(d+1) + ε). We then extend the RoundandApprox (R&A) framework [BansalKhan, SODA14] to wider classes of algorithms, and show how it can be adapted to GVBP. Using more sophisticated techniques, we obtain algorithms for GVBP having an AAR of 2(1+ln((d+4)/2))+ε, which improves to 2.919+ε for the special case of d=1.
Next, we explore approximation algorithms for the ddimensional geometric bin packing problem (dD GBP). Caprara (MOR 2008) gave a harmonicbased algorithm for dD GBP having an AAR of 1.69104^(d1). However, their algorithm doesnt allow items to be rotated. This is in contrast to some common applications of dD GBP, like packing boxes into shipping containers. We give approximation algorithms for dD GBP when items can be orthogonally rotated about all or a subset of axes. We first give a fast and simple harmonicbased algorithm, called fullh_k, having an AAR of 1.69104^d. We next give a more sophisticated harmonicbased algorithm, which we call hgap_k, having an AAR of (1+ε)1.69104^(d1). This gives an AAR of roughly 2.860 + ε for 3D GBP with rotations, which improves upon the bestknown AAR of 4.5. In addition, we study the multiplechoice bin packing problem that generalizes the rotational case. Here we are given n sets of ddimensional cuboidal items and we have to choose exactly one item from each set and then pack the chosen items. Our algorithms fullh_k and hgap_k also work for the multiplechoice bin packing problem. We also give fast and simple approximation algorithms for the multiplechoice versions of dD strip packing and dD geometric knapsack. These algorithms have AARs 1.69104^(d1) and (1ε)3^(d), respectively.
A rectangle is said to be δskewed if it has width at most δ or height at most δ. We give an approximation algorithm for bin packing δskewed rectangles whose asymptotic approximation ratio approaches 1 as δ approaches 0. Our result indicates that hard instances in geometric bin packing arise due to items that are large in both dimensions.
A packing of rectangles into a bin is said to be guillotineseparable iff we can use a sequence of endtoend cuts to separate the items from each other. The asymptotic price of guillotinability (APoG) is the maximum value of opt_G(I)/opt(I) for large opt(I), where opt(I) and opt_G(I) are the minimum number of bins and the minimum number of guillotineseparable bins, respectively, needed to pack I. Computing lower and upper bounds on APoG is an important problem, since proving an upper bound smaller than 1.5 would beat the stateoftheart algorithm for 2D GBP. The bestknown lower and upper bounds are 4/3 and 1.69104, respectively. We analyze this problem for the special case of δskewed rectangles, where δ is a small constant (i.e., close to 0). We give a roughly 4/3asymptoticapproximate algorithm for 2D GBP for this case, and our algorithms output is guillotineseparable. This proves an upperbound of roughly 4/3 on APoG for δskewed rectangles. We also prove a matching lowerbound of 4/3. This shows that hard examples for upperbounding APoG include items that are large in both dimensions.
Microsoft Teams link:
https://teams.microsoft.com/l/meetupjoin/19%3ameeting_NWU4MzkzMWEtZWY0ZS00MjU3LTk1YzMtMTMxZDVmZjM5Nzhl%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97f6a741e3b2c5ad4193976476%22%2c%22Oid%22%3a%22cd1ddf68b75e433787f3ded65154fa20%22%7d
 Series: Theory Seminar Title: Spectral Clustering Oracles in Sublinear Time  Speaker: Dr. Michael Kapralov
Assistant Professor
School of Computer and Communication Sciences
EPFL, Switzerland  Date and Time: Friday, July 23, 2021, 4:00 PM
 Venue: Microsoft teams  ONLINE
Abstract Given an nvertex graph G that can be partitioned into a few clusters with good inner conductance and
ϵsparse boundary, i.e. admits a good clustering, can we quickly tell which cluster a given vertex belongs to? A clustering oracle is a small space data structure that provides query access to an approximate clustering of the input graph in sublinear time. In this talk I will describe a clustering oracle that provides query access to an
O(ϵlogk) approximate clustering in time about n1/2+O(ϵ), where k is the number of clusters, which is essentially optimal for constant k. Our main tool is a new way of obtaining dot product access to the spectral embedding of a clusterable graph in sublinear time using the distribution of a few short random walks started at uniformly random vertices in the graph.
Microsoft teams link:
https://teams.microsoft.com/l/meetupjoin/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97f6a741e3b2c5ad4193976476%22%2c%22Oid%22%3a%227c84465ec38b4d7a9a9dff0dfa3638b3%22%7d
Host Faculty: Dr. Anand Louis
 Series: M.Tech (Research) Colloquium ONLINE Title: Enhancing Coverage and Robustness of Database Generators  Speaker: Mr. Rajkumar Santhanam
M.Tech (Research) student
Dept. of Computer Science and Automation  Faculty Advisor: Prof. Jayant R. Haritsa
 Date and Time: Friday, July 23, 2021, 11:00 AM
 Venue: Microsoft Teams  ONLINE
Abstract Generating synthetic databases that capture essential data characteristics of client databases is a common requirement for enterprise database vendors. This need stems from a variety of usecases, such as application testing and assessing performance impacts of planned engine upgrades. A rich body of literature exists in this area, spanning from the early techniques that simply generated data abinitio to the contemporary ones that use a predefined client query workload to guide the data generation. In the latter category, the aim specifically is to ensure volumetric similarity  that is, assuming a common choice of query execution plans at the client and vendor sites, the output row cardinalities of individual operators in these plans are similar in the original and synthetic databases.
Hydra is a recently proposed data regeneration framework that provides volumetric similarity. In addition, it also provides a mechanism to generate data dynamically during query execution, using a minuscule database summary. Notwithstanding its desirable characteristics, Hydra has the following critical limitations: (a) limited scope of SQL operators in the input query workload, (b) poor scalability with respect to the number of queries in the input workload, and (c) poor volumetric similarity on unseen queries. The data generation algorithm internally uses a linear programming (LP) solver that throttles the workload scalability. This not only puts a threshold on the training (seen) workload size but also reduces the accuracy for test (unseen) queries. Robustness towards test queries is further adversely affected by design choices such as a lack of preference among candidate synthetic databases, and artificial skew in the generated data.
In this work, we present an enhanced version of Hydra, called HighFidelity Hydra (HFHydra), which attempts to address the above limitations. To start with, we expand the SQL operator coverage to also include the LIKE operator, and, in certain restricted settings, projectionbased operators such as GROUP BY and DISTINCT. To sidestep the challenge of workload scalability, HFHydra outputs not one, but a suite of database summaries such that they collectively cover the entire input workload. The division of the workload into the associated subworkloads is governed by heuristics that aim to balance robustness with LP solvability.
For generating richer database summaries, HFHydra additionally exploits metadata statistics maintained by the database engine. Further, the database query optimizer is leveraged to make the choice among the various candidate databases. The data generation is also augmented to provide greater diversity in the represented values. Finally, when a test query is fired, HFHydra directs it to the database summary that is expected to provide the highest volumetric similarity.
We have experimentally evaluated HFHydra on a customized set of queries based on the TPCDS decisionsupport benchmark framework. We first evaluated the specialized case where each training query has its own summary, and here HFHydra achieves perfect volumetric similarity. Further, each summary construction took just under a second and the summary sizes were just in the order of a few tens of kilobytes. Also, our dynamic generation technique produced gigabytes of data in just a few seconds.
For the general setting of a limited set of summaries representing the training query workload, the data generated by HFHydra was compared with that from Hydra. We observed that HFHydra delivers more than forty percent better accuracy for outputs from filter nodes in the plans, while also achieving an improvement of about twenty percent with regard to join nodes. Further, the degradation in volumetric similarity is minor as compared to the perfectly accurate onesummaryperquery scenario, while the summary production is significantly more efficient due to reduced overheads on the LP solver.
Microsoft Teams link:
https://teams.microsoft.com/l/meetupjoin/19%3azGmzJOhD_rLkNaZfQlJPHgDuCqDsmM8agcKyHnG2E1%40thread.tacv2/1626698346505?context=%7b%22Tid%22%3a%226f15cd97f6a741e3b2c5ad4193976476%22%2c%22Oid%22%3a%2220a4bde227ad4a579b14bb2f66dfd6d0%22%7d
 Series: M.Tech (Research) Colloquium ONLINE Title: QuantumSafe IdentityBased Signature Scheme in Multivariate Quadratic Setting  Speaker: Ms. Akansha Dimri
M.Tech (Research) student
Dept. of CSA  Faculty Advisor: Prof. Sanjit Chatterjee
 Date and Time: Tuesday, July 20, 2021, 4:00 PM
 Venue: Microsoft Teams  ONLINE
Abstract Cryptographic techniques are essential for the security of communication in modern society. Today, nearly all public key cryptographic schemes used in practice are based on the two problems of factoring large integers and solving discrete logarithms. However, as the world grapples with the possibility of widespread quantum computing, these schemes are the ones most threatened. Multivariate Public Key Cryptography is one of the possible candidates for security in a postquantum society, especially in the area of digital signature. This thesis uses the setting of multivariate cryptography to propose an identitybased signature scheme. Our proposal is based on the Rainbow signature scheme and the multivariate 3pass identification scheme, both of which have been subjected to scrutiny by cryptographers all over the world and have emerged as strong postquantum candidates. In our construction, we use the identity of users to generate their private key using Rainbow signature scheme. Thereafter, we use these user private keys to sign messages by applying FiatShamir transform to the 3pass identification scheme. We support the proposed scheme with suitable proof under appropriate computational assumptions, using the standard notions of security. We study the known attacks against multivariate schemes in general, and Rainbow and MQDSS in particular. We then use this analysis to propose concrete parameter sets for our construction. We implement our proposed scheme on an x8664 PC platform and provide timing results. Our implementation shows that our construction is both practical and efficient. Thus, our proposed scheme stands as a potential postquantum multivariate signature candidate in the identitybased setting.
Microsoft teams link:
https://teams.microsoft.com/l/meetupjoin/19%3ameeting_ZDVhMmEzZmYtY2Q2MS00ZWVhLWJiYjktZTY3ZTVhMGNiNjli%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97f6a741e3b2c5ad4193976476%22%2c%22Oid%22%3a%227b997a2ded1848f799c1eaec40b37793%22%7d
 Series: M.Tech (Research) Colloquium ONLINE Title: Recovery Algorithms for planted structures in Semirandom models.  Speaker: Mr. Rameesh Paul
M.Tech (Research) student
Dept. of CSA  Faculty Advisor: Dr. Anand Louis
 Date and Time: Monday, July 19, 2021, 4:00 PM
 Venue: Microsoft Teams  ONLINE
Abstract For many NPhard problems, the analysis of bestknown approximation algorithms yields “poor” worstcase guarantees. However, using various heuristics, the problems can be solved (to some extent) in reallife instances. This success can be attributed to the atypicality of worstcase instances in real life, and therefore motivates studying the problem in “easier” instances. Analyzing the problem in Planted solution models and Semirandom models is one such systematic approach along these lines.
In this thesis, we study planted solution models and semirandom models for various graph problems. Given a graph G with n vertices, we consider the task of finding the largest induced subgraph of G with a particular structure. We start by studying the problem where the particular structure is a planar graph. Next, we look at the Odd Cycle Transversal problem or equivalently the problem of finding the largest induced bipartite subgraph. Finally, we study the problem of finding the largest independent set in runiform hypergraphs. All these problems are NPhard and have abysmal worstcase approximation guarantees.
An instance of a planted solution model is constructed by starting with a set of vertices V, and choosing a set S ⊆ V of k vertices, and adding a particular structure to it. Edges between pairs of vertices in S x (V S) and (V S) x (V S) are added independently with probability p. The algorithmic task then is to recover this planted structure. As a special case for all these problems, when the planted structure is an empty graph, the problem reduces to recovering a planted independent set and we dont expect recovery algorithms for k =o(√n).
For the problem of finding the largest induced bipartite subgraph, we give an exact recovery algorithm that works for k = Ωp(n log n)^1/2. For the problem of finding the maximum independent set in runiform hypergraphs, we give an algorithm that works for Ωp(n^{r1/r0.5}). Our results also hold for a natural semirandom model of instances inspired by Feige and Kilian [FK01] model. Our algorithms are based on analyzing continuous relaxations of these problems. We employ techniques from Spectral Graph Theory, Convex Optimization (Linear Programs (LPs) and SemiDefinite Programs (SDPs) relaxations), and Lasserre/SumofSquares hierarchy strengthening of convex relaxations.
Microsoft teams link:
https://teams.microsoft.com/l/meetupjoin/19%3ameeting_OWJkMjBkMTEtZTQ0My00MTA3LWE1ZWYtNmM5NTM2MjY1YWI3%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97f6a741e3b2c5ad4193976476%22%2c%22Oid%22%3a%2220a2358f870a4a9baaedf1fbcc8c2f75%22%7d
 Series: M.Tech (Research) Colloquium ONLINE Title: Modeling and verification of databaseaccessing applications  Speaker: Mr. Geetam Chawla
M.Tech (Research) student
Dept. of CSA  Faculty Advisor: Prof. K V Raghavan
 Date and Time: Monday, July 19, 2021, 12:00 PM
 Venue: Microsoft Teams  ONLINE
Abstract Databases are central to the functioning of most ITenabled processes and services. In many domains, databases are accessed and updated via applications written in generalpurpose languages, as such applications need to contain the business logic and workflows that are key to the organization. Therefore, automated tools are required not only for creation and testing of database schemas and queries, etc., but also for analysis, testing, and verification of databaseaccessing applications. In this work we describe a novel approach for modeling, analysis and verification of databaseaccessing applications. We target applications that use Object Relational Mapping (ORM), which is the common databaseaccess paradigm in most ModelView Controller (MVC) based application development frameworks. In contrast with other approaches that try to directly analyze and prove properties of complex database accessing ORMbased code, our approach infers a relational algebra specification of each controller in the application. This specification can then be fed into any offtheshelf relational algebra solver to check properties (or assertions) given by a developer.
We have implemented this approach as a tool that works for "Spring" based MVC applications. The tool was evaluated on a set of 58 specifications. The tool found 35 of these to be satisfied; of the rest, upon manual analysis, we found that two were genuinely violated, while the remaining 21 "unsatisfied" warnings were actually false positives. This preliminary evaluation reveals that the approach is scalable and quite precise.
Microsoft teams link:
https://teams.microsoft.com/l/meetupjoin/19%3ameeting_NGViZTA2NDQtZjFlNi00Y2YyLTkwMGYtZmJkYTM3MjQ0N2E0%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97f6a741e3b2c5ad4193976476%22%2c%22Oid%22%3a%22cd42250e1d664966a4316a8d7d5235ba%22%7d
 Series: Theory Seminar Title: Average Sensitivity of Graph Algorithms  Speaker: Prof. Yuichi Yoshida
Associate Professor
National Institute of Informatics
Japan  Date and Time: Thursday, July 15, 2021, 11:00 AM
 Venue: Microsoft Teams  ONLINE
Abstract In modern applications of graph algorithms, where the graphs of interest are large and dynamic, it is unrealistic to assume that an input representation contains the full information of a graph being studied. Hence, it is desirable to use algorithms that, even when provided with only a subgraph that misses a few edges, output solutions that are close to the solutions output when the whole graph is available. We formalize this feature by introducing the notion of average sensitivity of graph algorithms, which is the average earth movers distance between the output distributions of an algorithm on a graph and its subgraph obtained by removing an edge, where the average is over the edges removed and the distance between two outputs is the Hamming distance.
In this work, we initiate a systematic study of average sensitivity. After deriving basic properties of average sensitivity such as composition, we provide efficient approximation algorithms with low average sensitivities for concrete graph problems, including the minimum spanning for est problem, the global minimum cut problem, the minimum st cut problem, and the maximum matching problem. One of the main ideas involved in designing our algorithms with low average sensitivity is the following fact; if the presence of a vertex or an edge in the solution output by an algorithm can be decided locally, then the algorithm has a low average sensitivity, allowing us to reuse the analyses of known sublineartime algorithms and local computation algorithms.
Microsoft teams link:
https://teams.microsoft.com/l/meetupjoin/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97f6a741e3b2c5ad4193976476%22%2c%22Oid%22%3a%227c84465ec38b4d7a9a9dff0dfa3638b3%22%7d
Host Faculty: Dr. Anand Louis
 Series: M.Tech (Research)Thesis Defence ONLINE Title: Scaling Blockchains Using Coding Theory and Verifiable Computing  Speaker: Mr. Nilesh Rathi
M.Tech (Research) student
Dept. of CSA  Faculty Advisor: Prof. K Gopinath
 Date and Time: Tuesday, July 13, 2021, 4:00 PM
 Venue: Microsoft Teams  ONLINE
Abstract The issue of scalability has been restricting blockchains from their widespread adoption. The current transaction rate of bitcoin is around seven transactions/second while the blockchain size has crossed the 300 GB mark. Although many different approaches have been proposed to scale blockchains, e.g., sharding, lightning network, etc., we focus our analysis on methods utilizing ideas from coding theory and verifiable computing. We first consider SeF, a blockchain archiving architecture utilizing LT codes to reduce storage constraints per node up to 1000x. SeF enables full nodes to store only a small number of encoded blocks or droplets instead of an entire blockchain. Although efficient in the average case, the architecture sometimes requires large bandwidth (many droplets) to reconstruct blockchain. While other rateless coding strategies utilizing two encoding levels are proven better than LT codes, we investigate their suitability in the proposed architecture. We propose and simulate three techniques about how to incorporate these coding strategies. The results show that precodebased rateless coding schemes provide similar storage savings with reduced bandwidth variance for recovery.
The other work we examine is PolyShard, which introduces the notion of codedsharding. Coded sharding exports block verification of subledger to the whole network instead of nodes handling that subledger, making sharding resilient even to an adaptive adversary, i.e., adversary having the power to corrupt nodes after their assignment to shards. However innovative, PolyShard requires decoding of ReedSolomon codes over large fields for block verification in realworld settings, making it computationally intensive and less practical. We propose replacing the decoding phase with verifiable computing, which reduces the bottleneck and makes the system practical for light verification functions.
Microsoft teams link:
https://teams.microsoft.com/l/channel/19%3axqMz7NRjdoelpofbxvfoqtfenhrRts9h0hLf8CSRIsk1%40thread.tacv2/General?groupId=68ce4fbddc004f8698fd48239230b6e3&tenantId=6f15cd97f6a741e3b2c5ad4193976476
 Series: M.Tech (Research) Colloquium ONLINE Title: Automatic Code Generation for GPU Tensor Cores using MLIR  Speaker: Mr. Navdeep Kumar Katel
M.Tech (Research) student
Dept. of CSA  Faculty Advisor: Prof. Uday Kumar Reddy .B
 Date and Time: Monday, July 12, 2021, 4:00 PM
 Venue: Microsoft Teams  ONLINE
Abstract The state of the art in highperformance deep learning is primarily driven by
highly tuned libraries. These libraries are often handoptimized and tuned by
expert programmers using lowlevel abstractions with significant
effort. A lot of the effort may have to be repeated for similar hardware and future ones. Such a process is thus not modular or reusable to the same extent as compiler infrastructure like LLVM are. Manual optimization does not typically use a standard intermediate representation or transformations and passes on such intermediate representations, although the optimizations performed can be encoded as a sequence of transformation steps and customized passes. Hand tuning may also miss exploration of space or design points only reachable by automatic code generation. We believe that until the recent introduction of MLIR (Multilevel intermediate representation), intermediate representation infrastructure had not reached a stage to tackle the problem of automatic generation of libraries in a scalable and convenient manner. In particular, it was hard to represent and transform compute abstractions at high, middle and low levels using a single IR.
MLIR is an intermediate representation that aims to build reusable, extensible compiler infrastructure and reduce the cost of building domainspecific compilers and code generators. In this work, we tackle the problem of generating code targeting tensor cores on GPUs using the MLIR compiler infrastructure. Tensor cores are programmable matrixmultiplyandaccumulate units performing matrixmultiply accumulate operations on small matrices. First, we introduce lowlevel operations which are necessary to compute on tensor cores and which were absent from MLIR. Then, building on these operations, we put together a lowering pipeline that is able to fully automatically generate code for matrixmatrix multiplication (matmul) on tensor cores. Matmul is an excellent candidate to demonstrate our work as: (1) it is at the heart of many deeplearning models
such as BERT, and 2) it is an excellent candidate to demonstrate various
individual optimizations. We evaluate our pipeline on two different devices: 1) an NVIDIA Turingbased RTX 2080 Ti, and 2) an NVIDIA Amperebased Geforce RTX 3090 and with two different precisions for accumulation, namely 32bit and 16bit wide floats. On a set of problem sizes that we evaluate, we achieve performance that is within 93% to 117% for F32 accumulate and between 79% and 158% with F16 accumulate of CuBLAS on NVIDIA Turing and Ampere respectively. We take this approach further by demonstrating the fusion of MatMul with operations that commonly follow it in deeplearning models.
Microsoft teams link:
https://teams.microsoft.com/l/meetupjoin/19%3ameeting_ZmIwODY3ODYtNmFlMC00MThmLTgwNTQtNzBjNWYyMDYwM2Jj%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97f6a741e3b2c5ad4193976476%22%2c%22Oid%22%3a%22171d9abccf43429a9680c05b9523fa9a%22%7d
 Series: M.Tech (Research)Thesis Defence ONLINE Title: A Novel Neural Network Architecture for Sentimentoriented AspectOpinion Pair Extraction  Speaker: Mr. Kapil Jayesh Pathak
M.Tech (Research) student
Dept. of CSA  Faculty Advisor: Prof. Shirish K Shevade
 Date and Time: Thursday, July 08, 2021, 10:00 AM
 Venue: Microsoft Teams  ONLINE
Abstract Over the years, finegrained opinion mining in online reviews has received great attention from the NLP research community. It involves different tasks such as Aspect Term Extraction (ATE), Opinion Term Extraction (OTE), etc. Opinion Term Extraction (OTE) aims to detect different opinion expressions which convey certain attitude in the review while Aspect Term Extraction (ATE) aims to identify the entities or proposition from the review at which the attitude is directed. Recently, the NLP research community got attracted to aspectopinion relation modeling. Such modeling would be helpful for aspectopinion pair extraction that would be used for downstream tasks such as aspectbased sentiment analysis, opinion summarization, etc.
As online reviews may contain different sentiment polarities for different aspects of the products, it would help companies find all aspects for which the customers gave positive or negative feedback. In this thesis, we propose a new opinion mining task called Sentimentoriented AspectOpinion Pair Extraction (SAOPE), which aims to find all aspectopinion pairs from customer reviews given that these pairs convey the specified sentiment polarity.
We present a novel neural network architecture for the SAOPE task. In the proposed approach, aspectopinion coextraction is performed first and then the aspectopinion pairs are generated through relation modeling. The aspect and the corresponding opinion words are closely related in the dependency trees. Hence, we explore graph neural networks to utilize syntactic information generated from the dependency tree of the reviews to model the relationship between the aspects and corresponding opinion words. We design a modified graph attention network (GAT) called Graph Coattention Network (GCAT) and compare its performance with Graph Convolution Network (GCN) and Graph Attention Network (GAT) for the aspectopinion coextraction and the relation detection. For the SAOPE task, we evaluate our model on SemEval Challenge datasets and show that GCAT and GAT perform better than the baseline model with GCN for aspectopinion coextraction. We demonstrate that the proposed Graph Coattention Network (GCAT) performs better than other graph neural networks for aspectopinion relation detection on the publicly available benchmark datasets.
Microsoft teams link:
https://teams.microsoft.com/l/meetupjoin/19%3ameeting_NDZjMTE0ZTYtOWI5YS00MGZiLThiMjktNzM4NWZiMTNlNGEz%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97f6a741e3b2c5ad4193976476%22%2c%22Oid%22%3a%229c3e2bfe1b0f4d7ba589832878069dc6%22%7d
 Series: M.Tech (Research) Colloquium ONLINE Title: A Framework for Privacy Compliant Delivery Drones  Speaker: Mr. Rakesh Rajan Beck
M.Tech (Research) student
Dept. of CSA  Faculty Advisor: Prof. Vinod Ganapathy
 Date and Time: Tuesday, July 06, 2021, 10:00 AM
 Venue: Microsoft Teams  ONLINE
Abstract We present Privaros, a framework to enforce privacy policies on drones. Privaros is designed for commercial delivery drones, such as the ones that will likely be used by Amazon Prime Air. Such drones visit various host airspaces, each of which may have different privacy requirements. Privaros uses mandatory access control to enforce the policies of these hosts on guest delivery drones. Privaros is tailored for ROS, a middleware popular in many drone platforms. This paper presents the design and implementation of Privaross policyenforcement mechanisms, describes how policies are specified, and shows that policy specification can be integrated with Indias Digital Sky portal. Our evaluation shows that a drone running Privaros can robustly enforce various privacy policies specified by hosts, and that its core mechanisms only marginally increase communication latency and power consumption.
Microsoft Teams link:
https://teams.microsoft.com/l/meetupjoin/19%3ameeting_YzIwYTk3MzYtOTZjMS00Zjg4LWJjMzItN2E5MmQ4ZGQwZDJm%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97f6a741e3b2c5ad4193976476%22%2c%22Oid%22%3a%220432f3a0d225405cb0f4ff1ffaf4f1fd%22%7d
 Series: Ph.D. (Engg.) Colloquium ONLINE Title: Reinforcement Learning Algorithms for OffPolicy, MultiAgent Learning and their Applications to Smart Grids.  Speaker: Mr. D Raghu Ram Bharadwaj
Ph.D (Engg.) student
Dept. of CSA  Faculty Advisor: Prof. Shalabh Bhatnagar
 Date and Time: Friday, July 02, 2021, 3:00 PM
 Venue: Microsoft Teams  ONLINE
Abstract Reinforcement Learning (RL) algorithms are a popular class of algorithms for training an agent to learn desired behavior through interaction with an environment whose dynamics are unknown to the agent. RL algorithms combined with neural network architectures have enjoyed much success in various disciplines like games, economics, medicine, energy management, and supply chain management. In our thesis, we study interesting extensions of singleagent RL settings, like offpolicy and multiagent settings. We discuss the motivations and importance of these settings and propose convergent algorithms to solve these problems. Finally, we consider one of the important applications of RL, namely smart grids. The goal of the smart grid is to develop an intelligent power grid model that intelligently manages its energy resources. In our thesis, we develop RL algorithms for efficient smart grid design.
Learning the value function of a given policy (target policy) from the data samples obtained from a different policy (behavior policy) is an important problem in Reinforcement Learning (RL). This problem is studied under the setting of offpolicy prediction. Temporal Difference (TD) learning algorithms are a popular class of algorithms for solving prediction problems. TD algorithms with linear function approximation are convergent when the data samples are generated from the target policy (known as onpolicy prediction) itself. However, it has been well established in the literature that offpolicy TD algorithms under linear function approximation may diverge. In the first part of the thesis, we propose a convergent online offpolicy TD algorithm under linear function approximation. The main idea is to penalize updates of the algorithm to ensure convergence of the iterates. We provide a convergence analysis of our algorithm. Through numerical evaluations, we further demonstrate the effectiveness of our proposed scheme.
Subsequently, we consider the ``offpolicy`` control setup in RL, where an agents objective is to compute an optimal policy based on the data obtained from a behavior policy. As the optimal policy can be very different from the behavior policy, learning optimal behavior is very hard in the ``offpolicy`` setting compared to the ``onpolicy`` setting wherein the data is collected from the new policy updates. In this work, we propose the first offpolicy natural actorcritic algorithm that utilizes stateaction distribution correction for handling the offpolicy behavior and the natural policy gradient for sample efficiency. Unlike the existing natural gradientbased actorcritic algorithms that use only fixed features for policy and value function approximation, the proposed natural actorcritic algorithm can utilize a deep neural networks power to approximate both policy and value function. We illustrate the benefit of the proposed offpolicy natural gradient algorithm by comparing it with the Euclidean gradient actorcritic algorithm on benchmark RL tasks.
In the third part of the thesis, we consider the problem of twoplayer zerosum games. In this setting, there are two agents, both of whom aim to optimize their payoffs. Both the agents observe the same state of the game, and the agents objective is to compute a strategy profile that maximizes their payoffs. However, the payoff of the second agent is the negative of the payoff obtained by the first agent. Therefore, the objective of the second agent is to minimize the total payoff obtained by the first agent.
This problem is formulated as a minmax Markov game in the literature. In this work, we compute the solution of the twoplayer zerosum game utilizing the technique of successive relaxation. Successive relaxation has been successfully applied in the literature to compute a faster value iteration algorithm in the context of Markov Decision Processes. We extend the concept of successive relaxation to the twoplayer zerosum games. We then derive a generalized minimax Qlearning algorithm that computes the optimal policy when the model information is unknown. Finally, we prove the convergence of the proposed generalized minimax Qlearning algorithm utilizing stochastic approximation techniques. Through experiments, we demonstrate the effectiveness of our proposed algorithm.
Next, we consider a cooperative stochastic games framework where multiple agents work towards learning optimal joint actions in an unknown environment to achieve a common goal. In many realworld applications, however, constraints are often imposed on the actions that the agents can jointly take. In such scenarios, the agents aim to learn joint actions to achieve a common goal (minimizing a specified cost function) while meeting the given constraints (specified via certain penalty functions). Our work considers the relaxation of the constrained optimization problem by constructing the Lagrangian of the cost and penalty functions. We propose a nested actorcritic solution approach to solve this relaxed problem. In this approach, an actorcritic scheme is employed to improve the policy for a given Lagrange parameter update on a faster timescale as in the classical actorcritic architecture. Using this faster timescale policy update, a meta actorcritic scheme is employed to improve the Lagrange parameters on the slower timescale. Utilizing the proposed nested actorcritic scheme, we develop three Nested ActorCritic (NAC) algorithms.
In recent times, actorcritic algorithms with attention mechanisms have been successfully applied to obtain optimal actions for RL agents in multiagent environments. In the fifth part of our thesis, we extend this algorithm to the constrained multiagent RL setting considered above. The idea here is that optimizing the common goal and satisfying the constraints may require different modes of attention. Thus, by incorporating different attention modes, the agents can select useful information required for optimizing the objective and satisfying the constraints separately, thereby yielding better actions. Through experiments on benchmark multiagent environments, we show the effectiveness of our proposed algorithm.
In the last part of our thesis, we study the applications of RL algorithms to Smart Grids. We consider two important problems  on the supplyside and demandside, respectively and study both in a unified framework. On the supply side, we study the problem of energy trading among microgrids to maximize profit obtained from selling power while at the same time satisfying the customer demand. On the demand side, we consider optimally scheduling the timeadjustable demand  i.e., of loads with flexible time windows in which they can be scheduled. While previous works have treated these two problems in isolation, we combine these problems and provide a unified Markov decision process (MDP) framework for these problems.
Microsoft Teams Link:
https://teams.microsoft.com/l/meetupjoin/19%3ameeting_ZDNjYTdhOWItYTMyMC00MzEyLWFhZWItYmQ3MzMwOTFkZmQ1%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97f6a741e3b2c5ad4193976476%22%2c%22Oid%22%3a%22d931ce1d4f8248c0805396272991d288%22%7d
 Series: M.Tech (Research)Thesis Defence ONLINE Title: Towards Efficient PrivacyPreserving TwoParty kMeans Clustering Protocol  Speaker: Ms. Chim Sonali Eknath
M.Tech. (Research) student
Dept. of CSA  Faculty Advisor: Prof. Sanjit Chatterjee
 Date and Time: Wednesday, June 30, 2021, 11:00 AM
 Venue: Microsoft Teams  ONLINE
Abstract Twoparty data mining is a winwin game if played with a guarantee of data privacy from each other. This guarantee is provided by the use of cryptographic techniques in designing the twoparty protocol. The need to obtain collaborative data mining results is growing and so is the need for privacypreserving data mining protocols. Clustering is one of the data mining techniques and one of the popular clustering algorithms is kmeans clustering. We studied the recent work for the secure twoparty kmeans clustering by Bunn and Ostrovosky and found that the protocol is inefficient for practical purposes. The protocol requires communication rounds which are linear in security parameter for the center initialization step and are quadratic in security parameter for an iterative Lloyds step of the kmeans clustering algorithm. The challenge in the secure twoparty kmeans clustering is the exorbitant communication cost occurring due to the high number of interactions between the parties for performing computations on the data. Our work attempts to resolve this problem of inefficiency in kmeans clustering protocol in a twoparty setting by proposing some modifications. We have come up with two comparison protocols that are required in the kmeans clustering protocol. One of the protocols is to find a minimum of two shared numbers which runs in constant communication rounds. Using this protocol as a building block, another protocol is designed to find a minimum of n shared numbers, which runs in O(n) communication rounds. We have also improved a protocol that selects a random value from a domain oblivious to both parties. Apart from this, the idea to avoid the twoparty integer division altogether is incorporated in the kmeans clustering protocol. With these improvements, we propose a twoparty kmeans clustering protocol for which the initialization step requires communication rounds linear in security parameter and Lloyds step requires communications rounds that are independent of the security parameter. The protocol provides a security guarantee in the semihonest model except for some minor information leakage. We argue that this leakage in the protocol can be tolerated considering the substantial gain in the communication cost We have verified the gain in performance of the modified protocol by implementing both the kmeans clustering protocols and running their instances in the same setup
Microsoft Teams link: ONLINE
https://teams.microsoft.com/l/meetupjoin/19%3ameeting_MWFjODE3MDQtNGVlYy00MmU2LTkzNzEtY2ZmNTUxYTdjMTE0%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97f6a741e3b2c5ad4193976476%22%2c%22Oid%22%3a%229be1cf83a6ec4e58a5cab440a35ae199%22%7d
 Series: M.Tech (Research) Colloquium ONLINE Title: Novel Reinforcement Learning Algorithms and Applications to Hybrid Control Design Problems  Speaker: Mr. Meet Pradhuman Gandhi
M.Tech (Research) student
Dept. of CSA  Faculty Advisor: Prof. Shalabh Bhatnagar
 Date and Time: Thursday, June 24, 2021, 3:00 PM
 Venue: Microsoft Teams  ONLINE
Abstract The thesis is a compilation of two independent works.
In the first work, we develop novel weight assignment procedure, which helps us develop several schedule based algorithms.
Learning the value function of a given policy from the data samples is an important problem in Reinforcement Learning.
TD($lambda$) is a popular class of algorithms to solve this problem.
However, the weight assigned to different $n$step returns decreases exponentially with increasing $n$ in TD($lambda$).
Here, we present a $lambda$schedule procedure that allows flexibility in weight assignment to the different $n$step returns.
Based on this procedure, we propose an onpolicy algorithm, TD($lambda$)schedule, and an offpolicy algorithm, TDC($lambda$)schedule, respectively.
We provide proofs of almost sure convergence for both algorithms under a general Markov noise framework as well as present the results of experiments where these algorithms are seen to show improved performance.
In the second work, we design hybrid control policies for hybrid systems whose mathematical models are unknown.
Our contributions are threefold.
First, we propose a framework for modelling the hybrid control design problem as a single Markov Decision Process (MDP).
This result facilitates the application of offtheshelf algorithms from Reinforcement Learning (RL) literature towards designing optimal control policies.
Second, we model a set of benchmark examples of hybrid control design problem in the proposed MDP framework.
Third, we adapt the recently proposed Proximal Policy Optimisation (PPO) algorithm for the hybrid action space and apply it to the above set of problems.
It is observed that in each case the algorithm converges and finds the optimal policy.
Microsoft teams link:
https://teams.microsoft.com/l/meetupjoin/19%3ameeting_NGQ2OTk0MWQtZGI5OC00OWQ1LWJmZDUtOTM4MzVhZDllNzVm%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97f6a741e3b2c5ad4193976476%22%2c%22Oid%22%3a%229d60e18526004b28b2d52d47a54928f3%22%7d
 Series: Department Seminar Title: Specification Synthesis with Constrained Horn Clauses  Speaker: Ms.Sumanth Prabhu
Ph.D student
Department of Computer Science and Automation, IISc, and TCS Research  Faculty Advisor: Prof. Deepak DSouza
 Date and Time: Monday, June 21, 2021, 4:00 PM
 Venue: Google Meet joining info: Video call link: https://meet.google.com/feeusjdoxj
Abstract The problem of synthesizing specifications of undefined
procedures has a broad range of applications, but the usefulness of
the generated specifications depends on their quality. In this paper,
we propose a technique for finding maximal and nonvacuous
specifications. Maximality allows for more choices for implementations
of undefined procedures, and nonvacuity ensures that safety
assertions are reachable. To handle programs with complex control
flow, our technique discovers not only specifications but also
inductive invariants. Our iterative algorithm lazily generalizes
nonvacuous specifications in a counterexampleguided loop. The key
component of our technique is an effective nonvacuous specification
synthesis algorithm. We have implemented the approach in a tool called
HornSpec, taking as input systems of constrained Horn clauses. We have
experimentally demonstrated the tools effectiveness, efficiency, and
the quality of generated specifications, on a range of benchmarks.
This is joint work with Grigory Fedyukovich, Kumar Madhukar, and
Deepak DSouza. The paper will be presented at the upcoming PLDI 2021
conference.
Google Meet joining info:
Video call link: https://meet.google.com/feeusjdoxj
Host Faculty: Prof. Deepak DSouza

