Abstract: It is said that one should not argue with idiots because they will bring you down to their level and then beat you with experience. This talk focuses on simplifying hard problems using query complexity and analyzing strategies like linear search, binary search, period finding and gradient descent. Joint work with Ankit Garg, Robin Kothari and Praneeth Netrapalli.

Abstract: The talk introduces interesting computer vision applications and explains how graphical models approximate real-world challenges and help in achieving acceptable solutions.

Abstract:The Japanese puzzle game of Roma (see https://www.janko.at/Raetsel/Roma/index.htm for a playable version of this game) is played on a square grid consisting of quadratic cells. The cells are grouped into boxes of at most four neighboring cells, and are filled (or are to be filled) with arrows pointing in cardinal directions. The goal of the game is to fill up the empty cells with arrows such that each box contains at most one arrow of each direction, and regardless of where we start from, if we follow the arrows, we will always end up in the special Roma-cell. In this talk, we will explore the computational complexity of Roma

Abstract: Cryptographic hash functions are functions that take arbitrary length inputs and output fixed length digest. They are one of the most important cryptographic primitives and widely used in applications today. Apart from the compression requirement, the applications using these functions could need additional properties to be provably secure. One such, perhaps the most important property is collision resistance. This property has been well studied for uniform adversaries. However, uniform adversaries fail to capture many real-world adversaries. Hence, several recent works have studied the collision resistance property for non-uniform adversaries. Analyzing non-uniform adversaries presents several challenges. That is why Dodis et al in their EUROCRYPT 18 paper presented a reduction to another (easier to analyze) model named Bit-fixing model. In our CRYPTO 20 paper, we showed that adversaries in this Bit-fixing model are too strong when the length of the collisions are bounded. We also showed a reduction to the Multi-instance model, which helped us obtain better results for restricted parameter ranges. In our recent CRYPTO 22 paper, we further explored the relation between the Bit-fixing model and the Multi-instance model and further improved the results with our new findings. The talk will include some preliminary definitions, detailed description of these models, results and a high level idea of the techniques from all the relevant works.

Abstract: The gap between the processing speed of the CPU and the access speed of the memory is becoming a bottleneck for many emerging applications. This gap can be reduced if the computation can be taken closer to the memory through near-memory processing (NMP). Among the logic units, application-specific integrated circuits (ASICs) are highly efficient in terms of power and area overhead for NMP integration. We aim to accelerate neural network workloads by integrating custom hardware near the memory. As CNNs are widely used in several applications, the designed hardware can be extensively used in all such cases. To design an NMP-based system with high performance and energy efficiency, we explore various optimization techniques, such as leveraging parallelism, exploiting data sparsity, and utilizing computation redundancy to reduce the number of computations. All such techniques result in hardware designs that implement the appropriate dataflow and data-parallel algorithm. These designs have positively impacted the system's performance and energy efficiency. To examine the deployability of the NMP approach, we also perform experiments on various memory technologies like 3D memory, hybrid memory, and the commodity DRAM. The designed systems have performed substantially well when comparing them with multiple baselines and state-of-the-art works.

Abstract: Events are central to the content of human experience. From the constant stream of the sensory onslaught, the brain segments, extracts, represents aspects related to activities, and stores in memory for future comparison, retrieval, and re-storage. This talk will focus on the first problem of event segmentation from video streams. Can we temporally segment activity into its constituent sub-events? Can we spatially localize the event in the image frame? These tasks have been tackled through supervised learning, often requiring large amounts of training data associated with many manual annotations. The question we ask is: can we do these tasks without the need for manual labels? Human perception experiments suggest that we can solve these tasks without requiring high-level supervision. I will share our experience with a set of minimal, self-supervised, predictive learning models that draws inspiration from cognitive psychology and recent brain models from neuroscience. This approach can be used for temporal segmentation and spatial localization of events in the image. We will see results on traditional activity datasets such as Breakfast Actions, 50 Salads, and INRIA Instructional Videos datasets and on ten days of continuous video footage of a bird's nest. The proposed approach can outperform weakly supervised and other unsupervised learning approaches by up to 24% and have competitive performance compared to fully supervised methods.

Abstract: The primary focus of classification problems has been on algorithms that return a prediction on every example. However, in many real-life situations, it may be prudent to reject an example rather than run the risk of a costly potential misclassification. Consider, for instance, a physician who has to return a diagnosis for a patient based on the observed symptoms and a preliminary examination. If the symptoms are either ambiguous, or rare enough to be unexplainable without further investigation, then the physician might choose not to risk misdiagnosing the patient. He might instead ask for further medical tests to be performed or refer the case to an appropriate specialist. The principal response in these cases is to “reject” the example. From a geometric standpoint, we can view the classifier as being possessed of a decision surface as well as a rejection surface. The rejection region impacts the proportion of examples that are likely to be rejected, as well as the proportion of predicted examples that are likely to be correctly classified. A well-optimized classifier with a reject option is the one which minimizes the rejection rate as well as the mis-classification rate on the predicted examples. We will discuss some of our recent contributions in this direction.

Abstract: How does one store a graph in the database of a computer? Typically, the vertices are labelled by the set: {1, 2, 3, ..., n}. The edges can be denoted in several different ways: adjacency matrix, incidence matrix, adjacency list. But, what if the vertices are labelled in a somewhat more creative way, so that the labels of the vertices themselves denote their adjacencies? This entirely eliminates all the need for storing the edges! This topic is part of a heavily researched field called graph labelling, with connections to coding theory and information theory. In this talk we will explore a type of graph labelling known as sum labelling. This is based on joint work with Henning Fernau (University of Trier, Germany). Our paper can be accessed using the link: https://eccc.weizmann.ac.il/report/2021/114

Abstract: In recent years, we have witnessed widespread adoption of AI tools across various sectors, making them capable of impacting lives. Today AI-powered tools aid critical decision-making in policy, law and order, recruiting, healthcare and education. However, they also bring the massive risk of making wrong decisions, which can turn one’s life upside down, as we have seen with COMPASS in the US judicial system and the A-level grading fiasco in the UK’s education system. Implementation of AI and ML tools without much deliberation on its ethical and social impact has resulted in unfair outcomes, often resulting from algorithmic and data biases. In this talk, I will introduce the concept of AI Ethics, why it is essential and the gaps in the present-day AI Ethics discourse. The talk will also examine the notion of AI Ethics from a social and cultural perspective.

Abstract: RNNs and LSTMs have been used for quite some time for various NLP tasks. But these models are large especially because of the input and output embedding parameters. In the past three-four years, the field of NLP has made significant progress thanks to Transformer based models like BERT, GPT, T5, etc. But these models are humongous in size. Real-world applications however demand a small model size, low response times, and low computational power wattage. In this talk, I will discuss four different types of methods for compression of such models for text, in order to enable their deployment in real industry NLP applications and projects. The four types of methods include pruning, quantization, knowledge distillation, and other Transformer based methods.

Abstract: In this talk, I present some of my past work that uses deep learning in two completely different contexts: One being recommender systems for online shopping and the other is on task-oriented chat-bots. Deep Learning has seen a wide range of applications of late in both academia and industry. Through these two case studies, we showcase the versatile nature of deep learning in solving complex business problems in two very different domains that are currently trending in the industry - online recommendations and task-oriented chat bots. We also discuss some practical performance metrics and trade-offs that need to be considered for scaling solutions in both the case studies.

Abstract: Artificial Intelligence deals with machines that take smart decisions. For a large spectrum of decision problems, particularly when the decision involves multiple self-interested agents, such intelligence is beyond the scope of 'learning from data'. In this talk, I am going to address 'strategic multi agent systems' from a game theoretic viewpoint -- a tool used in mathematics and microeconomics to analyze the behavior of rational and intelligent agents -- and show how robust AI systems can be built with such agents. In the process, I will discuss two problems of social importance, namely, social distancing and peer grading, where computational mechanism design approaches are useful. The tools developed based on these ideas will also be briefly presented.

Abstract: Propositional model counting problem (#SAT) is a generalization of SAT, where the aim is to compute the number of satisfying assignments of a formula φ. Model counting is #P-complete even for 2CNF, although checking satisfiability of 2CNF can be done in polynomial time. We consider #SAT parameterized by the treewidth (tw) of the primal graph of the input CNF formula. The best-known algorithm runs in time 2^tw n^O(1), where n is the number of variables. One of the main challenges is whether we can have a faster algorithm, even if we allow a (multiplicative) approximation. In this talk we will see a lower bound on the running time of such algorithms assuming Strong Exponential Time Hypothesis (SETH). For monotone formulas, given a tree decomposition of width w for the primal graph of the input formula, for any \epsilon> 0, we will see a 2^{(1−\epsilon)w} n^O(1)-time 2^{\epsilon n}-approximation algorithm.

Abstract: In this talk, we will design and analyze "cool" (beautiful and efficient) algorithms for simple problems that are of recreational nature. Emphasis will be given on fundamental concepts in an interactive manner. Afterall the goal is to have fun!!

Abstract: Traditional occupant sensing methods employ physical sensors and buttons to detect and react to explicit driver/passenger requests in a passenger vehicle. We explore a computer vision based approach to understand implicit requests from the occupants. Our Interior Assist system uses images captured from an in-car camera sensor that are processed by a tiny deep neural network to react to the dynamic scenarios within the passenger vehicle. In this talk we will specifically focus on how gesture recognition can be used for occupant sensing in car interiors to enhance user experience and comfort, what are the challenges faced and some future research directions.

Abstract: Matching under preferences is a research area that finds numerous applications in practice as diverse as assigning students to colleges, workers to firms, kidney donors to recipients, users to servers in a distributed internet service, to just name a few. Indeed this topic is at the heart of the intersection between Computer Science and Economics, and has been recognized as such by a Nobel Memorial prize in Economics. In the first part of the talk, I will discuss canonical problems in this area, namely, stable matching and its generalization, popular matching. In the second part of the talk, I will present a result that resolved the arguably main open problem in the subarea of popular matching: In an arbitrary graph, deciding if a popular matching exists is NP-complete.

Abstract: Current approach to cancer treatment is moving away from a "carpet bombing" to a "surgical strike." This means that each patient's cancer is profiled for specific molecular or genomic characteristics to prescribe targeted therapies. The cost of these tests remain unaffordable by a vast majority of the population in low-income countries, such as India. On the other hand, general pathology and radiology has become ubiquitous even in tier 3 cities. By using the latest advances in machine learning or artificial intelligence, our research group develops and validates tests that can utilize inexpensive medical imaging modalities to analyze subtle visual patterns of various subtypes of cancer to aid precision medicine. In this talk we will give a few examples of successful results and the process that was required to get there.

Abstract: Modern deep learning methods are data-hungry. While such methods may require millions of annotated training data, humans can learn new concepts with only a few annotated examples. To mimic this incredible cognitive ability of human beings, different methods for data-efficient machine learning have been proposed in recent years. Few-shot learning and Zero-shot learning are two of the most promising avenues among these methods. In the last few years, several few-shot and zero-shot learning methods have been designed for problems related to natural images. However, such methods are relatively rare in the field of radiology diagnosis. In this webinar, we will present several approaches for few-shot and zero-shot diagnosis of chest radiographs. Our methods show promising results on publicly available chest x-ray datasets.

Abstract: Over the years, supply chains have evolved from a few regional traders to globally complex chains of trade. Consequently, supply chain management systems have become heavily dependent on digitisation for the purpose of data storage and traceability of goods. However, current approaches suffer from issues such as scattering of information across multiple silos, susceptibility of erroneous or untrustworthy data, inability to accurately capture physical events associated with the movement of goods and protection of trade secrets. Our work aims to address above mentioned challenges related to traceability, scalability, trustworthiness and privacy. To support traceability and provenance, a consortium blockchain based framework, ProductChain, is proposed which provides an immutable audit trail of product's supply chain events and its origin. The framework also presents a sharded network model to meet the scalability needs of complex supply chains. Next, we address the issue of trust associated with the qualities of the commodities and the entities logging data on the blockchain through an extensible framework, TrustChain. TrustChain tracks interactions among supply chain entities and dynamically assigns trust and reputation scores to commodities and traders using smart contracts. For protecting trade secrets, we propose a privacy-preservation framework PrivChain, which allows traders to keep trade related information private and rather return computations or proofs on data to support provenance and traceability claims. The traders are in turn incentivised for providing such proofs. A different privacy-preservation approach for decoupling the identities of traders is explored in TradeChain by managing two ledgers: one for managing decentralised identities and another for recording supply chain events. The information from two ledgers is then collated using access tokens provided by the data owners, i.e. traders themselves.

Abstract: Artificial Intelligence has played a key role from predicting, minimizing and stalling Pandemic outbreak such as Coronavirus to making autonomous vehicles a reality. The world of computing is going through an incredible change. With deep learning and AI, computers are learning to write their own software. Learn how Deep learning relies on GPU eco system helping the research and data science community to solve use cases in domains like Healthcare, Autonomous Driving, Financial and many more.

Abstract: This talk discusses the nature of software engineering from multiple perspectives, its historical contributions, and presents a future perspective based on current research trends. What can Software Engineering do for the design of AI/ML systems? Are they energy efficient?

Abstract: For many years, practitioners have been interested in solving optimization and AI related problems to find a single acceptable solution. With the advent of efficient methodologies and human quest for knowledge, optimization and AI systems are now embedded with existing knowledge or modified to extract essential knowledge with which they solve problems. Efforts to explain AI systems with interpretable rules are also getting attention. In this talk, we present knowledge-driven optimization and explainable AI applications using a novel nonlinear decision tree approach in solving a variety of practical problems.

Abstract: Future is about a large complex system of systems that need to operate in an increasingly dynamic environment where the changes cannot be deduced a-priori. Typically, a complex system of systems is understood in terms of its various parts and interactions between them. Moreover, this understanding is typically partial and uncertain from which the overall system behavior emerges over time. With the overall system behavior hard to know a-priori and conventional techniques for system-wide analysis either lacking in rigor or defeated by the scale of the problem, the current practice often exclusively relies on human expertise for analysis and synthesis leading to decision-making. This is a time-, effort-, cost- and intellect-intensive endeavor. The talk will present an approach aimed at overcoming these limitations and also illustrate its efficacy on a few representative real-world problems.