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

UPCOMING SEMINARS

Series: Theory Seminar
Title: Superpolynomial lower bounds against low-depth 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 - ON-LINE

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 (product-depth 1) circuits. Before our work, the best known lower bound for product-depth 1 circuit was (slightly less than) cubic. No lower bounds were known for general product-depth 2 circuits.

In this work, we show the first superpolynomial lower bound for low-product-depth 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 product-depth 1 circuits.

This talk is based on joint work with Srikanth Srinivasan and Sébastien Tavenas.

Microsoft Teams Link:

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

Host Faculty: Dr. Anand Louis

Video Archive Go Top

 

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

Abstract
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, government-controlled 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 publicly-visible 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 (real-time voice) are mostly ignored. As a part of our research we have extensively explored the feasibility of transporting real-time 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 end-points 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 top-tier 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 as-is for transporting traffic. The scheme provides unobservability and good QoS, due to its inherent properties, such as low-latency 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 top-1k 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 dial-up 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 end-to-end confidentiality. At low data rates (<=64bps), the errors are under 5% and suitable for supporting delay-tolerant 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 anti-censorship, counter-surveillance, 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/meetup-join/19%3ameeting_NjA3ZmM1ZDYtZTdjYi00NTZjLTgzNDUtZjRhNjJmZmNiMDdl%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%220432f3a0-d225-405c-b0f4-ff1ffaf4f1fd%22%7d

Host Faculty: Prof. Vinod Ganapathy

Video Archive Go Top

 

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 long-standing 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, well-studied in the context of the total coloring conjecture, another well-known and long-standing 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 total-chromatic 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 long-pending addition to the literature.

Microsoft teams link:

https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGMzMDhiNTItM2IwNS00MDZhLWI4Y2ItMThhMjkwN2M4YjNi%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%22ed2e5ccd-b870-455c-862e-26e9ab1908be%22%7d

Video Archive Go Top

 

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

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 bi-criteria 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 state-of-the-art. 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 bi-criteria 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/meetup-join/19%3ameeting_YjZkYWU2MjEtMGYwZS00YmZlLWI1MGMtMzA3YjhiMGUyZjgy%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%220c3c2a63-37e3-4ad6-b0bd-ddfa9589e2d5%22%7d

Video Archive Go Top

 

Series: M.Tech (Research)Thesis Defence -ONLINE
Title: Locally Reconstructable Non-Malleable 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 - ON-LINE

Abstract
Non-malleable 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 t-1 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, non-malleable 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 non-malleable secret sharing scheme and compiles it into a locally reconstructable non-malleable 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/meetup-join/19%3ameeting_MzNjOGVkNzgtNTM5Zi00OWRlLWJkYWItYWNjMjI4ZGI1NzJi%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%225f3273b8-8838-46b7-b675-b1e9eab4d8ef%22%7d

Video Archive Go Top

 

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

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

We first study an extension of 2D GBP called the generalized multidimensional bin packing problem (GVBP). Here each item i additionally has d nonnegative weights v_1(i), v_2(i), …, v_d(i) associated with it. Our goal is to compute an axis-parallel non-overlapping packing of the items into bins so that for all j ∈ [d], the sum of the jth weight of items in each bin is at most 1. Despite being well studied in practice, surprisingly, approximation algorithms for this problem have rarely been explored. We first obtain two simple algorithms for GVBP having asymptotic approximation ratios (AARs) 6(d+1) and 3(1 + ln(d+1) + ε). We then extend the Round-and-Approx (R&A) framework [Bansal-Khan, 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 d-dimensional geometric bin packing problem (dD GBP). Caprara (MOR 2008) gave a harmonic-based algorithm for dD GBP having an AAR of 1.69104^(d-1). However, their algorithm doesnt allow items to be rotated. This is in contrast to some common applications of 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 harmonic-based algorithm, called fullh_k, having an AAR of 1.69104^d. We next give a more sophisticated harmonic-based algorithm, which we call hgap_k, having an AAR of (1+ε)1.69104^(d-1). This gives an AAR of roughly 2.860 + ε for 3D GBP with rotations, which improves upon the best-known AAR of 4.5. In addition, we study the multiple-choice bin packing problem that generalizes the rotational case. Here we are given n sets of d-dimensional cuboidal items and we have to choose exactly one item from each set and then pack the chosen items. Our algorithms fullh_k and hgap_k also work for the multiple-choice bin packing problem. We also give fast and simple approximation algorithms for the multiple-choice versions of dD strip packing and dD geometric knapsack. These algorithms have AARs 1.69104^(d-1) and (1-ε)3^(-d), respectively.

A rectangle is said to be δ-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 guillotine-separable iff we can use a sequence of end-to-end cuts to separate the items from each other. The asymptotic price of guillotinability (APoG) is the maximum value of opt_G(I)/opt(I) for large opt(I), where opt(I) and opt_G(I) are the minimum number of bins and the minimum number of guillotine-separable bins, respectively, needed to pack I. Computing lower and upper bounds on APoG is an important problem, since proving an upper bound smaller than 1.5 would beat the state-of-the-art algorithm for 2D GBP. The best-known 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/3-asymptotic-approximate algorithm for 2D GBP for this case, and our algorithms output is guillotine-separable. This proves an upper-bound of roughly 4/3 on APoG for δ-skewed rectangles. We also prove a matching lower-bound of 4/3. This shows that hard examples for upper-bounding APoG include items that are large in both dimensions.

Microsoft Teams link:

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

Video Archive Go Top

 

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

Host Faculty: Dr. Anand Louis

Video Archive Go Top

 

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 use-cases, 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 ab-initio 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 High-Fidelity Hydra (HF-Hydra), 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, projection-based operators such as GROUP BY and DISTINCT. To sidestep the challenge of workload scalability, HF-Hydra 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 sub-workloads is governed by heuristics that aim to balance robustness with LP solvability.

For generating richer database summaries, HF-Hydra 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, HF-Hydra directs it to the database summary that is expected to provide the highest volumetric similarity.

We have experimentally evaluated HF-Hydra on a customized set of queries based on the TPC-DS decision-support benchmark framework. We first evaluated the specialized case where each training query has its own summary, and here HF-Hydra 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 HF-Hydra was compared with that from Hydra. We observed that HF-Hydra 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 one-summary-per-query 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/meetup-join/19%3azGm-zJOhD_rL-kNaZfQlJPHgDuCqDsmM8agcKyHnG2E1%40thread.tacv2/1626698346505?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%2220a4bde2-27ad-4a57-9b14-bb2f66dfd6d0%22%7d

Video Archive Go Top

 

Series: M.Tech (Research) Colloquium- ON-LINE
Title: Quantum-Safe Identity-Based 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 - ON-LINE

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 post-quantum society, especially in the area of digital signature. This thesis uses the setting of multivariate cryptography to propose an identity-based signature scheme. Our proposal is based on the Rainbow signature scheme and the multivariate 3-pass identification scheme, both of which have been subjected to scrutiny by cryptographers all over the world and have emerged as strong post-quantum 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 Fiat-Shamir transform to the 3-pass 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 x86-64 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 post-quantum multivariate signature candidate in the identity-based setting.

Microsoft teams link:

https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZDVhMmEzZmYtY2Q2MS00ZWVhLWJiYjktZTY3ZTVhMGNiNjli%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227b997a2d-ed18-48f7-99c1-eaec40b37793%22%7d

Video Archive Go Top

 

Series: M.Tech (Research) Colloquium- ON-LINE
Title: Recovery Algorithms for planted structures in Semi-random 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 - ON-LINE

Abstract
For many NP-hard problems, the analysis of best-known approximation algorithms yields “poor” worst-case guarantees. However, using various heuristics, the problems can be solved (to some extent) in real-life instances. This success can be attributed to the atypicality of worst-case instances in real life, and therefore motivates studying the problem in “easier” instances. Analyzing the problem in Planted solution models and Semi-random models is one such systematic approach along these lines.

In this thesis, we study planted solution models and semi-random 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 r-uniform hypergraphs. All these problems are NP-hard and have abysmal worst-case 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 r-uniform hypergraphs, we give an algorithm that works for Ωp(n^{r-1/r-0.5}). Our results also hold for a natural semi-random 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 Semi-Definite Programs (SDPs) relaxations), and Lasserre/Sum-of-Squares hierarchy strengthening of convex relaxations.

Microsoft teams link:

https://teams.microsoft.com/l/meetup-join/19%3ameeting_OWJkMjBkMTEtZTQ0My00MTA3LWE1ZWYtNmM5NTM2MjY1YWI3%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%2220a2358f-870a-4a9b-aaed-f1fbcc8c2f75%22%7d

Video Archive Go Top

 

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

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

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

Microsoft teams link:

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

Video Archive Go Top

 

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

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 s-t 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 sublinear-time algorithms and local computation algorithms.

Microsoft teams link:

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

Host Faculty: Dr. Anand Louis

Video Archive Go Top

 

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

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

Microsoft teams link:

https://teams.microsoft.com/l/channel/19%3axqMz7NRjdoelpofbxvfoqtfenhrRts9h0hLf8CSRIsk1%40thread.tacv2/General?groupId=68ce4fbd-dc00-4f86-98fd-48239230b6e3&tenantId=6f15cd97-f6a7-41e3-b2c5-ad4193976476

Video Archive Go Top

 

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

Abstract
The state of the art in high-performance deep learning is primarily driven by highly tuned libraries. These libraries are often hand-optimized and tuned by expert programmers using low-level 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 (Multi-level 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 domain-specific 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 matrix-multiply-and-accumulate units performing matrix-multiply accumulate operations on small matrices. First, we introduce low-level 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 matrix-matrix multiplication (matmul) on tensor cores. Matmul is an excellent candidate to demonstrate our work as: (1) it is at the heart of many deep-learning 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 Turing-based RTX 2080 Ti, and 2) an NVIDIA Ampere-based Geforce RTX 3090 and with two different precisions for accumulation, namely 32-bit and 16-bit 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 deep-learning models.

Microsoft teams link:

https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZmIwODY3ODYtNmFlMC00MThmLTgwNTQtNzBjNWYyMDYwM2Jj%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%22171d9abc-cf43-429a-9680-c05b9523fa9a%22%7d

Video Archive Go Top

 

Series: M.Tech (Research)Thesis Defence -ONLINE
Title: A Novel Neural Network Architecture for Sentiment-oriented Aspect-Opinion Pair Extraction

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

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

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

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

Microsoft teams link:

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

Video Archive Go Top

 

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

Video Archive Go Top

 

Series: Ph.D. (Engg.) Colloquium- ONLINE
Title: Reinforcement Learning Algorithms for Off-Policy, Multi-Agent 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 - ON-LINE

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 single-agent RL settings, like off-policy and multi-agent 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 off-policy 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 on-policy prediction) itself. However, it has been well established in the literature that off-policy TD algorithms under linear function approximation may diverge. In the first part of the thesis, we propose a convergent online off-policy 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 ``off-policy`` 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 ``off-policy`` setting compared to the ``on-policy`` setting wherein the data is collected from the new policy updates. In this work, we propose the first off-policy natural actor-critic algorithm that utilizes state-action distribution correction for handling the off-policy behavior and the natural policy gradient for sample efficiency. Unlike the existing natural gradient-based actor-critic algorithms that use only fixed features for policy and value function approximation, the proposed natural actor-critic algorithm can utilize a deep neural networks power to approximate both policy and value function. We illustrate the benefit of the proposed off-policy natural gradient algorithm by comparing it with the Euclidean gradient actor-critic algorithm on benchmark RL tasks.

In the third part of the thesis, we consider the problem of two-player zero-sum 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 min-max Markov game in the literature. In this work, we compute the solution of the two-player zero-sum 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 two-player zero-sum games. We then derive a generalized minimax Q-learning algorithm that computes the optimal policy when the model information is unknown. Finally, we prove the convergence of the proposed generalized minimax Q-learning 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 real-world 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 actor-critic solution approach to solve this relaxed problem. In this approach, an actor-critic scheme is employed to improve the policy for a given Lagrange parameter update on a faster timescale as in the classical actor-critic architecture. Using this faster timescale policy update, a meta actor-critic scheme is employed to improve the Lagrange parameters on the slower timescale. Utilizing the proposed nested actor-critic scheme, we develop three Nested Actor-Critic (N-AC) algorithms.

In recent times, actor-critic algorithms with attention mechanisms have been successfully applied to obtain optimal actions for RL agents in multi-agent environments. In the fifth part of our thesis, we extend this algorithm to the constrained multi-agent 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 multi-agent 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 supply-side and demand-side, 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 time-adjustable 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/meetup-join/19%3ameeting_ZDNjYTdhOWItYTMyMC00MzEyLWFhZWItYmQ3MzMwOTFkZmQ1%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%22d931ce1d-4f82-48c0-8053-96272991d288%22%7d

Video Archive Go Top

 

Series: M.Tech (Research)Thesis Defence -ONLINE
Title: Towards Efficient Privacy-Preserving Two-Party k-Means 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
Two-party data mining is a win-win 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 two-party protocol. The need to obtain collaborative data mining results is growing and so is the need for privacy-preserving data mining protocols. Clustering is one of the data mining techniques and one of the popular clustering algorithms is k-means clustering. We studied the recent work for the secure two-party k-means 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 k-means clustering algorithm. The challenge in the secure two-party k-means 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 k-means clustering protocol in a two-party setting by proposing some modifications. We have come up with two comparison protocols that are required in the k-means 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 two-party integer division altogether is incorporated in the k-means clustering protocol. With these improvements, we propose a two-party k-means 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 semi-honest 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 k-means clustering protocols and running their instances in the same set-up

Microsoft Teams link: ONLINE

https://teams.microsoft.com/l/meetup-join/19%3ameeting_MWFjODE3MDQtNGVlYy00MmU2LTkzNzEtY2ZmNTUxYTdjMTE0%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%229be1cf83-a6ec-4e58-a5ca-b440a35ae199%22%7d

Video Archive Go Top

 

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

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 on-policy algorithm, TD($lambda$)-schedule, and an off-policy 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 off-the-shelf 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/meetup-join/19%3ameeting_NGQ2OTk0MWQtZGI5OC00OWQ1LWJmZDUtOTM4MzVhZDllNzVm%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%229d60e185-2600-4b28-b2d5-2d47a54928f3%22%7d

Video Archive Go Top

 

Series: 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/fee-usjd-oxj

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 non-vacuous specifications. Maximality allows for more choices for implementations of undefined procedures, and non-vacuity 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 non-vacuous specifications in a counterexample-guided loop. The key component of our technique is an effective non-vacuous 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/fee-usjd-oxj

Host Faculty: Prof. Deepak DSouza

Video Archive Go Top

 

 

 

 

 

 

 

 

 

 

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