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: Department Seminar
Title: Unified Question Answering over RDF Knowledge Graphs and Natural Language Text

  • Speaker: Dr. Soumajit Pramanik, IIT Bhilai.
  • Date and Time: Monday, December 19, 2022, 11:00 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Question answering over knowledge graphs and other RDF data has been greatly advanced, with a number of good systems providing crisp answers for natural language questions or telegraphic queries. Some of these systems incorporate textual sources as additional evidence for the answering process, but cannot compute answers that are present in text alone. Conversely, systems from the IR and NLP communities have addressed QA over text, but such systems barely utilize semantic data and knowledge. In this work, we develop a QA system that can seamlessly operate over RDF datasets and text corpora, or both together, in a unified framework. Our method, called Uniqorn, builds a context graph on-the-fly, by retrieving question-relevant triples from the RDF data and/or snippets from a text corpus, using a fine-tuned BERT model. The resulting graph is typically rich but highly noisy. Uniqorn copes with this input by advanced graph algorithms for Group Steiner Trees, that identify the best answer candidates in the context graph. Experimental results on several benchmarks of complex questions with multiple entities and relations, show that Uniqorn produces results comparable to the state-of-the-art on KGs, text corpora, and heterogeneous sources. The graph-based methodology provides user-interpretable evidence for the complete answering process.

Speaker Bio:
Dr. Soumajit Pramanik is an Assistant Professor in the Department of Electrical Engineering and Computer Science (EECS) at Indian Institute of Technology Bhilai. Prior to joining IIT Bhilai, he was a Postdoctoral researcher at the Max Planck Institute for Informatics, Saarbrücken, Germany. Dr. Pramanik's research interest lies in the fields of Information Retrieval, Machine Learning, Social Computing and Complex Networks. His doctoral work was solely devoted to the progress of our understanding of multilayer networks and their applications. Dr. Pramanik identified four particularly important problems related to structural and functional properties of multilayer networks - (a) information diffusion, (b) community detection, (c) node movement and (d) entity recommendation and investigated each of them thoroughly. During his Postdoctoral research, he worked on complex question-answering over hybrid knowledge bases and textual corpora. He (along with his collaborators) has developed QUEST, a method that can answer complex questions directly from textual sources on-the-fly, by computing similarity joins over partial results from different documents. He is currently working on extending this work for answering factoid questions jointly over both knowledge graphs and text corpora. Moreover, he has also started exploring the areas of conversational and temporal question answering.

Host Faculty: R Govindarajan

Video Archive Go Top

 

Series: Department Seminar
Title: Anti-virus hardware: Applications in Embedded, Automotive and Power Systems security.

  • Speaker: Kanad Basu
                   Assistant Professor
                   ECSN 4.922
                   Department of Electrical and Computer Engineering,
                   University of Texas at Dallas
  • Date and Time: Friday, December 16, 2022, 3:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Anti-virus software (AVS) tools are used to detect Malware in a system. However, software-based AVS are vulnerable to attacks. A malicious entity can exploit these vulnerabilities to subvert the AVS. Recently, hardware components such as Hardware Performance Counters (HPC) have been used for Malware detection, in the form of Anti-virus Hardware (AVH). In this talk, we will discuss HPC-based AVHs for improving embedded security and privacy. Furthermore, we will discuss the application of HPCs in security cyber physical systems (CPS), namely automotive and microgrid systems. Subsequently, we will discuss their pitfalls. Finally, we will present PREEMPT, a zero overhead, high-accuracy and low-latency technique to detect Malware by re-purposing the embedded trace buffer (ETB), a debug hardware component available in most modern processors. The ETB is used for post-silicon validation and debug and allows us to control and monitor the internal activities of a chip, beyond what is provided by the Input/Output pins. PREEMPT combines these hardware-level observations with machine learning-based classifiers to preempt Malware before it can cause damage. We will conclude the talk with future research directions and challenges.

Speaker Bio:
Kanad Basu received his Ph.D. from the department of Computer and Information Science and Engineering, University of Florida. His thesis was focused on improving signal observability for post-silicon validation. Post-PhD, Kanad worked in various semiconductor companies like IBM and Synopsys. During his PhD days, Kanad interned at Intel. Currently, Kanad is an Assistant Professor at the Electrical and Computer Engineering Department of the University of Texas at Dallas, where he leads the Trustworthy and Intelligent Embedded Systems (TIES) lab. Prior to this, Kanad was an Assistant Research Professor at the Electrical and Computer Engineering Department of NYU. He has authored 1 book, 2 US patents, 2 book chapters and several peer reviewed journal and conference articles. Kanad was awarded the ”Best Paper Award” at the International Conference on VLSI Design 2011. Several News agencies have covered his research including NBC Austin and CBS Dallas-Fort Worth. Kanads current research interests are hardware and systems security as well as Quantum Computing.

Host Faculty: Dr. Sumit Kumar Mandal

Video Archive Go Top

 

Series: Department Seminar
Title: Fairness in AI-based Decision Making

  • Speaker: Manisha Padala, IIIT Hyderabad
  • Date and Time: Thursday, December 15, 2022, 4:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
AI systems are ubiquitous in the current times, facilitating numerous real-world and even real-time applications. The existing models achieve near-optimal results for specific performance measures. Such perfection is often obtained at the cost of "Fairness". By fairness, we quantify an application's impact on a group of users (Group Fairness) or an individual user (Individual Fairness). We consider the two settings,

i) Fair classification: towards this, we propose neural network based fair classifier satisfying group fairness notions. We validate its empirical performance on real-world data and provide generalization bounds. Further, we propose a fair and private framework that provides certain privacy, fairness and accuracy trade-offs.

ii) Fair resource allocation with autonomous agents: we consider allocating finite indivisible resources among a finite number of agents. Economists have extensively studied fairness notions like, envy freeness, proportionality and max-min share in the setting without externalities. We study a particular setting of externality and provide theoretical results for these notions.

Speaker Bio:
Manisha Padala is a doctoral student at the International Institute of Information Technology, Hyderabad, under the supervision of Dr. Sujit Gujar. She looks at how to build fair AI-based systems. Towards this, she addresses research challenges to ensure fairness in AI-based decision-making. The fairness here could be individual or group fairness. Her approach is to make models as simple as possible-- easy to understand and provide theoretical and empirical guarantees. She has 10+ research publications, including A* venues such as AAAI, IJCAI, and AAMAS. She received the best paper award at the first conference on deployable AI and the best paper runner-up award at PRICAI'22. She completed her BTech from IIT Jodhpur in 2017 and is expected to graduate soon. She is actively collaborating with Adobe Research, Google Research, and UNSW, where she has done research internships.

Host Faculty: R Govindarajan

Video Archive Go Top

 

Series: Department Seminar
Title: Applications of Dedekinds Index Theorem to Lattice-based Cryptography

  • Speaker: Charanjit S. Jutla
                   IBM T. J. Watson Research Center
                   Yorktown Heights, NY
  • Date and Time: Wednesday, December 14, 2022, 3:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Computationally hard problems on integer lattices, such as shortest vector problem (SVP), have become an important tool in designing modern cryptographic schemes, especially since these problems are considered post-quantum secure. For example, Shors quantum polynomial-time algorithm for integer factorization has rendered the famous RSA cryptosystem insecure, assuming existence of quantum computers.

Instead of basing hardness on worst-case integer lattices, to make the lattice-based encryption schemes more efficient, there has been a significant push to use ideal lattices in ring of integers of number fields, and such a scheme has even been standardized by NIST recently. However, it is not clear if the additional algebraic structure of such ideal lattices, which lie in well known Dedekind-domains, can withstand quantum attacks. In this work we show that we can base similar and natural cryptosystems on hardness of ideal lattices in non Dedekind-domains which have less algebraic structure. This allows the security of the efficient cryptosystems to be based on problems closer to the worst-case integer lattices. The main technical contribution of the work is a novel and generalized way to prove the “ideal-clearing lemma” of Lyubashevsky et al (Eurocrypt 2010). This is joint work with Chengyu Lin.

Speaker Bio:
Charanjit S. Jutla obtained his BTech in Computer Science from IIT Kanpur in 1985 and PhD in Computer Science from the University of Texas at Austin in 1990. Since then he has been a research staff member at IBM T. J. Watson Research Center. He has published many papers in the fields of modal logics, coding theory and cryptography. His current research interests include complexity theory and cryptography.

Host Faculty: Prof. Chaya Ganesh

Video Archive Go Top

 

Series: Department Seminar
Title: Enabling Efficient Memory Systems using Novel Compression Methods

  • Speaker: Prof. Per Stenstrom
                   Chalmers University of Technology/ZeroPoint Technologies, Sweden
  • Date and Time: Wednesday, December 14, 2022, 11:00 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Using data compression methods in the memory hierarchy can improve the efficiency of memory systems by enabling higher effective cache capacity, more effective use of available memory bandwidth and by enabling higher effective main memory capacity. This can lead to higher substantially higher performance and lower power consumption. However, to enable these values requires highly effective compression algorithms that can be implemented with low latency and high throughput. Research at Chalmers University of Technology and at ZeroPoint Technologies, a fabless startup company, has yielded many new families of compression methods that are now being commercially deployed. This talk will present the major insights of more than a decade of research on memory compression methods for the memory hierarchy. The talk covers value-aware and statistical compression caches, compression algorithms that are tuned to the data at hand through data analysis using new clustering algorithms to allow for substantially higher memory bandwidth.

Speaker Bio:
Per Stenstrom is professor at Chalmers University of Technology. His research interests are in parallel computer architecture. He has authored or co-authored four textbooks, about 200 publications and twenty patents in this area. He has been program chairman of several top-tier IEEE and ACM conferences including IEEE/ACM Symposium on Computer Architecture and acts as Associate Editor of ACM TACO, Topical Editor IEEE Transaction on Computers and Associate Editor-in-Chief of JPDC. He is a Fellow of the ACM and the IEEE and a member of Academia Europaea, the Royal Swedish Academy of Engineering Sciences and the Royal Spanish Academy of Engineering Science.

Host Faculty: R Govindarajan

Video Archive Go Top

 

Series: Ph.D. Colloquium
Title: An MLIR-based High-level Synthesis Compiler for Hardware Accelerator Design

  • Speaker: Kingshuk Majumder
                   Ph.D (Engg.) student
                   Dept. of CSA
  • Faculty Advisor: Prof. Uday Kumar Reddy .B
  • Date and Time: Monday, December 12, 2022, 4:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
The emergence of machine learning, image and audio processing on edge devices has motivated research towards power-efficient custom hardware accelerators. Though FPGAs are an ideal target for custom accelerators, the difficulty of hardware design and the lack of vendor-agnostic, standardized hardware compilation infrastructure has hindered their adoption. High-level synthesis (HLS) offers a more compiler-centric alternative to the traditional Verilog-based hardware design improving developer productivity.

In this work, we propose an MLIR-based end-to-end HLS compiler and an an intermediate representation that is suitable for the design and implementation of domain-specific accelerators for affine workloads. Our compiler brings similar levels of modularity and extensibility to the HLS compilation domain, which LLVM brought to the area of a software compilation. A modular compiler infrastructure offers the advantage of incrementally introducing new language frontends and optimization passes without the need to reinvent the whole HLS compiler stack.

Our compiler converts a high-level description of the accelerator specified in the C programming language into a register-transfer-level design in SystemVerilog. We use memory dependence analysis and integer-linear-program(ILP) based automatic scheduling on improving loop-pipelining and introduce parallelization between producer-consumer kernels. Our ILP-based optimizer beats the state-of-the-art Vitis HLS compiler by 1.3x in performance over a representative set of benchmarks while requiring fewer FPGA resources.

Microsoft Teams meeting

Join on your computer, mobile app or room device https://teams.microsoft.com/l/meetup-join/19%3ameeting_YjZiOWVkMzgtOGU2MS00YjExLWE1ZTctNjBkNmYzZjQwODE4%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

Meeting ID: 448 946 611 293 Passcode: gQbJz4

Video Archive Go Top

 

Series: M.Tech (Research) Colloquium
Title: Stochastic Optimization And Its Application In Reinforcement Learning.

  • Speaker: Akash Mondal
                   M.Tech (Research) student
                   Dept. of CSA
  • Faculty Advisor: Prof. Shalabh Bhatnagar
  • Date and Time: Monday, December 12, 2022, 12:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Numerous engineering fields, including transportation systems, manufacturing, communication networks, healthcare, and finance, frequently encounter problems requiring optimization, including uncertainty. Simulation-based optimization is a workable substitute for accurate analytical solutions because of the numerous input variables and the need for a system model. Smoothed functional (SF) algorithms

belong to the class of simultaneous perturbation methods that have been found useful for stochastic optimization problems particularly in high-dimensional parameter spaces. SF methods update the gradient of the objective using function measurements involving parameters

that are perturbed simultaneously along all component directions. Katkovnik and Kulchitsky originally developed the SF gradient procedure. This results in the objective function

getting smoothed because of the convolution. The objective function smoothing

that results from the convolution with a smoothing density function can help the algorithm converge to a global minimum or to a point close to it.

First we present a stochastic gradient algorithm for minimizing a smooth objective function that is an expectation over

noisy cost samples, and only the latter are observed for any given parameter. Our algorithm employs a gradient estimation scheme with random perturbations, which are formed using the truncated Cauchy distribution from the $delta$ sphere. We analyze the bias and variance of the proposed gradient estimator. Our algorithm is found to be particularly useful in the case when the objective function is non-convex, and the parameter dimension is high. From an asymptotic convergence analysis, we establish that our algorithm converges almost surely to the set of stationary points of the objective function and obtain the asymptotic convergence rate. We also show that our algorithm avoids unstable equilibria, implying convergence to local minima. Further, we perform a non-asymptotic convergence analysis of our algorithm. In particular, we establish here a non-asymptotic bound for finding an $epsilon$-stationary point of the non-convex objective function. Finally, we demonstrate numerically through simulations that our algorithm outperforms GSF, SPSA and RDSA by a significant margin over a few non-convex settings and we further validate its performance over convex (noisy) objectives.

Next we consider the problem of control in the setting of reinforcement learning (RL), where model information is not available. Policy gradient algorithms are a popular solution approach for this problem, and are usually shown to converge to a stationary point of the value function. We propose two policy Newton algorithms that incorporate cubic regularization. Both algorithms employ the likelihood ratio method to form estimates of the gradient and Hessian of the value function using sample trajectories. The first algorithm requires exact solution of the cubic regularized problem in each iteration, while the second algorithm employs an efficient gradient descent-based approximation to the cubic regularized problem. We establish convergence of our proposed algorithms to a second-order stationary point (SOSP) of the value function, which results in avoidance of traps in the form of saddle points. In particular, the sample complexity of our algorithms towards finding an $epsilon$-SOSP is $O(epsilon^{-3.5})$, and this is a significant improvement over the state-of-the-art sample complexity of $O(epsilon^{-4.5})$.

Microsoft teams link:

Join on your computer, mobile app or room device

https://teams.microsoft.com/l/meetup-join/19%3ameeting_OGI4YjEzMmUtNGFkZi00YmE5LTgzMzQtYWVmZTI5OGQxNTE3%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%22578cbfbe-b1e9-4f20-91bd-984b656368e5%22%7d

Meeting ID: 488 618 948 051 Passcode: XQantJ

Video Archive Go Top

 

Series: Bangalore Theory Seminars
Title: Lifelong Learning of Representations with Provable Guarantees

  • Speaker: Santosh Vempala
                   Georgia Tech
  • Date and Time: Friday, December 09, 2022, 3:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
In lifelong learning, tasks (or classes) to be learned arrive sequentially over time in arbitrary order. During training, knowledge from previous tasks can be captured and transferred to subsequent ones to improve sample efficiency. We consider the setting where all target tasks can be represented in the span of a small number of unknown linear (or nonlinear) features of the input data and propose a lifelong learning algorithm that maintains and refines the internal feature representation. We prove that for any desired accuracy on all tasks, the dimension of the representation remains close to that of the underlying representation. The resulting algorithm is provably efficient and the sample complexity for input dimension d, m tasks with k total features up to error ϵ is O~((dk^1.5 + km)/ϵ). We also prove a matching lower bound for any lifelong learning algorithm that uses a single task learner as a black box. An empirical study, with a lifelong learning heuristic for deep neural networks, performs favorably on challenging image datasets compared to state-of-the-art continual learning methods.

Speaker Website https://faculty.cc.gatech.edu/~vempala/

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

Hosts: Aditya Abhay Lonkar, Rahul Madhavan and Rameesh Paul

Video Archive Go Top

 

PAST SEMINARS

Series: Bangalore Theory Seminars
Title: Exploring the Gap between Tolerant and Non-tolerant Distribution Testing

  • Speaker: Sayantan Sen
                   Indian Statistical Institute, Kolkata
  • Date and Time: Monday, December 05, 2022, 11:00 AM
  • Venue: CSA Lecture Hall (Room No. 112, Ground Floor)

Abstract
The framework of distribution testing is currently ubiquitous in the field of property testing. In this model, the input is a probability distribution accessible via independently drawn samples from an oracle. The testing task is to distinguish a distribution that satisfies some property from a distribution that is far in some distance measure from satisfying it. The task of tolerant testing imposes a further restriction, that distributions close to satisfying the property are also accepted.

This work focuses on the connection between the sample complexities of non-tolerant testing of distributions and their tolerant testing counterparts. When limiting our scope to label-invariant (symmetric) properties of distributions, we prove that the gap is at most quadratic, ignoring poly-logarithmic factors. Conversely, the property of being the uniform distribution is indeed known to have an almost-quadratic gap.

Moreover, we prove lower bounds on the sample complexities of non-tolerant as well as tolerant testing for a special class of distribution properties, namely non-concentrated distribution properties, where the probability mass of the distributions in the property is sufficiently spread out. Finally, we design an algorithm that can learn a concentrated distribution even when its support set is unknown apriori.

This is a joint work with Sourav Chakraborty, Eldar Fischer, Arijit Ghosh and Gopinath Mishra.

Speaker Website https://sites.google.com/view/sayantans/home



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

Hosts: Aditya Abhay Lonkar, Rahul Madhavan and Rameesh Paul

Video Archive Go Top

 

Series: Bangalore Theory Seminars
Title: Robustly Learning Mixtures of Arbitrary Gaussians in Polynomial Time

  • Speaker: Santosh Vempala
                   Georgia Tech
  • Date and Time: Friday, December 02, 2022, 11:00 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
The Gaussian Mixture Model (Pearson 1894) is widely used for high-dimensional data. While classical results establish its unique identifiability, it was shown in 2010 (Kalai-Moitra-Valiant, Belkin-Sinha) that for any fixed number of component Gaussians, the underlying mixture parameters can be estimated to arbitrary accuracy in polynomial time. Robust Statistics (Huber 1964) asks for estimation of underlying models robustly, i.e., even if a bounded fraction of data is noisy, possibly chosen adversarially. This goal seemed to be computationally intractable, even for estimating the mean of "nice" distributions, till 2016 (Diakonikolas-Kamath-Kane-Li-Moitra-Stewart, Lai-Rao-Vempala). These methods were extended to many problems, but the robust estimation of GMMs remained a central open problem. In this talk, we will present the first polytime algorithm for any fixed number of components with no assumptions on the underlying mixture. The techniques developed, clustering using convex relaxations and approximate tensor decomposition allowing for error in both Frobenius norm and low-rank terms, might be useful more generally.

Speaker Website https://faculty.cc.gatech.edu/~vempala/

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

Hosts: Aditya Abhay Lonkar, Rahul Madhavan and Rameesh Paul

Video Archive Go Top

 

Series: IISc-CRYPTO Seminars
Title: Verifiable Relation Sharing and Multi-Verifier Zero-Knowledge in Two Rounds: Trading NIZKs with Honest Majority

  • Speaker: Eliran Kachlon
                   PhD student
                   Tel-Aviv university
  • Date and Time: Thursday, December 01, 2022, 5:00 PM
  • Venue: Microsoft Teams - ON-LINE

Abstract
We introduce the problem of Verifiable Relation Sharing (VRS) where a client (prover) wishes to share a vector of secret data items among k servers (the verifiers) while proving in zero knowledge that the shared data satisfies some properties. This combined task of sharing and proving generalizes notions like verifiable secret sharing and zero-knowledge proofs over secret-shared data. We study VRS from a theoretical perspective and focus on its round complexity.

As our main contribution, we show that every efficiently-computable relation can be realized by a VRS with an optimal round complexity of two rounds where the first round is input-independent (offline round). The protocol achieves full UC-security against an active adversary that is allowed to corrupt any t-subset of the parties that may include the client together with some of the verifiers. For a small (logarithmic) number of parties, we achieve an optimal resiliency threshold of t < 0.5(k + 1), and for a large (polynomial) number of parties, we achieve an almost-optimal resiliency threshold of t < 0.5(k + 1)(1 − ε) for an arbitrarily small constant ε > 0. Both protocols can be based on sub-exponentially hard injective one-way functions. If the parties have an access to a collision resistance hash function, we can derive statistical everlasting security, i.e., the protocols are secure against adversaries that are computationally bounded during the protocol execution and become computationally unbounded after the protocol execution.

Previous 2-round solutions achieve smaller resiliency thresholds and weaker security notions regardless of the underlying assumptions. As a special case, our protocols give rise to 2-round offline/online constructions of multi-verifier zero-knowledge proofs (MVZK). Such constructions were previously obtained under the same type of assumptions that are needed for NIZK, i.e., public-key assumptions or random-oracle type assumptions (Abe et al., Asiacrypt 2002; Groth and Ostrovsky, Crypto 2007; Boneh et al., Crypto 2019; Yang, and Wang, Eprint 2022). Our work shows, for the first time, that in the presence of an honest majority these assumptions can be replaced with more conservative “Minicrypt”-type assumptions like injective one-way functions and collision-resistance hash functions. Indeed, our MVZK protocols provide a round-efficient substitute for NIZK in settings where honest-majority is present.

This is a joint work with Benny Applebaum and Arpita Patra.

Speaker Bio:
Eliran Kachlon is a PhD student at Tel-Aviv university under the supervision of Benny Applebaum. Microsoft teams link: https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZDUzYjJlZDItZmIwNC00ZWY5LWIzNzEtZTg3OWViZThjYzgx%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%22f8aaf4da-ac16-401f-a953-eeb416835728%22%7d

Host Faculty: Prof. Arpita Patra

Video Archive Go Top

 

Series: Bangalore Theory Seminars
Title: Approximate Representation of Symmetric Submodular Functions via Hypergraph Cut Functions

  • Speaker: Karthekeyan Chandrasekaran
                   University of Illinois, Urbana-Champaign
  • Date and Time: Monday, November 28, 2022, 11:00 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Submodular functions are fundamental to combinatorial optimization. We consider the problem of approximating symmetric submodular functions everywhere using hypergraph cut functions. Prior works have shown that symmetric submodular functions over n-element ground sets cannot be approximated within a (n/8)-factor using a graph cut function and raised the question of approximating them using hypergraph cut functions. In this talk, I will show that there exist symmetric submodular functions over n-element ground sets that cannot be approximated within a o(n^{1/3}/log^2 n)-factor using a hypergraph cut function. On the positive side, I will discuss the approximability of symmetrized concave linear functions and symmetrized rank functions of uniform matroids and partition matroids using hypergraph cut functions.

Based on joint work with Calvin Beideman, Chandra Chekuri, and Chao Xu.

Speaker Website: http://karthik.ise.illinois.edu/

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

For more details please visit: https://csa.iisc.ac.in/theoryseminars/

Hosts: Rahul Madhavan and Rameesh Paul

Video Archive Go Top

 

Series: Ph.D (Engg.)Thesis Defence -ON-LINE
Title: Comparative Analysis of Topological Structures

  • Speaker: Raghavendra GS
                   Ph.D (Engg.) student
                   Dept. of C.S.A
                   IISc.,
  • Faculty Advisor: Prof. Vijay Natarajan
  • Date and Time: Friday, November 25, 2022, 11:00 AM
  • Venue: Microsoft Teams - ON-LINE

Abstract
Measuring scientific processes result in a set of scalar functions (scalar fields) which may be related temporally, be part of an ensemble, or unrelated. Overall understanding and visualization of scientific processes require the study of individual fields and, more importantly, the development of methods to compare them meaningfully. In this thesis, we focus on the problem of designing meaningful measures to compare scalar fields by comparing their abstract representations called topological structures. We emphasize on intuitive and practical measures with useful properties and applications.

The first part of the thesis deals with comparing a topological structure called the merge tree. We propose two global comparison measures, both based on tree edit distances. The first measure OTED is based on the assumption that merge trees are ordered rooted trees. Upon finding that there is no meaningful way of imposing such an order, we propose a second measure called MTED for comparing unordered rooted trees. We propose intuitive cost models and prove that MTED is a metric. We also provide various applications such as shape comparison, periodicity detection, symmetry detection, temporal summarization, and an analysis of the effects of sub-sampling /smoothing on the topology of the scalar field.

The second part deals with a local comparison measure LMTED for merge trees that supports the comparison of substructures of scalar fields, thus facilitating hierarchical or multi-scale analysis and alleviating some drawbacks of MTED. We propose a dynamic programming algorithm, prove that LMTED is a metric and also provide applications such as symmetry detection in multiple scales, a finer level analysis of sub-sampling effects, an analysis of the effects of topological compression, and feature tracking in time-varying fields.

The third part of the thesis deals with comparison of a topological structure called the extremum graph. We provide two comparison measures for extremum graphs based on persistence distortion (PDEG) and Gromov-Wasserstein distance (GWEG). Both persistence distortion and Wasserstein distance are known metrics. We analyze how the underlying metric affects these comparison measures and present various applications such as periodicity detection to facilitate scientific data analysis and visualization.

The final part of the thesis introduces a time-varying version of extremum graphs (TVEG) with a simple comparison criterion to identify correspondences between features in successive time steps. We provide applications to tracking features in time-varying scalar fields from computational fluid dynamics.

Microsoft teams link:

https://teams.microsoft.com/l/meetup-join/19%3ameeting_YWQ3OGE4ODEtYmJiNi00OGMxLWFjMTEtN2ZkMzI0YTYxYzVi%40thread.v2/0?context={"Tid"%3a"6f15cd97-f6a7-41e3-b2c5-ad4193976476"%2c"Oid"%3a"aed44988-a973-4f25-80f9-21c27cc766d2"}

Video Archive Go Top

 

Series: Department Seminar
Title: Multi-Party Computing for Privacy in Machine Learning Systems

  • Speaker: Prof. Murali Annavaram, Smt.Rukmini-Sri.Gopalakrishnachar Visiting Chair Professor, CSA, IISc & Univ. of Southern California, Los Angeles, CA, USA
  • Date and Time: Friday, November 25, 2022, 11:00 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Given the resource management benefits such as elasticity, availability, and cost-effectiveness offered by cloud service providers, a growing number of machine learning workloads are migrated to the cloud for operations. Under this modern compute paradigm, confidential data and models can be leaked to unwanted parties if the service providers are curious, malicious, or compromised. The privacy concern is particularly pressing for natural language processing (NLP) where user’s audio features are inputs to ML models. These inputs contain sensitive private information about the users and require rigorous protection.

Secure multi party computing (MPC) is one approach to tackle the privacy leaks without relying on any additional hardware support. MPC protocols provide strong security even when a subset of parties are compromised. However, when it comes to protecting privacy there is no free lunch, and in fact we show that it is a very expensive lunch. Through a detailed characterization of industry-strength MPC implementation of Transformer-based NLP models, we analyze where the MPC performance bottlenecks are. First, we show that Transformers rely extensively on ``softmax" functions. While softmax functions are relatively cheap in a non-private execution, softmax dominates the MPC inference runtime, consuming up to 50% of the total inference runtime. We explain the reasons for this significant performance loss. Second, MPC relies on approximating non-linear functions that are part of the softmax computations, and the narrow dynamic ranges make optimizing softmax while maintaining accuracy quite difficult.

Based on the above characterization data we developed MPC-Pipe to accelerate MPC. MPC-Pipe is based on the intuition that most MPC protocols today perform communications and computations in sequential manner. This serialization is not a poor implementation choice, but a requirement for MPC to work correctly. Without the data communication the parties cannot progress to the next computation step. Thus GPU servers that are parties in an MPC setting are idle when waiting for data transmission to complete. This phenomenon inspires us to enable MPC servers to perform computations and communications concurrently through a series of novel MPC-abiding computation transformation. MPC-Pipe, an MPC pipeline inference technique is based on two ML-specific approaches. 1) inter-linear-layer pipeline and 2) inner layer pipeline. The first scheme benefits linear layers by transmitting input-independent MPC metadata beforehand, and the second benefits non-linear layers by breaking big inputs into smaller ones to overlap communications and computations. Those two techniques combined shorten the total inference runtime for machine learning models by up to 14.5%, compared to current MPC protocol implementations.

Speaker Bio:
Murali Annavaram is a Dean’s Chair Professor in the Ming-Hsieh Department of Electrical and Computer Engineering, and in the department of Computer Science (joint appointment) at the University of Southern California. He currently holds the Rukmini Gopalakrishnachar Visiting Chair Professorship at the Indian Institute of Science, Benguluru. He is the founding director of the REAL@USC-Meta center that is focused on research and education in AI and learning, and the co-PI on the DISCoVER NSF Expeditions center focused on superconducting technologies. His research group tackles a wide range of computer system design challenges, relating to energy efficiency, security and privacy. He has been inducted to the hall of fame for three of the prestigious computer architecture conferences ISCA, MICRO and HPCA. He served as the Technical Program Chair for HPCA 2021, and served as the General Co-Chair for ISCA 2018, and the Computer Architecture Track Chair for HiPC-2016 and SBACPAD-22 conferences. Prior to his appointment at USC he worked at Intel Microprocessor Research Labs from 2001 to 2007. His work at Intel lead to the first 3D microarchitecture paper, and also influenced Intel’s TurboBoost technology. In 2007 he was a visiting researcher at the Nokia Research Center working on mobile phone-based wireless traffic sensing using virtual trip lines, which later become Nokia Traffic Works product. In 2020 he was a visiting faculty scientist at Facebook, where he designed the checkpoint systems for distributed training. Murali co-authored Parallel Computer Organization and Design, a widely used textbook to teach both the basic and advanced principles of computer architecture. Murali received the Ph.D. degree in Computer Engineering from the University of Michigan, Ann Arbor, in 2001. He is a Fellow of IEEE and Senior Member of ACM.

Host Faculty: R Govindarajan

Video Archive Go Top

 

Series: IISc-CRYPTO Seminars
Title: On Perfectly Secure Two-Party Computation for Symmetric Functionalities with Correlated Randomness

  • Speaker: Bar Alon
                   Ph.D. student
                   Ariel University
  • Date and Time: Thursday, November 24, 2022, 5:00 PM
  • Venue: Microsoft Teams - ON-LINE

Abstract
A multiparty computation protocol is perfectly secure for some function f if it perfectly emulates an ideal computation of f. Thus, perfect security is the strongest and most desirable notion of security, as it guarantees security in the face of any adversary and eliminates the dependency on any security parameter. Ben-Or et al. [STOC 88] and Chaum et al. [STOC 88] showed that any function can be computed with perfect security if strictly less than one-third of the parties can be corrupted. For two-party sender-receiver functionalities (where only one party receives an output), Ishai et al. [TCC 13] showed that any function can be computed with perfect security in the correlated randomness model. Unfortunately, they also showed that perfect security cannot be achieved in general for two-party functions that give outputs to both parties (even in the correlated randomness model).

We study the feasibility of obtaining perfect security for deterministic symmetric two-party functionalities (i.e., where both parties obtain the same output) in the face of malicious adversaries. We explore both the plain model as well as the correlated randomness model. We provide positive results in the plain model, and negative results in the correlated randomness model. As a corollary, we obtain the following results. - We provide a characterization of symmetric functionalities with (up to) four possible outputs that can be computed with perfect security. The characterization is further refined when restricted to three possible outputs and to Boolean functions. All characterizations are the same for both the plain model and the correlated randomness model. -We show that if a functionality contains an embedded XOR or an embedded AND, then it cannot be computed with perfect security (even in the correlated randomness model).

Speaker Bio:
Bar Alon is a Ph.D. student at Ariel University and I work under the supervision of Dr. Eran Omri. Microsoft teams link: https://teams.microsoft.com/l/meetup-join/19%3ameeting_OWQ0MTkyYWEtYTdjNi00MGJiLWEyNTgtYTNjNmY3NjU5YWVj%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%22f8aaf4da-ac16-401f-a953-eeb416835728%22%7d

Host Faculty: Prof. Arpita Patra

Video Archive Go Top

 

Series: Invited talk at IISc ACM student chapter
Title: Doing your Lifes work

  • Speaker: Dr. Balakrishnan Srinivasan
                   Senior System Software engineer, Compiler Team
                   NVIDIA, Bangalore
  • Date and Time: Thursday, November 24, 2022, 3:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
The rapid evolution of technologies within and outside a company deeply affect the choice of work we intend to do as our lifes work. As a case study, in this talk, I will give a high-level overview of technologies developed in NVIDIA, and the backdrop in which these technologies evolved. Further, I will give a birds eye view of the implications of the dynamic settings in the current day workplace to doing our lifes work.

Speaker Bio:
Balakrishnan Srinivasan got his Ph.D in 2000 from the Supercomputer Education and Research Center, IISc. From 2001 to 2005, he worked as a senior scientist at the Philips Research Laboratories, The Netherlands, where he primarily worked on vector processing architectures for 3G baseband receivers. From 2005 to 2010 he worked as a principal scientist researching on healthcare applications and later as department head at the Philips Research labs in Bangalore. From 2010-2013 he worked at Morphing Machines as a Principal Researcher attempting to bring new technologies to the market. He has been with NVIDIA since April 2013 as a senior software engineer working in the compiler team that generates code for the GPU.

Host Faculty: Prof. R Govindarajan In association with IISc ACM student chapter.

Video Archive Go Top

 

Series: IISc-CRYPTO Seminars
Title: Efficient zero-knowledge proofs based on vector-oblivious linear evaluation

  • Speaker: Xiao Wang
                   Assistant Professor
                   Computer Science
                   Northwestern University.
  • Date and Time: Friday, November 18, 2022, 10:00 AM
  • Venue: Microsoft Teams - ON-LINE

Abstract
Zero-knowledge (ZK) proofs with an optimal memory footprint have attracted a lot of attention because such protocols can easily prove very large computations with a small memory requirement. In this talk, the speaker will talk about some recent progress on concretely efficient ZK protocols based on VOLE and their applications in this setting. These protocols are very cheap computationally and can prove large statements like ResNet inference or large RAM-based computation with ease; on the other hand, it is designated-verifier, and the proof size is often linear to the circuit size. Finally, the speaker will talk about more recent advances that lead to sublinear communication VOLE zero-knowledge proof protocols.

Speaker Bio:
Xiao Wang is an Assistant Professor of Computer Science at Northwestern University. He was a post-doc with Vinod Vaikuntanathan at MIT and Ran Canetti at BU. He obtained his Ph.D. at the University of Maryland with Jonathan Katz. His research interests focus on applied cryptography, specifically designing efficient privacy-preserving systems based on secure multi-party computation. He received a Best Paper Award in Applied Cyber Security at CSAW 2015, an iDASH Competition Award in 2015, a Human Longevity Inc. Award for MPC in 2016, an ACM CCS Best Paper Award in 2017, and an ACM CCS Best Paper Award runner-up in 2021. Microsoft teams link: https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZmYxMjQxM2ItOGM0NS00MTEwLTkyYTEtNGFkNjYxNGU2NTVh%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%22f8aaf4da-ac16-401f-a953-eeb416835728%22%7d

Host Faculty: Prof. Arpita Patra

Video Archive Go Top

 

Series: Department Seminar
Title: Birthday Paradox, Monochromatic Subgraphs, and Algorithmic Applications

  • Speaker: Prof. Bhaswar B. Bhattacharya
                   Department of Statistics and Data Science, The Wharton School
                   University of Pennsylvania
  • Date and Time: Thursday, November 17, 2022, 4:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
What is the chance that among a group of friends, there are friends all of whom have the same birthday? This is the celebrated birthday problem which can be formulated as the existence of a monochromatic -clique (matching birthdays) in the complete graph , where every vertex of is uniformly colored with 365 colors (corresponding to birthdays). More generally, for a connected graph, let be the number of monochromatic copies of in a uniformly random coloring of the vertices of the graph with colors. In this talk, the asymptotic properties of this quantity will be derived, and applications in distributional property testing and computation of discrete logarithms will be discussed.

Speaker Bio:
Prof. Bhaswar Bhattacharya is a faculty in the Department of Statistics and Data Science at the Wharton School, with a secondary appointment in the Department of Mathematics, at the University of Pennsylvania. He received Ph.D from the Department of Statistics at Stanford University in 2016, under supervision of Persi Diaconis. His research interests are in Nonparametric statistics, Combinatorial probability, Discrete and Computational Geometry. Microsoft teams link: https://teams.microsoft.com/l/meetup-join/19%3ameeting_N2Y3MThjNWEtOWRiOC00NjEzLWExMWUtYTgzNDkyZTY0YmY4%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%22c747ccaa-ceaa-4197-b4cb-ce2f1d4694da%22%7d

Host Faculty: Prof. Ambedkar Dukkipati

Video Archive Go Top

 

Series: Department Seminar
Title: The Role of Adaptivity in Learning and Decision-Making

  • Speaker: Dr. Arpit Agarwal, Columbia University, USA
  • Date and Time: Thursday, November 17, 2022, 11:00 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
In many machine learning applications the learner is faced with a *stochastic environment* and it (sequentially) probes or influences the environment so as to optimize a given objective function. Examples of such applications include recommendation systems, web advertising, viral marketing, clinical trials, search ranking etc. For instance, in recommendation systems, the learner attempts to identify good recommendations by probing the stochastic preferences of users. Similarly, in viral marketing, the learner attempts to spread information through a social network using marketing campaigns that influence (stochastic) subsets of the network.

Most existing learning algorithms for these applications operate in one of two settings: (1) non-adaptive, and (2) fully adaptive. In the non-adaptive setting, all the selections/probes are completely determined ahead of time. However, these a priori selections might be inefficient as some of them might be unnecessary in hindsight. In the fully adaptive setting, the selection policy is updated after each observation from the environment. However, this fully adaptive setting might not be practical in many applications due to delays in receiving observations from many parallel sources. In this talk we introduce a semi-adaptive setting that interpolates between these two extreme settings for a wide range of learning and decision-making problems such as best arm identification in multi-armed bandits, ranking from pairwise comparisons, dueling bandits, and stochastic submodular maximization. We show that semi-adaptive policies enjoy the power of fully adaptive policies while requiring very few updates to the selection/probing rules. We also identify the trade-offs between rounds of adaptivity and performance.

Speaker Bio:
Dr. Arpit Agarwal is a Postdoctoral Research Fellow at the Data Science Institute at Columbia University. His research interests primarily lie in machine learning, with connections to algorithmic economics and theoretical computer science. Before joining Columbia, he received a Ph.D. in Computer Science from the University of Pennsylvania and a masters in Computer Science from the Indian Institute of Science.

Host Faculty: R Govindarajan

Video Archive Go Top

 

Series: Department Seminar
Title: Rethinking the IID Assumption for Data-efficient and Robust NLP

  • Speaker: Dr. Pradeep Dasigi, Allen Institute for AI
  • Date and Time: Friday, November 11, 2022, 11:00 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
The standard practice for training Machine Learning models is to assume access to independent and identically distributed (IID) labelled data, to optimise for the average loss on a training set and to measure generalisation on a held-out in-distribution test set. While this assumption is grounded in theory, it does not often hold in practice. In this talk I will focus on two issues with the setup that affect NLP systems: 1) Obtaining sufficient high quality labelled training data can be expensive, making it difficult to train models that generalise well to in-distribution test sets; 2) Even when large enough labelled training sets are available, they may come with unwanted correlations between labels and task-independent features. These spurious correlations are a consequence of unavoidable biases in the dataset collection processes, and can provide shortcuts to models that allow them to generalise well to in-distribution test sets that also have those spurious correlations, without actually learning the intended tasks.

To illustrate the first problem, I will first present Qasper, a complex document-level Question Answering task over research papers and an associated dataset collection process that requires expert annotators. To address the problem, I will present a data-efficient training method that leverages data from other tasks where it is easier to obtain labelled data. In contrast with recent work that trained massive multitask models (e.g. T0, FLAN) on tens of millions of instances from all available datasets without any knowledge of the target tasks, our method selects small subsets of multi-task training instances that are relevant to the target tasks, using only unlabelled target task instances. Our method is algorithmically simple, yet quite effective and data-efficient—on Qasper and ten other datasets, the target-task specific models outperform the T0 model of the same size by up to 30% without accessing target task labels (zero-shot), and by up to 23% while accessing a few target-task labels (few-shot), all while using about 2% of the multitask data used to train T0 models.

To address the second problem, as an alternative to Empirical Risk Minimisation (ERM) which optimises for average training loss under the IID assumption, I will present a novel optimisation technique based on Group Distributionally Robust Optimisation (G-DRO) which optimises for worst group performance over a known set of pre-defined groups in the training data. Since spurious correlations are often unknown, directly applying G-DRO to this problem is not feasible. Our method, AGRO, simultaneously identifies error-prone groups in the training data and optimises for the model’s performance on them. We show that on several NLP and Vision tasks, AGRO based models outperform models trained using ERM on known error-prone subsets of in-distribution test data by up to 8%, and also on out-of-distributions test sets by up to 10% without using any knowledge of the distribution shifts.

Speaker Bio:
Dr. Pradeep Dasigi is a researcher in the field of Artificial Intelligence, specializing in Natural Language Processing, currently working at the Allen Institute for AI in Seattle, USA. Prior to joining Allen Institute, he completed his Ph.D. from CMU and Masters from Columbia University. His research interests are in the areas of Natural Language Processing and Machine Learning.

Host Faculty: R Govindarajan

Video Archive Go Top

 

 

 

 

 

 

 

 

 

 

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