Talks by visitors to the Department
2025 talks
- Online, greedy, and conceptually simple algorithms
Abstract:Speaker: Allan Borodin, University of Toronto
Date: 2025-01-24 Time: 12:00:00 (IST) Venue: #501, Bharti Building What can and cannot be computed by “conceptually simple algorithms"? In this regard, my primary interest is on approximation algorithms for combinatorial optimization problems and the relation of such problems to areas such as scheduling, algorithmic game theory and computational social choice.
Why do we care about conceptual simplicity, and can we formalize such a concept? For some problems, simple algorithmic ideas provide the best-known solution or are reasonably competitive with the best-known algorithms especially in the context of real data. Moreover, “in
practice", it is often the case that users will opt for a quick understandable algorithm. While it is arguably impossible to precisely define a useful general definition of “simplicity", we can study well used (albeit rarely precisely defined) combinatorial algorithmic paradigms such as various forms and extensions of online and greedy algorithms, primal dual algorithms, local search, and “simple" dynamic programming. Can we then provide definitions for such paradigms that are sufficiently expressive so as to capture many or most existing algorithms, but still allow us to prove impossibility results that do not rely on computational complexity assumptions? To what extent is our theoretical analysis consistent with performance in practice? We will consider the specific problem of online interval selection in different online settings. In particular we will consider the problem in the random order arrival model when the online algorithm has the ability to permanently reject previously accepted intervals.
Bio:prof. , University of Toranto
- Cybersecurity: Why it’s hard, solutions, and careers
Abstract:Speaker: Rajeev Barua, University of Maryland.
Date: 2025-01-21 Time: 12:00:00 (IST) Venue: Bharti-501 The battle between cyber attackers and attack detection teams is an arms race that is not letting up. Attackers constantly devise new ways of exploiting system vulnerabilities, and new methods to hide from detection. In response, detection teams have responded with new technologies to detect attacks.
This talk will overview why cybersecurity is hard, the solutions available, and the latest industry trends, and it will discuss careers in cybersecurity in India and worldwide.
Bio:Dr Rajeev Barua is a Professor of Electrical and Computer Engineering at the University of Maryland. He is also the Founder and CEO of SecondWrite Inc, which commercializes binary rewriting technology his research group developed at the university. He received his BTech in Computer Science from IIT Delhi, and his PhD in Computer Science and Electrical Engineering from the Massachusetts Institute of Technology in 2000. Dr Barua’s research interests are in the areas of program analysis, cybersecurity, and Applied AI.
Dr Barua is a recipient of the NSF CAREER award in 2002, the UMD George Corcoran Award for teaching excellence in 2003, and the UMD Jimmy Lin Award for innovation in 2014. He has published over 70 academic papers and five issued patents. His company, SecondWrite, has raised over [scripts/talks.php] [visitor] .4M in funding, including jumi.3M in US governments SBIR grants, and the rest from professional private investors.
- A Theory of Alternating Paths and Blossoms, from the Perspective of Minimum Length
Abstract:Speaker: Vijay V. Vazirani , University of California, Irvine.
Date: 2025-01-20 Time: 14:30:00 (IST) Venue: #501, Bharti Building It is well known that the proof of some prominent results in mathematics took a very long time — decades and even centuries. The first proof of the Micali-Vazirani (MV) algorithm, for finding a maximum cardinality matching in general graphs, was recently completed — over four decades after the publication of the algorithm (1980). MV is still the most efficient known algorithm for the problem. In contrast, spectacular progress in the field of combinatorial optimization has led to improved running times for most other fundamental problems in the last three decades, including bipartite matching and max-flow.
Bio:Vijay Vazirani is a distinguished professor at the University of California, Irvine. A description of his research appears in the citation of his 2022 INFORMS John von Neumann Theory Prize. In 2001, he published Approximation Algorithms, which was followed by two co-edited books, Algorithmic Game Theory in 2007 and Online and Matching-Based Market Design in 2023.
- Approximation Algorithms for the Minimum Non-Linear Arrangement Problem
Abstract:Speaker: Vignesh Viswanathan (University of Massachusetts Amherst)
Date: 2025-01-15 Time: 12:00:00 (IST) Venue: Bharti Building #404 The Minimum Non-Linear Arrangement problem asks, given an n-vertex undirected graph and a set of n nonnegative numbers, how to place the numbers on the vertices of the graph in a way that minimizes the sum of the edgewise absolute differences. This problem is a natural generalization of the well-studied minimum linear arrangement problem.
In this talk, I will present a simple cutwidth-based algorithm and analyze its approximation guarantees. I will then show that these guarantees cannot be improved by any other efficient algorithm (up to log factors) unless P = NP. Finally, I will present an attempt to eliminate the "up to log factors" caveat in the previous sentence; specifically, I will present a constant factor approximation for the special case when the graph is a complete binary tree.
This talk is based on joint work with Hadi Hosseini, Andrew McGregor, Justin Payan, Rik Sengupta, and Rohit Vaish.
Links: Paper 1 and Paper 2
Bio:Vignesh Viswanathan is a 5th-year PhD student at the University of Massachusetts Amherst, working under the supervision of Prof. Yair Zick. His current research focus revolves around problems in computational social choice. During his PhD, he has published papers at EC, AAMAS, WINE, and AAAI. Prior to his PhD, he received his bachelors from Indian Institute of Technology Kharagpur.
- Bridging Expressiveness and Performance for Service Mesh Policies
Abstract:Speaker: Divyanshu Saxena is a Ph.D. student at The University of Texas at Austin (UT Austin)
Date: 2025-01-08 Time: 12:00:00 (IST) Venue: Bharti-501 Cloud applications are increasingly migrating from monolithic applications to distributed microservice deployments. Distributed microservice applications require a convenient means of controlling L7 communication between services. Service meshes have emerged as a popular approach to achieving this. However, current service mesh frameworks are difficult to use -- they burden developers in realizing even simple communication policies, lack compatibility with diverse dataplanes, and introduce performance and resource overheads.
In this talk, I will discuss the root causes of these drawbacks and propose a ground-up new service mesh architecture that overcomes them. I will introduce novel abstractions for microservice communication that simplify policy specification and enable policy expression for diverse, heterogeneous dataplanes. I will then present a new mesh policy language, named Copper, centered on these abstractions to enable expressive policies. Finally, I will present a novel control plane, named Wire, that can enforce a given set of service mesh policies with provably minimal dataplane resources.
Evaluation of Copper Wire on realistic workloads and policies and open-source production traces shows that complex policies can be specified in up to 6.75× fewer lines, enforced with up to 2.6× smaller tail latencies and up to 39% fewer CPU resources than today. I will conclude the talk with some potential research directions on service mesh frameworks. This talk is based on joint work with William Zhang, Shankara Pailoor, Isil Dillig, and Aditya Akella (To appear in ASPLOS 2025).
Bio:Divyanshu Saxena (https://divyanshusaxena.github.io/) is a Ph.D. student at The University of Texas at Austin (UT Austin), advised by Prof. Aditya Akella. His research interest is broadly in the domain of Networked Systems, primarily focussing on: (a) microservice and serverless deployments, and (b) machine learning for systems. Before joining UT Austin, he completed his B.Tech. in Computer Science and Engineering from IIT Delhi in 2020.
- TensorRight: Automated Verification of Tensor Graph Rewrites
Abstract:Speaker: Jai Arora, an IITD alumnus who is currently doing his PhD at UIUC
Date: 2025-01-07 Time: 12:00:00 (IST) Venue: Bharti-501 Tensor compilers, essential for generating efficient code for deep learning models across various applications, employ tensor graph rewrites as one of the key optimizations. These rewrites optimize tensor computational graphs with the expectation of preserving semantics for tensors of arbitrary rank and size. Despite this expectation, to the best of our knowledge, there does not exist a fully automated verification system to prove the soundness of these rewrites for tensors of arbitrary rank and size. Previous works, while successful in verifying rewrites with tensors of concrete rank, do not provide guarantees in the unbounded setting. To fill this gap, we introduce TensorRight, the first automatic verification system that can verify tensor graph rewrites for input tensors of arbitrary rank and size. We introduce a core language, TensorRight DSL, to represent rewrite rules using a novel axis definition, called aggregated-axis, which allows us to reason about an unbounded number of axes. We achieve unbounded verification by proving that there exists a bound on tensor ranks, under which bounded verification of all instances implies the correctness of the rewrite rule in the unbounded setting. We derive an algorithm to compute this rank using the denotational semantics of TensorRight DSL. TensorRight employs this algorithm to generate a finite number of bounded-verification proof obligations, which are then dispatched to an SMT solver using symbolic execution to automatically verify the correctness of the rewrite rules. We evaluate TensorRight's verification capabilities by implementing rewrite rules present in XLA's algebraic simplifier. The results demonstrate that TensorRight can prove the correctness of 115 out of 175 rules in their full generality, while the closest automatic, bounded-verification system can express only 18 of these rules.
Bio:Jai Arora (https://jaiarora0011.github.io/) is a 2nd-year PhD student advised by Prof. Charith Mendis at University of Illinois Urbana-Champaign (UIUC). He is broadly interested in Compilers, Formal Methods, and Programming Languages. Currently, he is working on verifying optimizations in tensor compilers such as XLA. Before joining UIUC, he completed his Integrated Bachelor's and Master's in Computer Science and Engineering from IIT Delhi in 2023.
- New Approaches to Multi-Objective Optimization with Applications to Fairness and Online Learning
Abstract:Speaker: Jai Moondra, Georgia Tech
Date: 2025-01-06 Time: 12:00:00 (IST) Venue: #501, Bharti Building Real-world optimization problems often involve balancing competing objectives, such as fairness objectives in resource allocation or the trade-off between regret and runtime in online learning. Traditional approaches rely on predefined composite objectives, which (i) require fixing a composite objective a priori (ii) can pose challenges to policymakers in selecting appropriate trade-offs and (iii) lead to unintended biases in outcomes. In this talk, I will present new approaches for addressing these challenges. First, motivated by organ transplantation policies, we introduce "fairness portfolios" for optimization problems, which are small sets of solutions such that any fairness objective is approximately satisfied by some solution in the portfolio. We study the trade-off between portfolio size and solution quality for classical problems such as scheduling and facility location, giving new approximation algorithms and a primal-dual counting technique. I will also discuss applications to real-world settings.
Next, I will discuss the trade-off between regret and runtime in online learning problems. Drawing from applications in recommendation systems, we demonstrate how combining discrete and continuous techniques over submodular base polytopes can significantly reduce runtimes of optimal-regret algorithms such as Mirror Descent.
Bio:Jai Moondra is a fifth-year PhD student at the School of Computer Science at Georgia Tech, advised by Dr. Swati Gupta (MIT) and Dr. Mohit Singh (Georgia Tech). He completed his B.Tech. in Computer Science from IIT Delhi in 2019. His research focuses on discrete optimization and its applications to algorithmic fairness, quantum computing, and machine learning.
- Leveraging LLMs for Networking & Security in Cloud Environments
Abstract:Speaker: Deepak Bansal, Microsoft
Date: 2025-01-03 Time: 16:00:00 (IST) Venue: Bharti-501 Customer networks have grown, mostly organically, large and complex in cloud environments like Azure. Customers are often afraid to make changes and find it hard to diagnose when things go wrong. In this talk, I am going to share how Microsoft is using LLMs to simplify network operations at scale in Azure and how it is enabling the same for its customers through Azure Copilot. On the security side, I will share how LLMs are being used to enable security monitoring and threat hunting.
Bio:Deepak graduated from IIT D in CS in 1999 and did a Master’s in CS at MIT. He is currently a Corp Vice President and Technical Fellow at Microsoft in Redmond, WA USA and is driving cloud (Azure infrastructure) and security (Microsoft’s Secure Future Initiative).
2024 talks
- From theory to practice: the Marvelous journey of Mighty MPC
Abstract:Speaker: Prof. Arpita Patra, Associate Professor, IISc
Date: 2024-12-20 Time: 11:00:00 (IST) Venue: Bharti-501 Secure Multi-party Computation (MPC) is the standard-bearer and holy-grail problem in Cryptography that permits a collection of data-owners to compute a collaborative result, without any of them gaining any knowledge about the data provided by the other, except what is derivable from the result of the computation. The area was introduced in the seminal work of Yao in 1982. Since then the theory of MPC has seen some of the most fundamental results in theory of computation. Technology follows techniques and so a huge effort has gone in for turning techniques of MPC to technology. In this talk, I plan to cover the contribution we made towards solving real-world problems via applied MPC. The broad domains we tackle include social good, Health, FinTech and Smart cities.
Bio:Arpita Patra is presently an Associate Professor at Indian Institute of Science. She served as a visiting faculty at Silence Laboratories, Singapore in 2024 and as a visiting faculty researcher at Google Research between 2022-2023. Her area of interest is Cryptography, focusing on theoretical and practical aspects of secure multiparty computation protocols. She received her PhD from Indian Institute of Technology (IIT), Madras and held post-doctoral positions at University of Bristol, UK, ETH Zurich, Switzerland, and Aarhus University, Denmark.
Her research has been recognized with Prof. S. K. Chatterjee Award for Outstanding Woman Researcher or Industry Leader 2023 by IISc (2023), Google Privacy Research Faculty Award 2023, J P Morgan Chase Faculty Award 2022, SONY Faculty Innovation Award 2021, Google Research Award 2020, NASI Young Scientist Platinum Jubilee Award 2018, SERB Women Excellence award 2016, INAE Young Engineer award 2016 and associateships with various scientific bodies such as Indian Academy of Sciences (IAS), National Academy of Engineering (INAE ), The World Academy of Sciences (TWAS). She has coauthored a textbook on Multi-party Computation titled “Secure Multiparty Computation against Passive Adversaries” (published by Springer in 2023) and on consensus titled “Fault Tolerant Distributed Consensus in Synchronous Networks” (in press, Springer). - Global Search and Discovery with Differential Policy Optimization
Abstract:Speaker: Chandrajit Bajaj, UT Austin
Date: 2024-12-19 Time: 12:00:00 (IST) Venue: Bharti Building #501 Reinforcement learning (RL) with continuous state and action spaces is arguably one the most challenging problems within the field of machine learning. Most current learning methods focus on integral identities such as value (Q) functions to derive an optimal strategy for the learning agent. In this talk we present the dual form of the original RL formulation to propose the first differential RL framework that can handle settings with limited training samples and short-length episodes. Our approach introduces Differential Policy Optimization (DPO), a pointwise and stage-wise iteration method that optimizes policies encoded by local-movement operators. We prove a pointwise convergence estimate for DPO and provide a regret bound comparable with the best current theoretical derivation. Such pointwise estimate ensures that the learned policy matches the optimal path uniformly across different steps. We then apply DPO to a class of practical RL problems with continuous state and action spaces, e.g. shape and material optimization and discovery of new molecules with targeted dynamics.
This is joint work with Garvit Bansal, Minh Nguyen.
Bio:Chandrajit Bajaj, UT Austin
- New Algorithmic Challenges for Ethical Decision-Making
Abstract:Speaker: Swati Gupta, MIT
Date: 2024-12-09 Time: 12:30:00 (IST) Venue: #501, Bharti Building When someone is denied a job, offered a different price for the same goods or services, or declined a loan, intent to discriminate is often not the case. The decision system applies the same data and rules to all and yet has a disproportionate effect on various groups. The causes of such disparate impact in machine learning and optimization are many, and these create an opportunity for us to develop new algorithms. I will present three such opportunities. The first is motivated by challenges due to bias and errors in evaluation data. I will present new optimization problems using ordinal data, which can create a pathway to solving discrimination in hiring (Management Science, 2023 with Salem, and UC Davis Law Review, 2023 with Salem and Desai). Next, I will discuss the challenge of selecting the “right” notion of fairness. I will present the concept of “portfolios”, that ask to find a small set of approximate solutions that summarize the set (potentially infinite) set of fairness objectives. I will showcase combinatorial techniques to tackle this challenge, and connections to polyhedral structure (EC 2023, SODA 2025, with Singh and Moondra). Finally, motivated by the recent lawsuits on price fluctuations, I will discuss challenges in trajectory-constrained stochastic optimization, which for example, can provide algorithms that monotonically change prices in demand learning (WINE 2022, with Kamble and Salem). This talk is based on joint work with Jad Salem, Deven Desai, Mohit Singh, Jai Moondra, and Vijay Kamble.
Bio:Dr. Swati Gupta is an Associate Professor at the MIT Sloan School of Management in the Operations Research and Statistics Group, and holds the Class of 1947 Career Development Professorship. She received a Ph.D. in Operations Research from MIT, and a dual Bachelors + Masters in Computer Science and Engineering from IIT Delhi. Her research interests include optimization and machine learning, with a focus on algorithmic fairness. Her work is cross-disciplinary and spans various domains such as hiring, admissions, e-commerce, healthcare, districting, power systems, and quantum optimization. She served as the lead of Ethical AI for the NSF AI Institute on Advances in Optimization, from 2021-2023. She has received the NSF CAREER Award in 2023, the JP Morgan Early Career Faculty Recognition in 2021, the NSF CISE Research Initiation Initiative Award in 2019, Simons-Berkeley Research Fellowship in 2017-2018, and the Google Women in Engineering Award (India) in 2011. Dr. Gupta’s research is partially funded by the National Science Foundation (NSF) and Defense Advanced Research Projects Agency (DARPA), as well as Social and Ethical Responsibilities in Computing (SERC) at MIT.
- Where old meets new: Digitization of documents in Serbian
Abstract:Speaker: Anastazia Zunic,
Date: 2024-12-09 Time: 10:00:00 (IST) Venue: #501, Bharti Building Digital humanities is an interdisciplinary field which brings together traditional humanities and computer science to study cultural and historical data. Numerous tools and platforms are being utilised in digital humanities to advance and enrich work with digitized documents. At the core of these tools are complex machine learning algorithms for image and text processing, trained on appropriately prepared document repositories. Their most common functionalities include image quality enhancement, document layout analysis, optical character recognition, and text post-correction. In this talk, we will explore the experiences gained from using modern open-source tools for digitizing documents in Serbian. The existing tools are designed to address individual steps in the digitization process or the complete end-to-end pipeline. The resources used for testing these tools include periodicals published from the mid-19th century to the mid-20th century, provided by the National Library of Serbia. These periodicals are characterized by a great diversity of graphic elements, non-standard formats, physical degradation, and lower-quality scans. Along with the observed advantages and limitations of these tools, we will discuss ways to further expand and adapt them to the Serbian language. Special attention will be given to the role of language technologies and scenarios where their use is essential.
Bio:Anastazia Zunic, Mathematical Institute of the Serbian Academy of Sciences and Arts, Serbia
- "Curious Case of AI in Maths: Being proficient in advancing open conjectures in Maths yet having struggles in AI for Education"
Abstract:Speaker: Ankit Anand
Date: 2024-12-05 Time: 16:00:00 (IST) Venue: SIT #113 AI has made great strides in multiple domains including robotics, game playing, biology and climate science etc. The story in AI for maths has a bizarre story . On the one hand, we use AI methods for developing new lower bounds for a simple yet open problem in extremal graph theory proposed by Erdos in 1975. On the other hand, we describe our approach of developing a robust evaluation in AI for Education especially in math benchmarks.
Firstly, we will describe our recent work on studying a central extremal graph theory problem inspired by a 1975 conjecture of Erdős. We formulate the graph generation problem as a sequential decision-making problem and compare AlphaZero, a neural network-guided tree search, with tabu search, a heuristic local search method. Using curriculum, we improve the state-of-the-art lower bounds for several sizes for this problem.
Secondly, we describe how advances in generative AI (gen AI) have created excitement about the potential of new technologies to offer a personal tutor for every learner The full extent of this dream, however, has not yet materialised. We argue that this is primarily due to the difficulties with verbalising pedagogical intuitions into gen AI prompts and the lack of good evaluation practices, reinforced by the challenges in defining excellent pedagogy. We particularly focus on reasoning challenges in math tutoring where we argue reasoning is just beyond problem solving and although current models have improved a lot in solving problems yet fails on simple aspects like identifying mistakes in partially correct solutions. We even argue how tutoring could in fact be seen as a turing test for reasoning in LLMs.
Bio:Ankit Anand is currently a Staff Research Scientist at Google DeepMind Montreal, an adjunct faculty member at McGill University and associate industry member at MILA. He is working with Prof. Doina Precup in Montreal. His research interests lie at the intersection of logical methods, neural networks and reinforcement learning in general and particularly, applying AI and ML to make advances in Mathematics as well as AI for Education. Previously, he completed his Ph.D at IIT Delhi working with Prof. Mausam and Prof. Parag Singla. During his Ph.D, he worked on making symmetry aware A.I algorithms in context of probabilistic graphical models and Monte Carlo Tree Search algorithms.
- How Do We Involve People in AI Decision-Making? Towards Effective Participatory AI Designs
Abstract:Speaker: Vijay Keswani, Duke University
Date: 2024-11-29 Time: 12:00:00 (IST) Venue: Bharti Building #501 The expanding capabilities of AI come with a surge in the reports of societal and personal harms related to its use. Examples range from systemic biases in AI decision-aid tools in healthcare and policing to stereotype propagation in AI-based search and translation tools. Technical research on mitigating such harms forward certain solutions to ensure that AI behavior is aligned with ethical norms and values. Yet, this research leaves unanswered the question of "whose norms are followed" and can fail to counter AI harms when there is a disparity between the assumed ethical norms and the values of the people impacted by AI. But what if there was a way for the stakeholders (e.g., AI users or domain experts) to tell us how an AI tool should ideally operate?
In this talk, I will argue for democratizing how we build AI tools and undertaking a participatory approach to AI assessment and development. By eliciting feedback from relevant stakeholders on the harms they observe and the outcomes they expect, AI models can be aligned with the expressed stakeholder values. We will see concrete illustrations of such participatory mechanisms for image search audits, multi-winner elections, and medical decision-making. Across these applications, certain features of participation in AI will become clear: (a) participatory designs are domain-specific, (b) their efficacy relies heavily on the effectiveness of mechanisms used for eliciting stakeholder preferences, and (c) (when done right) they enhance user agency and trust in AI tools.
Bio:Vijay Keswani is a Postdoctoral Associate at Duke University. His research interests center around community-focused AI development and the ethics of data and technology. His work leverages tools from various disciplines to build robust AI models, combining computational and statistical learning mechanisms with methods from law, philosophy, psychology, and economics. He received his PhD from Yale University in 2023. While at Yale, he was a Resident Fellow at the Information Society Project during 2022-2023 and a 2022 Policy Fellow at the Yale Institute for Social and Policy Studies.
- Fine-Grained Segmentation and Control of Materials
Abstract:Speaker: Prafull Sharma, Post Doc
Date: 2024-11-25 Time: 11:00:00 (IST) Venue: SIT #001 With the recent advancements in computer vision and graphics, scene understanding has become critical for both downstream applications and photorealistic synthesis. Tasks such as image classification, semantic segmentation, and text-to-image generation parse scenes in terms of high-level object and scene properties. Beyond these dimensions, it is equally important to understand low-level information, including geometry, material, lighting configuration, and camera parameters. Such understanding facilitates tasks like material acquisition, fine-grained synthesis, and robotics. In this talk, we will focus on recent works that use synthetic data rendered in graphics renderers and representations from pre-trained models for material segmentation and editing, specifically discussing the following papers: Materialistic: Selecting Similar Materials in Images (SIGGRAPH 2023) and Alchemist: Parametric Control of Material Properties with Diffusion Models (CVPR 2024). Materialistic introduces a method for selecting regions in images with the same material properties, leveraging unsupervised DINO features and a Cross-Similarity module trained on synthetically rendered data. Alchemist employs diffusion models fine-tuned on synthetic datasets to control material attributes such as roughness, metallicness, albedo, and transparency in real images.
Bio:Prafull Sharma is a Postdoctoral Associate working with Prof. Josh Tenenbaum and Prof. Phillip Isola in the Computer Science and Artificial Intelligence Lab (CSAIL) and Brain and Cognitive Science (BCS) department at MIT on world modeling. During his PhD, he was advised by Prof. Bill Freeman and Prof. Fredo Durand in the Computer Vision and Graphics group at MIT CSAIL. His research focuses on representation learning grounded in physical properties using synthetic data. He is interested in leveraging the priors of pre-trained models to obtain disentangled representations grounded in the physic
- Algebraic complexity classes and their characterizations
Abstract:Speaker: Prasad Chaugule
Date: 2024-11-25 Time: 12:30:00 (IST) Venue: #501, Bharti Building The main central question in the algebraic complexity theory is "VP vs. VNP," where the class VP is the algebraic analog of the boolean class P and the class NP is the algebraic analog of the counting version of the boolean class NP, which is #P. By definition, the class VP sits inside the class VNP, but whether the containment is strict is not known. While these classes are widely believed to be different, the lower bounds are hard to prove. As it is always meaningful to characterize the classes in other ways, one way to characterize such a class is to find a polynomial sequence complete for the class. Permanent (counting weighted perfect matching in a complete bipartite graph) is known to be VNP complete (for fields of characteristic not equal to 2). Almost a decade ago, there were no polynomial sequences (independent of the computational model) known to be VP complete. Durand et al. [1] gave new model-independent polynomial sequences complete for the class VP, which were based on the notion of counting weighted homomorphisms between two graph sequences (G_n) and (H_n). This line of work was later extended by Mahajan et al. [2] and Chaugule et al. [3].
In this talk, we will discuss a new polynomial sequence that is shown to be VP-complete for large enough fields. We show that counting weighted homomorphisms from a Log-Depth (log n) perfect complete binary tree to a complete graph of size, say poly(n), is VP complete. Moreover, we show that counting weighted homomorphisms from a path of length n to a complete graph of size poly(n) characterizes the class VBP (VBP is in VP). We will also discuss the characterizations of the classes VP and VNP by an algebraic branching program appended by a stack-like memory/random access memory due to Mengel [4] and new results/ideas in this context.
[1] Homomorphism Polynomials Complete for VP. FSTTCS 2014: 493-504
[2] Some Complete and Intermediate Polynomials in Algebraic Complexity Theory. CSR 2016
[3] Variants of Homomorphism Polynomials Complete for Algebraic Complexity Classes. COCOON 2019
[4] Arithmetic Branching Programs with Memory. MFCS 2013
Bio:MS Teams link: https://teams.microsoft.com/l/meetup-join/19%3ameeting_OTFlOTNmNzAtNWZlYi00YmMzLTg2NWItNjJiN2E4OWI0ZDUw%40thread.v2/0?context=%7b%22Tid%22%3a%22624d5c4b-45c5-4122-8cd0-44f0f84e945d%22%2c%22Oid%22%3a%221b7f86d4-5db1-499a-8627-45898b91c9a0%22%7d
- Probabilistic Generating Circuits - Demystified
Abstract:Speaker: Sanyam Agarwal, Saarland University
Date: 2024-11-13 Time: 16:00:00 (IST) Venue: #501, Bharti Building Zhang et al. (ICML 2021, PLMR 139, pp. 12447–1245) introduced probabilistic generating circuits (PGCs) as a probabilistic model to unify probabilistic circuits (PCs) and determinantal point processes (DPPs). At a first glance, PGCs store a distribution in a very different way, they compute the probability generating polynomial instead of the probability mass function and it seems that this is the main reason why PGCs are more powerful than PCs or DPPs. However, PGCs also allow for negative weights, whereas classical PCs assume that all weights are nonnegative. One of the main insights of our paper is that the negative weights are responsible for the power of PGCs and not the different representation. PGCs are PCs in disguise, in particular, we show how to transform any PGC into a PC with negative weights with only polynomial blowup. PGCs were defined by Zhang et al. only for binary random variables. As our second main result, we show that there is a good reason for this: we prove that PGCs for categorial variables with larger image size do not support tractable marginalization unless NP = P. On the other hand, we show that we can model categorial variables with larger image size as PC with negative weights computing set-multilinear polynomials. These allow for tractable marginalization. In this sense, PCs with negative weights strictly subsume PGCs.
Bio:(https://sanyamagarwal7.github.io/
- Interactive Cognition and Haptics
Abstract:Speaker: Dr. Madhan Kumar Vasudevan
Date: 2024-11-06 Time: 12:00:00 (IST) Venue: Bharti Building #501 Haptics, the exploration of touch-based interaction, is becoming an essential part of Human-Computer Interaction (HCI), influencing how we engage with both digital and physical systems. From enhancing immersive experiences in virtual environments to creating tools for improving fine motor skills and addressing sensorimotor impairments, haptic feedback is transforming the way humans interact with technology. My research explores the intersection of sensory perception, emotion, human cognition, and engineering, aiming to develop haptic technologies that enrich and deepen user experiences through innovative design and technical advancements. In this talk, I will present a series of research projects that highlight how haptics can be leveraged to shape user interaction in HCI. Starting with computational models of vibration receptors in the skin to understand neurophysiology and moving on to interactions in virtual reality environments where vibrotactile feedback enhances fine motor skills training, I will explore both human perception and interaction methods. Furthermore, I will discuss my recent exploration of affective touch communication and mindfulness meditation combined with mid-air haptic technology—a form of haptic feedback that delivers tactile sensations through ultrasound waves in mid-air, without physical contact—which has been shown to enhance sensory perception and emotional well-being. By focusing on the integration of haptic technology within HCI frameworks, these projects demonstrate how touch-based interfaces can foster more intuitive, emotionally engaging, and human-centered interactions. Through this research, we can enhance user experience in diverse fields ranging from virtual environments to healthcare, ultimately making technology more responsive to human needs and emotions.
Bio:Dr. Madhan Kumar Vasudevan is a Postdoctoral Research Fellow at University College London (UCL), specializing in Human-Computer Interaction (HCI), computational neuroscience, and haptics. He earned his Ph.D. from the Indian Institute of Technology (IIT) Madras, where he contributed to the study of sensory perception, haptic technology, and virtual/extended reality interactions, particularly in the computational modeling of vibration receptors. His current research focuses on affective computing, specifically on how emotions can be conveyed through mid-air haptics, with the goal of enabling intuitive, long-distance touch communication to enhance emotional connections in remote interactions. In addition to his postdoctoral work, Dr. Madhan has secured funding from the UCL Institute of Healthcare Engineering and led cross-cultural research initiatives on healthy aging, in collaboration with IIT Madras and UCL Computer Science. He has published extensively in top-tier conferences such as CHI and World Haptics, and served as an Associate Chair for CHI 2024. He has actively mentored students in HCI research at UCL and demonstrated his commitment to public engagement through co-production workshops with elderly communities in both the UK and India, focusing on cross-cultural nuances in sensory experiences and healthy aging.
- Logic and asymptotic combinatorics of Graph Neural Networks.
Abstract:Speaker: Prof. Michael Benedikt
Date: 2024-11-01 Time: 14:00:00 (IST) Venue: Bharti Building #501 Graph neural networks (GNNs) are the predominant architectures for a variety of learning tasks on graphs. We present a new angle on the expressive power of GNNs by studying how the predictions of a GNN probabilistic classifier evolve as we apply the classifier on larger graphs drawn from some random graph model. We show that the output converges asymptotically almost surely to a constant function, which upper-bounds what these classifiers can express uniformly.
Our convergence results are framed within a query language with aggregates, subsuming a very wide class of GNNs, including state of the art models, with aggregates including mean and the attention-based mechanism of graph transformers. The results apply to a broad class of random graph models, but in the talk we will focus on Erdős-Rényi model and the stochastic block model. The query language-based approach allows our results to be situated within the long line of research on convergence laws for logic.
The talk will include joint work with Sam Adam-Day, Ismail Ceylan, and Ben Finkeshtein -- see https://arxiv.org/abs/2403.03880, and also joint work with Sam Adam-Day and Alberto Larrauri.
Bio:Prof. Michael Benedikt (https://www.cs.ox.ac.uk/people/michael.benedikt/home.html) from the University of Oxford
- Improvising the Generalizability of Meta-learning Approaches for Few-shot Learning.
Abstract:Speaker: Dr. Aroof Aimen
Date: 2024-10-25 Time: 17:00:00 (IST) Venue: online Deep learning models often require large labeled datasets for training, which can be difficult to obtain in real-world scenarios. To address this, few-shot learning has emerged as a key area in machine learning, aiming to train models effectively with minimal data and enabling them to generalize to new, unseen instances. Meta-learning offers a promising approach for few-shot learning but relies on several assumptions about task distributions, meta-knowledge, and evaluation setups. This talk will focus on the assumption concerning task distribution, specifically addressing Support-Query Shifts (SQS). The concept of SQS is extended to a more practical scenario, termed SQS+, which involves unknown support-query shifts during meta-testing that may differ from the meta-training shift. Existing methods to handle SQS and SQS+ typically use transductive approaches that require unlabeled query data during meta-testing. An inductive approach Adversarial Query Projection (AQP) is introduced which is designed to address both SQS and SQS+ without relying on unlabeled query data. AQP introduces adversarial perturbations to the query sets, creating a deliberate gap between the support and query sets within a new virtual task. This approach leverages the inherent dissimilarity between the initial and perturbed distributions to encourage the model to learn robust, shift-resistant representations. As a result, AQP enhances the model's ability to handle diverse and unfamiliar distribution shifts during meta-testing.
Bio:Aroof Aimen is a Research Associate in the Department of Radiology at the University of Wisconsin-Madison. Her research focuses on applying machine learning techniques for diagnosing and predicting the progression of brain tumors. She is also working on foundational models for detecting neurological disorders. Aroof earned her Ph.D. from the Indian Institute of Technology, Ropar, where she specialized in machine learning within the computer science and engineering domain. Her dissertation, "Analyzing and Improving the Generalizability of Meta-Learning Approaches for Few-Shot Learning," concentrated on advancing meta-learning methods to enhance generalization. She has also developed metrics for monitoring the training progress of Generative Adversarial Networks (GANs). Her research has been featured in top-tier machine learning conferences and journals, including ECML, ICML, and Transactions on AI. During her Ph.D., Aroof completed a one-year research internship at Wadhwani AI, focusing on machine learning models for disease detection from chest X-rays, particularly in low-resource settings. Outside of her academic work, Aroof enjoys traveling and trying new cuisines.
- Presburger Arithmetic : Quantifier Elimination and Some Applications.
Abstract:Speaker: Dr. Khushraj Nanik Madnani
Date: 2024-10-23 Time: 12:00:00 (IST) Venue: #501, Bharti Building In this talk, we revisit the fundamental problem of quantifier elimination in Existential Presburger Arithmetic. Presburger Arithmetic (equivalently Linear Integer Arithmetic) is a decidable fragment of first-order logic over the integers with addition(+) and order(<,=), and it is widely used in formal verification, logic, and model checking. Existential Presburger Arithmetic is a fragment of Presburger Arithmetic containing only existential quantifiers. Quantifier elimination is a fundamental problem in First Order Theories, which involves transforming a formula with quantifiers (existential and for all) into an equivalent formula without them, while maintaining the same logical meaning, and has wide applications in the domain of automated reasoning and formal verification.
Historically, quantifier elimination in Existential Presburger Arithmetic has been believed to require doubly exponential time. As the main highlight of this talk, we challenge this long-standing claim. Our recent work refutes this by introducing a novel procedure which accomplishes quantifier elimination for the existential fragment of Presburger Arithmetic in singly exponential time. The core of our approach is a small model property for parametric integer programming, which extends the seminal results of von zur Gathen and Sieveking on small integer points within convex polytopes. Additionally, if time permits, I will discuss a compelling application of Presburger Arithmetic in proving a dichotomy related to the reachability problem for counter machines (automata extended with integer variables) with infrequent reversals.
Bio:Khushraj Madnani is a postdoctoral researcher at the Max-Planck Institute for Software Systems in Kaiserslautern, Germany, associated with the Rigorous Software Engineering group and the Models of Computation group. His research interest is broadly within the domain of formal verification of infinite-state systems, focusing primarily on (1) automata and logics for timed systems, (2) formal logics and models of computation, and (3) network controlled cyber physical systems.
Khushraj completed his Master's and Ph.D. in Computer Science and Engineering at the Indian Institute of Technology (IIT) Bombay, Mumbai, India, under the guidance of Prof. S. Krishna and Prof. Paritosh K. Pandya where he defended his thesis titled "On Decidable Extensions of Metric Temporal Logic".
Before joining the Max-Planck Institute, Khushraj was a postdoctoral researcher at the Delft Center for Systems and Control (DCSC) within the Faculty of Mechanical Engineering at Delft University of Technology, The Netherlands. He also served as a visiting postdoctoral fellow at the Tata Institute of Fundamental Research (TIFR) in Mumbai, India.
- Recent Advances in Polynomial Identity Testing
Abstract:Speaker: Pranjal Dutta from NUS
Date: 2024-10-16 Time: 12:00:00 (IST) Venue: #501, Bharti Building Polynomial Identity Testing (PIT) is the problem of testing whether a succinctly given polynomial is zero. Though efficient randomized algorithms exist, derandomizing PIT is a fundamental challenge with remarkable consequences in algebraic complexity theory and various classical algorithmic problems. Significant progress has been made on this problem in the last decade. In this talk, we will present a comprehensive overview of these recent developments and discuss a few techniques behind them.
This survey talk is based on many recent papers on PIT, and the survey, jointly written with Sumanta Ghosh (CMI), which got invited and published in the ACM SIGACT Complexity Theory Column; one can find it here: https://dl.acm.org/doi/10.1145/3674159.3674165.
Bio:Pranjal Dutta (https://sites.google.com/view/pduttashomepage) is currently a Postdoc at the School of Computing, NUS, hosted by Prof. Divesh Aggarwal. His broad research area is Complexity theory. He finished his PhD in Computer Science (2018-2022), from Chennai Mathematical Institute (CMI), under the guidance of Prof. Nitin Saxena (IIT Kanpur). He was a Google PhD Fellow (2018-2022) and subsequently, he won the ACM India Doctoral Dissertation Award 2023. He obtained his bachelor's in Mathematics and Computer science (2013-2016) and master's in Computer science (2016-2018) both from CMI.
- Bridging the Theory and Practice of Cryptography
Abstract:Speaker: Ashrujit Ghoshal, Carnegie Mellon University
Date: 2024-10-10 Time: 16:00:00 (IST) Venue: online In the current internet landscape, cryptography plays a central role in securing communication. We rely on mathematical proofs to ensure security of the cryptographic systems that are deployed in practice. However, in many cases, due to issues like efficiency constraints, there is a gap between what these deployments need and what we can prove. In this talk, I will describe how my research identifies these gaps and makes progress towards bridging these gaps using new theoretical insights and techniques from different areas of computer science like complexity theory, algorithms, combinatorics, information theory, etc.
More concretely, my work contributes towards bridging these gaps in three different ways. First, I provide exact security analyses of cryptographic systems that have been deployed at scale that did not have such analyses before. With the exact analyses available, practitioners can set parameters of the cryptographic system in a way that maximizes efficiency without sacrificing security. Secondly, I construct new cryptographic schemes that are better than existing schemes in terms of efficiency. This work helps make purely theoretical cryptographic notions practical. Finally, my work incorporates newer perspectives into the framework of security proofs that captures a more complete picture of the real world. This is in contrast to prior work where only certain adversarial resources were taken into account. A more complete picture of adversarial resources often helps in setting parameters in a way that increases efficiency of cryptographic systems.
Bio:Ashrujit Ghoshal is a postdoctoral fellow at Carnegie Mellon University. He received his PhD from the University of Washington in 2023. His research focuses on bridging the gap between the theory and practice of cryptography by developing new theory that characterizes security and efficiency of cryptographic systems as precisely as possible. In particular his work has provided exact security analyses for cryptography that is widely used in practice e.g., standard hash functions like SHA-2 and SHA-3, TLS, etc. His work has also made progress towards making theoretical cryptographic functionalities like private information retrieval more practical by giving new concretely efficient constructions. These works have led to multiple papers at the two top cryptography conferences- CRYPTO and EUROCRYPT.
- Brick Kiln Detection from low-resolution satellite imagery
Abstract:Speaker: Zeel, IIT Gandhinagar
Date: 2024-10-09 Time: 16:00:00 (IST) Venue: SIT #001 Air pollution kills 7 million people annually. The brick manufacturing industry is the second largest consumer of coal, contributing to 8%-14% of air pollution in the Indo-Gangetic plain. Due to the unorganized nature of brick kilns, monitoring their compliance with evolving national policies is challenging. Air quality experts digitally locate the brick kilns using tools such as Google Earth. Previous work has employed computer vision to detect brick kilns from high-resolution imagery which is costly and has barriers for the open research due to licensing issues. In this work, we explore low-resolution Sentinel-2 imagery (10m) for brick kiln detection, which is available freely for anyone to download and redistribute. We use YOLO's oriented object detection variant to detect the kilns. After detection, we show the automatic compliance monitoring with the detected kilns which can be immensely helpful for the policy executors including but not limited to the pollution control boards.
Bio:Zeel is a PhD student in Computer Science and Engineering at the Sustainability lab, IIT Gandhinagar advised by Prof. Nipun Batra. His research area of interest is AI for Social Good. Zeel has recently received Microsoft Research PhD Fellowship award. He was a Google Summer of Code contributor at TensorFlow in 2022. Zeel has co-authored the "Active Learning" section in the latest addition of a well-known ML book, "Probabilistic Machine Learning" by Kevin Murphy.
- ApneaEye: Thermal-Imaging Based Respiration Sensing for Sleep Apnea Diagnosis
Abstract:Speaker: Dr. Nipin Batra, IIT Gandhinagar
Date: 2024-10-09 Time: 17:00:00 (IST) Venue: SIT #001 Sleep apnea, a sleep disorder characterized by breathing pauses during sleep has a global prevalence of approximately one billion people and is associated with an increased risk of heart attack and stroke. The gold standard of diagnosing sleep apnea requires instrumenting a person with various sensors during her sleep to extract respiratory parameters like nasal airflow and thoracoabdominal movement. Prior works have investigated non-contact methods of diagnosing apnea but they are limited because i) they sense only either thorax or abdomen movements, and ii) they are evaluated on subjects under controlled sleeping conditions. In this work, we present textit{ApneaEye}: a low resolution non-contact thermal camera based system that senses i) nasal airflow and ii) thoracoabdominal movement to diagnose apnea and its types. We evaluated the system on 44 participants including 24 individuals with a sleep apnea who slept unobtrusively overnight. Our results show that ApneaEye can sense respiration from temperature differences between inhalation and exhalation and thoracoabdominal movement with an error of 0.33 and 0.57 BrPM (Breaths Per Minute), respectively. Using these two respiration signals, ApneaEye also estimates apnea and hypopnea instances with a Mean Absolute Error (MAE) of 1.6 and 0.6 respectively in comparison to the gold standard. Our work shows that it is possible to identify other sleep-related complications like thoracoabdominal asynchrony and causes of sleep apnea like nasal blockage by monitoring the thermal data. ApneaEye promises to aid in the diagnosis and management of sleep apnea without the need for in-contact sensors or in-situ training data or personalization.
Bio:Nipun Batra is an Assistant Professor in Computer Science at IIT Gandhinagar. He previously completed his postdoc from University of Virginia. He completed his PhD. from IIIT Delhi where he was a TCS PhD fellow. His group called the Sustainability Lab broadly works on machine learning and sensing for computational sustainability problems like smart buildings, air quality and wearable healthcare. His work has been awarded several awards, including, young alumni award from IIIT Delhi, the best PhD presentation at ACM Sensys, best demo at ACM Buildsys, and a best video nominee at ACM.
- John Gardner’s Adventures in Information Accessibility
Abstract:Speaker: Prof. John Gardner, ViewPlus
Date: 2024-10-07 Time: 15:00:00 (IST) Venue: SIT #001 This is not a scientific lecture. It is a personal accounting of adventures and misadventures that have led to me standing before an audience at IIT Delhi. I will explain the reasons that led me to begin research on accessibility to complex information and why today my work is primarily on accessibility of graphical information. I will also describe at least briefly the developments that have been made in my Oregon State University lab and at ViewPlus. And of course, I will paint a picture of what is being developed today and what I see as the future of information accessibility by people with visual disabilitie
Bio:John Gardner is a physicist who lost his sight in mid-career as Professor of Physics at Oregon State University. He was born with only one eye and developed glaucoma as a small child. When eyedrops became ineffective in controlling the glaucoma, he underwent a “minor” operation to install a pressure valve. His eye reacted badly, and he lost his sight overnight. Prof. Gardner continued to do physics research but found it difficult to analyse the visually fitted data, so he established an accessibility institute at Oregon State University funded by the National Science Foundation. It was devoted to improving accessibility of math, science, graphics, and other complex information. In 1996 he founded ViewPlus Technologies, which has grown into a multi-million-dollar company producing information-access hardware and software. He has received numerous awards and has given invited presentations on both physics and information accessibility on five continents.
- ARMOUR: Architecting Selective Refresh based Multi-Retention Cache for Heterogeneous System
Abstract:Speaker: Dr. Sukarn Agarwal, IIT Guwahati
Date: 2024-10-03 Time: 11:00:00 (IST) Venue: online he increasing use of chiplets, and the demand for high-performance yet low-power systems, will result in heterogeneous systems that combine both CPUs and accelerators (e.g., general-purpose GPUs). Chiplet based designs also enable the inclusion of emerging memory technologies, since such technologies can reside on a separate chiplet without requiring complex integration in existing high-performance process technologies. One such emerging memory technology is spin-transfer torque (STT) memory, which has the potential to replace SRAM as the last-level cache (LLC). STT-RAM has the advantage of high density, non-volatility, and reduced leakage power, but suffers from a higher write latency and energy, as compared to SRAM. However, by relaxing the retention time, the write latency and energy can be reduced at the cost of the STT-RAM becoming more volatile. The retention time and write latency/energy can be traded against each other by creating an LLC with multiple retention zones. With a multi-retention LLC, the challenge is to direct the memory accesses to the most advantageous zone, to optimize for overall performance and energy efficiency. We propose ARMOUR, a mechanism for efficient management of memory accesses to a multi-retention LLC, where based on the initial requester (CPU or GPU) the cache blocks are allocated in the high (CPU) or low (GPU) retention zone. Furthermore, blocks that are about to expire are either refreshed (CPU) or written back (GPU). In addition, ARMOUR evicts CPU blocks with an estimated short lifetime, which further improves cache performance by reducing cache pollution. Our evaluation shows that ARMOUR improves average performance by 28.9% compared to a baseline STT-RAM based LLC and reduces the energy-delay product (EDP) by 74.5% compared to an iso-area SRAM LLC.
Bio:Dr. Sukarn Agarwal received his Ph.D. in Computer Science and Engineering from IIT Guwahati, India, in 2020. He is currently working as an assistant professor at EECS, IISER Bhopal. Before that, He was a Senior Research Fellow with the School of Informatics, University of Edinburgh, Edinburgh, U.K. His research interests include Emerging Memory Technologies, Memory System Design, Network-on-chip design, Thermal-Aware Cache Management, Memory Consistency, and Heterogeneous Systems. He has published seven journal papers and sixteen conference papers. He has received the best paper awards in VLSI-SOC 2017 and ISED 2018 and has received a TCS research fellowship.
- Recent progress on interpretable clustering
Abstract:Speaker: Prof. Sanjoy Dasgupta from UCSD
Date: 2024-09-23 Time: 12:00:00 (IST) Venue: #501, Bharti Building The widely-used k-means procedure returns k clusters that have arbitrary convex shapes. In high dimension, such a clustering might not be easy to understand. A more interpretable alternative is to constraint the clusters to be the leaves of a decision tree with axis-parallel splits; then each cluster is a hyperrectangle given by a small number of features.
Is it always possible to find clusterings that are intepretable in this sense and yet have k-means cost that is close to the unconstrained optimum? A recent line of work has answered this in the affirmative and moreover shown that these interpretable clusterings are easy to construct.
I will give a survey of these results: algorithms, methods of analysis, and open problems.
Bio:Sanjoy Dasgupta is Professor of Computer Science at UC San Diego. He works primarily on unsupervised and minimally supervised learning. He is the author of a textbook, Algorithms, with Christos Papadimitriou and Umesh Vazirani.
- Recent Advances in the Maker Breaker Triangle Game
Abstract:Speaker: Anand Srivastav, Kiel University, Germany
Date: 2024-09-20 Time: 12:00:00 (IST) Venue: #501, Bharti Building The triangle game introduced by Chvátal and Erdős (1978) is one of the old and famous combinatorial games. For n, q ∈ N, the (n,q)-triangle game is played by two players, called Maker and Breaker, on the complete graph K_n.
Alternately Maker claims one edge and thereafter Breaker claims q edges of the graph. Maker wins the game if he can claim all three edges of a triangle. Otherwise, Breaker wins. Chvátal and Erdős (1978) proved that for q < sqrt(n/2), Maker has a winning strategy, while for q > 2 sqrt(n), Breaker wins. So, the threshold bias must be in the interval [sqrt(1/2)sqrt(n) , 2 sqrt(n)].
Since then, the problem of finding the exact constant (and an associated Breaker strategy) for the threshold bias of the triangle game has been one of the interesting open problems in combinatorial game theory. In fact, the constant is not known for any graph with a cycle and we do not even know if such a constant exists. Balogh and Samotij (2011) slightly improved the Chvátal-Erdős constant for Breaker's winning strategy from 2 to 1.935 with a randomized approach. Thereafter, no progress was made. In this work, we present a new deterministic strategy for Breaker leading to his win if q > sqrt(8/3) sqrt(n), for sufficiently large n. This almost matches the Chvátal-Erdős bound of sqrt(1/2)sqrt(n) for Maker's win (Glazik, Srivastav, Europ.J.Comb.2022).
In contrast to previous (greedy) strategies, we introduce a suitable non-linear potential function on the set of nodes. By keeping the potential small, Breaker picks edges that neutralize the most 'dangerous' nodes with incident Maker edges blocking Maker triangles. A characteristic property of the dynamics of the game is that the total potential is not monotonely decreasing. In fact, the total potential of the game may increase, even for several turns, but finally Breaker's strategy prevents the total potential of the game from exceeding a critical level, which results in Breaker's win. We further survey recent and first results for Breaker's win for cycles of length k, a general potential function theorem, and a winning strategy for Maker for the C_4. (Sowa, Srivastav 2024)
This is joint work with Christian Glazik, Christian Schielke and Mathias Sowa, Kiel University.
Bio:Anand Srivastav, Kiel University, Germany
- On the Power of Interactive Proofs for Learning
Abstract:Speaker: Dr. Ninad Rajgopal
Date: 2024-09-18 Time: 16:00:00 (IST) Venue: #501, Bharti Building Interactive proof systems for delegating computation allow a resource-constrained client (or a verifier) to outsource a computational task to a powerful, yet untrusted server (prover). The goal of such a proof system is for the client to verify the result of the task using significantly fewer resources, than performing it from scratch, by interactively exchanging messages with the server who is required to prove the correctness of its computation. Such proof systems have found ubiquitous use in computational complexity theory, as well as for practical applications.
In this talk, we will first introduce a model by Goldwasser, Shafer, Rothblum and Yehudayoff (2021), for delegating a learning task to a server and interactively verifying its correctness. Following this we will see delegation proof systems for problems fundamental to the study of the computational complexity of learning, that allow for highly efficient verification in comparison with performing the learning task.
This is joint work with Tom Gur, Mohammad Mahdi Jahanarah, Mohammad Mahdi Khodabandeh, Bahar Salamatian, and Igor Shinkar (STOC 2024).
Bio:Dr. Ninad Rajgopal is a postdoctoral researcher at the University of Cambridge. He will be starting a post-doctoral position at Charles University, Prague. Prior to this, he was a postdoctoral researcher at the University of Warwick. He obtained his PhD in Computer Science from the University of Oxford advised by Prof. Rahul Santhanam, and Masters in Computer Science from IISc Bengaluru.
His research interests are broadly in complexity theory, with current focus on computational learning theory, probabilistic proof systems, circuit complexity, and meta-complexity.
- Exploring the Cookieverse: A Multi-Perspective Analysis of Web Cookies
Abstract:Speaker: Devashish Gosain, Assistant Professor, IITB
Date: 2024-09-12 Time: 12:00:00 (IST) Venue: #501, Bharti Building Web cookies serve various purposes, like keeping the user logged in or storing a user's preferences for multiple visits to the same website. However, besides their originally intended use, cookies have been exploited for commercial activities like user tracking and targeted advertisement. Thus, web cookies have been extensively studied over the last few years. However, most existing research does not consider multiple crucial perspectives that can influence the cookie landscape and may lead to incorrect inferences. These perspectives include the client's location and operating system, landing vs. inner web pages, desktop vs. mobile phone, and cookie banner interaction. In this talk, I will present the challenges in analyzing the cookie landscape due to these perspectives and elaborate on the methods we use to study them through our measurement research.
Our research demonstrates that "cookie banners" (or cookie notices) are one of the most crucial factors influencing the cookie ecosystem. They are essentially alert messages on the website allowing users to "accept" or "reject" cookies. Thus, we developed the first tool, BannerClick, to automatically detect, accept, and reject cookie banners with an accuracy of 99%. By using BannerClick on the Tranco top-10k websites from different geographic locations, we observe that websites send, on average, 5.5x more third-party cookies after clicking "accept," underlining that it is critical to interact with banners when performing Web measurement. Interestingly, we also found that a new form of paywall-like cookie banner has taken hold on the Web, allowing users to either accept cookies (and consequently user tracking) or buy a paid subscription for a tracking-free website experience. Thus, we performed the first completely automated analysis of cookiewalls, i.e., cookie banners acting as a paywall. We find cookiewalls on 0.6% of all queried 45k websites. Moreover, cookiewalls are deployed to a large extent on European websites, e.g., for Germany, we see cookiewalls on 8.5% of the top 1k websites.
Bio:Devashish Gosain completed his Ph.D. in 2020 from IIIT Delhi in Network Security. In his research, he studied how the knowledge of Internet structure (and maps) can be used to achieve efficient nation-scale traffic filtering. The research involved collecting actual network traces from different Indian ISPs and studying the filtering policies and websites blocked by them. After completing his Ph.D., he worked as a postdoctoral researcher in the INET research group at Max Planck Institute of Informatics, followed by a year postdoc at the COSIC research group at KU Leuven. During his postdoc, he worked on network security problems like measuring the anonymity of peer-to-peer networks, mitigating MITM attacks in end-to-end encrypted protocols (e.g., Signal), and measuring the impact of privacy laws like GDPR on user tracking, etc. His research has been published in the reputed security and networking venues like CCS, NDSS, INFOCOM, IMC, PETS, Usenix Security, ACSAC, PAM, etc. He is currently working as an assistant professor at IIT Bombay.
- Trust in the Untrusted World?
Abstract:Speaker: Divy Agrawal, Computer Science at the University of California
Date: 2024-08-23 Time: 11:00:00 (IST) Venue: SIT #001 We live in interesting times in that our digital lives have become increasingly interdependent and interconnected. Such interconnections rely on a vast network of multiple actors whose trustworthiness is not always guaranteed. Over the past three decades, rapid advances in computing and communication technologies have enabled billions of users with access to information and connectivity at their fingertips. Unfortunately, this rapid digitization of our personal lives is also now vulnerable to invasion of privacy. In particular, now we have to worry about the malicious intent of individual actors in the network as well as large and powerful organizations such as service providers and nation states. In the backdrop of this reality of the untrusted world, we raise the following research questions: (i) Can we design a scalable infrastructure for voice communication that will hide the knowledge of who is communicating with whom? (ii) Can we design a scalable system for oblivious search for documents from public repositories? (iii) Can we develop scalable solutions for private query processings over public databases? These are some of the iconic problems that must be solved before we can embark on building trusted platforms and services over untrusted infrastructures. In this talk, we present a detailed overview of a system for voice communication that hides communication metadata over fully untrusted infrastructures and scales to tens of thousands of users. We also note that solutions to the above problems rely on an intermediary service provider. We conclude this talk with an open question on the efficacy of a decentralized paradigm for cryptocurrency in the broader context of our digital lives that can potentially eliminate the need for an intermediary in provisioning trusted services and platforms.
Bio:Divy Agrawal is a Distinguished Professor and Chair of Computer Science at the University of California at Santa Barbara. He also holds the Leadership Endowed Chair in the Department of Computer Science at UCSB. He received BE(Hons) from BITS Pilani in Electrical Engineering and then received MS and PhD degrees in Computer Science from State University of New York at Stony Brook. Since 1987, he has been on the faculty of computer science at the University of California at Santa Barbara. His research expertise is in the areas of databases, distributed systems, cloud computing, and big data infrastructures and analysis. Over the course of his career, he has published more than 400 research articles and has mentored approximately 50 PhD students. He serves as Editor-in-Chief of the Proceedings of the ACM on Modeling of Data and Springer journal on Distributed and Parallel Databases and has either served or is serving on several Editorial Boards including ACM Transactions on Databases, IEEE Transactions on Data and Knowledge Engineering, ACM Transaction on Spatial Algorithms and Systems, ACM Books, and the VLDB Journal. He served as a Trustee on the VLDB Endowment and is currently serving as the Chair of ACM Special Interest Group on Management of Data (ACM SIGMOD). He received a Gold Medal from BITS Pilani. Professor Agrawal is the recipient of the UCSB Academic Senate Award for Outstanding Graduate Mentoring. He and his co-authors are recipients of best paper awards (ICDE 2002, MDM 2011), influential paper (NDSS 2024), and test-of-time awards (ICDT, MDM). He is a Fellow of the ACM, the IEEE, and the AAAS.
- Revisiting Inclusion Problems
Abstract:Speaker: Ramanathan. S. Thinniyam from Uppsala university
Date: 2024-08-07 Time: 16:00:00 (IST) Venue: #501, Bharti Building A problem of theoretical interest which also has application to program verification is the following: Given two context free languages (CFLs) A and B, is A a subset of B? Unfortunately, the problem is undecidable. Surprisingly, a slight weakening is in PTIME: Given a CFL L, it is included in the corresponding Dyck language (the language of balanced string of brackets). The study of inclusion problems has a long history, starting with Knuth's 1967 paper showing how to decide inclusion in Dyck1. The previously mentioned general PTIME result, however, took about 40 more years to obtain via use of sophisticated techniques which use compressed representations of words.
Since just two stacks can simulate a Turing machine, general undecidability results follow for more sophisticated machines. Our recent results showing that under context-bounding (a highly practically successful approximation technique) the following problem can be solved in coNP: Given an MPDA language L and a context bound k, is L_k included in the corresponding Dyck language? This result gives fresh impetus to study the tractability of different inclusion problems. It also enables the use of SAT/SMT techniques to provide practical new algorithms to questions which have previously been relegated to the domain of heuristics.
Bio: - Automated Synthesis of Decision Lists for Polynomial Specifications over Integers (LPAR 2024)
Abstract:Speaker: Supratik Chakraborty
Date: 2024-06-13 Time: 11:30:00 (IST) Venue: Bharti Building #404 We consider two sets I and O of bounded integer variables, modeling the inputs and outputs of a program. Given a specification Post, which is a Boolean combination of linear or polynomial inequalities with real coefficients over I ∪ O, our goal is to synthesize the weakest pre-condition Pre and a program P satisfying the Hoare triple {Pre}P{Post}. We provide a novel, sound and complete algorithm, inspired by Farkas' Lemma and Handelman's Theorem, that synthesizes both the program P and the pre-condition Pre over a bounded integral region. Our approach is exact and guaranteed to find the weakest pre-condition. Moreover, it always synthesizes both P and Pre as linear decision lists. Thus, our output consists of simple programs and pre-conditions that facilitate further static analysis. We also provide experimental results over benchmarks showcasing the applicability of our approach and performance gains over state-of-the-art.
(Joint work with S. Akshay, Amir Goharshady, Harshit Motwani, R. Govind, Sai T. Varanasi)
Bio:Supratik Chakraborty is Bajaj Group Chair Professor of Computer Science and Engineering at IIT Bombay. He completed his B.Tech. in Computer Science and Engineering from IIT Kharagpur, and M.S. and Ph.D. in Electrical Engineering from Stanford University. After spending a year at Fujitsu Laboratories of America, he joined the CSE Department at IIT Bombay, where he has been a faculty since 2000. His research interests lie at the intersection of theoretical and applied computer science, with a focus on scalable and practical formal methods. He has collaborated extensively with and transferred technologies to government and private industrial organizations. He has also served as an Advisory Board member to Microsoft Research India, and as a Research Advisor to Tata Consultancy Services.
Supratik is a recipient of several awards, including the President of India Gold Medal from IIT Kharagpur, Excellence in Teaching Award from IIT Bombay, IIT Bombay Research Publication Award, and IBM and Qualcomm Faculty Awards. He is a Fellow of Indian National Academy of Engineering, a Distinguished Member of ACM, and a Distinguished
Alumnus of IIT Kharagpur. - Using Hierarchies of Skills to Assess and Achieve Automatic Multimodal Comprehension
Abstract:Speaker: Ajay Divakaran
Date: 2024-06-05 Time: 15:30:00 (IST) Venue: SIT #001 Unlike current visual question answering (VQA), elementary school (K-5) teaching of reading comprehension has a graded approach based on a hierarchy of skills ranging from memorization to content creation. We take inspiration from such hierarchies to investigate the comprehension capabilities of large pretrained multimodal models. First, we have created a new visual question answering dataset that tests comprehension of VQA systems in a graded manner using hierarchical question answering with picture stories. Second, we use Bloom's Taxonomy of comprehension skills it to analyze and improve the comprehension skills of large pre-trained language models. Third, we propose conceptual consistency and consistency of chain of thought to measure a LLM's understanding of relevant concepts. While conceptual consistency, like other metrics, does increase with the scale of the LLM used, we find that popular models do not necessarily have high conceptual consistency. We find overall that large pretrained models still fall well short of true comprehension but are steadily improving.
Bio:Ajay Divakaran, Ph.D., is the Technical Director of the Vision and Learning Lab at the Center for Vision Technologies, SRI International, Princeton. Divakaran has been a principal investigator for several SRI research projects for DARPA, IARPA, ONR etc. His work includes comprehension based characterization of large multimodal models, multimodal analytics for social media, real-time human behavior assessment, event detection, and multi-camera tracking. He has developed several innovative technologies for government and commercial multimodal systems. He worked at Mitsubishi Electric Research Labs during 1998-2008 where he was the lead inventor of the world's first sports highlights playback-enabled DVR, and several machine learning applications. Divakaran was named a Fellow of the IEEE in 2011 for his contributions to multimedia content analysis. He has authored two books, 140+ publications and 65+ issued patents. He received his Ph.D. degree in electrical engineering from Rensselaer Polytechnic Institute.
- Fast list decoding of univariate multiplicity codes
Abstract:Speaker: Mrinal Kumar
Date: 2024-05-31 Time: 15:00:00 (IST) Venue: Bharti Building #501 Univariate multiplicity codes are a family of algebraic error correcting codes that are obtained by evaluating low degree univariate polynomials and all their derivatives up to a certain order at a set of distinct input points in an underlying field. These codes are a well studied generalisation of the more well known Reed-Solomon codes and are now known to have amazing list decodable properties; specifically, they are known to be efficiently list decodable up to the so-called list decoding capacity with constant list size.
In this talk, he will discuss a recent joint work with Rohan Goyal, Prahladh Harsha and Ashutosh Shankar, where show that these codes can be list decoded up to capacity in nearly linear time. On the way, he will talk about lattices over the univariate polynomial ring, and will see a nearly linear time algorithm for solving linear differential equations of high order.
Bio:Faculty member at STCS, TIFR
- From Randomness to Trainability in Deep Neural Networks.
Abstract:Speaker: Dr. Vinayak Abrol
Date: 2024-04-30 Time: 11:00:00 (IST) Venue: SIT #001 In this work, we study how to avoid two problems at initialisation in very deep neural networks identified in prior works: rapid convergence of pairwise input correlations and vanishing and exploding gradients. We prove that both these problems can be avoided by choosing an activation function possessing a sufficiently large linear region around the origin relative to the bias variance of the network's random initialisation. We demonstrate empirically that using such activation functions leads to tangible benefits in practice, both in terms of test and training accuracy and in terms of training time. Furthermore, we observe that the shape of the nonlinear activation outside the linear region appears to have a relatively limited impact on training.
Bio:Dr. Vinayak Abrol is an Assistant Professor at the Department of Computer Science and Engineering & associated with the Infosys Centre for AI at IIIT Delhi, India. Prior to this, he held an Oxford-Emirates data science fellowship at the Mathematical Institute, University of Oxford, the position of Academic Advisor at Kellogg College, Oxford and SNSF funded postdoctoral position at IDIAP Research Institute, Switzerland. He received his TCS Innovation Labs funded Ph.D. from the School of Computing and Electrical Engineering, IIT Mandi, India in 2018; following M.E and B.E in Electronics and Communication Engineering from Panjab University Chandigarh, India in 2013 and 2011, respectively. He is a recipient of the TCS PhD fellowship, the JP Morgan & Chase faculty research award, the Google exploreCS award and IIT Mandi's Young Achiever Award. His research focuses on the design and analysis of numerical algorithms for information-inspired applications.
- Efficient Control-Scheduling Co-Design of Cyber-Physical Systems
Abstract:Speaker: Dr. Sumana Ghosh, Assistant Professor, Indian Statistical Institute (ISI) Kolkata
Date: 2024-04-24 Time: 12:00:00 (IST) Venue: #501, Bharti Building The rapid growth in the number of features in modern cyber-physical systems (CPSs) has led the current design trend to focus on control-scheduling co-design approaches. These co-design approaches address the joint optimization of control parameters (e.g., control performance) and scheduling parameters (e.g., resource utilization) while guaranteeing the real-time properties of all software control tasks. Software control tasks often share computing resources (e.g., processor-bandwidth). The control performance of such implementations can be improved if the bandwidth sharing can be dynamically regulated in response to input disturbances. In the absence of a structured methodology for planning such measures, the scheduler may spend too much time deciding the optimal scheduling results. This research talk presents a unique approach that can be used a priori for computing co-schedulable execution patterns for a given set of control tasks such that stability remains guaranteed under all possible disturbance scenarios. Additionally, the design of the control scheduling patterns optimizes the average case-control performance and the bandwidth utilization under time-varying input disturbances.
Bio:Dr. Sumana Ghosh is currently working as an assistant professor at the Indian Statistical Institute Kolkata. Prior to that, she completed her postdoc at the Department of Electrical and Computer Engineering, Technical University of Munich in 2020, and her Ph.D. from the Department of Computer Science and Engineering, IIT Kharagpur in 2019. During her postdoctoral research, she also received the prestigious PRIME (Postdoctoral Researchers International Mobility Experience) fellowship from the German Academic Exchange Service. She was the one among two who bagged this fellowship worldwide under the "Engineering" category in the year 2019. She obtained her B.Sc. (Hons.) degree in computer science and M.Sc degree in computer and information science from the University of Calcutta in 2010 and 2012, respectively. Her current research interests include cyber-physical systems, formal verification of neural networks and AI-assisted systems, real-time scheduling for heterogeneous embedded systems, cyber security, and application of ML in electronic design automation.
- Multiagent Reinforcement Learning For Large Agent Population
Abstract:Speaker: Dr. Arambam James Singh, Nanyang Technical University
Date: 2024-04-23 Time: 11:00:00 (IST) Venue: online In today's world, many sectors, such as healthcare, transportation, etc., are rapidly digitizing their industrial processes. This presents a significant opportunity for developing next-generation artificial intelligence systems with multiple agents that can operate effectively at scale. Multiagent reinforcement learning is a field of study that focuses on solving problems in multiagent systems. In this talk, I will share my research that addresses critical challenges such as scalability and credit assignment problems in large-scale multiagent systems, specifically in a cooperative environment. My proposed methodology is built around aggregate information, which offers a high level of scalability. Importantly, the dimension of key statistics needed for training the multiagent policies does not change, even if the number of agents increases significantly, making it an effective solution for large-scale complex systems.
Bio:Dr. Arambam James Singh completed his Ph.D. in Computer Science from the School of Computing & Information Systems at Singapore Management University (SMU) in August 2021. He is currently pursuing his second postdoctoral fellowship at Nanyang Technological University (NTU) in Singapore after completing his first postdoctoral fellowship at the National University of Singapore (NUS). His research interests primarily focused on reinforcement learning and multiagent reinforcement learning.
- Modeling Nonstrategic Human Play in Games
Abstract:Speaker: Kevin Leyton-Brown, University of British Columbia
Date: 2024-04-05 Time: 17:00:00 (IST) Venue: #501, Bharti Building It is common to assume that players in a game will adopt Nash equilibrium strategies. However, experimental studies have demonstrated that Nash equilibrium is often a poor description of human players' behavior, even in unrepeated normal-form games. Nevertheless, human behavior in such settings is far from random. Drawing on data from real human play, the field of behavioral game theory has developed a variety of models that aim to capture these patterns.
This talk will survey over a decade of work on this topic, built around the core idea of treating behavioral game theory as a machine learning problem. It will touch on questions such as:- Which human biases are most important to model in single-shot game theoretic settings?
- What loss function should be used to evaluate and fit behavioral models?
- What can be learned about examining the parameters of these models?
- How can richer models of nonstrategic play be leveraged to improve models of strategic agents?
- When does a description of nonstrategic behavior "cross the line" and deserve to be called strategic?
- How can advances in deep learning be used to yield stronger--albeit harder to interpret--models?
Finally, there has been much recent excitement about large language models such as GPT-4. The talk will conclude by describing how the economic rationality of such models can be assessed and presenting some initial experimental findings showing the extent to which these models replicate human-like cognitive biases.
Bio:Kevin Leyton-Brown is a professor of Computer Science and a Distinguished University Scholar at the University of British Columbia. He also holds a Canada CIFAR AI Chair at the Alberta Machine Intelligence Institute and is an associate member of the Vancouver School of Economics. He received a PhD and an M.Sc. from Stanford University (2003; 2001) and a B.Sc. from McMaster University (1998). He studies artificial intelligence, mostly at the intersection of machine learning and either the design and operation of electronic markets or the design of heuristic algorithms. He is increasingly interested in large language models, particularly as components of agent architectures. He believes we have both a moral obligation and a historical opportunity to leverage AI to benefit underserved communities, particularly in the developing world.
He has co-written over 150 peer-refereed technical articles and two books ("Multiagent Systems" and "Essentials of Game Theory"); his work has received over 26,000 citations and an h-index of 61. He is an Fellow of the Royal Society of Canada (RSC; awarded in 2023), the Association for Computing Machinery (ACM; awarded in 2020), and the Association for the Advancement of Artificial Intelligence (AAAI; awarded in 2018). He was a member of a team that won the 2018 INFORMS Franz Edelman Award for Achievement in Advanced Analytics, Operations Research and Management Science, described as "the leading O.R. and analytics award in the industry." He and his coauthors have received paper awards from AIJ, JAIR, ACM-EC, KDD, AAMAS and LION, and numerous medals for the portfolio-based SAT solver SATzilla at international SAT solver competitions (2003–15).
He has co-taught two Coursera courses on "Game Theory" to over a million students (and counting!), and has received awards for his teaching at UBC—notably, a Killam Teaching Prize. He served as General Chair of the 2023 ACM Conference on Economics and Computation (ACM-EC); Program Co-Chair for AAAI 2021 (one of the top two international conferences on artificial intelligence), amongst others. He currently advises Auctionomics, AI21, and OneChronos. He is a co-founder of Kudu.ug and Meta-Algorithmic Technologies. He was scientific advisor to UBC spinoff Zite until it was acquired by CNN in 2011. His past consulting has included work for Zynga, Qudos, Trading Dynamics, Ariba, and Cariocas.
- Data Management for Data Science: a study on space-efficiency
Abstract:Speaker: Prof. Panagiotis Karras , computer science with the University of Copenhagen
Date: 2024-04-01 Time: 16:00:00 (IST) Venue: #501, Bharti Building Data science has the potential to extract valuable insights from data on an unprecedented scale. However, several fundamental data science tasks call for data management solutions that can effectively address problems of space-efficiency to realize this potential. This talk will focus on two cases of data management solutions that enhance scalability and space-efficiency in data science tasks. Firstly, we will discuss how to use a sophisticated technique to render the classical solution for Viterbi decoding via dynamic programming more space-efficient. Secondly, we will outline how to compute the optimal actions in a finite-horizon Markov Decision Process in a space-efficient manner. Thereby, we will outline a vision of how data management expertise can facilitate and advance the frontiers of data science.
Bio:Panagiotis Karras is a professor of computer science with the University of Copenhagen. His research interests include designing robust and versatile methods for data access, mining, analysis, and representation. He received the MSc degree in electrical and computer engineering from the National Technical University of Athens and the PhD degree in computer science from the University of Hong Kong. He was the recipient of the Hong Kong Young Scientist Award, the Singapore Lee Kuan Yew Postdoctoral Fellowship, the Rutgers Business School Teaching Excellence Fellowship, and the Skoltech Best Faculty Performance Award. His work has been published in PVLDB, SIGMOD, ICDE, KDD, AAAI, IJCAI, NeurIPS, ICLR, USENIX Security, TheWebConf, SIGIR, and ACL.
- A billion lifelong readers: The Same Language Subtitling (SLS) story of system change from concept to national policy to quality implementation.
Abstract:Speaker: Dr. Brij Kothari, Adjunct Professor, School of Public Policy, IIT-D and Lead, Billion Readers (BIRD) Initiative
Date: 2024-04-01 Time: 15:30:00 (IST) Venue: #501, Bharti Building The weak foundational literacy outcomes of our complex school system have been known for decades, resulting in 600 million weak readers in addition to 250 million non-readers. Over 60 percent are girls and women. The Billion Readers (BIRD) Initiative's vision is: Every Indian a fluent reader. BIRD leverages India's vibrant and multilingual entertainment ecosystem to deliver guaranteed daily and lifelong reading practice to one billion small screen (TV, streaming & mobile) viewers.
Brij will focus on the system change strategy that BIRD has pursued with government, civil society, academia and media companies, spanning 28 years, including a mix of evidence-based-policymaking, advocacy, coalition-building with disability rights groups, design thinking, technology development, and legal tools. Having recently joined as Adjunct Professor at SPP, IIT-D, Brij is actively exploring cross-disciplinary collaboration with faculty and students and has several projects and internship possibilities to suggest. He is especially looking for collaboration on AI-based speech-to-text tech projects in Indian languages to make entertainment accessible in cinema halls, on TV and mobiles/streaming.
Bio:Dr. Brij Kothari is an academic and social entrepreneur. He recently joined the School of Public Policy, IIT-D as Adjunct Professor. He leads the Billion Readers (BIRD) Initiative and is the founder of PlanetRead.org and BookBox.com. Brij conceived of Same Language Subtitling (SLS) on mainstream TV in India for mass reading literacy in 1996, while pursuing his Ph.D. in Education at Cornell University. Since then, he has researched and pushed for SLS in national broadcast policy on the faculty of IIM-Ahmedabad (1996-2023). He is an Ashoka Fellow, a Schwab Social Entrepreneur, the recipient of the International Literacy Prize from the Library of Congress, USA, and Co-Impact's system change grant for BIRD. At IIT-D he is looking for collaboration, coffee, and tennis partners.
- Linguistically-Informed Neural Architectures for Lexical, Syntactic, and Semantic Tasks in Sanskrit
Abstract:Speaker: Dr. Jivnesh Sandhan, IIT Dharwad
Date: 2024-03-21 Time: 11:00:00 (IST) Venue: SIT #001 In this talk, we will focus on how to make Sanskrit manuscripts more accessible to end-users through natural language technologies. The morphological richness, compounding, free word orderliness, and low-resource nature of Sanskrit pose significant challenges for developing deep learning solutions. We identify four fundamental tasks, which are crucial for developing a robust NLP technology for Sanskrit: word segmentation, dependency parsing, compound type identification, and poetry analysis. While addressing these challenges, we make various contributions, such as proposing linguistically-informed neural architectures, showcasing their interpretability and multilingual extension, reporting state-of-the-art performance, and presenting a neural toolkit called SanskritShala, which offers real-time analysis for NLP tasks.
Bio:Dr. Jivnesh Sandhan is a visiting assistant professor at IIT Dharwad in the Department of Computer Science. Prior to that, he remotely worked in the Electrical Engineering and Computer Sciences (EECS) department at the University of California, Berkeley. He completed his Ph.D. in the Department of Electrical Engineering from IIT Kanpur in 2023, where he also earned a dual degree in the Department of Mathematics and Scientific Computing in 2018. He received the prestigious Prime Minister's Research Fellowship (PMRF). His research expertise is Natural Language Processing (NLP) for Sanskrit Computational Linguistics. His primary research objective is to enhance accessibility to Sanskrit literature for pedagogical and annotation purposes. To achieve this goal, he has developed cutting-edge deep-learning-based solutions for various downstream tasks in Sanskrit. His scholarly endeavors have resulted in several publications in high-ranking conference venues, including CORE-ranking A*/A conferences. His current research revolves around developing a Sanskrit-to-English machine translation system to provide accessibility to Vedic literature. Through his work, he seeks to bridge the language barrier and contribute to a broader understanding and appreciation of ancient Sanskrit texts.
- From Biased Observations to Fair and More Effective Decisions
Abstract:Speaker: Nisheeth Vishnoi is the A. Bartlett Giamatti Professor of Computer Science and a co-founder of the Computation and Society Initiative at Yale University
Date: 2024-03-19 Time: 17:00:00 (IST) Venue: Bharti-501 Data from individuals is extensively utilized by various organizations, from multinational corporations to educational institutions, to inform decisions about individuals. However, this data often emerges from the interaction between the individual being observed and the measurement process, whether conducted by humans or AI systems. This observed data often represents a biased version of the 'true' data, and basing decisions on such data can significantly affect their fairness and effectiveness, impacting individuals, organizations, and society as a whole.
This raises critical questions of understanding when and to what extent algorithms can be designed to behave as if they had access to true data. This talk outlines an approach to these questions for the ubiquitous subset selection problem important in hiring and admissions. It starts with behavioral models that illustrate the
transformation of true data into biased data. It then analyzes the impact of existing algorithms when working with such data, and concludes by proposing new algorithms designed to mitigate these biases.
This talk is based on joint works with several co-authors and is suited for a wide audience, including students, academics,
professionals, and anyone interested in the ethical or policy dimensions of data science and AI.
Bio:Nisheeth Vishnoi is the A. Bartlett Giamatti Professor of Computer Science and a co-founder of the Computation and Society Initiative at Yale University. He is a co-PI of an NSF-funded AI Institute: The Institute for Learning-enabled Optimization at Scale. His research spans various areas of Theoretical Computer Science, Optimization, and
Artificial Intelligence. Specific current research topics include Responsible AI, foundations of AI, and data reduction methods. He is also interested in understanding nature and society from a computational viewpoint.
Professor Vishnoi was the recipient of the Best Paper Award at IEEE Symposium on Foundations of Computer Science in 2005, the IBM Research Pat Goldberg Memorial Award in 2006, the Indian National Science Academy Young Scientist Award in 2011, the IIT Bombay Young Alumni Achievers Award in 2016, and the Best Paper award at ACM Conference on Fairness, Accountability, and Transparency in 2019. He was named an ACM Fellow in 2019. His most recent book Algorithms for Convex Optimization was published by Cambridge University Press. - Towards Robust and Reliable Machine Learning: Adversaries and Fundamental Limits
Abstract:Speaker: Arjun Bhagoji, University of Chicago
Date: 2024-03-04 Time: 11:00:00 (IST) Venue: SIT #001 While ML-based AI systems are increasingly deployed in safety-critical settings, they continue to remain unreliable under adverse conditions that violate underlying statistical assumptions. In my work, I aim to (i) understand the conditions under which a lack of reliability can occur and (ii) reason rigorously about the limits of robustness, during both training and test phases.
In the first part of the talk, I demonstrate the existence of strong but stealthy training-time attacks on federated learning, a recent paradigm in distributed learning. I show how a small number of compromised agents can modify model parameters via optimized updates to ensure desired data is misclassified by the global model, while bypassing custom detection methods. Experimentally, this model poisoning attack leads to a lack of reliable prediction on standard datasets.
Test-time attacks via adversarial examples, i.e. imperceptible perturbations to test inputs, have sparked an attack-defense arms race. In the second part of the talk, I step away from this arms race to provide model-agnostic fundamental limits on the loss under adversarial input perturbations. The robust loss is shown to be lower bounded by the optimal transport cost between class-wise distributions using an appropriate adversarial point-wise cost, the latter of which can be efficiently computed via a linear program for empirical distributions of interest.
To conclude, I will discuss my ongoing efforts and future vision towards building continuously reliable and accessible ML systems by accounting for novel attack vectors and new ML paradigms such as generative AI, as well as developing algorithmic tools to improve performance in data-scarce regimes.
Bio:Arjun Bhagoji is a Research Scientist in the Department of Computer Science at the University of Chicago. He obtained his Ph.D. in Electrical and Computer Engineering from Princeton University, where he was advised by Prateek Mittal. Before that, he received his Dual Degree (B.Tech+M.Tech) in Electrical Engineering at IIT Madras, where he was advised by Andrew Thangaraj and Pradeep Sarvepalli. Arjun's research has been recognized with a Spotlight at the NeurIPS 2023 conference, the Siemens FutureMakers Fellowship in Machine Learning (2018-2019) and the 2018 SEAS Award for Excellence at Princeton University. He was a 2021 UChicago Rising Star in Data Science, a finalist for the 2020 Bede Liu Best Dissertation Award in Princeton's ECE Department and a finalist for the 2017 Bell Labs Prize.
- Trends and recent results in the study of non-interactive multi-party computation (NIMPC)
Abstract:Speaker: Prof. Tomoharu Shibuya from Sophia University
Date: 2024-03-01 Time: 16:00:00 (IST) Venue: #501, Bharti Building A large amount of data is required to improve the accuracy of machine learning. However, data often contains personal privacy and corporate sensitive information, making it difficult to freely utilize large amounts of data. Therefore, security technologies that perform various calculations on data while maintaining data confidentiality are attracting attention.
Secure Multi Party Computation (MPC) is a method for parties to jointly compute a function over their inputs while keeping those inputs private. MPC has the drawback that as the number of participating parties increases, the amount of communication between the parties becomes enormous. To overcome this drawback, Secure non-interactive MPC (NIMPC) was developed, which introduces a protocol setup server and a computation server, and each party communicates only with these servers.
In this talk, I will explain a simple method for realizing NIMPC and introduce recent research on NIMPC. In particular, we will introduce an evolving NIMPC that can perform calculations without changing the setup at the start of the protocol even if the number of parties increases after the protocol starts.
I will also provide a comprehensive introduction to the research and faculty members at the Department of Information and Communication Sciences, Sophia University, and discuss possibilities for student and research exchanges between IIT Delhi and Sophia University.
Bio:Prof. Tomoharu Shibuya
(https://researchmap.jp/read0183734?lang=en)
- Heterogenous Benchmarking across Domains and Languages: The Key to Enable Meaningful Progress in IR Research.
Abstract:Speaker: Nandan Thakur
Date: 2024-01-23 Time: 15:00:00 (IST) Venue: SIT #001 Benchmarks are ever so necessary to measure realistic progress within Information Retrieval. However, existing benchmarks quickly saturate as they are prone to overfitting affecting retrieval model generalization. To overcome these challenges, I would present two of my research efforts: BEIR, a heterogeneous benchmark for zero-shot evaluation across specialized domains, and MIRACL, a monolingual benchmark covering a diverse range of languages. In BEIR, we show that neural retrievers surprisingly struggle to generalize zero-shot on specialized domains due to a lack of training data. To overcome this, we develop GPL that distills cross-encoder knowledge using cross-domain BEIR synthetic data. On the language side, MIRACL is robust in annotations and includes a broader coverage of the languages. However, generating supervised training data is cumbersome in realistic settings. To supplement, we construct SWIM-IR, a synthetic training dataset with 28 million LLM-generated pairs across 37 languages to develop multilingual retrievers comparable to supervised models in performance. We can cheaply extend to several new languages.
Bio:Nandan Thakur is a third-year PhD student in the David R. Cheriton School of Computer Science at the University of Waterloo under the supervision of Prof. Jimmy Lin. His research broadly investigates data efficiency and model generalization across specialized domains and languages in information retrieval. He was the co-organizer of the MIRACL competition in WSDM 2023 and will co-organize the upcoming RAG Track in TREC 2024. His work has been published in top conferences and journals, including ACL, NAACL, NeurIPS, SIGIR, and TACL.
- LLMs for Everybody: How inclusive are the LLMs today and Why should we care?
Abstract:Speaker: Monojit Choudhury , professor of Natural Language Processing at Mohd bin Zayed University of Artificial Intelligence (MBZUAI), Abu Dhabi
Date: 2024-01-23 Time: 17:00:00 (IST) Venue: SIT #001 Large Language Models (LLMs) have revolutionized the field of NLP and natural human-computer interactions; they hold a lot of promise, but are these promises equitable across countries, languages and other demographic groups? Research from our group as well as from around the world is constantly revealing that LLMs are biased in terms of their language processing abilities in most but a few of the world's languages, cultural awareness (or lack thereof) and value alignment. In this talk, I will highlight some of our recent findings around value alignment bias in the models and argue why we need models that can reason generically across moral values and cultural conventions.
We will also discuss some of the opportunities for students at postgraduate, PhD and Post doctoral levels at the newly founded MBZUAI university.
Bio:Monojit Choudhury is a professor of Natural Language Processing at Mohd bin Zayed University of Artificial Intelligence (MBZUAI), Abu Dhabi. Prior to this, he was a principal scientist at Microsoft Research Lab and Microsoft Turing, India. He is also a professor of practice at Plaksha University, and an adjunct professor at IIIT Hyderabad. Prof Choudhury's research interests lie in the intersection of NLP, Social and Cultural aspects of Technology use, and Ethics. In particular, he has been working on multilingual aspects of large language models (LLMs), their use in low resource languages and making LLMs more inclusive and safer by addressing bias and fairness aspects. Prof Choudhury is the general chair of Indian national linguistics Olympiad and the founding co-chair of Asia-Pacific linguistics Olympiad. He holds a BTech and PhD degree in Computer Science and Engineering from IIT Kharagpur.
- Geometric GNNs for 3D Atomic Systems
Abstract:Speaker: Chaitanya K. Joshi
Date: 2024-01-18 Time: 15:00:00 (IST) Venue: #501, Bharti Building Recent advances in computational modelling of atomic systems, spanning molecules, proteins, and materials, represent them as geometric graphs with atoms embedded as nodes in 3D Euclidean space. Geometric Graph Neural Networks have emerged as the preferred ML architecture powering breakthroughs ranging from protein structure prediction to molecular simulations and material generation. Their specificity lies in the inductive biases they leverage — such as the underlying physical symmetries and chemical properties — to learn informative representations of geometric graphs. This talk will provide an overview of Geometric GNNs for 3D atomic systems. I will introduce a pedagogical taxonomy of Geometric GNN architectures from the perspective of their theoretical expressive power and highlight practical shortcomings of current models. This talk is based on our recent works: https://arxiv.org/abs/2301.09308, https://arxiv.org/abs/2312.0751
Bio:Chaitanya K. Joshi is a 3rd year PhD student at the Department of Computer Science, University of Cambridge, supervised by Prof. Pietro Liò. His research explores the intersection of Geometric Deep Learning and Graph Neural Networks for applications in biomolecule modelling & design. He previously did an undergraduate degree in Computer Science from Nanyang Technological University and worked as a Research Engineer at A*STAR in Singapore.
- Introduction to Digital Forensics
Abstract:Speaker: Dr. Andrey Chechulin
Date: 2024-01-18 Time: 12:00:00 (IST) Venue: #501, Bharti Building This lecture is a foundational exploration into Digital Forensics, a discipline focusing on the identification, extraction, preservation, and analysis of digital evidence. The relevance of it spans across criminal and civil law where digital evidence is increasingly pivotal. During the lecture we will discuss the broad spectrum of digital evidence, from computer systems to mobile devices, and the unique challenges each presents. The lecture will highlight the critical role digital forensics plays in solving cybercrimes and in resolving legal disputes involving digital data. In addition to theoretical aspects, the examples of practical application of digital forensics will be discussed. Designed for beginners and professionals alike, such as IT experts, lecturers, or students, this lecture aims to impart a comprehensive understanding of digital forensics and its indispensable role in contemporary digital investigations.
Bio:Andrey Chechulin is a Candidate of Technical Sciences (2013, SPbSUT, Russia) and an Associate Professor (2021, SPbSUT, Russia). Currently, he is the Head of the International Digital Forensic Center for Digital Forensics and a leading researcher at the Laboratory of Computer Security Problems of the SPC RAS (Saint-Petersburg, Russia). He is also an associate professor at SPbSUT and ITMO Universities. He has been an invited professor and a scientific advisor of master and PhD students at universities in France, Sweden, and Russia. He is member of many editorial boards of Russian and international journals, and the author of more than 200 refereed publications, including several books and monographs. As a project leader, he has participated in over 15 Russian and international scientific projects for the Russian and EU scientific foundations and commercial companies in Russia and abroad. As a security expert, he has conducted more than 200 expert assessments both in the practical field of cybercrime investigation and court cases and in the academic field, serving as a reviewer for leading international journals, conferences, and research foundations. As a science communicator, he regularly appears on various regional and federal media broadcasts and delivers public lectures on information security. His main research interests include digital forensics, computer network security, artificial intelligence, cyber-physical systems, social network analysis, and security data visualization.
- Network Security and Vulnerabilities Analysis
Abstract:Speaker: Dr. Dmitry Levshun
Date: 2024-01-18 Time: 12:45:00 (IST) Venue: #501, Bharti Building Scientists and developers all over the world are working hard to ensure the information security of network systems. This task is complex due to the diversity of threats and wide range of security requirements. Moreover, specialists detect new vulnerabilities every day, while old vulnerabilities are still present in working systems. The goal of this lecture is to provide the information about the basics of network security evaluation using attack graphs. We will go deep into details how vulnerabilities can be represented in open databases as well as how we can categorise them. After that we will go step by step through the host attack graph construction and analysis. In the end we will discuss how Artificial Intelligence can be used to improve vulnerabilities categorisation.
Bio:Dmitry Levshun is a Candidate of Technical Sciences (ITMO University, Russia) and a Doctor of Philosophy in Computer Science (University of Toulouse III, France). Author of more than 30 publications indexed by Scopus and Web of Science (H-index 8), 5 of which are included in the Q1 quartile. Has over 20 certificates of state registration of programs and databases. Active participant in more than 15 research and development projects of Russian funds. Head of the initiative research project conducted by young scientists. He works as a Senior Researcher at the Laboratory of Computer Security Problems of SPC RAS. Additionally, he works as a leading expert at the International Center for Digital Forensics of SPC RAS. Moreover, Dmitry is an Associate Professor at leading universities in St. Petersburg, namely SPbSUT (Secure communication systems department) and EUSPb (Applied data analysis program). Member of the program committee of FRUCT and COMSNETS conferences. Reviewer for scientific journals such as Electronics, Machines, Micromachines, Inventions, Future Internet and Microprocessors and Microsystems. Area of scientific interests: information security, Internet of Things, artificial intelligence, security by design, modeling of malicious activity.
- Artificial Intelligence for Cyber Security
Abstract:Speaker: Dr. Igor Kotenko
Date: 2024-01-17 Time: 16:00:00 (IST) Venue: #501, Bharti Building Artificial intelligence (AI) has become one of the main approaches to processing huge amounts of heterogeneous data and performing various cyber security tasks, including vulnerability management and security assessment, security monitoring, distributed access control. AI is changing the way computers are programmed and how they are used. In the modern interpretation, AI systems are systems, first, of machine learning, and sometimes these AI systems are even more narrowed down to artificial neural networks. In cyber security, AI methods provided the opportunity to create advanced cyber security tools, but also allowed attackers to significantly improve the cyber attacks. The evolution of attack and defense tools took place mainly in the form of an arms race, which in its essence was asymmetric and beneficial to attackers. Cybercriminals can launch targeted attacks at unprecedented speed and scale, while bypassing traditional detection mechanisms. The talk shows the current state of AI in cyber security. The key areas of focus at the intersection of AI and cyber security are analyzed: enhancing cyber security with AI, AI for cyber attacks, the vulnerability of AI systems to attacks, and the use of AI in malicious information operations. The own research in the field of intelligent monitoring of cyber security and detection of cyber attacks is presented. This research is being supported by the grant of Russian Science Foundation #21-71-20078 in SPC RAS.
Bio:Igor Kotenko is a Chief Scientist and Head of Research Laboratory of Computer Security Problems of the St. Petersburg Federal Research Center of the Russian Academy of Sciences. He is also Professor of ITMO University, St. Petersburg, Russia, and Bonch-Bruevich Saint-Petersburg State University of Telecommunications. He is the Honored Scientist of the Russian Federation, IEEE Senior member, member of many Editorial Boards of Russian and International Journals, and the author of more than 800 refereed publications, including 25 books and monographs. Main research results are in artificial intelligence, telecommunication, cyber security, including network intrusion detection, modeling and simulation of network attacks, vulnerability assessment, security information and event management, verification and validation of security policy. Igor Kotenko was a project leader in the research projects from the European Office of Aerospace Research and Development, EU FP7 and FP6 Projects, HP, Intel, F-Secure, Huawei, etc. The research results of Igor Kotenko were tested and implemented in multitude of Russian research and development projects, including grants of Russian Science Foundation, Russian Foundation of Basic Research and multitude of State contracts. He has been a keynote and invited speaker on multitude of international conferences and workshops, as well as chaired many international conferences.
- A New Perspective on Invariant Generation as Semantic Unification
Abstract:Speaker: Prof. Deepak Kapur, University of New Mexico
Date: 2024-01-12 Time: 15:00:00 (IST) Venue: #501, Bharti Building Unification is the problem of finding instantiations of variables in a finite set of equations constructed using function symbols such that both sides of the instantiated equations are equal. In semantic unification, also called E-unification, function symbols can have properties specified typically by an equational theory; a unifier then makes the two instantiated sides of each equation, equivalent modulo the equation theory. By generalizing the unification problem to a first-order theory in which variables in the problem stand for formulas in the theory, the invariant generation problem in software, hardware, and cyber-physical system can be formulated as a unification problem. Finding a nontrivial unifier in this case amounts to finding an invariant which is a formula in the theory. Similarly, finding a most general unifier in that theory amounts to finding the strongest invariant. Instantiation of variables can be further restricted to formulas with certain shapes/properties. A number of examples from the literature of the automatic generation of loop invariants in software will be used to illustrate this new perspective.
Bio:A distinguished professor at the University of New Mexico since 1998, Kapur served as chair of the Department of Computer Science from Dec. 1998 to June 2006. He has adjunct appointments at IIT, Delhi, India, as well as Tata Institute of Fundamental Research, Mumbai, India. From 1980-1987, he was on the research staff of General Electric Corporate Research and Development, Schenectady, NY. He was appointed tenured full professor at the University at Albany, SUNY, and Albany, NY, in 1988, where he also founded the Institute for Programming and Logics. He has had research collaborations all over the world including TIFR, India; MPI, Saarbrucken, Germany; Chinese Academy of Sciences, Beijing; IMDEA, Madrid, and UPC, Barcelona; Naval Research Lab, Washington. He serves on the editorial boards of numerous journals including the Journal of Symbolic Computation and Journal of Automated Reasoning, for which he also served as the editor-in-chief from 1993-2007. Kapur is on the board of United Nations University-International Institute for Software Technology as well as LIPIcs: Leibniz International Proceedings in Informatics. Kapur was honored with the Herbrand Award in 2009 for distinguished contributions to automated reasoning.
- In Search of a Networking Unicorn: Realizing Closed-Loop ML Pipeline for Networking
Abstract:Speaker: Arpit Gupta, Assistant Professor, UCSB
Date: 2024-01-11 Time: 12:00:00 (IST) Venue: Bharti 501 Machine Learning (ML) and Artificial Intelligence (AI) are driving
transformative changes across various domains, including networking.
It is widely assumed that ML/AI-based solutions to complex security or
performance-specific problems outperform traditional heuristics and
statistical methods. However, this optimism raises a fundamental
question: Can our current ML/AI-based solutions be used for
high-stakes decision-making in production networks where errors can
have serious consequences? Unfortunately, many of these solutions have
struggled to fulfill their promises. The primary issues stem from the
use of inadequate training data and an overemphasis on narrowly scoped
performance metrics (e.g., F1 scores), neglecting other critical
aspects (e.g., a model's vulnerability to underspecification issues,
such as shortcut learning). The result has been a general reluctance
among network operators to deploy ML/AI-based solutions in their
networks.
In this talk, I will highlight our efforts to bridge this trust gap by
arguing for and developing a novel closed-loop ML workflow that
replaces the commonly used standard ML pipeline. Instead of focusing
solely on the model's performance and requiring the selection of the
"right" data upfront, our newly proposed ML pipeline emphasizes an
iterative approach to collecting the "right" training data guided by
an in-depth understanding and analysis of the model's decision-making
and its (in)ability to generalize In presenting the building blocks
of our novel closed-loop ML pipeline for networking, I will discuss
(1) Trustee: A global model explainability tool that helps
identify underspecification issues in ML models; (2) netUnicorn: A
data-collection platform that simplifies iteratively collecting the
"right" data for any given learning problem from diverse network
environments; and (3) PINOT: A suite of active and passive
data-collection tools that facilitate transforming enterprise networks
into scalable data-collection infrastructure. I will conclude the talk
by discussing the potential for developing a community-wide
infrastructure to support this closed-loop ML pipeline for developing
generalizable ML/AI models as key ingredients for the future creation
of deployment-ready ML/AI artifacts for networking.
Bio:Arpit Gupta is an assistant professor in the computer science
department at UCSB. His research focuses on building flexible,
scalable, and trustworthy systems that solve real-world problems at
the intersection of networking, security, and machine learning. He
also develops systems that aid in characterizing and addressing
digital inequity issues. He developed BQT, a tool to extract
broadband plans offered by ISPs in the US; Trustee, a tool to
explain decision-making of ML artifacts for networking; netUnicorn,
a network data collection platform for machine learning
applications; Sonata, a streaming network telemetry system; and SDX,
an Internet routing control system His work on augmenting crowdsourced
Internet measurement data using BQT received the Distinguished Paper
Award at ACM IMC’22; Trustee received IETF/IRTF Applied Networking
Research Award and Best Paper Award (honorable mention) at ACM
CCS’22; SDX received the Internet2 Innovation Award, Best of Rest,
Community Contribution Award USENIX NSDI’16, and the Best Paper
Award at ACM SOSR’17. Arpit received his Ph.D. from Princeton
University. He completed his master's degree at NC State University
and a bachelor's degree at the Indian Institute of Technology,
Roorkee, India.
- Towards Evolving Operating System
Abstract:Speaker: Prof. Sanidhya Kashyap, Assistant Professor, EPFL
Date: 2024-01-10 Time: 14:00:00 (IST) Venue: Bharti-501 In this talk, I will present our ongoing effort to dynamically specialize the OS kernel based on the application requirements. In the first part of the talk, I will propose a new synchronization paradigm, contextual concurrency control (C3), that enables applications to tune
concurrency control in the kernel. C3 allows developers to change the behavior and parameters of kernel locks, switch between different lock implementations, and dynamically profile one or multiple locks for a specific scenario of interest. This approach opens up a plethora of opportunities to fine-tune concurrency control mechanisms on the fly.
In the later part, I will present a new approach to designing a storage stack that allows file system developers to design userspace file systems without compromising file system security guarantees while at the same time ensuring direct access to non-volatile memory (NVM) hardware. I will present a new file system architecture called Trio that decouples file system design, access control, and metadata integrity enforcement. The key insight is that other state (i.e., auxiliary state) in a file system can be regenerated from its “ground truth” state (i.e., core state). This approach can pave the way for providing a clean structure to design file systems.
Bio:Sanidhya Kashyap is a systems researcher and an Assistant Professor at the School of Computer and Communication Sciences at EPFL. His research focuses on designing robust and scalable systems software, such as operating systems, file systems, and system security. He has published in top-tier systems conferences (SOSP, OSDI, ASPLOS, ATC, and EuroSys) and security conferences (CCS, IEEE S&P, and USENIX Security). He is the recipient of the VMware Early Career Faculty Award. He received his Ph.D. degree from Georgia Tech in 2020.
- Towards Evolving Operating Systems
Abstract:Speaker: Sanidhya Kashyap, Assistant Professor, EPFL
Date: 2024-01-10 Time: 14:30:00 (IST) Venue: Bharti-501 In this talk, I will present our ongoing effort to dynamically specialize the OS kernel based on the application requirements.
In the first part of the talk, I will propose a new synchronization paradigm, contextual concurrency control (C3), that enables applications to tune concurrency control in the kernel. C3 allows developers to change the behavior and parameters of kernel locks, switch between different lock implementations, and dynamically profile one or multiple locks for a specific scenario of interest. This approach opens up a plethora of opportunities to fine-tune concurrency control mechanisms on the fly.
In the later part, I will present a new approach to designing a storage stack that allows file system developers to design userspace file systems without compromising file system security guarantees while at the same time ensuring direct access to non-volatile memory (NVM) hardware. I will present a new file system architecture called Trio that decouples file system design, access control, and metadata integrity enforcement. The key insight is that other state (i.e., auxiliary state) in a file system can be regenerated from its “ground truth” state (i.e., core state). This approach can pave the way for providing a clean structure to design file systems.
Bio:Sanidhya Kashyap is a systems researcher and an Assistant Professor at the School of Computer and Communication Sciences at EPFL. His research focuses on designing robust and scalable systems software, such as operating systems, file systems, and system security. He has published in top-tier systems conferences (SOSP, OSDI, ASPLOS, ATC, and EuroSys) and security
conferences (CCS, IEEE S&P, and USENIX Security). He is the recipient of the VMware Early Career Faculty Award. He received his Ph.D. degree from Georgia Tech in 2020. - Memory as a lens to understand efficient learning and optimization
Abstract:Speaker: Dr. Vatsal Sharan (Univ. Southern California)
Date: 2024-01-02 Time: 12:00:00 (IST) Venue: #404, Bharti Building What is the role of memory in learning and optimization? The optimal convergence rates (measures in terms of the number of oracle queries or samples needed) for various optimization problems are achieved by computationally expensive optimization techniques, such as second-order methods and cutting-plane methods. We will discuss if simpler, faster and memory-limited algorithms such as gradient descent can achieve these optimal convergence rates for the prototypical optimization problem of minimizing a convex function with access to a gradient or a stochastic gradient oracle. Our results hint at a perhaps curious dichotomy---it is not possible to significantly improve on the convergence rate of known memory efficient techniques (which are linear-memory variants of gradient descent for many of these problems) without using substantially more memory (quadratic memory for many of these problems). Therefore memory could be a useful discerning factor to provide a clear separation between 'efficient' and 'expensive' techniques. Finally, we also discuss how exploring the landscape of memory-limited optimization sheds light on new problem structures where it is possible to circumvent our lower bounds, and suggests new variants of gradient descent.
Bio:Vatsal Sharan is an assistant professor in the CS department at the University of Southern California. He did his undergraduate at IIT Kanpur, PhD at Stanford and a postdoc at MIT. He is interested in the foundations of machine learning, particularly in questions of computational & statistical efficiency, fairness and robustness.
2024 talks
- From theory to practice: the Marvelous journey of Mighty MPC
Abstract:Speaker: Prof. Arpita Patra, Associate Professor, IISc
Date: 2024-12-20 Time: 11:00:00 (IST) Venue: Bharti-501 Secure Multi-party Computation (MPC) is the standard-bearer and holy-grail problem in Cryptography that permits a collection of data-owners to compute a collaborative result, without any of them gaining any knowledge about the data provided by the other, except what is derivable from the result of the computation. The area was introduced in the seminal work of Yao in 1982. Since then the theory of MPC has seen some of the most fundamental results in theory of computation. Technology follows techniques and so a huge effort has gone in for turning techniques of MPC to technology. In this talk, I plan to cover the contribution we made towards solving real-world problems via applied MPC. The broad domains we tackle include social good, Health, FinTech and Smart cities.
Bio:Arpita Patra is presently an Associate Professor at Indian Institute of Science. She served as a visiting faculty at Silence Laboratories, Singapore in 2024 and as a visiting faculty researcher at Google Research between 2022-2023. Her area of interest is Cryptography, focusing on theoretical and practical aspects of secure multiparty computation protocols. She received her PhD from Indian Institute of Technology (IIT), Madras and held post-doctoral positions at University of Bristol, UK, ETH Zurich, Switzerland, and Aarhus University, Denmark.
Her research has been recognized with Prof. S. K. Chatterjee Award for Outstanding Woman Researcher or Industry Leader 2023 by IISc (2023), Google Privacy Research Faculty Award 2023, J P Morgan Chase Faculty Award 2022, SONY Faculty Innovation Award 2021, Google Research Award 2020, NASI Young Scientist Platinum Jubilee Award 2018, SERB Women Excellence award 2016, INAE Young Engineer award 2016 and associateships with various scientific bodies such as Indian Academy of Sciences (IAS), National Academy of Engineering (INAE ), The World Academy of Sciences (TWAS). She has coauthored a textbook on Multi-party Computation titled “Secure Multiparty Computation against Passive Adversaries” (published by Springer in 2023) and on consensus titled “Fault Tolerant Distributed Consensus in Synchronous Networks” (in press, Springer). - Global Search and Discovery with Differential Policy Optimization
Abstract:Speaker: Chandrajit Bajaj, UT Austin
Date: 2024-12-19 Time: 12:00:00 (IST) Venue: Bharti Building #501 Reinforcement learning (RL) with continuous state and action spaces is arguably one the most challenging problems within the field of machine learning. Most current learning methods focus on integral identities such as value (Q) functions to derive an optimal strategy for the learning agent. In this talk we present the dual form of the original RL formulation to propose the first differential RL framework that can handle settings with limited training samples and short-length episodes. Our approach introduces Differential Policy Optimization (DPO), a pointwise and stage-wise iteration method that optimizes policies encoded by local-movement operators. We prove a pointwise convergence estimate for DPO and provide a regret bound comparable with the best current theoretical derivation. Such pointwise estimate ensures that the learned policy matches the optimal path uniformly across different steps. We then apply DPO to a class of practical RL problems with continuous state and action spaces, e.g. shape and material optimization and discovery of new molecules with targeted dynamics.
This is joint work with Garvit Bansal, Minh Nguyen.
Bio:Chandrajit Bajaj, UT Austin
- New Algorithmic Challenges for Ethical Decision-Making
Abstract:Speaker: Swati Gupta, MIT
Date: 2024-12-09 Time: 12:30:00 (IST) Venue: #501, Bharti Building When someone is denied a job, offered a different price for the same goods or services, or declined a loan, intent to discriminate is often not the case. The decision system applies the same data and rules to all and yet has a disproportionate effect on various groups. The causes of such disparate impact in machine learning and optimization are many, and these create an opportunity for us to develop new algorithms. I will present three such opportunities. The first is motivated by challenges due to bias and errors in evaluation data. I will present new optimization problems using ordinal data, which can create a pathway to solving discrimination in hiring (Management Science, 2023 with Salem, and UC Davis Law Review, 2023 with Salem and Desai). Next, I will discuss the challenge of selecting the “right” notion of fairness. I will present the concept of “portfolios”, that ask to find a small set of approximate solutions that summarize the set (potentially infinite) set of fairness objectives. I will showcase combinatorial techniques to tackle this challenge, and connections to polyhedral structure (EC 2023, SODA 2025, with Singh and Moondra). Finally, motivated by the recent lawsuits on price fluctuations, I will discuss challenges in trajectory-constrained stochastic optimization, which for example, can provide algorithms that monotonically change prices in demand learning (WINE 2022, with Kamble and Salem). This talk is based on joint work with Jad Salem, Deven Desai, Mohit Singh, Jai Moondra, and Vijay Kamble.
Bio:Dr. Swati Gupta is an Associate Professor at the MIT Sloan School of Management in the Operations Research and Statistics Group, and holds the Class of 1947 Career Development Professorship. She received a Ph.D. in Operations Research from MIT, and a dual Bachelors + Masters in Computer Science and Engineering from IIT Delhi. Her research interests include optimization and machine learning, with a focus on algorithmic fairness. Her work is cross-disciplinary and spans various domains such as hiring, admissions, e-commerce, healthcare, districting, power systems, and quantum optimization. She served as the lead of Ethical AI for the NSF AI Institute on Advances in Optimization, from 2021-2023. She has received the NSF CAREER Award in 2023, the JP Morgan Early Career Faculty Recognition in 2021, the NSF CISE Research Initiation Initiative Award in 2019, Simons-Berkeley Research Fellowship in 2017-2018, and the Google Women in Engineering Award (India) in 2011. Dr. Gupta’s research is partially funded by the National Science Foundation (NSF) and Defense Advanced Research Projects Agency (DARPA), as well as Social and Ethical Responsibilities in Computing (SERC) at MIT.
- Where old meets new: Digitization of documents in Serbian
Abstract:Speaker: Anastazia Zunic,
Date: 2024-12-09 Time: 10:00:00 (IST) Venue: #501, Bharti Building Digital humanities is an interdisciplinary field which brings together traditional humanities and computer science to study cultural and historical data. Numerous tools and platforms are being utilised in digital humanities to advance and enrich work with digitized documents. At the core of these tools are complex machine learning algorithms for image and text processing, trained on appropriately prepared document repositories. Their most common functionalities include image quality enhancement, document layout analysis, optical character recognition, and text post-correction. In this talk, we will explore the experiences gained from using modern open-source tools for digitizing documents in Serbian. The existing tools are designed to address individual steps in the digitization process or the complete end-to-end pipeline. The resources used for testing these tools include periodicals published from the mid-19th century to the mid-20th century, provided by the National Library of Serbia. These periodicals are characterized by a great diversity of graphic elements, non-standard formats, physical degradation, and lower-quality scans. Along with the observed advantages and limitations of these tools, we will discuss ways to further expand and adapt them to the Serbian language. Special attention will be given to the role of language technologies and scenarios where their use is essential.
Bio:Anastazia Zunic, Mathematical Institute of the Serbian Academy of Sciences and Arts, Serbia
- "Curious Case of AI in Maths: Being proficient in advancing open conjectures in Maths yet having struggles in AI for Education"
Abstract:Speaker: Ankit Anand
Date: 2024-12-05 Time: 16:00:00 (IST) Venue: SIT #113 AI has made great strides in multiple domains including robotics, game playing, biology and climate science etc. The story in AI for maths has a bizarre story . On the one hand, we use AI methods for developing new lower bounds for a simple yet open problem in extremal graph theory proposed by Erdos in 1975. On the other hand, we describe our approach of developing a robust evaluation in AI for Education especially in math benchmarks.
Firstly, we will describe our recent work on studying a central extremal graph theory problem inspired by a 1975 conjecture of Erdős. We formulate the graph generation problem as a sequential decision-making problem and compare AlphaZero, a neural network-guided tree search, with tabu search, a heuristic local search method. Using curriculum, we improve the state-of-the-art lower bounds for several sizes for this problem.
Secondly, we describe how advances in generative AI (gen AI) have created excitement about the potential of new technologies to offer a personal tutor for every learner The full extent of this dream, however, has not yet materialised. We argue that this is primarily due to the difficulties with verbalising pedagogical intuitions into gen AI prompts and the lack of good evaluation practices, reinforced by the challenges in defining excellent pedagogy. We particularly focus on reasoning challenges in math tutoring where we argue reasoning is just beyond problem solving and although current models have improved a lot in solving problems yet fails on simple aspects like identifying mistakes in partially correct solutions. We even argue how tutoring could in fact be seen as a turing test for reasoning in LLMs.
Bio:Ankit Anand is currently a Staff Research Scientist at Google DeepMind Montreal, an adjunct faculty member at McGill University and associate industry member at MILA. He is working with Prof. Doina Precup in Montreal. His research interests lie at the intersection of logical methods, neural networks and reinforcement learning in general and particularly, applying AI and ML to make advances in Mathematics as well as AI for Education. Previously, he completed his Ph.D at IIT Delhi working with Prof. Mausam and Prof. Parag Singla. During his Ph.D, he worked on making symmetry aware A.I algorithms in context of probabilistic graphical models and Monte Carlo Tree Search algorithms.
- How Do We Involve People in AI Decision-Making? Towards Effective Participatory AI Designs
Abstract:Speaker: Vijay Keswani, Duke University
Date: 2024-11-29 Time: 12:00:00 (IST) Venue: Bharti Building #501 The expanding capabilities of AI come with a surge in the reports of societal and personal harms related to its use. Examples range from systemic biases in AI decision-aid tools in healthcare and policing to stereotype propagation in AI-based search and translation tools. Technical research on mitigating such harms forward certain solutions to ensure that AI behavior is aligned with ethical norms and values. Yet, this research leaves unanswered the question of "whose norms are followed" and can fail to counter AI harms when there is a disparity between the assumed ethical norms and the values of the people impacted by AI. But what if there was a way for the stakeholders (e.g., AI users or domain experts) to tell us how an AI tool should ideally operate?
In this talk, I will argue for democratizing how we build AI tools and undertaking a participatory approach to AI assessment and development. By eliciting feedback from relevant stakeholders on the harms they observe and the outcomes they expect, AI models can be aligned with the expressed stakeholder values. We will see concrete illustrations of such participatory mechanisms for image search audits, multi-winner elections, and medical decision-making. Across these applications, certain features of participation in AI will become clear: (a) participatory designs are domain-specific, (b) their efficacy relies heavily on the effectiveness of mechanisms used for eliciting stakeholder preferences, and (c) (when done right) they enhance user agency and trust in AI tools.
Bio:Vijay Keswani is a Postdoctoral Associate at Duke University. His research interests center around community-focused AI development and the ethics of data and technology. His work leverages tools from various disciplines to build robust AI models, combining computational and statistical learning mechanisms with methods from law, philosophy, psychology, and economics. He received his PhD from Yale University in 2023. While at Yale, he was a Resident Fellow at the Information Society Project during 2022-2023 and a 2022 Policy Fellow at the Yale Institute for Social and Policy Studies.
- Fine-Grained Segmentation and Control of Materials
Abstract:Speaker: Prafull Sharma, Post Doc
Date: 2024-11-25 Time: 11:00:00 (IST) Venue: SIT #001 With the recent advancements in computer vision and graphics, scene understanding has become critical for both downstream applications and photorealistic synthesis. Tasks such as image classification, semantic segmentation, and text-to-image generation parse scenes in terms of high-level object and scene properties. Beyond these dimensions, it is equally important to understand low-level information, including geometry, material, lighting configuration, and camera parameters. Such understanding facilitates tasks like material acquisition, fine-grained synthesis, and robotics. In this talk, we will focus on recent works that use synthetic data rendered in graphics renderers and representations from pre-trained models for material segmentation and editing, specifically discussing the following papers: Materialistic: Selecting Similar Materials in Images (SIGGRAPH 2023) and Alchemist: Parametric Control of Material Properties with Diffusion Models (CVPR 2024). Materialistic introduces a method for selecting regions in images with the same material properties, leveraging unsupervised DINO features and a Cross-Similarity module trained on synthetically rendered data. Alchemist employs diffusion models fine-tuned on synthetic datasets to control material attributes such as roughness, metallicness, albedo, and transparency in real images.
Bio:Prafull Sharma is a Postdoctoral Associate working with Prof. Josh Tenenbaum and Prof. Phillip Isola in the Computer Science and Artificial Intelligence Lab (CSAIL) and Brain and Cognitive Science (BCS) department at MIT on world modeling. During his PhD, he was advised by Prof. Bill Freeman and Prof. Fredo Durand in the Computer Vision and Graphics group at MIT CSAIL. His research focuses on representation learning grounded in physical properties using synthetic data. He is interested in leveraging the priors of pre-trained models to obtain disentangled representations grounded in the physic
- Algebraic complexity classes and their characterizations
Abstract:Speaker: Prasad Chaugule
Date: 2024-11-25 Time: 12:30:00 (IST) Venue: #501, Bharti Building The main central question in the algebraic complexity theory is "VP vs. VNP," where the class VP is the algebraic analog of the boolean class P and the class NP is the algebraic analog of the counting version of the boolean class NP, which is #P. By definition, the class VP sits inside the class VNP, but whether the containment is strict is not known. While these classes are widely believed to be different, the lower bounds are hard to prove. As it is always meaningful to characterize the classes in other ways, one way to characterize such a class is to find a polynomial sequence complete for the class. Permanent (counting weighted perfect matching in a complete bipartite graph) is known to be VNP complete (for fields of characteristic not equal to 2). Almost a decade ago, there were no polynomial sequences (independent of the computational model) known to be VP complete. Durand et al. [1] gave new model-independent polynomial sequences complete for the class VP, which were based on the notion of counting weighted homomorphisms between two graph sequences (G_n) and (H_n). This line of work was later extended by Mahajan et al. [2] and Chaugule et al. [3].
In this talk, we will discuss a new polynomial sequence that is shown to be VP-complete for large enough fields. We show that counting weighted homomorphisms from a Log-Depth (log n) perfect complete binary tree to a complete graph of size, say poly(n), is VP complete. Moreover, we show that counting weighted homomorphisms from a path of length n to a complete graph of size poly(n) characterizes the class VBP (VBP is in VP). We will also discuss the characterizations of the classes VP and VNP by an algebraic branching program appended by a stack-like memory/random access memory due to Mengel [4] and new results/ideas in this context.
[1] Homomorphism Polynomials Complete for VP. FSTTCS 2014: 493-504
[2] Some Complete and Intermediate Polynomials in Algebraic Complexity Theory. CSR 2016
[3] Variants of Homomorphism Polynomials Complete for Algebraic Complexity Classes. COCOON 2019
[4] Arithmetic Branching Programs with Memory. MFCS 2013
Bio:MS Teams link: https://teams.microsoft.com/l/meetup-join/19%3ameeting_OTFlOTNmNzAtNWZlYi00YmMzLTg2NWItNjJiN2E4OWI0ZDUw%40thread.v2/0?context=%7b%22Tid%22%3a%22624d5c4b-45c5-4122-8cd0-44f0f84e945d%22%2c%22Oid%22%3a%221b7f86d4-5db1-499a-8627-45898b91c9a0%22%7d
- Probabilistic Generating Circuits - Demystified
Abstract:Speaker: Sanyam Agarwal, Saarland University
Date: 2024-11-13 Time: 16:00:00 (IST) Venue: #501, Bharti Building Zhang et al. (ICML 2021, PLMR 139, pp. 12447–1245) introduced probabilistic generating circuits (PGCs) as a probabilistic model to unify probabilistic circuits (PCs) and determinantal point processes (DPPs). At a first glance, PGCs store a distribution in a very different way, they compute the probability generating polynomial instead of the probability mass function and it seems that this is the main reason why PGCs are more powerful than PCs or DPPs. However, PGCs also allow for negative weights, whereas classical PCs assume that all weights are nonnegative. One of the main insights of our paper is that the negative weights are responsible for the power of PGCs and not the different representation. PGCs are PCs in disguise, in particular, we show how to transform any PGC into a PC with negative weights with only polynomial blowup. PGCs were defined by Zhang et al. only for binary random variables. As our second main result, we show that there is a good reason for this: we prove that PGCs for categorial variables with larger image size do not support tractable marginalization unless NP = P. On the other hand, we show that we can model categorial variables with larger image size as PC with negative weights computing set-multilinear polynomials. These allow for tractable marginalization. In this sense, PCs with negative weights strictly subsume PGCs.
Bio:(https://sanyamagarwal7.github.io/
- Interactive Cognition and Haptics
Abstract:Speaker: Dr. Madhan Kumar Vasudevan
Date: 2024-11-06 Time: 12:00:00 (IST) Venue: Bharti Building #501 Haptics, the exploration of touch-based interaction, is becoming an essential part of Human-Computer Interaction (HCI), influencing how we engage with both digital and physical systems. From enhancing immersive experiences in virtual environments to creating tools for improving fine motor skills and addressing sensorimotor impairments, haptic feedback is transforming the way humans interact with technology. My research explores the intersection of sensory perception, emotion, human cognition, and engineering, aiming to develop haptic technologies that enrich and deepen user experiences through innovative design and technical advancements. In this talk, I will present a series of research projects that highlight how haptics can be leveraged to shape user interaction in HCI. Starting with computational models of vibration receptors in the skin to understand neurophysiology and moving on to interactions in virtual reality environments where vibrotactile feedback enhances fine motor skills training, I will explore both human perception and interaction methods. Furthermore, I will discuss my recent exploration of affective touch communication and mindfulness meditation combined with mid-air haptic technology—a form of haptic feedback that delivers tactile sensations through ultrasound waves in mid-air, without physical contact—which has been shown to enhance sensory perception and emotional well-being. By focusing on the integration of haptic technology within HCI frameworks, these projects demonstrate how touch-based interfaces can foster more intuitive, emotionally engaging, and human-centered interactions. Through this research, we can enhance user experience in diverse fields ranging from virtual environments to healthcare, ultimately making technology more responsive to human needs and emotions.
Bio:Dr. Madhan Kumar Vasudevan is a Postdoctoral Research Fellow at University College London (UCL), specializing in Human-Computer Interaction (HCI), computational neuroscience, and haptics. He earned his Ph.D. from the Indian Institute of Technology (IIT) Madras, where he contributed to the study of sensory perception, haptic technology, and virtual/extended reality interactions, particularly in the computational modeling of vibration receptors. His current research focuses on affective computing, specifically on how emotions can be conveyed through mid-air haptics, with the goal of enabling intuitive, long-distance touch communication to enhance emotional connections in remote interactions. In addition to his postdoctoral work, Dr. Madhan has secured funding from the UCL Institute of Healthcare Engineering and led cross-cultural research initiatives on healthy aging, in collaboration with IIT Madras and UCL Computer Science. He has published extensively in top-tier conferences such as CHI and World Haptics, and served as an Associate Chair for CHI 2024. He has actively mentored students in HCI research at UCL and demonstrated his commitment to public engagement through co-production workshops with elderly communities in both the UK and India, focusing on cross-cultural nuances in sensory experiences and healthy aging.
- Logic and asymptotic combinatorics of Graph Neural Networks.
Abstract:Speaker: Prof. Michael Benedikt
Date: 2024-11-01 Time: 14:00:00 (IST) Venue: Bharti Building #501 Graph neural networks (GNNs) are the predominant architectures for a variety of learning tasks on graphs. We present a new angle on the expressive power of GNNs by studying how the predictions of a GNN probabilistic classifier evolve as we apply the classifier on larger graphs drawn from some random graph model. We show that the output converges asymptotically almost surely to a constant function, which upper-bounds what these classifiers can express uniformly.
Our convergence results are framed within a query language with aggregates, subsuming a very wide class of GNNs, including state of the art models, with aggregates including mean and the attention-based mechanism of graph transformers. The results apply to a broad class of random graph models, but in the talk we will focus on Erdős-Rényi model and the stochastic block model. The query language-based approach allows our results to be situated within the long line of research on convergence laws for logic.
The talk will include joint work with Sam Adam-Day, Ismail Ceylan, and Ben Finkeshtein -- see https://arxiv.org/abs/2403.03880, and also joint work with Sam Adam-Day and Alberto Larrauri.
Bio:Prof. Michael Benedikt (https://www.cs.ox.ac.uk/people/michael.benedikt/home.html) from the University of Oxford
- Improvising the Generalizability of Meta-learning Approaches for Few-shot Learning.
Abstract:Speaker: Dr. Aroof Aimen
Date: 2024-10-25 Time: 17:00:00 (IST) Venue: online Deep learning models often require large labeled datasets for training, which can be difficult to obtain in real-world scenarios. To address this, few-shot learning has emerged as a key area in machine learning, aiming to train models effectively with minimal data and enabling them to generalize to new, unseen instances. Meta-learning offers a promising approach for few-shot learning but relies on several assumptions about task distributions, meta-knowledge, and evaluation setups. This talk will focus on the assumption concerning task distribution, specifically addressing Support-Query Shifts (SQS). The concept of SQS is extended to a more practical scenario, termed SQS+, which involves unknown support-query shifts during meta-testing that may differ from the meta-training shift. Existing methods to handle SQS and SQS+ typically use transductive approaches that require unlabeled query data during meta-testing. An inductive approach Adversarial Query Projection (AQP) is introduced which is designed to address both SQS and SQS+ without relying on unlabeled query data. AQP introduces adversarial perturbations to the query sets, creating a deliberate gap between the support and query sets within a new virtual task. This approach leverages the inherent dissimilarity between the initial and perturbed distributions to encourage the model to learn robust, shift-resistant representations. As a result, AQP enhances the model's ability to handle diverse and unfamiliar distribution shifts during meta-testing.
Bio:Aroof Aimen is a Research Associate in the Department of Radiology at the University of Wisconsin-Madison. Her research focuses on applying machine learning techniques for diagnosing and predicting the progression of brain tumors. She is also working on foundational models for detecting neurological disorders. Aroof earned her Ph.D. from the Indian Institute of Technology, Ropar, where she specialized in machine learning within the computer science and engineering domain. Her dissertation, "Analyzing and Improving the Generalizability of Meta-Learning Approaches for Few-Shot Learning," concentrated on advancing meta-learning methods to enhance generalization. She has also developed metrics for monitoring the training progress of Generative Adversarial Networks (GANs). Her research has been featured in top-tier machine learning conferences and journals, including ECML, ICML, and Transactions on AI. During her Ph.D., Aroof completed a one-year research internship at Wadhwani AI, focusing on machine learning models for disease detection from chest X-rays, particularly in low-resource settings. Outside of her academic work, Aroof enjoys traveling and trying new cuisines.
- Presburger Arithmetic : Quantifier Elimination and Some Applications.
Abstract:Speaker: Dr. Khushraj Nanik Madnani
Date: 2024-10-23 Time: 12:00:00 (IST) Venue: #501, Bharti Building In this talk, we revisit the fundamental problem of quantifier elimination in Existential Presburger Arithmetic. Presburger Arithmetic (equivalently Linear Integer Arithmetic) is a decidable fragment of first-order logic over the integers with addition(+) and order(<,=), and it is widely used in formal verification, logic, and model checking. Existential Presburger Arithmetic is a fragment of Presburger Arithmetic containing only existential quantifiers. Quantifier elimination is a fundamental problem in First Order Theories, which involves transforming a formula with quantifiers (existential and for all) into an equivalent formula without them, while maintaining the same logical meaning, and has wide applications in the domain of automated reasoning and formal verification.
Historically, quantifier elimination in Existential Presburger Arithmetic has been believed to require doubly exponential time. As the main highlight of this talk, we challenge this long-standing claim. Our recent work refutes this by introducing a novel procedure which accomplishes quantifier elimination for the existential fragment of Presburger Arithmetic in singly exponential time. The core of our approach is a small model property for parametric integer programming, which extends the seminal results of von zur Gathen and Sieveking on small integer points within convex polytopes. Additionally, if time permits, I will discuss a compelling application of Presburger Arithmetic in proving a dichotomy related to the reachability problem for counter machines (automata extended with integer variables) with infrequent reversals.
Bio:Khushraj Madnani is a postdoctoral researcher at the Max-Planck Institute for Software Systems in Kaiserslautern, Germany, associated with the Rigorous Software Engineering group and the Models of Computation group. His research interest is broadly within the domain of formal verification of infinite-state systems, focusing primarily on (1) automata and logics for timed systems, (2) formal logics and models of computation, and (3) network controlled cyber physical systems.
Khushraj completed his Master's and Ph.D. in Computer Science and Engineering at the Indian Institute of Technology (IIT) Bombay, Mumbai, India, under the guidance of Prof. S. Krishna and Prof. Paritosh K. Pandya where he defended his thesis titled "On Decidable Extensions of Metric Temporal Logic".
Before joining the Max-Planck Institute, Khushraj was a postdoctoral researcher at the Delft Center for Systems and Control (DCSC) within the Faculty of Mechanical Engineering at Delft University of Technology, The Netherlands. He also served as a visiting postdoctoral fellow at the Tata Institute of Fundamental Research (TIFR) in Mumbai, India.
- Recent Advances in Polynomial Identity Testing
Abstract:Speaker: Pranjal Dutta from NUS
Date: 2024-10-16 Time: 12:00:00 (IST) Venue: #501, Bharti Building Polynomial Identity Testing (PIT) is the problem of testing whether a succinctly given polynomial is zero. Though efficient randomized algorithms exist, derandomizing PIT is a fundamental challenge with remarkable consequences in algebraic complexity theory and various classical algorithmic problems. Significant progress has been made on this problem in the last decade. In this talk, we will present a comprehensive overview of these recent developments and discuss a few techniques behind them.
This survey talk is based on many recent papers on PIT, and the survey, jointly written with Sumanta Ghosh (CMI), which got invited and published in the ACM SIGACT Complexity Theory Column; one can find it here: https://dl.acm.org/doi/10.1145/3674159.3674165.
Bio:Pranjal Dutta (https://sites.google.com/view/pduttashomepage) is currently a Postdoc at the School of Computing, NUS, hosted by Prof. Divesh Aggarwal. His broad research area is Complexity theory. He finished his PhD in Computer Science (2018-2022), from Chennai Mathematical Institute (CMI), under the guidance of Prof. Nitin Saxena (IIT Kanpur). He was a Google PhD Fellow (2018-2022) and subsequently, he won the ACM India Doctoral Dissertation Award 2023. He obtained his bachelor's in Mathematics and Computer science (2013-2016) and master's in Computer science (2016-2018) both from CMI.
- Bridging the Theory and Practice of Cryptography
Abstract:Speaker: Ashrujit Ghoshal, Carnegie Mellon University
Date: 2024-10-10 Time: 16:00:00 (IST) Venue: online In the current internet landscape, cryptography plays a central role in securing communication. We rely on mathematical proofs to ensure security of the cryptographic systems that are deployed in practice. However, in many cases, due to issues like efficiency constraints, there is a gap between what these deployments need and what we can prove. In this talk, I will describe how my research identifies these gaps and makes progress towards bridging these gaps using new theoretical insights and techniques from different areas of computer science like complexity theory, algorithms, combinatorics, information theory, etc.
More concretely, my work contributes towards bridging these gaps in three different ways. First, I provide exact security analyses of cryptographic systems that have been deployed at scale that did not have such analyses before. With the exact analyses available, practitioners can set parameters of the cryptographic system in a way that maximizes efficiency without sacrificing security. Secondly, I construct new cryptographic schemes that are better than existing schemes in terms of efficiency. This work helps make purely theoretical cryptographic notions practical. Finally, my work incorporates newer perspectives into the framework of security proofs that captures a more complete picture of the real world. This is in contrast to prior work where only certain adversarial resources were taken into account. A more complete picture of adversarial resources often helps in setting parameters in a way that increases efficiency of cryptographic systems.
Bio:Ashrujit Ghoshal is a postdoctoral fellow at Carnegie Mellon University. He received his PhD from the University of Washington in 2023. His research focuses on bridging the gap between the theory and practice of cryptography by developing new theory that characterizes security and efficiency of cryptographic systems as precisely as possible. In particular his work has provided exact security analyses for cryptography that is widely used in practice e.g., standard hash functions like SHA-2 and SHA-3, TLS, etc. His work has also made progress towards making theoretical cryptographic functionalities like private information retrieval more practical by giving new concretely efficient constructions. These works have led to multiple papers at the two top cryptography conferences- CRYPTO and EUROCRYPT.
- Brick Kiln Detection from low-resolution satellite imagery
Abstract:Speaker: Zeel, IIT Gandhinagar
Date: 2024-10-09 Time: 16:00:00 (IST) Venue: SIT #001 Air pollution kills 7 million people annually. The brick manufacturing industry is the second largest consumer of coal, contributing to 8%-14% of air pollution in the Indo-Gangetic plain. Due to the unorganized nature of brick kilns, monitoring their compliance with evolving national policies is challenging. Air quality experts digitally locate the brick kilns using tools such as Google Earth. Previous work has employed computer vision to detect brick kilns from high-resolution imagery which is costly and has barriers for the open research due to licensing issues. In this work, we explore low-resolution Sentinel-2 imagery (10m) for brick kiln detection, which is available freely for anyone to download and redistribute. We use YOLO's oriented object detection variant to detect the kilns. After detection, we show the automatic compliance monitoring with the detected kilns which can be immensely helpful for the policy executors including but not limited to the pollution control boards.
Bio:Zeel is a PhD student in Computer Science and Engineering at the Sustainability lab, IIT Gandhinagar advised by Prof. Nipun Batra. His research area of interest is AI for Social Good. Zeel has recently received Microsoft Research PhD Fellowship award. He was a Google Summer of Code contributor at TensorFlow in 2022. Zeel has co-authored the "Active Learning" section in the latest addition of a well-known ML book, "Probabilistic Machine Learning" by Kevin Murphy.
- ApneaEye: Thermal-Imaging Based Respiration Sensing for Sleep Apnea Diagnosis
Abstract:Speaker: Dr. Nipin Batra, IIT Gandhinagar
Date: 2024-10-09 Time: 17:00:00 (IST) Venue: SIT #001 Sleep apnea, a sleep disorder characterized by breathing pauses during sleep has a global prevalence of approximately one billion people and is associated with an increased risk of heart attack and stroke. The gold standard of diagnosing sleep apnea requires instrumenting a person with various sensors during her sleep to extract respiratory parameters like nasal airflow and thoracoabdominal movement. Prior works have investigated non-contact methods of diagnosing apnea but they are limited because i) they sense only either thorax or abdomen movements, and ii) they are evaluated on subjects under controlled sleeping conditions. In this work, we present textit{ApneaEye}: a low resolution non-contact thermal camera based system that senses i) nasal airflow and ii) thoracoabdominal movement to diagnose apnea and its types. We evaluated the system on 44 participants including 24 individuals with a sleep apnea who slept unobtrusively overnight. Our results show that ApneaEye can sense respiration from temperature differences between inhalation and exhalation and thoracoabdominal movement with an error of 0.33 and 0.57 BrPM (Breaths Per Minute), respectively. Using these two respiration signals, ApneaEye also estimates apnea and hypopnea instances with a Mean Absolute Error (MAE) of 1.6 and 0.6 respectively in comparison to the gold standard. Our work shows that it is possible to identify other sleep-related complications like thoracoabdominal asynchrony and causes of sleep apnea like nasal blockage by monitoring the thermal data. ApneaEye promises to aid in the diagnosis and management of sleep apnea without the need for in-contact sensors or in-situ training data or personalization.
Bio:Nipun Batra is an Assistant Professor in Computer Science at IIT Gandhinagar. He previously completed his postdoc from University of Virginia. He completed his PhD. from IIIT Delhi where he was a TCS PhD fellow. His group called the Sustainability Lab broadly works on machine learning and sensing for computational sustainability problems like smart buildings, air quality and wearable healthcare. His work has been awarded several awards, including, young alumni award from IIIT Delhi, the best PhD presentation at ACM Sensys, best demo at ACM Buildsys, and a best video nominee at ACM.
- John Gardner’s Adventures in Information Accessibility
Abstract:Speaker: Prof. John Gardner, ViewPlus
Date: 2024-10-07 Time: 15:00:00 (IST) Venue: SIT #001 This is not a scientific lecture. It is a personal accounting of adventures and misadventures that have led to me standing before an audience at IIT Delhi. I will explain the reasons that led me to begin research on accessibility to complex information and why today my work is primarily on accessibility of graphical information. I will also describe at least briefly the developments that have been made in my Oregon State University lab and at ViewPlus. And of course, I will paint a picture of what is being developed today and what I see as the future of information accessibility by people with visual disabilitie
Bio:John Gardner is a physicist who lost his sight in mid-career as Professor of Physics at Oregon State University. He was born with only one eye and developed glaucoma as a small child. When eyedrops became ineffective in controlling the glaucoma, he underwent a “minor” operation to install a pressure valve. His eye reacted badly, and he lost his sight overnight. Prof. Gardner continued to do physics research but found it difficult to analyse the visually fitted data, so he established an accessibility institute at Oregon State University funded by the National Science Foundation. It was devoted to improving accessibility of math, science, graphics, and other complex information. In 1996 he founded ViewPlus Technologies, which has grown into a multi-million-dollar company producing information-access hardware and software. He has received numerous awards and has given invited presentations on both physics and information accessibility on five continents.
- ARMOUR: Architecting Selective Refresh based Multi-Retention Cache for Heterogeneous System
Abstract:Speaker: Dr. Sukarn Agarwal, IIT Guwahati
Date: 2024-10-03 Time: 11:00:00 (IST) Venue: online he increasing use of chiplets, and the demand for high-performance yet low-power systems, will result in heterogeneous systems that combine both CPUs and accelerators (e.g., general-purpose GPUs). Chiplet based designs also enable the inclusion of emerging memory technologies, since such technologies can reside on a separate chiplet without requiring complex integration in existing high-performance process technologies. One such emerging memory technology is spin-transfer torque (STT) memory, which has the potential to replace SRAM as the last-level cache (LLC). STT-RAM has the advantage of high density, non-volatility, and reduced leakage power, but suffers from a higher write latency and energy, as compared to SRAM. However, by relaxing the retention time, the write latency and energy can be reduced at the cost of the STT-RAM becoming more volatile. The retention time and write latency/energy can be traded against each other by creating an LLC with multiple retention zones. With a multi-retention LLC, the challenge is to direct the memory accesses to the most advantageous zone, to optimize for overall performance and energy efficiency. We propose ARMOUR, a mechanism for efficient management of memory accesses to a multi-retention LLC, where based on the initial requester (CPU or GPU) the cache blocks are allocated in the high (CPU) or low (GPU) retention zone. Furthermore, blocks that are about to expire are either refreshed (CPU) or written back (GPU). In addition, ARMOUR evicts CPU blocks with an estimated short lifetime, which further improves cache performance by reducing cache pollution. Our evaluation shows that ARMOUR improves average performance by 28.9% compared to a baseline STT-RAM based LLC and reduces the energy-delay product (EDP) by 74.5% compared to an iso-area SRAM LLC.
Bio:Dr. Sukarn Agarwal received his Ph.D. in Computer Science and Engineering from IIT Guwahati, India, in 2020. He is currently working as an assistant professor at EECS, IISER Bhopal. Before that, He was a Senior Research Fellow with the School of Informatics, University of Edinburgh, Edinburgh, U.K. His research interests include Emerging Memory Technologies, Memory System Design, Network-on-chip design, Thermal-Aware Cache Management, Memory Consistency, and Heterogeneous Systems. He has published seven journal papers and sixteen conference papers. He has received the best paper awards in VLSI-SOC 2017 and ISED 2018 and has received a TCS research fellowship.
- Recent progress on interpretable clustering
Abstract:Speaker: Prof. Sanjoy Dasgupta from UCSD
Date: 2024-09-23 Time: 12:00:00 (IST) Venue: #501, Bharti Building The widely-used k-means procedure returns k clusters that have arbitrary convex shapes. In high dimension, such a clustering might not be easy to understand. A more interpretable alternative is to constraint the clusters to be the leaves of a decision tree with axis-parallel splits; then each cluster is a hyperrectangle given by a small number of features.
Is it always possible to find clusterings that are intepretable in this sense and yet have k-means cost that is close to the unconstrained optimum? A recent line of work has answered this in the affirmative and moreover shown that these interpretable clusterings are easy to construct.
I will give a survey of these results: algorithms, methods of analysis, and open problems.
Bio:Sanjoy Dasgupta is Professor of Computer Science at UC San Diego. He works primarily on unsupervised and minimally supervised learning. He is the author of a textbook, Algorithms, with Christos Papadimitriou and Umesh Vazirani.
- Recent Advances in the Maker Breaker Triangle Game
Abstract:Speaker: Anand Srivastav, Kiel University, Germany
Date: 2024-09-20 Time: 12:00:00 (IST) Venue: #501, Bharti Building The triangle game introduced by Chvátal and Erdős (1978) is one of the old and famous combinatorial games. For n, q ∈ N, the (n,q)-triangle game is played by two players, called Maker and Breaker, on the complete graph K_n.
Alternately Maker claims one edge and thereafter Breaker claims q edges of the graph. Maker wins the game if he can claim all three edges of a triangle. Otherwise, Breaker wins. Chvátal and Erdős (1978) proved that for q < sqrt(n/2), Maker has a winning strategy, while for q > 2 sqrt(n), Breaker wins. So, the threshold bias must be in the interval [sqrt(1/2)sqrt(n) , 2 sqrt(n)].
Since then, the problem of finding the exact constant (and an associated Breaker strategy) for the threshold bias of the triangle game has been one of the interesting open problems in combinatorial game theory. In fact, the constant is not known for any graph with a cycle and we do not even know if such a constant exists. Balogh and Samotij (2011) slightly improved the Chvátal-Erdős constant for Breaker's winning strategy from 2 to 1.935 with a randomized approach. Thereafter, no progress was made. In this work, we present a new deterministic strategy for Breaker leading to his win if q > sqrt(8/3) sqrt(n), for sufficiently large n. This almost matches the Chvátal-Erdős bound of sqrt(1/2)sqrt(n) for Maker's win (Glazik, Srivastav, Europ.J.Comb.2022).
In contrast to previous (greedy) strategies, we introduce a suitable non-linear potential function on the set of nodes. By keeping the potential small, Breaker picks edges that neutralize the most 'dangerous' nodes with incident Maker edges blocking Maker triangles. A characteristic property of the dynamics of the game is that the total potential is not monotonely decreasing. In fact, the total potential of the game may increase, even for several turns, but finally Breaker's strategy prevents the total potential of the game from exceeding a critical level, which results in Breaker's win. We further survey recent and first results for Breaker's win for cycles of length k, a general potential function theorem, and a winning strategy for Maker for the C_4. (Sowa, Srivastav 2024)
This is joint work with Christian Glazik, Christian Schielke and Mathias Sowa, Kiel University.
Bio:Anand Srivastav, Kiel University, Germany
- On the Power of Interactive Proofs for Learning
Abstract:Speaker: Dr. Ninad Rajgopal
Date: 2024-09-18 Time: 16:00:00 (IST) Venue: #501, Bharti Building Interactive proof systems for delegating computation allow a resource-constrained client (or a verifier) to outsource a computational task to a powerful, yet untrusted server (prover). The goal of such a proof system is for the client to verify the result of the task using significantly fewer resources, than performing it from scratch, by interactively exchanging messages with the server who is required to prove the correctness of its computation. Such proof systems have found ubiquitous use in computational complexity theory, as well as for practical applications.
In this talk, we will first introduce a model by Goldwasser, Shafer, Rothblum and Yehudayoff (2021), for delegating a learning task to a server and interactively verifying its correctness. Following this we will see delegation proof systems for problems fundamental to the study of the computational complexity of learning, that allow for highly efficient verification in comparison with performing the learning task.
This is joint work with Tom Gur, Mohammad Mahdi Jahanarah, Mohammad Mahdi Khodabandeh, Bahar Salamatian, and Igor Shinkar (STOC 2024).
Bio:Dr. Ninad Rajgopal is a postdoctoral researcher at the University of Cambridge. He will be starting a post-doctoral position at Charles University, Prague. Prior to this, he was a postdoctoral researcher at the University of Warwick. He obtained his PhD in Computer Science from the University of Oxford advised by Prof. Rahul Santhanam, and Masters in Computer Science from IISc Bengaluru.
His research interests are broadly in complexity theory, with current focus on computational learning theory, probabilistic proof systems, circuit complexity, and meta-complexity.
- Exploring the Cookieverse: A Multi-Perspective Analysis of Web Cookies
Abstract:Speaker: Devashish Gosain, Assistant Professor, IITB
Date: 2024-09-12 Time: 12:00:00 (IST) Venue: #501, Bharti Building Web cookies serve various purposes, like keeping the user logged in or storing a user's preferences for multiple visits to the same website. However, besides their originally intended use, cookies have been exploited for commercial activities like user tracking and targeted advertisement. Thus, web cookies have been extensively studied over the last few years. However, most existing research does not consider multiple crucial perspectives that can influence the cookie landscape and may lead to incorrect inferences. These perspectives include the client's location and operating system, landing vs. inner web pages, desktop vs. mobile phone, and cookie banner interaction. In this talk, I will present the challenges in analyzing the cookie landscape due to these perspectives and elaborate on the methods we use to study them through our measurement research.
Our research demonstrates that "cookie banners" (or cookie notices) are one of the most crucial factors influencing the cookie ecosystem. They are essentially alert messages on the website allowing users to "accept" or "reject" cookies. Thus, we developed the first tool, BannerClick, to automatically detect, accept, and reject cookie banners with an accuracy of 99%. By using BannerClick on the Tranco top-10k websites from different geographic locations, we observe that websites send, on average, 5.5x more third-party cookies after clicking "accept," underlining that it is critical to interact with banners when performing Web measurement. Interestingly, we also found that a new form of paywall-like cookie banner has taken hold on the Web, allowing users to either accept cookies (and consequently user tracking) or buy a paid subscription for a tracking-free website experience. Thus, we performed the first completely automated analysis of cookiewalls, i.e., cookie banners acting as a paywall. We find cookiewalls on 0.6% of all queried 45k websites. Moreover, cookiewalls are deployed to a large extent on European websites, e.g., for Germany, we see cookiewalls on 8.5% of the top 1k websites.
Bio:Devashish Gosain completed his Ph.D. in 2020 from IIIT Delhi in Network Security. In his research, he studied how the knowledge of Internet structure (and maps) can be used to achieve efficient nation-scale traffic filtering. The research involved collecting actual network traces from different Indian ISPs and studying the filtering policies and websites blocked by them. After completing his Ph.D., he worked as a postdoctoral researcher in the INET research group at Max Planck Institute of Informatics, followed by a year postdoc at the COSIC research group at KU Leuven. During his postdoc, he worked on network security problems like measuring the anonymity of peer-to-peer networks, mitigating MITM attacks in end-to-end encrypted protocols (e.g., Signal), and measuring the impact of privacy laws like GDPR on user tracking, etc. His research has been published in the reputed security and networking venues like CCS, NDSS, INFOCOM, IMC, PETS, Usenix Security, ACSAC, PAM, etc. He is currently working as an assistant professor at IIT Bombay.
- Trust in the Untrusted World?
Abstract:Speaker: Divy Agrawal, Computer Science at the University of California
Date: 2024-08-23 Time: 11:00:00 (IST) Venue: SIT #001 We live in interesting times in that our digital lives have become increasingly interdependent and interconnected. Such interconnections rely on a vast network of multiple actors whose trustworthiness is not always guaranteed. Over the past three decades, rapid advances in computing and communication technologies have enabled billions of users with access to information and connectivity at their fingertips. Unfortunately, this rapid digitization of our personal lives is also now vulnerable to invasion of privacy. In particular, now we have to worry about the malicious intent of individual actors in the network as well as large and powerful organizations such as service providers and nation states. In the backdrop of this reality of the untrusted world, we raise the following research questions: (i) Can we design a scalable infrastructure for voice communication that will hide the knowledge of who is communicating with whom? (ii) Can we design a scalable system for oblivious search for documents from public repositories? (iii) Can we develop scalable solutions for private query processings over public databases? These are some of the iconic problems that must be solved before we can embark on building trusted platforms and services over untrusted infrastructures. In this talk, we present a detailed overview of a system for voice communication that hides communication metadata over fully untrusted infrastructures and scales to tens of thousands of users. We also note that solutions to the above problems rely on an intermediary service provider. We conclude this talk with an open question on the efficacy of a decentralized paradigm for cryptocurrency in the broader context of our digital lives that can potentially eliminate the need for an intermediary in provisioning trusted services and platforms.
Bio:Divy Agrawal is a Distinguished Professor and Chair of Computer Science at the University of California at Santa Barbara. He also holds the Leadership Endowed Chair in the Department of Computer Science at UCSB. He received BE(Hons) from BITS Pilani in Electrical Engineering and then received MS and PhD degrees in Computer Science from State University of New York at Stony Brook. Since 1987, he has been on the faculty of computer science at the University of California at Santa Barbara. His research expertise is in the areas of databases, distributed systems, cloud computing, and big data infrastructures and analysis. Over the course of his career, he has published more than 400 research articles and has mentored approximately 50 PhD students. He serves as Editor-in-Chief of the Proceedings of the ACM on Modeling of Data and Springer journal on Distributed and Parallel Databases and has either served or is serving on several Editorial Boards including ACM Transactions on Databases, IEEE Transactions on Data and Knowledge Engineering, ACM Transaction on Spatial Algorithms and Systems, ACM Books, and the VLDB Journal. He served as a Trustee on the VLDB Endowment and is currently serving as the Chair of ACM Special Interest Group on Management of Data (ACM SIGMOD). He received a Gold Medal from BITS Pilani. Professor Agrawal is the recipient of the UCSB Academic Senate Award for Outstanding Graduate Mentoring. He and his co-authors are recipients of best paper awards (ICDE 2002, MDM 2011), influential paper (NDSS 2024), and test-of-time awards (ICDT, MDM). He is a Fellow of the ACM, the IEEE, and the AAAS.
- Revisiting Inclusion Problems
Abstract:Speaker: Ramanathan. S. Thinniyam from Uppsala university
Date: 2024-08-07 Time: 16:00:00 (IST) Venue: #501, Bharti Building A problem of theoretical interest which also has application to program verification is the following: Given two context free languages (CFLs) A and B, is A a subset of B? Unfortunately, the problem is undecidable. Surprisingly, a slight weakening is in PTIME: Given a CFL L, it is included in the corresponding Dyck language (the language of balanced string of brackets). The study of inclusion problems has a long history, starting with Knuth's 1967 paper showing how to decide inclusion in Dyck1. The previously mentioned general PTIME result, however, took about 40 more years to obtain via use of sophisticated techniques which use compressed representations of words.
Since just two stacks can simulate a Turing machine, general undecidability results follow for more sophisticated machines. Our recent results showing that under context-bounding (a highly practically successful approximation technique) the following problem can be solved in coNP: Given an MPDA language L and a context bound k, is L_k included in the corresponding Dyck language? This result gives fresh impetus to study the tractability of different inclusion problems. It also enables the use of SAT/SMT techniques to provide practical new algorithms to questions which have previously been relegated to the domain of heuristics.
Bio: - Automated Synthesis of Decision Lists for Polynomial Specifications over Integers (LPAR 2024)
Abstract:Speaker: Supratik Chakraborty
Date: 2024-06-13 Time: 11:30:00 (IST) Venue: Bharti Building #404 We consider two sets I and O of bounded integer variables, modeling the inputs and outputs of a program. Given a specification Post, which is a Boolean combination of linear or polynomial inequalities with real coefficients over I ∪ O, our goal is to synthesize the weakest pre-condition Pre and a program P satisfying the Hoare triple {Pre}P{Post}. We provide a novel, sound and complete algorithm, inspired by Farkas' Lemma and Handelman's Theorem, that synthesizes both the program P and the pre-condition Pre over a bounded integral region. Our approach is exact and guaranteed to find the weakest pre-condition. Moreover, it always synthesizes both P and Pre as linear decision lists. Thus, our output consists of simple programs and pre-conditions that facilitate further static analysis. We also provide experimental results over benchmarks showcasing the applicability of our approach and performance gains over state-of-the-art.
(Joint work with S. Akshay, Amir Goharshady, Harshit Motwani, R. Govind, Sai T. Varanasi)
Bio:Supratik Chakraborty is Bajaj Group Chair Professor of Computer Science and Engineering at IIT Bombay. He completed his B.Tech. in Computer Science and Engineering from IIT Kharagpur, and M.S. and Ph.D. in Electrical Engineering from Stanford University. After spending a year at Fujitsu Laboratories of America, he joined the CSE Department at IIT Bombay, where he has been a faculty since 2000. His research interests lie at the intersection of theoretical and applied computer science, with a focus on scalable and practical formal methods. He has collaborated extensively with and transferred technologies to government and private industrial organizations. He has also served as an Advisory Board member to Microsoft Research India, and as a Research Advisor to Tata Consultancy Services.
Supratik is a recipient of several awards, including the President of India Gold Medal from IIT Kharagpur, Excellence in Teaching Award from IIT Bombay, IIT Bombay Research Publication Award, and IBM and Qualcomm Faculty Awards. He is a Fellow of Indian National Academy of Engineering, a Distinguished Member of ACM, and a Distinguished
Alumnus of IIT Kharagpur. - Using Hierarchies of Skills to Assess and Achieve Automatic Multimodal Comprehension
Abstract:Speaker: Ajay Divakaran
Date: 2024-06-05 Time: 15:30:00 (IST) Venue: SIT #001 Unlike current visual question answering (VQA), elementary school (K-5) teaching of reading comprehension has a graded approach based on a hierarchy of skills ranging from memorization to content creation. We take inspiration from such hierarchies to investigate the comprehension capabilities of large pretrained multimodal models. First, we have created a new visual question answering dataset that tests comprehension of VQA systems in a graded manner using hierarchical question answering with picture stories. Second, we use Bloom's Taxonomy of comprehension skills it to analyze and improve the comprehension skills of large pre-trained language models. Third, we propose conceptual consistency and consistency of chain of thought to measure a LLM's understanding of relevant concepts. While conceptual consistency, like other metrics, does increase with the scale of the LLM used, we find that popular models do not necessarily have high conceptual consistency. We find overall that large pretrained models still fall well short of true comprehension but are steadily improving.
Bio:Ajay Divakaran, Ph.D., is the Technical Director of the Vision and Learning Lab at the Center for Vision Technologies, SRI International, Princeton. Divakaran has been a principal investigator for several SRI research projects for DARPA, IARPA, ONR etc. His work includes comprehension based characterization of large multimodal models, multimodal analytics for social media, real-time human behavior assessment, event detection, and multi-camera tracking. He has developed several innovative technologies for government and commercial multimodal systems. He worked at Mitsubishi Electric Research Labs during 1998-2008 where he was the lead inventor of the world's first sports highlights playback-enabled DVR, and several machine learning applications. Divakaran was named a Fellow of the IEEE in 2011 for his contributions to multimedia content analysis. He has authored two books, 140+ publications and 65+ issued patents. He received his Ph.D. degree in electrical engineering from Rensselaer Polytechnic Institute.
- Fast list decoding of univariate multiplicity codes
Abstract:Speaker: Mrinal Kumar
Date: 2024-05-31 Time: 15:00:00 (IST) Venue: Bharti Building #501 Univariate multiplicity codes are a family of algebraic error correcting codes that are obtained by evaluating low degree univariate polynomials and all their derivatives up to a certain order at a set of distinct input points in an underlying field. These codes are a well studied generalisation of the more well known Reed-Solomon codes and are now known to have amazing list decodable properties; specifically, they are known to be efficiently list decodable up to the so-called list decoding capacity with constant list size.
In this talk, he will discuss a recent joint work with Rohan Goyal, Prahladh Harsha and Ashutosh Shankar, where show that these codes can be list decoded up to capacity in nearly linear time. On the way, he will talk about lattices over the univariate polynomial ring, and will see a nearly linear time algorithm for solving linear differential equations of high order.
Bio:Faculty member at STCS, TIFR
- From Randomness to Trainability in Deep Neural Networks.
Abstract:Speaker: Dr. Vinayak Abrol
Date: 2024-04-30 Time: 11:00:00 (IST) Venue: SIT #001 In this work, we study how to avoid two problems at initialisation in very deep neural networks identified in prior works: rapid convergence of pairwise input correlations and vanishing and exploding gradients. We prove that both these problems can be avoided by choosing an activation function possessing a sufficiently large linear region around the origin relative to the bias variance of the network's random initialisation. We demonstrate empirically that using such activation functions leads to tangible benefits in practice, both in terms of test and training accuracy and in terms of training time. Furthermore, we observe that the shape of the nonlinear activation outside the linear region appears to have a relatively limited impact on training.
Bio:Dr. Vinayak Abrol is an Assistant Professor at the Department of Computer Science and Engineering & associated with the Infosys Centre for AI at IIIT Delhi, India. Prior to this, he held an Oxford-Emirates data science fellowship at the Mathematical Institute, University of Oxford, the position of Academic Advisor at Kellogg College, Oxford and SNSF funded postdoctoral position at IDIAP Research Institute, Switzerland. He received his TCS Innovation Labs funded Ph.D. from the School of Computing and Electrical Engineering, IIT Mandi, India in 2018; following M.E and B.E in Electronics and Communication Engineering from Panjab University Chandigarh, India in 2013 and 2011, respectively. He is a recipient of the TCS PhD fellowship, the JP Morgan & Chase faculty research award, the Google exploreCS award and IIT Mandi's Young Achiever Award. His research focuses on the design and analysis of numerical algorithms for information-inspired applications.
- Efficient Control-Scheduling Co-Design of Cyber-Physical Systems
Abstract:Speaker: Dr. Sumana Ghosh, Assistant Professor, Indian Statistical Institute (ISI) Kolkata
Date: 2024-04-24 Time: 12:00:00 (IST) Venue: #501, Bharti Building The rapid growth in the number of features in modern cyber-physical systems (CPSs) has led the current design trend to focus on control-scheduling co-design approaches. These co-design approaches address the joint optimization of control parameters (e.g., control performance) and scheduling parameters (e.g., resource utilization) while guaranteeing the real-time properties of all software control tasks. Software control tasks often share computing resources (e.g., processor-bandwidth). The control performance of such implementations can be improved if the bandwidth sharing can be dynamically regulated in response to input disturbances. In the absence of a structured methodology for planning such measures, the scheduler may spend too much time deciding the optimal scheduling results. This research talk presents a unique approach that can be used a priori for computing co-schedulable execution patterns for a given set of control tasks such that stability remains guaranteed under all possible disturbance scenarios. Additionally, the design of the control scheduling patterns optimizes the average case-control performance and the bandwidth utilization under time-varying input disturbances.
Bio:Dr. Sumana Ghosh is currently working as an assistant professor at the Indian Statistical Institute Kolkata. Prior to that, she completed her postdoc at the Department of Electrical and Computer Engineering, Technical University of Munich in 2020, and her Ph.D. from the Department of Computer Science and Engineering, IIT Kharagpur in 2019. During her postdoctoral research, she also received the prestigious PRIME (Postdoctoral Researchers International Mobility Experience) fellowship from the German Academic Exchange Service. She was the one among two who bagged this fellowship worldwide under the "Engineering" category in the year 2019. She obtained her B.Sc. (Hons.) degree in computer science and M.Sc degree in computer and information science from the University of Calcutta in 2010 and 2012, respectively. Her current research interests include cyber-physical systems, formal verification of neural networks and AI-assisted systems, real-time scheduling for heterogeneous embedded systems, cyber security, and application of ML in electronic design automation.
- Multiagent Reinforcement Learning For Large Agent Population
Abstract:Speaker: Dr. Arambam James Singh, Nanyang Technical University
Date: 2024-04-23 Time: 11:00:00 (IST) Venue: online In today's world, many sectors, such as healthcare, transportation, etc., are rapidly digitizing their industrial processes. This presents a significant opportunity for developing next-generation artificial intelligence systems with multiple agents that can operate effectively at scale. Multiagent reinforcement learning is a field of study that focuses on solving problems in multiagent systems. In this talk, I will share my research that addresses critical challenges such as scalability and credit assignment problems in large-scale multiagent systems, specifically in a cooperative environment. My proposed methodology is built around aggregate information, which offers a high level of scalability. Importantly, the dimension of key statistics needed for training the multiagent policies does not change, even if the number of agents increases significantly, making it an effective solution for large-scale complex systems.
Bio:Dr. Arambam James Singh completed his Ph.D. in Computer Science from the School of Computing & Information Systems at Singapore Management University (SMU) in August 2021. He is currently pursuing his second postdoctoral fellowship at Nanyang Technological University (NTU) in Singapore after completing his first postdoctoral fellowship at the National University of Singapore (NUS). His research interests primarily focused on reinforcement learning and multiagent reinforcement learning.
- Modeling Nonstrategic Human Play in Games
Abstract:Speaker: Kevin Leyton-Brown, University of British Columbia
Date: 2024-04-05 Time: 17:00:00 (IST) Venue: #501, Bharti Building It is common to assume that players in a game will adopt Nash equilibrium strategies. However, experimental studies have demonstrated that Nash equilibrium is often a poor description of human players' behavior, even in unrepeated normal-form games. Nevertheless, human behavior in such settings is far from random. Drawing on data from real human play, the field of behavioral game theory has developed a variety of models that aim to capture these patterns.
This talk will survey over a decade of work on this topic, built around the core idea of treating behavioral game theory as a machine learning problem. It will touch on questions such as:- Which human biases are most important to model in single-shot game theoretic settings?
- What loss function should be used to evaluate and fit behavioral models?
- What can be learned about examining the parameters of these models?
- How can richer models of nonstrategic play be leveraged to improve models of strategic agents?
- When does a description of nonstrategic behavior "cross the line" and deserve to be called strategic?
- How can advances in deep learning be used to yield stronger--albeit harder to interpret--models?
Finally, there has been much recent excitement about large language models such as GPT-4. The talk will conclude by describing how the economic rationality of such models can be assessed and presenting some initial experimental findings showing the extent to which these models replicate human-like cognitive biases.
Bio:Kevin Leyton-Brown is a professor of Computer Science and a Distinguished University Scholar at the University of British Columbia. He also holds a Canada CIFAR AI Chair at the Alberta Machine Intelligence Institute and is an associate member of the Vancouver School of Economics. He received a PhD and an M.Sc. from Stanford University (2003; 2001) and a B.Sc. from McMaster University (1998). He studies artificial intelligence, mostly at the intersection of machine learning and either the design and operation of electronic markets or the design of heuristic algorithms. He is increasingly interested in large language models, particularly as components of agent architectures. He believes we have both a moral obligation and a historical opportunity to leverage AI to benefit underserved communities, particularly in the developing world.
He has co-written over 150 peer-refereed technical articles and two books ("Multiagent Systems" and "Essentials of Game Theory"); his work has received over 26,000 citations and an h-index of 61. He is an Fellow of the Royal Society of Canada (RSC; awarded in 2023), the Association for Computing Machinery (ACM; awarded in 2020), and the Association for the Advancement of Artificial Intelligence (AAAI; awarded in 2018). He was a member of a team that won the 2018 INFORMS Franz Edelman Award for Achievement in Advanced Analytics, Operations Research and Management Science, described as "the leading O.R. and analytics award in the industry." He and his coauthors have received paper awards from AIJ, JAIR, ACM-EC, KDD, AAMAS and LION, and numerous medals for the portfolio-based SAT solver SATzilla at international SAT solver competitions (2003–15).
He has co-taught two Coursera courses on "Game Theory" to over a million students (and counting!), and has received awards for his teaching at UBC—notably, a Killam Teaching Prize. He served as General Chair of the 2023 ACM Conference on Economics and Computation (ACM-EC); Program Co-Chair for AAAI 2021 (one of the top two international conferences on artificial intelligence), amongst others. He currently advises Auctionomics, AI21, and OneChronos. He is a co-founder of Kudu.ug and Meta-Algorithmic Technologies. He was scientific advisor to UBC spinoff Zite until it was acquired by CNN in 2011. His past consulting has included work for Zynga, Qudos, Trading Dynamics, Ariba, and Cariocas.
- Data Management for Data Science: a study on space-efficiency
Abstract:Speaker: Prof. Panagiotis Karras , computer science with the University of Copenhagen
Date: 2024-04-01 Time: 16:00:00 (IST) Venue: #501, Bharti Building Data science has the potential to extract valuable insights from data on an unprecedented scale. However, several fundamental data science tasks call for data management solutions that can effectively address problems of space-efficiency to realize this potential. This talk will focus on two cases of data management solutions that enhance scalability and space-efficiency in data science tasks. Firstly, we will discuss how to use a sophisticated technique to render the classical solution for Viterbi decoding via dynamic programming more space-efficient. Secondly, we will outline how to compute the optimal actions in a finite-horizon Markov Decision Process in a space-efficient manner. Thereby, we will outline a vision of how data management expertise can facilitate and advance the frontiers of data science.
Bio:Panagiotis Karras is a professor of computer science with the University of Copenhagen. His research interests include designing robust and versatile methods for data access, mining, analysis, and representation. He received the MSc degree in electrical and computer engineering from the National Technical University of Athens and the PhD degree in computer science from the University of Hong Kong. He was the recipient of the Hong Kong Young Scientist Award, the Singapore Lee Kuan Yew Postdoctoral Fellowship, the Rutgers Business School Teaching Excellence Fellowship, and the Skoltech Best Faculty Performance Award. His work has been published in PVLDB, SIGMOD, ICDE, KDD, AAAI, IJCAI, NeurIPS, ICLR, USENIX Security, TheWebConf, SIGIR, and ACL.
- A billion lifelong readers: The Same Language Subtitling (SLS) story of system change from concept to national policy to quality implementation.
Abstract:Speaker: Dr. Brij Kothari, Adjunct Professor, School of Public Policy, IIT-D and Lead, Billion Readers (BIRD) Initiative
Date: 2024-04-01 Time: 15:30:00 (IST) Venue: #501, Bharti Building The weak foundational literacy outcomes of our complex school system have been known for decades, resulting in 600 million weak readers in addition to 250 million non-readers. Over 60 percent are girls and women. The Billion Readers (BIRD) Initiative's vision is: Every Indian a fluent reader. BIRD leverages India's vibrant and multilingual entertainment ecosystem to deliver guaranteed daily and lifelong reading practice to one billion small screen (TV, streaming & mobile) viewers.
Brij will focus on the system change strategy that BIRD has pursued with government, civil society, academia and media companies, spanning 28 years, including a mix of evidence-based-policymaking, advocacy, coalition-building with disability rights groups, design thinking, technology development, and legal tools. Having recently joined as Adjunct Professor at SPP, IIT-D, Brij is actively exploring cross-disciplinary collaboration with faculty and students and has several projects and internship possibilities to suggest. He is especially looking for collaboration on AI-based speech-to-text tech projects in Indian languages to make entertainment accessible in cinema halls, on TV and mobiles/streaming.
Bio:Dr. Brij Kothari is an academic and social entrepreneur. He recently joined the School of Public Policy, IIT-D as Adjunct Professor. He leads the Billion Readers (BIRD) Initiative and is the founder of PlanetRead.org and BookBox.com. Brij conceived of Same Language Subtitling (SLS) on mainstream TV in India for mass reading literacy in 1996, while pursuing his Ph.D. in Education at Cornell University. Since then, he has researched and pushed for SLS in national broadcast policy on the faculty of IIM-Ahmedabad (1996-2023). He is an Ashoka Fellow, a Schwab Social Entrepreneur, the recipient of the International Literacy Prize from the Library of Congress, USA, and Co-Impact's system change grant for BIRD. At IIT-D he is looking for collaboration, coffee, and tennis partners.
- Linguistically-Informed Neural Architectures for Lexical, Syntactic, and Semantic Tasks in Sanskrit
Abstract:Speaker: Dr. Jivnesh Sandhan, IIT Dharwad
Date: 2024-03-21 Time: 11:00:00 (IST) Venue: SIT #001 In this talk, we will focus on how to make Sanskrit manuscripts more accessible to end-users through natural language technologies. The morphological richness, compounding, free word orderliness, and low-resource nature of Sanskrit pose significant challenges for developing deep learning solutions. We identify four fundamental tasks, which are crucial for developing a robust NLP technology for Sanskrit: word segmentation, dependency parsing, compound type identification, and poetry analysis. While addressing these challenges, we make various contributions, such as proposing linguistically-informed neural architectures, showcasing their interpretability and multilingual extension, reporting state-of-the-art performance, and presenting a neural toolkit called SanskritShala, which offers real-time analysis for NLP tasks.
Bio:Dr. Jivnesh Sandhan is a visiting assistant professor at IIT Dharwad in the Department of Computer Science. Prior to that, he remotely worked in the Electrical Engineering and Computer Sciences (EECS) department at the University of California, Berkeley. He completed his Ph.D. in the Department of Electrical Engineering from IIT Kanpur in 2023, where he also earned a dual degree in the Department of Mathematics and Scientific Computing in 2018. He received the prestigious Prime Minister's Research Fellowship (PMRF). His research expertise is Natural Language Processing (NLP) for Sanskrit Computational Linguistics. His primary research objective is to enhance accessibility to Sanskrit literature for pedagogical and annotation purposes. To achieve this goal, he has developed cutting-edge deep-learning-based solutions for various downstream tasks in Sanskrit. His scholarly endeavors have resulted in several publications in high-ranking conference venues, including CORE-ranking A*/A conferences. His current research revolves around developing a Sanskrit-to-English machine translation system to provide accessibility to Vedic literature. Through his work, he seeks to bridge the language barrier and contribute to a broader understanding and appreciation of ancient Sanskrit texts.
- From Biased Observations to Fair and More Effective Decisions
Abstract:Speaker: Nisheeth Vishnoi is the A. Bartlett Giamatti Professor of Computer Science and a co-founder of the Computation and Society Initiative at Yale University
Date: 2024-03-19 Time: 17:00:00 (IST) Venue: Bharti-501 Data from individuals is extensively utilized by various organizations, from multinational corporations to educational institutions, to inform decisions about individuals. However, this data often emerges from the interaction between the individual being observed and the measurement process, whether conducted by humans or AI systems. This observed data often represents a biased version of the 'true' data, and basing decisions on such data can significantly affect their fairness and effectiveness, impacting individuals, organizations, and society as a whole.
This raises critical questions of understanding when and to what extent algorithms can be designed to behave as if they had access to true data. This talk outlines an approach to these questions for the ubiquitous subset selection problem important in hiring and admissions. It starts with behavioral models that illustrate the
transformation of true data into biased data. It then analyzes the impact of existing algorithms when working with such data, and concludes by proposing new algorithms designed to mitigate these biases.
This talk is based on joint works with several co-authors and is suited for a wide audience, including students, academics,
professionals, and anyone interested in the ethical or policy dimensions of data science and AI.
Bio:Nisheeth Vishnoi is the A. Bartlett Giamatti Professor of Computer Science and a co-founder of the Computation and Society Initiative at Yale University. He is a co-PI of an NSF-funded AI Institute: The Institute for Learning-enabled Optimization at Scale. His research spans various areas of Theoretical Computer Science, Optimization, and
Artificial Intelligence. Specific current research topics include Responsible AI, foundations of AI, and data reduction methods. He is also interested in understanding nature and society from a computational viewpoint.
Professor Vishnoi was the recipient of the Best Paper Award at IEEE Symposium on Foundations of Computer Science in 2005, the IBM Research Pat Goldberg Memorial Award in 2006, the Indian National Science Academy Young Scientist Award in 2011, the IIT Bombay Young Alumni Achievers Award in 2016, and the Best Paper award at ACM Conference on Fairness, Accountability, and Transparency in 2019. He was named an ACM Fellow in 2019. His most recent book Algorithms for Convex Optimization was published by Cambridge University Press. - Towards Robust and Reliable Machine Learning: Adversaries and Fundamental Limits
Abstract:Speaker: Arjun Bhagoji, University of Chicago
Date: 2024-03-04 Time: 11:00:00 (IST) Venue: SIT #001 While ML-based AI systems are increasingly deployed in safety-critical settings, they continue to remain unreliable under adverse conditions that violate underlying statistical assumptions. In my work, I aim to (i) understand the conditions under which a lack of reliability can occur and (ii) reason rigorously about the limits of robustness, during both training and test phases.
In the first part of the talk, I demonstrate the existence of strong but stealthy training-time attacks on federated learning, a recent paradigm in distributed learning. I show how a small number of compromised agents can modify model parameters via optimized updates to ensure desired data is misclassified by the global model, while bypassing custom detection methods. Experimentally, this model poisoning attack leads to a lack of reliable prediction on standard datasets.
Test-time attacks via adversarial examples, i.e. imperceptible perturbations to test inputs, have sparked an attack-defense arms race. In the second part of the talk, I step away from this arms race to provide model-agnostic fundamental limits on the loss under adversarial input perturbations. The robust loss is shown to be lower bounded by the optimal transport cost between class-wise distributions using an appropriate adversarial point-wise cost, the latter of which can be efficiently computed via a linear program for empirical distributions of interest.
To conclude, I will discuss my ongoing efforts and future vision towards building continuously reliable and accessible ML systems by accounting for novel attack vectors and new ML paradigms such as generative AI, as well as developing algorithmic tools to improve performance in data-scarce regimes.
Bio:Arjun Bhagoji is a Research Scientist in the Department of Computer Science at the University of Chicago. He obtained his Ph.D. in Electrical and Computer Engineering from Princeton University, where he was advised by Prateek Mittal. Before that, he received his Dual Degree (B.Tech+M.Tech) in Electrical Engineering at IIT Madras, where he was advised by Andrew Thangaraj and Pradeep Sarvepalli. Arjun's research has been recognized with a Spotlight at the NeurIPS 2023 conference, the Siemens FutureMakers Fellowship in Machine Learning (2018-2019) and the 2018 SEAS Award for Excellence at Princeton University. He was a 2021 UChicago Rising Star in Data Science, a finalist for the 2020 Bede Liu Best Dissertation Award in Princeton's ECE Department and a finalist for the 2017 Bell Labs Prize.
- Trends and recent results in the study of non-interactive multi-party computation (NIMPC)
Abstract:Speaker: Prof. Tomoharu Shibuya from Sophia University
Date: 2024-03-01 Time: 16:00:00 (IST) Venue: #501, Bharti Building A large amount of data is required to improve the accuracy of machine learning. However, data often contains personal privacy and corporate sensitive information, making it difficult to freely utilize large amounts of data. Therefore, security technologies that perform various calculations on data while maintaining data confidentiality are attracting attention.
Secure Multi Party Computation (MPC) is a method for parties to jointly compute a function over their inputs while keeping those inputs private. MPC has the drawback that as the number of participating parties increases, the amount of communication between the parties becomes enormous. To overcome this drawback, Secure non-interactive MPC (NIMPC) was developed, which introduces a protocol setup server and a computation server, and each party communicates only with these servers.
In this talk, I will explain a simple method for realizing NIMPC and introduce recent research on NIMPC. In particular, we will introduce an evolving NIMPC that can perform calculations without changing the setup at the start of the protocol even if the number of parties increases after the protocol starts.
I will also provide a comprehensive introduction to the research and faculty members at the Department of Information and Communication Sciences, Sophia University, and discuss possibilities for student and research exchanges between IIT Delhi and Sophia University.
Bio:Prof. Tomoharu Shibuya
(https://researchmap.jp/read0183734?lang=en)
- Heterogenous Benchmarking across Domains and Languages: The Key to Enable Meaningful Progress in IR Research.
Abstract:Speaker: Nandan Thakur
Date: 2024-01-23 Time: 15:00:00 (IST) Venue: SIT #001 Benchmarks are ever so necessary to measure realistic progress within Information Retrieval. However, existing benchmarks quickly saturate as they are prone to overfitting affecting retrieval model generalization. To overcome these challenges, I would present two of my research efforts: BEIR, a heterogeneous benchmark for zero-shot evaluation across specialized domains, and MIRACL, a monolingual benchmark covering a diverse range of languages. In BEIR, we show that neural retrievers surprisingly struggle to generalize zero-shot on specialized domains due to a lack of training data. To overcome this, we develop GPL that distills cross-encoder knowledge using cross-domain BEIR synthetic data. On the language side, MIRACL is robust in annotations and includes a broader coverage of the languages. However, generating supervised training data is cumbersome in realistic settings. To supplement, we construct SWIM-IR, a synthetic training dataset with 28 million LLM-generated pairs across 37 languages to develop multilingual retrievers comparable to supervised models in performance. We can cheaply extend to several new languages.
Bio:Nandan Thakur is a third-year PhD student in the David R. Cheriton School of Computer Science at the University of Waterloo under the supervision of Prof. Jimmy Lin. His research broadly investigates data efficiency and model generalization across specialized domains and languages in information retrieval. He was the co-organizer of the MIRACL competition in WSDM 2023 and will co-organize the upcoming RAG Track in TREC 2024. His work has been published in top conferences and journals, including ACL, NAACL, NeurIPS, SIGIR, and TACL.
- LLMs for Everybody: How inclusive are the LLMs today and Why should we care?
Abstract:Speaker: Monojit Choudhury , professor of Natural Language Processing at Mohd bin Zayed University of Artificial Intelligence (MBZUAI), Abu Dhabi
Date: 2024-01-23 Time: 17:00:00 (IST) Venue: SIT #001 Large Language Models (LLMs) have revolutionized the field of NLP and natural human-computer interactions; they hold a lot of promise, but are these promises equitable across countries, languages and other demographic groups? Research from our group as well as from around the world is constantly revealing that LLMs are biased in terms of their language processing abilities in most but a few of the world's languages, cultural awareness (or lack thereof) and value alignment. In this talk, I will highlight some of our recent findings around value alignment bias in the models and argue why we need models that can reason generically across moral values and cultural conventions.
We will also discuss some of the opportunities for students at postgraduate, PhD and Post doctoral levels at the newly founded MBZUAI university.
Bio:Monojit Choudhury is a professor of Natural Language Processing at Mohd bin Zayed University of Artificial Intelligence (MBZUAI), Abu Dhabi. Prior to this, he was a principal scientist at Microsoft Research Lab and Microsoft Turing, India. He is also a professor of practice at Plaksha University, and an adjunct professor at IIIT Hyderabad. Prof Choudhury's research interests lie in the intersection of NLP, Social and Cultural aspects of Technology use, and Ethics. In particular, he has been working on multilingual aspects of large language models (LLMs), their use in low resource languages and making LLMs more inclusive and safer by addressing bias and fairness aspects. Prof Choudhury is the general chair of Indian national linguistics Olympiad and the founding co-chair of Asia-Pacific linguistics Olympiad. He holds a BTech and PhD degree in Computer Science and Engineering from IIT Kharagpur.
- Geometric GNNs for 3D Atomic Systems
Abstract:Speaker: Chaitanya K. Joshi
Date: 2024-01-18 Time: 15:00:00 (IST) Venue: #501, Bharti Building Recent advances in computational modelling of atomic systems, spanning molecules, proteins, and materials, represent them as geometric graphs with atoms embedded as nodes in 3D Euclidean space. Geometric Graph Neural Networks have emerged as the preferred ML architecture powering breakthroughs ranging from protein structure prediction to molecular simulations and material generation. Their specificity lies in the inductive biases they leverage — such as the underlying physical symmetries and chemical properties — to learn informative representations of geometric graphs. This talk will provide an overview of Geometric GNNs for 3D atomic systems. I will introduce a pedagogical taxonomy of Geometric GNN architectures from the perspective of their theoretical expressive power and highlight practical shortcomings of current models. This talk is based on our recent works: https://arxiv.org/abs/2301.09308, https://arxiv.org/abs/2312.0751
Bio:Chaitanya K. Joshi is a 3rd year PhD student at the Department of Computer Science, University of Cambridge, supervised by Prof. Pietro Liò. His research explores the intersection of Geometric Deep Learning and Graph Neural Networks for applications in biomolecule modelling & design. He previously did an undergraduate degree in Computer Science from Nanyang Technological University and worked as a Research Engineer at A*STAR in Singapore.
- Introduction to Digital Forensics
Abstract:Speaker: Dr. Andrey Chechulin
Date: 2024-01-18 Time: 12:00:00 (IST) Venue: #501, Bharti Building This lecture is a foundational exploration into Digital Forensics, a discipline focusing on the identification, extraction, preservation, and analysis of digital evidence. The relevance of it spans across criminal and civil law where digital evidence is increasingly pivotal. During the lecture we will discuss the broad spectrum of digital evidence, from computer systems to mobile devices, and the unique challenges each presents. The lecture will highlight the critical role digital forensics plays in solving cybercrimes and in resolving legal disputes involving digital data. In addition to theoretical aspects, the examples of practical application of digital forensics will be discussed. Designed for beginners and professionals alike, such as IT experts, lecturers, or students, this lecture aims to impart a comprehensive understanding of digital forensics and its indispensable role in contemporary digital investigations.
Bio:Andrey Chechulin is a Candidate of Technical Sciences (2013, SPbSUT, Russia) and an Associate Professor (2021, SPbSUT, Russia). Currently, he is the Head of the International Digital Forensic Center for Digital Forensics and a leading researcher at the Laboratory of Computer Security Problems of the SPC RAS (Saint-Petersburg, Russia). He is also an associate professor at SPbSUT and ITMO Universities. He has been an invited professor and a scientific advisor of master and PhD students at universities in France, Sweden, and Russia. He is member of many editorial boards of Russian and international journals, and the author of more than 200 refereed publications, including several books and monographs. As a project leader, he has participated in over 15 Russian and international scientific projects for the Russian and EU scientific foundations and commercial companies in Russia and abroad. As a security expert, he has conducted more than 200 expert assessments both in the practical field of cybercrime investigation and court cases and in the academic field, serving as a reviewer for leading international journals, conferences, and research foundations. As a science communicator, he regularly appears on various regional and federal media broadcasts and delivers public lectures on information security. His main research interests include digital forensics, computer network security, artificial intelligence, cyber-physical systems, social network analysis, and security data visualization.
- Network Security and Vulnerabilities Analysis
Abstract:Speaker: Dr. Dmitry Levshun
Date: 2024-01-18 Time: 12:45:00 (IST) Venue: #501, Bharti Building Scientists and developers all over the world are working hard to ensure the information security of network systems. This task is complex due to the diversity of threats and wide range of security requirements. Moreover, specialists detect new vulnerabilities every day, while old vulnerabilities are still present in working systems. The goal of this lecture is to provide the information about the basics of network security evaluation using attack graphs. We will go deep into details how vulnerabilities can be represented in open databases as well as how we can categorise them. After that we will go step by step through the host attack graph construction and analysis. In the end we will discuss how Artificial Intelligence can be used to improve vulnerabilities categorisation.
Bio:Dmitry Levshun is a Candidate of Technical Sciences (ITMO University, Russia) and a Doctor of Philosophy in Computer Science (University of Toulouse III, France). Author of more than 30 publications indexed by Scopus and Web of Science (H-index 8), 5 of which are included in the Q1 quartile. Has over 20 certificates of state registration of programs and databases. Active participant in more than 15 research and development projects of Russian funds. Head of the initiative research project conducted by young scientists. He works as a Senior Researcher at the Laboratory of Computer Security Problems of SPC RAS. Additionally, he works as a leading expert at the International Center for Digital Forensics of SPC RAS. Moreover, Dmitry is an Associate Professor at leading universities in St. Petersburg, namely SPbSUT (Secure communication systems department) and EUSPb (Applied data analysis program). Member of the program committee of FRUCT and COMSNETS conferences. Reviewer for scientific journals such as Electronics, Machines, Micromachines, Inventions, Future Internet and Microprocessors and Microsystems. Area of scientific interests: information security, Internet of Things, artificial intelligence, security by design, modeling of malicious activity.
- Artificial Intelligence for Cyber Security
Abstract:Speaker: Dr. Igor Kotenko
Date: 2024-01-17 Time: 16:00:00 (IST) Venue: #501, Bharti Building Artificial intelligence (AI) has become one of the main approaches to processing huge amounts of heterogeneous data and performing various cyber security tasks, including vulnerability management and security assessment, security monitoring, distributed access control. AI is changing the way computers are programmed and how they are used. In the modern interpretation, AI systems are systems, first, of machine learning, and sometimes these AI systems are even more narrowed down to artificial neural networks. In cyber security, AI methods provided the opportunity to create advanced cyber security tools, but also allowed attackers to significantly improve the cyber attacks. The evolution of attack and defense tools took place mainly in the form of an arms race, which in its essence was asymmetric and beneficial to attackers. Cybercriminals can launch targeted attacks at unprecedented speed and scale, while bypassing traditional detection mechanisms. The talk shows the current state of AI in cyber security. The key areas of focus at the intersection of AI and cyber security are analyzed: enhancing cyber security with AI, AI for cyber attacks, the vulnerability of AI systems to attacks, and the use of AI in malicious information operations. The own research in the field of intelligent monitoring of cyber security and detection of cyber attacks is presented. This research is being supported by the grant of Russian Science Foundation #21-71-20078 in SPC RAS.
Bio:Igor Kotenko is a Chief Scientist and Head of Research Laboratory of Computer Security Problems of the St. Petersburg Federal Research Center of the Russian Academy of Sciences. He is also Professor of ITMO University, St. Petersburg, Russia, and Bonch-Bruevich Saint-Petersburg State University of Telecommunications. He is the Honored Scientist of the Russian Federation, IEEE Senior member, member of many Editorial Boards of Russian and International Journals, and the author of more than 800 refereed publications, including 25 books and monographs. Main research results are in artificial intelligence, telecommunication, cyber security, including network intrusion detection, modeling and simulation of network attacks, vulnerability assessment, security information and event management, verification and validation of security policy. Igor Kotenko was a project leader in the research projects from the European Office of Aerospace Research and Development, EU FP7 and FP6 Projects, HP, Intel, F-Secure, Huawei, etc. The research results of Igor Kotenko were tested and implemented in multitude of Russian research and development projects, including grants of Russian Science Foundation, Russian Foundation of Basic Research and multitude of State contracts. He has been a keynote and invited speaker on multitude of international conferences and workshops, as well as chaired many international conferences.
- A New Perspective on Invariant Generation as Semantic Unification
Abstract:Speaker: Prof. Deepak Kapur, University of New Mexico
Date: 2024-01-12 Time: 15:00:00 (IST) Venue: #501, Bharti Building Unification is the problem of finding instantiations of variables in a finite set of equations constructed using function symbols such that both sides of the instantiated equations are equal. In semantic unification, also called E-unification, function symbols can have properties specified typically by an equational theory; a unifier then makes the two instantiated sides of each equation, equivalent modulo the equation theory. By generalizing the unification problem to a first-order theory in which variables in the problem stand for formulas in the theory, the invariant generation problem in software, hardware, and cyber-physical system can be formulated as a unification problem. Finding a nontrivial unifier in this case amounts to finding an invariant which is a formula in the theory. Similarly, finding a most general unifier in that theory amounts to finding the strongest invariant. Instantiation of variables can be further restricted to formulas with certain shapes/properties. A number of examples from the literature of the automatic generation of loop invariants in software will be used to illustrate this new perspective.
Bio:A distinguished professor at the University of New Mexico since 1998, Kapur served as chair of the Department of Computer Science from Dec. 1998 to June 2006. He has adjunct appointments at IIT, Delhi, India, as well as Tata Institute of Fundamental Research, Mumbai, India. From 1980-1987, he was on the research staff of General Electric Corporate Research and Development, Schenectady, NY. He was appointed tenured full professor at the University at Albany, SUNY, and Albany, NY, in 1988, where he also founded the Institute for Programming and Logics. He has had research collaborations all over the world including TIFR, India; MPI, Saarbrucken, Germany; Chinese Academy of Sciences, Beijing; IMDEA, Madrid, and UPC, Barcelona; Naval Research Lab, Washington. He serves on the editorial boards of numerous journals including the Journal of Symbolic Computation and Journal of Automated Reasoning, for which he also served as the editor-in-chief from 1993-2007. Kapur is on the board of United Nations University-International Institute for Software Technology as well as LIPIcs: Leibniz International Proceedings in Informatics. Kapur was honored with the Herbrand Award in 2009 for distinguished contributions to automated reasoning.
- In Search of a Networking Unicorn: Realizing Closed-Loop ML Pipeline for Networking
Abstract:Speaker: Arpit Gupta, Assistant Professor, UCSB
Date: 2024-01-11 Time: 12:00:00 (IST) Venue: Bharti 501 Machine Learning (ML) and Artificial Intelligence (AI) are driving
transformative changes across various domains, including networking.
It is widely assumed that ML/AI-based solutions to complex security or
performance-specific problems outperform traditional heuristics and
statistical methods. However, this optimism raises a fundamental
question: Can our current ML/AI-based solutions be used for
high-stakes decision-making in production networks where errors can
have serious consequences? Unfortunately, many of these solutions have
struggled to fulfill their promises. The primary issues stem from the
use of inadequate training data and an overemphasis on narrowly scoped
performance metrics (e.g., F1 scores), neglecting other critical
aspects (e.g., a model's vulnerability to underspecification issues,
such as shortcut learning). The result has been a general reluctance
among network operators to deploy ML/AI-based solutions in their
networks.
In this talk, I will highlight our efforts to bridge this trust gap by
arguing for and developing a novel closed-loop ML workflow that
replaces the commonly used standard ML pipeline. Instead of focusing
solely on the model's performance and requiring the selection of the
"right" data upfront, our newly proposed ML pipeline emphasizes an
iterative approach to collecting the "right" training data guided by
an in-depth understanding and analysis of the model's decision-making
and its (in)ability to generalize In presenting the building blocks
of our novel closed-loop ML pipeline for networking, I will discuss
(1) Trustee: A global model explainability tool that helps
identify underspecification issues in ML models; (2) netUnicorn: A
data-collection platform that simplifies iteratively collecting the
"right" data for any given learning problem from diverse network
environments; and (3) PINOT: A suite of active and passive
data-collection tools that facilitate transforming enterprise networks
into scalable data-collection infrastructure. I will conclude the talk
by discussing the potential for developing a community-wide
infrastructure to support this closed-loop ML pipeline for developing
generalizable ML/AI models as key ingredients for the future creation
of deployment-ready ML/AI artifacts for networking.
Bio:Arpit Gupta is an assistant professor in the computer science
department at UCSB. His research focuses on building flexible,
scalable, and trustworthy systems that solve real-world problems at
the intersection of networking, security, and machine learning. He
also develops systems that aid in characterizing and addressing
digital inequity issues. He developed BQT, a tool to extract
broadband plans offered by ISPs in the US; Trustee, a tool to
explain decision-making of ML artifacts for networking; netUnicorn,
a network data collection platform for machine learning
applications; Sonata, a streaming network telemetry system; and SDX,
an Internet routing control system His work on augmenting crowdsourced
Internet measurement data using BQT received the Distinguished Paper
Award at ACM IMC’22; Trustee received IETF/IRTF Applied Networking
Research Award and Best Paper Award (honorable mention) at ACM
CCS’22; SDX received the Internet2 Innovation Award, Best of Rest,
Community Contribution Award USENIX NSDI’16, and the Best Paper
Award at ACM SOSR’17. Arpit received his Ph.D. from Princeton
University. He completed his master's degree at NC State University
and a bachelor's degree at the Indian Institute of Technology,
Roorkee, India.
- Towards Evolving Operating System
Abstract:Speaker: Prof. Sanidhya Kashyap, Assistant Professor, EPFL
Date: 2024-01-10 Time: 14:00:00 (IST) Venue: Bharti-501 In this talk, I will present our ongoing effort to dynamically specialize the OS kernel based on the application requirements. In the first part of the talk, I will propose a new synchronization paradigm, contextual concurrency control (C3), that enables applications to tune
concurrency control in the kernel. C3 allows developers to change the behavior and parameters of kernel locks, switch between different lock implementations, and dynamically profile one or multiple locks for a specific scenario of interest. This approach opens up a plethora of opportunities to fine-tune concurrency control mechanisms on the fly.
In the later part, I will present a new approach to designing a storage stack that allows file system developers to design userspace file systems without compromising file system security guarantees while at the same time ensuring direct access to non-volatile memory (NVM) hardware. I will present a new file system architecture called Trio that decouples file system design, access control, and metadata integrity enforcement. The key insight is that other state (i.e., auxiliary state) in a file system can be regenerated from its “ground truth” state (i.e., core state). This approach can pave the way for providing a clean structure to design file systems.
Bio:Sanidhya Kashyap is a systems researcher and an Assistant Professor at the School of Computer and Communication Sciences at EPFL. His research focuses on designing robust and scalable systems software, such as operating systems, file systems, and system security. He has published in top-tier systems conferences (SOSP, OSDI, ASPLOS, ATC, and EuroSys) and security conferences (CCS, IEEE S&P, and USENIX Security). He is the recipient of the VMware Early Career Faculty Award. He received his Ph.D. degree from Georgia Tech in 2020.
- Towards Evolving Operating Systems
Abstract:Speaker: Sanidhya Kashyap, Assistant Professor, EPFL
Date: 2024-01-10 Time: 14:30:00 (IST) Venue: Bharti-501 In this talk, I will present our ongoing effort to dynamically specialize the OS kernel based on the application requirements.
In the first part of the talk, I will propose a new synchronization paradigm, contextual concurrency control (C3), that enables applications to tune concurrency control in the kernel. C3 allows developers to change the behavior and parameters of kernel locks, switch between different lock implementations, and dynamically profile one or multiple locks for a specific scenario of interest. This approach opens up a plethora of opportunities to fine-tune concurrency control mechanisms on the fly.
In the later part, I will present a new approach to designing a storage stack that allows file system developers to design userspace file systems without compromising file system security guarantees while at the same time ensuring direct access to non-volatile memory (NVM) hardware. I will present a new file system architecture called Trio that decouples file system design, access control, and metadata integrity enforcement. The key insight is that other state (i.e., auxiliary state) in a file system can be regenerated from its “ground truth” state (i.e., core state). This approach can pave the way for providing a clean structure to design file systems.
Bio:Sanidhya Kashyap is a systems researcher and an Assistant Professor at the School of Computer and Communication Sciences at EPFL. His research focuses on designing robust and scalable systems software, such as operating systems, file systems, and system security. He has published in top-tier systems conferences (SOSP, OSDI, ASPLOS, ATC, and EuroSys) and security
conferences (CCS, IEEE S&P, and USENIX Security). He is the recipient of the VMware Early Career Faculty Award. He received his Ph.D. degree from Georgia Tech in 2020. - Memory as a lens to understand efficient learning and optimization
Abstract:Speaker: Dr. Vatsal Sharan (Univ. Southern California)
Date: 2024-01-02 Time: 12:00:00 (IST) Venue: #404, Bharti Building What is the role of memory in learning and optimization? The optimal convergence rates (measures in terms of the number of oracle queries or samples needed) for various optimization problems are achieved by computationally expensive optimization techniques, such as second-order methods and cutting-plane methods. We will discuss if simpler, faster and memory-limited algorithms such as gradient descent can achieve these optimal convergence rates for the prototypical optimization problem of minimizing a convex function with access to a gradient or a stochastic gradient oracle. Our results hint at a perhaps curious dichotomy---it is not possible to significantly improve on the convergence rate of known memory efficient techniques (which are linear-memory variants of gradient descent for many of these problems) without using substantially more memory (quadratic memory for many of these problems). Therefore memory could be a useful discerning factor to provide a clear separation between 'efficient' and 'expensive' techniques. Finally, we also discuss how exploring the landscape of memory-limited optimization sheds light on new problem structures where it is possible to circumvent our lower bounds, and suggests new variants of gradient descent.
Bio:Vatsal Sharan is an assistant professor in the CS department at the University of Southern California. He did his undergraduate at IIT Kanpur, PhD at Stanford and a postdoc at MIT. He is interested in the foundations of machine learning, particularly in questions of computational & statistical efficiency, fairness and robustness.
2023 talks
- Towards More Responsible Data-Driven Systems
Abstract:Speaker: Dr. Suraj Shetiya
Date: 2023-12-11 Time: 10:00:00 (IST) Venue: MS Teams Improper management of data brings tremendous harm to society. Explain-ability and interpretability are an important part of responsible data management. In this talk, I present some of my recent research on fairness and responsible data management, with emphasis on how these impact systems. More specifically, the talk deep dives into integration of fairness into range queries in databases. In the later parts of the talk, we will look at interpretability of user preferences in multi-criteria decision systems and its practical applications. I will end the talk with outlining my future research and teaching plan.
Bio:Suraj Shetiya received his Bachelor of Engineering degree in Computer Science from Visvesvaraya Technological University, India, in 2010. After completing his Master's in Computer Science from University of Texas at Arlington in 2017, he started pursuing doctoral research under the supervision of Dr. Gautam Das. During this time, he has served as Teaching Assistant in the CS Department in various courses from 2018 to 2023. He is the recipient of the STEM fellowship from 2017 to 2023. For his outstanding work as a PhD student, he has received Outstanding Doctoral Student and Outstanding Doctoral Dissertation from the Computer Science department. During his Ph.D., he has been co-author of 6+ peer-reviewed papers published in top-tier database conferences - SIGMOD, VLDB, ICDE - Towards More Responsible Data-Driven Systems
Abstract:Speaker: Suraj Shetiya (Online Link)
https://teams.microsoft.com/l/meetup-join/19%3ameeting_NTliMGQ3YmUtMGQyZS00Y2NmLWE3NWEtYWQ4YThhYjYzOGIw%40thread.v2/0?context=%7b%22Tid%22%3a%22624d5c4b-45c5-4122-8cd0-44f0f84e945d%22%2c%22Oid%22%3a%22b071c84d-6396-4f94-a800-871037aba25d%22%7d
Date: 2023-12-11 Time: 10:00:00 (IST) Venue: online Improper management of data brings tremendous harm to society. Explain-ability and interpretability are an important part of responsible data management. In this talk, I present some of my recent research on fairness and responsible data management, with emphasis on how these impact systems. More specifically, the talk deep dives into integration of fairness into range queries in databases. In the later parts of the talk, we will look at interpretability of user preferences in multi-criteria decision systems and its practical applications. I will end the talk with outlining my future research and teaching plan.
Bio:Suraj Shetiya received his Bachelor of Engineering degree in Computer Science from Visvesvaraya Technological University, India, in 2010. After completing his Master's in Computer Science from University of Texas at Arlington in 2017, he started pursuing doctoral research under the supervision of Dr. Gautam Das. During this time, he has served as Teaching Assistant in the CS Department in various courses from 2018 to 2023. He is the recipient of the STEM fellowship from 2017 to 2023. For his outstanding work as a PhD student, he has received Outstanding Doctoral Student and Outstanding Doctoral Dissertation from the Computer Science department. During his Ph.D., he has been co-author of 6+ peer-reviewed papers published in top-tier database conferences - SIGMOD, VLDB, ICDE
- Robust Autonomous Vehicle Localization using GPS: from Tandem Drifting Cars to "GPS" on the Moon
Abstract:Speaker: Prof. Grace Gao
Date: 2023-12-05 Time: 12:00:00 (IST) Venue: SIT #001 Autonomous vehicles often operate in complex environments with various sensing uncertainties. On Earth, GPS signals can be blocked or reflected by buildings; and camera measurements are susceptible to lighting conditions. While having a variety of sensors is beneficial, including more sensing information can introduce more sensing failures as well as more computational load. For space applications, such as localization on the Moon, it can be even more challenging. In this talk, I will present our recent research efforts on robust vehicle localization under sensing uncertainties. We turn sensing noise and even absence of sensing into useful navigational signals. Inspired by cognitive attention in humans, we select a subset of "attention landmarks" from sensing measurements to reduce computation load and provide robust positioning. I will also show our localization techniques that enable various applications, from autonomous tandem drifting cars to a GPS-like system for the Moon.
Bio:Grace X. Gao is an assistant professor in the Department of Aeronautics and Astronautics at Stanford University. She leads the Navigation and Autonomous Vehicles Laboratory (NAV Lab). Prof. Gao has won a number of awards, including the National Science Foundation CAREER Award, the Institute of Navigation Early Achievement Award and the RTCA William E. Jackson Award. Prof. Gao and her students won Best Presentation of the Session/Best Paper Awards 29 times at Institute of Navigation conferences over the past 17 years. She also won various teaching and advising awards, including the Illinois College of Engineering Everitt Award for Teaching Excellence, the Engineering Council Award for Excellence in Advising, AIAA Illinois Chapter's Teacher of the Year, and most recently Advisor of the Year Award and Teacher of the Year Award by AIAA Stanford Chapter in 2022 and 2023, respectively.
- Robust Autonomous Vehicle Localization using GPS: from Tandem Drifting Cars to "GPS" on the Moon
Abstract:Speaker: Prof. Grace Gao
Date: 2023-12-05 Time: 12:00:00 (IST) Venue: SIT- 001 Autonomous vehicles often operate in complex environments with various sensing uncertainties. On Earth, GPS signals can be blocked or reflected by buildings; and camera measurements are susceptible to lighting conditions. While having a variety of sensors is beneficial, including more sensing information can introduce more sensing failures as well as more computational load. For space applications, such as localization on the Moon, it can be even more challenging. In this talk, I will present our recent research efforts on robust vehicle localization under sensing uncertainties. We turn sensing noise and even absence of sensing into useful navigational signals. Inspired by cognitive attention in humans, we select a subset of "attention landmarks" from sensing measurements to reduce computation load and provide robust positioning. I will also show our localization techniques that enable various applications, from autonomous tandem drifting cars to a GPS-like system for the Moon.
Bio:Grace X. Gao is an assistant professor in the Department of Aeronautics and Astronautics at Stanford University. She leads the Navigation and Autonomous Vehicles Laboratory (NAV Lab). Prof. Gao has won a number of awards, including the National Science Foundation CAREER Award, the Institute of Navigation Early Achievement Award and the RTCA William E. Jackson Award. Prof. Gao and her students won Best Presentation of the Session/Best Paper Awards 29 times at Institute of Navigation conferences over the past 17 years. She also won various teaching and advising awards, including the Illinois College of Engineering Everitt Award for Teaching Excellence, the Engineering Council Award for Excellence in Advising, AIAA Illinois Chapter's Teacher of the Year, and most recently Advisor of the Year Award and Teacher of the Year Award by AIAA Stanford Chapter in 2022 and 2023, respectively.
- Formal Methods for Software Reliability and Synthesis
Abstract:Speaker: Ashish Mishra
Date: 2023-11-23 Time: 11:30:00 (IST) Venue: MS Teams Building reliable software has been a classical goal in Computer Science. The most basic premise of my research is derived from this goal; Can we make programs safe and reliable using formal techniques while making programming as a discipline more democratic and accessible to the masses?
In this talk, I will begin by highlighting some of these overarching research interests and directions. I will primarily present two of my recent works highlighting the effective use of Refinement types, DSLs, and SMT-based techniques for the verification and synthesis of programs.
(i) The first is a new specification-guided synthesis procedure that uses Hoare-style pre- and post-conditions to express fine-grained effects of potential library component candidates to drive a bi-directional synthesis search strategy. It integrates a conflict-driven learning procedure into the synthesis algorithm that provides a semantic characterization of previously encountered unsuccessful search paths used to prune possible candidates' space as synthesis proceeds.
(ii) The second work is a new Refinement-Type system called Coverage Type which adapts the recent work in Incorrectness Logic to the specification and automated verification of test input generators used in modern property-based testing systems. Specifications are expressed in the language of refinement types, augmented with coverage types, types that reflect underapproximate constraints on program behavior.
Bio:Ashish Mishra is a Postdoctoral Researcher at Purdue University, where he works with Suresh Jagannathan in the areas of Programming Languages, Program Verification, and Program Synthesis. Ashish obtained his Ph.D. from the Indian Institute of Science, where he worked under the supervision of Y. N. Srikant. In addition to his work in Computer Science, Ashish is also interested in applying technology to public policies and solving social problems. He is currently involved with several Indian NGOs such as PARI (People's Archive for Rural India), Mosali (a startup trying to bring women into workforce), and others that are involved in Media Monitoring and Research.
- Stochastic Window Mean-payoff Games
Abstract:Speaker: Shibashis Guha, TIFR Bombay
Date: 2023-11-22 Time: 12:00:00 (IST) Venue: #501, Bharti Building Stochastic two-player games model systems with an environment that is both adversarial and stochastic. The environment is modeled by a player (Player 2) who tries to prevent the system (Player 1) from achieving its objective. We consider finitary versions of the traditional mean-payoff objective, replacing the long-run average of the payoffs by payoff average computed over a finite sliding window. Two variants have been considered: in one variant, the maximum window length is fixed and given, while in the other, it is not fixed but is required to be bounded. For both variants, we present complexity bounds and algorithmic solutions for computing strategies for Player 1 to ensure that the objective is satisfied with positive probability, with probability 1, or with probability at least p, regardless of the strategy of Player 2. The solution crucially relies on a reduction to the special case of non-stochastic two-player games. We give a general characterization of prefix-independent objectives for which this reduction holds. The memory requirement for both players in stochastic games is also the same as in non-stochastic games by our reduction. Moreover, for non-stochastic games, we improve upon the upper bound for the memory requirement of Player 1 and upon the lower bound for the memory requirement of Player 2.
This is a joint work with Laurent Doyen and Pranshu Gaba.
Bio:Shibashis Guha (https://www.tifr.res.in/~shibashis.guha/)
- Reasoning with interactive guidance
Abstract:Speaker: Dr.Niket Tandon
Date: 2023-11-21 Time: 11:00:00 (IST) Venue: SIT- 001 Humans view AI as a tool that listens and learns from their interactions, but this differs from the standard train-test paradigm. The goal of this talk is to introduce a step towards bridging this gap by enabling large language models to focus on human needs and continuously learn. Drawing inspiration from the theory of recursive reminding in Psychology, we propose a memory architecture to guide models to avoid repeating past errors. The talk discusses four essential research questions: who to ask, what to ask, when to ask and how to apply the obtained guidance. In tasks such as moral reasoning, planning, and other reasoning as well as benchmark tasks, our approach enables models to improve with reflection.
Bio:Niket Tandon is a Senior Research Scientist at the Allen Institute for AI in Seattle. His research interests are in commonsense reasoning and natural language guided reasoning. He works at the Aristo team responsible for creating AI which aced science exams. He obtained his Ph.D. from the Max Planck Institute for Informatics in Germany in 2016, where he was supervised by Professor Gerhard Weikum, resulting in the largest automatically extracted commonsense knowledge base at the time, called WebChild. He is also the founder of PQRS research, which introduces undergraduate students from underrepresented institutes to AI research. More information from him is available here: https://niket.tandon.info/
- Online List Labeling: Leveraging Predictions for Data Structures
Abstract:Speaker: Dr. Shikha Singh
Date: 2023-11-06 Time: 04:00:00 (IST) Venue: Bharti 501 A growing line of work shows how learned predictions can be used to break through worst-cast barriers to improve the running time of an algorithm. However, incorporating predictions into data structures with strong theoretical guarantees remains underdeveloped. This talk describes recent results on how predictions can be leveraged in the fundamental online list labeling problem. In the problem, n items arrive over time and must be stored in sorted order in an array of size Θ(n). The array slot of an element is its label and the goal is to maintain sorted order while minimizing the total number of elements moved (i.e., relabeled).
Bio:Shikha Singh is an Assistant Professor of Computer Science at Williams College. She obtained her PhD in Computer Science from Stony Brook University in 2018 and her Integrated MSc. in Mathematics and Computing from Indian Institute of Technology Kharagpur in 2013. Shikha's research is in the area of algorithms, with a focus on cache-efficient and scalable data structures, as well as algorithmic game theory.
- Training with Talk: A Machine Learning Makeover
Abstract:Speaker: Shashank Srivastava
Date: 2023-10-19 Time: 12:00:00 (IST) Venue: SIT- 001 Language and learning are deeply intertwined in humans. For example, in schools, we rely on processes such as reading books, listening to lectures, and engaging in student-teacher dialogs. In this talk, we will explore some recent work on building automated learning systems that can learn new tasks through natural language interactions with their users. We will cover multiple scenarios in this general direction: learning classifiers from language-based supervision, learning web-based tasks from explained demonstrations; and investigating when pretraining on language imparts effective inductive biases to large language models.
Bio:Shashank Srivastava is an assistant professor in the Computer Science department at the University of North Carolina (UNC) Chapel Hill. Shashank received his PhD from the Machine Learning department at CMU in 2018, and was an AI Resident at Microsoft Research in 2018-19. Shashank's research interests lie in conversational AI, interactive machine learning and grounded language understanding. Shashank has an undergraduate degree in Computer Science from IIT Kanpur, and a Master's degree in Language Technologies from CMU. He received the Yahoo InMind Fellowship for 2016-17. His research has been covered by popular media outlets including GeekWire and New Scientist.
- Socially aware Natural Language Processing
Abstract:Speaker: Snigdha Chaturvedi
Date: 2023-10-18 Time: 12:00:00 (IST) Venue: SIT- 001 NLP systems have made tremendous progress in recent years but lack a human-like language understanding. This is because there is a deep connection between language and people-- most text is created by people and for people. Despite this strong connection between language and people, existing NLP systems remain incognizant of the social aspects of language. In this talk, I describe three ways of designing Socially aware NLP systems. In the first part of the talk, I describe our socially aware approach to story generation by incorporating social relationships between various people to be mentioned in the story. We use a latent-variable-based approach that generates the story by conditioning on relationships to be exhibited in the story text using the latent variable. This latent variable-based design results in a better and explainable generation process. In the second part of the talk, I briefly describe our work on uncovering inherent social bias in automatically generated stories. We use a commonsense engine to reveal how such stories learn and amplify implicit social biases, especially gender biases. In the last part of the talk, I discuss methods to alleviate social biases. Specifically, I discuss debiasing text representations grounded in information theory. Using the rate-distortion function we show how we can remove information about sensitive attributes like race or gender from pre-trained text representations. This approach can successfully remove undesirable information while being robust to non-linear probing attacks.
Bio:Snigdha Chaturvedi is an Assistant Professor of Computer Science at the University of North Carolina, Chapel Hill. She specializes in Natural Language Processing, emphasizing narrative-like and socially aware understanding, summarization, and generation of language. Previously, she was an Assistant Professor at UC-Santa Cruz, and a postdoctoral fellow at UIUC and UPenn working with Dan Roth. She earned her Ph.D. in Computer Science from UMD in 2016, where she was advised by Hal Daume III. Her research has been supported by NSF, Amazon, and IBM.
- Securing Processors against Side-Channel Attacks: CPU Caches, Schedulers, and Beyond!
Abstract:Speaker: Prof. Gururaj Saileshwar
Date: 2023-10-13 Time: 11:00:00 (IST) Venue: SIT- 001 In recent years, micro-architectural side-channel attacks have emerged
as a unique and potent threat to security and privacy. Identifying these
side-channels is difficult as they often originate from undocumented
hardware structures, which are hidden from the software. Moreover, their
root-cause lies in crucial hardware performance optimizations, making
low overhead mitigation challenging. This talk will focus on both
discovery of new attacks and new low-cost defenses.
Bio:Gururaj Saileshwar is an Assistant Professor at the University of
Toronto, Dept of Computer Science. His research bridges computer
architecture and systems security, with interests including
micro-architectural side-channels, DRAM Rowhammer attacks, and trusted
execution environments. His past work has received an IEEE HPCA Best
Paper Award, an IEEE Micro Top Picks Honorable Mention, and his PhD
dissertation has been recognized with an IEEE HOST Best PhD Dissertation
Award and an IEEE TCCA / ACM SIGARCH Best Dissertation Award Honorable
Mention. His work appears in computer architecture conferences like
ASPLOS, MICRO, HPCA, and ISCA, and security conferences like USENIX
Security, IEEE S&P and CCS
- Computational modeling of neuronal dynamics
Abstract:Speaker: Parul Verma
Date: 2023-10-06 Time: 09:30:00 (IST) Venue: Online (MS Teams Link) Understanding neuronal dynamics, and how they are affected in neurological disorders, is one of the key problems in neuroscience today. This talk will describe advances in theoretical and biophysically grounded tools to understand neuronal mechanisms, with a focus on the functional activity of the entire brain. Specifically, it will demonstrate a graph-based mathematical model that captures the spectral and spatial features of the brain’s functional activity. This modeling approach revealed biophysical alterations in Alzheimer’s disease, different stages of sleep, and spontaneous fluctuations in electrophysiological functional activity. Together, these results aim to highlight the importance of such modeling techniques in identifying the underlying biophysical mechanisms of neuronal dynamics, which can be intractable to infer using neuroimaging data alone.
Bio:Parul Verma is a postdoc at the University of California San Francisco, Department of Radiology, since 2020. She obtained her Ph.D. at Purdue University. Before that, she obtained her B.Tech in Chemical Engineering from IIT Bombay. Parul’s doctoral work has been recognized by a faculty lectureship award from Purdue Chemical Engineering, and her postdoctoral work has been awarded a fellowship by the Alzheimer’s association.
- Computational modeling of neuronal dynamics
Abstract:Speaker: Parul Verma
Date: 2023-10-06 Time: 09:30:00 (IST) Venue: MS Teams Understanding neuronal dynamics, and how they are affected in neurological disorders, is one of the key problems in neuroscience today. This talk will describe advances in theoretical and biophysically grounded tools to understand neuronal mechanisms, with a focus on the functional activity of the entire brain. Specifically, it will demonstrate a graph-based mathematical model that captures the spectral and spatial features of the brain’s functional activity. This modeling approach revealed biophysical alterations in Alzheimer’s disease, different stages of sleep, and spontaneous fluctuations in electrophysiological functional activity. Together, these results aim to highlight the importance of such modeling techniques in identifying the underlying biophysical mechanisms of neuronal dynamics, which can be intractable to infer using neuroimaging data alone.
Bio:Parul Verma is a postdoc at the University of California San Francisco, Department of Radiology, since 2020. She obtained her Ph.D. at Purdue University. Before that, she obtained her B.Tech in Chemical Engineering from IIT Bombay. Parul’s doctoral work has been recognized by a faculty lectureship award from Purdue Chemical Engineering, and her postdoctoral work has been awarded a fellowship by the Alzheimer’s association.
- Deep Sensing: Jointly Optimizing Imaging and Processing
Abstract:Speaker: Dr. Sudhakar Kumawat,
Date: 2023-10-03 Time: 11:00:00 (IST) Venue: #001, SIT Building In this seminar, I will talk about the area of deep sensing where we jointly optimize the imaging (camera) parameters along with the deep learning models for novel computer vision applications. I will begin by discussing our recently published work "Action Recognition From a Single-Coded Image" where I will present our proposed framework for recognizing human actions directly from coded exposure images, without reconstructing the original scene. Next, I will talk about deep sensing in a broader context, discussing the motivation behind pursuing this research area, key ideas, and its application to existing and novel vision applications. Finally, I will briefly discuss how we are using deep sensing for a novel computer vision application called "Multimodal Material Segmentation in Road Scene Images".
Bio:Sudhakar Kumawat is a post-doctoral fellow at the Institute of Datability, Osaka University, Japan. He received his PhD from IIT Gandhinagar under the supervision of Dr. Shanmuganathan Raman. He was a TCS research fellow during PhD. Before that, he received his Integrated Dual Degree (B.Tech+M.Tech, 5 years) from the Computer Science and Engineering Department, IIT (BHU) Varanasi, in 2014. His broad area of research is computer vision, with a special interest in privacy-preserving computer vision, compressive sensing, and domain generalization. He has published papers in top computer vision journals and conferences such as TPAMI, ECCV, CVPR, and ICASSP. He received the best paper runner-up award at NCVPRIPG 2019.
- The Story of AWS Glue (VLDB 2023)
Abstract:Speaker: Mohit Saxena
https://www.amazon.science/publications/the-story-of-aws-glue
Date: 2023-09-27 Time: 12:00:00 (IST) Venue: SIT-001 AWS Glue is Amazon's serverless data integration cloud service that makes it simple and cost effective to extract, clean, enrich, load, and organize data. Originally launched in August 2017, AWS Glue began as an extract-transform-load (ETL) service designed to relieve developers and data engineers of the undifferentiated heavy lifting needed to load databases, data warehouses, and build data lakes on Amazon S3. Since then, it has evolved to serve a larger audience including ETL specialists and data scientists, and includes a broader suite of data integration capabilities. Today, hundreds of thousands of customers use AWS Glue every month.
Bio:Mohit Saxena is Senior Manager at Amazon Web Services. He leads the team that manages the serverless data integration service at Amazon globally. Earlier, he worked at IBM Research - Almaden and focused on database and storage systems. He completed his Ph.D in Computer Sciences from University of Wisconsin-Madison, M.S. from Purdue University and B.Tech in Computer Sciences from Indian Institute of Technology-Delhi.
- Bayesian spatiotemporal regression approaches for modelling and understanding the drivers of childhood vaccination outcomes
Abstract:Speaker: Sumeet Agarwal
Online (MS Teams): https://teams.microsoft.com/l/meetup-join/19%3a859e0622905d4a7980e595706e31fa0d%40thread.tacv2/1694307532808?context=%7b%22Tid%22%3a%22624d5c4b-45c5-4122-8cd0-44f0f84e945d%22%2c%22Oid%22%3a%22d147ea6a-9288-4db2-9f47-d243d61e426a%22%7d
Date: 2023-09-12 Time: 12:00:00 (IST) Venue: #001, SIT Building Incomplete immunisation coverage causes preventable illness and death in both developing and developed countries. Identification of factors that might modulate coverage could inform effective immunisation programmes and policies. We construct performance indicators to quantitatively approximate measures of the susceptibility of immunisation programmes to coverage losses, with an aim to identify correlations between trends in vaccine coverage and socioeconomic factors. We undertook a data-driven time-series analysis to examine trends in coverage of diphtheria, tetanus, and pertussis (DTP) vaccination across 190 countries over the past 30 years. We grouped countries into six world regions and used Gaussian process regression to forecast future coverage rates and provide a vaccine performance index: a summary measure of the strength of immunisation coverage in a country. Our vaccine performance index highlighted countries at risk of failing to achieve the global target of 90% coverage by 2015, and could aid policy makers' assessments of the strength and resilience of immunisation programmes. Subsequently, we have undertaken more localised analyses of vaccination coverage and confidence for India, including the development of novel latent-variable Bayesian hierarchical approaches for the inference of unobserved behavioural and social drivers of vaccination; we also discuss some outcomes from this ongoing work.
Bio:Sumeet Agarwal teaches in the areas of Electrical Engineering, Artificial Intelligence, and Cognitive Science at IIT Delhi. His research interests are focused around the use of machine learning and statistical modelling techniques to better understand the structure, function, and evolution of complex systems, in both the biological and the social sciences.
- Architectural Insights for Robustness and Fairness in Machine Learning
Abstract:Speaker: Professor Upamanyu Madhow
Date: 2023-09-05 Time: 12:00:00 (IST) Venue: Bharti 501 As data-driven machine-learnt algorithms become the technology of choice in an increasing array of applications, the research community recognizes the urgency of addressing shortcomings such as the lack of robustness (e.g., against adversarial examples and distribution shifts) and fairness (e.g., caused by bias in the training data). In this talk, we present two architectural insights, each based on a shift of perspective from the state of the art.
1) Software Architecture: We view the standard end-to-end paradigm for training DNNs, which does not provide explicit control over the features extracted by intermediate layers, as a fundamental bottleneck in the design of robust, interpretable DNNs. Motivated by ideas from communication theory (processing with matched filters) and neuroscience (neuronal competition), we propose adapting the training and inference framework for DNNs to provide more direct control over the shape of activations in intermediate layers. Preliminary results for the CiFAR-10 image database indicate significant gains in general-purpose robustness against noise and common corruptions, as well as against adversarial perturbations. We hope these results motivate further theoretical and experimental investigations: variants of the ideas we propose apply, in principle, to any DNN architecture or training model (supervised, unsupervised, self-supervised, semi-supervised).
2) Social Architecture: We view unfairness in DNNs resulting from data bias as a symptom of the unfairness and bias in the society from which the data is extracted. In an approach that is complementary to existing research on enhancing fairness during training and inference, we propose a framework for sequential decision-making aimed at dynamically influencing long-term societal fairness via positive feedback. We illustrate our ideas via a problem of selecting applicants from a pool consisting of two groups, one of which is under-represented, and hope that our results stimulate the collaboration between policymakers, social scientists and machine learning researchers required for real-world impact.
Bio:Upamanyu Madhow is Distinguished Professor of Electrical and Computer Engineering at the University of California, Santa Barbara. His current research interests focus on next generation communication, sensing and inference infrastructures, with emphasis on millimeter wave systems, and on fundamentals and applications of robust machine learning. Dr. Madhow is a recipient of the 1996 NSF CAREER award, co-recipient of the 2012 IEEE Marconi prize paper award in wireless communications, and recipient of a 2018 Distinguished Alumni award from the ECE Department at the University of Illinois, Urbana-Champaign. He is the author of two textbooks published by Cambridge University Press, Fundamentals of Digital Communication (2008) and Introduction to Communication Systems (2014). Prof. Madhow is co-inventor on 32 US patents, and has been closely involved in technology transfer of his research through several start-up companies, including ShadowMaps, a software-only approach to GPS location improvement which was deployed worldwide by Uber.
- Architectural Insights for Robustness and Fairness in Machine Learning
Abstract:Speaker: Professor Upamanyu Madhow , Department of Electrical & Computer Engineering, University of California, Santa Barbara
Date: 2023-09-05 Time: 12:00:00 (IST) Venue: #501, Bharti Building As data-driven machine-learnt algorithms become the technology of choice in an increasing array of applications, the research community recognizes the urgency of addressing shortcomings such as the lack of robustness (e.g., against adversarial examples and distribution shifts) and fairness (e.g., caused by bias in the training data). In this talk, we present two architectural insights, each based on a shift of perspective from the state of the art.
1) Software Architecture: We view the standard end-to-end paradigm for training DNNs, which does not provide explicit control over the features extracted by intermediate layers, as a fundamental bottleneck in the design of robust, interpretable DNNs. Motivated by ideas from communication theory (processing with matched filters) and neuroscience (neuronal competition), we propose adapting the training and inference framework for DNNs to provide more direct control over the shape of activations in intermediate layers. Preliminary results for the CiFAR-10 image database indicate significant gains in general-purpose robustness against noise and common corruptions, as well as against adversarial perturbations. We hope these results motivate further theoretical and experimental investigations: variants of the ideas we propose apply, in principle, to any DNN architecture or training model (supervised, unsupervised, self-supervised, semi-supervised).
2) Social Architecture: We view unfairness in DNNs resulting from data bias as a symptom of the unfairness and bias in the society from which the data is extracted. In an approach that is complementary to existing research on enhancing fairness during training and inference, we propose a framework for sequential decision-making aimed at dynamically influencing long-term societal fairness via positive feedback. We illustrate our ideas via a problem of selecting applicants from a pool consisting of two groups, one of which is under-represented, and hope that our results stimulate the collaboration between policymakers, social scientists and machine learning researchers required for real-world impact.
Bio:Upamanyu Madhow is Distinguished Professor of Electrical and Computer Engineering at the University of California, Santa Barbara. His current research interests focus on next generation communication, sensing and inference infrastructures, with emphasis on millimeter wave systems, and on fundamentals and applications of robust machine learning. Dr. Madhow is a recipient of the 1996 NSF CAREER award, co-recipient of the 2012 IEEE Marconi prize paper award in wireless communications, and recipient of a 2018 Distinguished Alumni award from the ECE Department at the University of Illinois, Urbana-Champaign. He is the author of two textbooks published by Cambridge University Press, Fundamentals of Digital Communication (2008) and Introduction to Communication Systems (2014). Prof. Madhow is co-inventor on 32 US patents, and has been closely involved in technology transfer of his research through several start-up companies, including ShadowMaps, a software-only approach to GPS location improvement which was deployed worldwide by Uber.
- Automated Decision Making for Safety Critical Applications
Abstract:Speaker: Prof. Mykel Kochenderfer (Stanford University)
Date: 2023-09-04 Time: 16:00:00 (IST) Venue: #501, Bharti Building Building robust decision making systems for autonomous systems is challenging. Decisions must be made based on imperfect information about the environment and with uncertainty about how the environment will evolve. In addition, these systems must carefully balance safety with other considerations, such as operational efficiency. Typically, the space of edge cases is vast, placing a large burden on human designers to anticipate problem scenarios and develop ways to resolve them. This talk discusses major challenges associated with ensuring computational tractability and establishing trust that our systems will behave correctly when deployed in the real world. We will outline some methodologies for addressing these challenges and point to some research applications that can serve as inspiration for building safer systems.
Bio:Mykel Kochenderfer is an Associate Professor of Aeronautics and Astronautics at Stanford University. He is the director of the Stanford Intelligent Systems Laboratory (SISL), conducting research on advanced algorithms and analytical methods for the design of robust decision making systems. Of particular interest are systems for air traffic control, unmanned aircraft, and automated driving where decisions must be made in uncertain, dynamic environments while maintaining safety and efficiency. Research at SISL focuses on efficient computational methods for deriving optimal decision strategies from high-dimensional, probabilistic problem representations. Prior to joining the faculty in 2013, he was at MIT Lincoln Laboratory where he worked on aircraft collision avoidance, leading to the creation of the ACAS X international standard for manned and unmanned aircraft. Prof. Kochenderfer is a co-director of the Center for AI Safety. He is an associate editor of the Journal of Artificial Intelligence Research and the Journal of Aerospace Information Systems. He is an author of the textbooks Decision Making under Uncertainty: Theory and Application (MIT Press, 2015), Algorithms for Optimization (MIT Press, 2019), and Algorithms for Decision Making (MIT Press, 2022).
- Deep Sensing: Jointly Optimizing Imaging and Processing
Abstract:Speaker: Dr. Sudhakar Kumawat
Date: 2023-09-03 Time: 11:00:00 (IST) Venue: SIT- 001 In this seminar, I will talk about the area of deep sensing where we jointly optimize the imaging (camera) parameters along with the deep learning models for novel computer vision applications. I will begin by discussing our recently published work "Action Recognition From a Single-Coded Image" where I will present our proposed framework for recognizing human actions directly from coded exposure images, without reconstructing the original scene. Next, I will talk about deep sensing in a broader context, discussing the motivation behind pursuing this research area, key ideas, and its application to existing and novel vision applications. Finally, I will briefly discuss how we are using deep sensing for a novel computer vision application called "Multimodal Material Segmentation in Road Scene Images".
Bio:Sudhakar Kumawat is a post-doctoral fellow at the Institute of Datability, Osaka University, Japan. He received his PhD from IIT Gandhinagar under the supervision of Dr. Shanmuganathan Raman. He was a TCS research fellow during PhD. Before that, he received his Integrated Dual Degree (B.Tech+M.Tech, 5 years) from the Computer Science and Engineering Department, IIT (BHU) Varanasi, in 2014. His broad area of research is computer vision, with a special interest in privacy-preserving computer vision, compressive sensing, and domain generalization. He has published papers in top computer vision journals and conferences such as TPAMI, ECCV, CVPR, and ICASSP. He received the best paper runner-up award at NCVPRIPG 2019.
- Gen-AI, its applications and end to end Development Life Cycle of AI solutions
Abstract:Speaker: Anupam Purwar
Date: 2023-09-01 Time: 16:00:00 (IST) Venue: Bharti 501 Generative AI in the natural language space is showing tremendous potential in automating various routine jobs. Recent studies have also demonstrated that Gen AI can aid with creative content creations. At the centre of this innovation in Gen AI are Large Language Models (LLMs), the leading ones are GPT 4, Claude2 and Llama 2 etc. Many of these LLMs are commercial, but there are open source ones too which can help organizations unlock tremendous value and help innovate. Through this talk, I would provide a practical way to develop an end to end application using LLMs in a scalable and affordable way. Speaker would cover software development life cycle for Generative AI solutions along with problem statement definition to help budding AI engineers, AI researchers and product managers alike.
Bio:Anupam Purwar is a Senior Research Scientist at Amazon Development Centre India, Hyderabad. He is a leading development of data science and machine learning-based solutions for Amazon Global Fulfillment. Anupam holds an MBA in Finance and Information Systems from the Indian School of Business and a Bachelor of Engineering from Birla Institute of Technology and Science, Pilani. He received merit scholarship and graduated among Top 5% in class both at ISB and BITS-Pilani. Prior to this, Anupam worked as a Research Scientist at Indian Institute of Science (IISc). At IISc, he was part of a multi-institutional effort which included IITs and ISRO to develop novel structures. Besides, he has authored 20+ peer reviewed articles pertaining to Machine Learning, IoT, computational design with 200+ citations and received multiple best paper awards. He is a certified Machine learning professional with 8+ certifications from Google and AWS.
- Fusing AI and Formal Methods for Automated Synthesis
Abstract:Speaker: Priyanka Golia
Date: 2023-08-28 Time: 12:00:00 (IST) Venue: MS Teams We entrust large parts of our daily lives to computer systems, which are becoming increasingly more complex. Developing scalable yet trustworthy techniques for designing and verifying such systems is an important problem. In this talk, our focus will be on automated synthesis, a technique that uses formal specifications to automatically generate systems (such as functions, programs, or circuits) that provably satisfy the requirements of the specification. I will introduce a state-of-the-art functional synthesis algorithm that leverages artificial intelligence to provide an initial guess for the system and then uses formal methods to repair and verify the guess to synthesize a system that is correct by construction. I will conclude by exploring the potential for combining AI and formal methods to address real-world scenarios.
Bio:Priyanka Golia has completed her Ph.D. in the joint degree program of NUS, Singapore and IIT Kanpur, India. Her research interests lie at the intersection of formal methods and artificial intelligence. In particular, her dissertation work has focused on designing scalable automated synthesis and testing techniques.
Her work has been awarded Best Paper Nomination at ICCAD-21 and Best Paper Candidate at DATE-23. She was named one of the EECS Rising Stars in 2022. She has co-presented a tutorial on Automated Synthesis: Towards the Holy Grail of AI at AAAI-22 and IJCAI-22, and she is co-authoring an upcoming book (on invitation from NOW publishers) on functional synthesis. - "Fast Multivariate Multipoint Evaluation over Finite Fields"
Abstract:Speaker: Dr. Sumanta Ghosh (Caltech) Online Talk
https://teams.microsoft.com/l/meetup-join/19%3ac00a05b5843f4486843ed7ca9c863eeb%40thread.tacv2/1692427565207?context=%7b%22Tid%22%3a%22624d5c4b-45c5-4122-8cd0-44f0f84e945d%22%2c%22Oid%22%3a%22870c4f19-6710-453d-a17d-f35f49b733e1%22%7d
Date: 2023-08-24 Time: 09:30:00 (IST) Multivariate multipoint evaluation is the problem of evaluating a multivariate polynomial, given as a coefficient vector, simultaneously at multiple evaluation points. The straightforward algorithm for this problem is to iteratively evaluate the input polynomial at each input point. The question of obtaining faster-than-naive (ideally, linear time) algorithms for this problem is a natural and fundamental question in computational algebra. Besides, fast algorithms for this problem are closely related to fast algorithms for other natural algebraic questions like polynomial factorization and modular composition.
Nearly linear time algorithms have been known for the univariate instance of multipoint evaluation for close to five decades due to the work of Borodin and Moenck. However, fast algorithms for the multivariate version have been much harder to come by. In a significant improvement to the state of art for this problem, Umans in 2008 and Kedlaya-Umans in 2011 gave nearly linear time algorithms for this problem over field of small characteristic and over all finite fields respectively, provided that the number of variables m is at most d^{o(1)} where the degree of the input polynomial in every variable is less than d. They also stated the question of designing fast algorithms for the large variable case as an open problem.
In this talk, we present two new algorithms for this problem. The first one is a nearly linear time (algebraic) algorithm for not-too-large fields of small characteristics. For the large variable case, this is the first nearly linear time algorithm for this problem over any large enough field. The second gives a nearly linear time (non-algebraic) algorithm over all finite fields.
The talk is based on joint work with Vishwas Bhargava, Zeyu Guo, Mrinal Kumar, Chandra Kanta Mohapatra, and Chris Umans.
Bio:Dr. Sumanta Ghosh (Caltech)
- Text image analysis from low resource dataset
Abstract:Speaker: Prof. Partha PratimRoy, IIT Roorkee
Date: 2023-08-23 Time: 12:00:00 (IST) Venue: #501, Bharti building Text image understanding has long been an active research area because of its complexity and challenges due to a variety of shapes. For bench-marking such a system, the dataset is a necessary and important resource to develop. The deep learning-based text image analytics tasks, such as detection and recognition have shown impressive results under the setting of full supervision of completely labeled datasets. However, the creation of such datasets with a large volume of samples is a challenging and time-consuming task. This research presentation will highlight a few solutions towards effective analysis of textual image analysis in scarcity of data annotation.
It is observed that the performance of the generic scene text detection method drops significantly due to the partial annotation of training data which introduces unnecessary noise. We propose a text region refinement method that provides robustness against the partially annotated training data in scene text detection. This approach works as a two-tier scheme. In the first tier text-probable regions apart from ground-truth text are obtained by applying hybrid loss. Next, these text-probable regions generate pseudo-labels to refine annotated text regions in the second tier during training. The proposed method exhibits a significant improvement over the baseline and existing approaches for the partially annotated training data.
Besides, recognition of textual images is a difficult task sometimes as sufficient labeling of data is not available for some unexplored scripts, especially Indic scripts. The design of deep neural network models makes it necessary to extend training datasets in order to introduce unseen variations. We propose an Adversarial Feature DeformationModule (AFDM) that learns ways to elastically warp extracted features in a scalable manner. The AFDM is inserted between intermediate layers and trained alternatively with the original framework, boosting its capability to better learn highly informative features rather than trivial ones. We record results for varying sizes of training data and observe that our enhanced network generalizes much better in the low-data regime.
Bio:Dr. Partha Pratim Roy (FIETE, SMIEEE) is presently working as an Associate Professor in the Department of Computer Science and Engineering, Indian Institute of Technology (IIT), Roorkee. He received his Masters in 2006 and Ph.D. in 2010 from Universitat Autonoma de Barcelona, Spain. He did postdoctoral stays in France and Canada from 2010 to 2013. Dr. Roy gathered industrial experience while working for about 4 years in TCS and Samsung. In Samsung, he was a part-leader of the Computer Vision research team. He is the recipient of the "Best Student Paper" awarded by the International Conference on Document Analysis and Recognition (ICDAR), 2009, Spain. He has published more than 200 research papers in various international journals, and conference proceedings. He has co-organized several international conferences and workshops, has been a member of the Program Committee of a number of international conferences, and acts as a reviewer for many journals in the field. His research interests include Pattern Recognition, Document Image Processing, Biometrics, and Human-Computer Interaction. He is presently serving as Associate Editor of ACM Transactions on Asian and Low-Resource Language Information Processing, Neurocomputing, IET Image Processing, IET Biometrics, IEICE Transactions on Information and Systems, and Springer Nature Computer Science.
- Principled Reinforcement Learning to Model our Dynamic Environments
Abstract:Speaker: Prof Chandrajit Bajaj
Date: 2023-08-11 Time: 12:00:00 (IST) Venue: #501, Bharti Building Can computers be programmed to learn to model progressive approximations of the underlying dynamical processes of specific environments, through interaction (i.e. spatio-temporal sensing) . We answer this in the affirmative with a proviso that not all the Hamiltonian models of environmental processes are learnable at optimal fidelity. Computers equipped with stable numerical solvers (some, possibly simultaneously learnable), are at the mercy of the noise and uncertainty of the sensed environmental observations. can nevertheless be programmed to stably train, cross-validate and test stochastic PDE (partial differential equation) neural operators. The learning is along optimally controlled pathways that satisfy a form of the Hamilton-Jacobi-Bellman equation. In this talk, I shall explain a framework of learning Hamiltonian models (Hamiltonians) as a partially observable controlled Markov decision process model (COMDP) and based on the Pontryagin's maximum principle. The COMDP model learning trajectory operates on a constrained manifold that satisfy the conservation laws of the underlying physics, via application of Noether's theorem. The COMDP includes learning dynamic stabilizing control satisfying learned Lyapunov functions for error bounded, convergent solutions, and additionally produces sparse approximations that avoid overfitting This talk shall show a few examples of such learned spatio-temporal models of dynamic environments, with various approximations of dynamic shape and function .
This is joint work with my students Taemin Heo, Minh Nguyen, Yi Wan
Bio:Chandrajit Bajaj, Department of Computer Science and Oden Institute, Center for Computational Visualization,University of Texas at Austin
http://www.cs.utexas.edu/~bajaj
bajaj@cs.utexas.edu, bajaj@oden.utexas.edu
- A Quantum Revolution in Computation
Abstract:Speaker: Umesh Vazirani (UC Berkeley)
Date: 2023-07-31 Time: 03:30:00 (IST) Venue: #501, Bharti Building We are well into the NISQ era of Noisy Intermediate Scale Quantum Computers. Four years on from Google's ‘quantum supremacy’ experiment, we have a deeper understanding of the nature of that experiment, the computing power of NISQ and novel techniques for benchmarking such computers and characterizing their error models. I will also describe how concepts from cryptography have provided novel and counter-intuitive ways of probing quantum systems and the prospects they hold for the next generation of quantum computers taking on the quantum supremacy challenge.
Bio:Prof Umesh V. Vazirani is the Roger A. Strauch Professor of Electrical Engineering and Computer Science at the University of California, Berkeley, and the director of the Berkeley Quantum Computation Center. His research interests lie primarily in quantum computing. Vazirani is one of the founders of the field of quantum computing. His 1993 paper with his student Ethan Bernstein on quantum complexity theory defined a model of quantum Turing machines which was amenable to complexity based analysis. This paper also gave an algorithm for the quantum Fourier transform, which was then used by Peter Shor within a year in his celebrated quantum algorithm for factoring integers. With Charles Bennett, Ethan Bernstein, and Gilles Brassard, he showed that quantum computers cannot solve black-box search problems faster than O({sqrt {N}}) in the number of elements to be searched. This result shows that the Grover search algorithm is optimal. It also shows that quantum computers cannot solve NP-complete problems in polynomial time using only the certifier. He is also a co-author of a textbook on algorithms. Vazirani was awarded the Fulkerson Prize for 2012 for his work on improving the approximation ratio for graph separators and related problems (jointly with Satish Rao and Sanjeev Arora). In 2018, he was elected to the National Academy of Sciences.
- Hardness of Testing Equivalence to Sparse Polynomials Under Shifts
Abstract:Speaker: Suryajith Chillara
Date: 2023-07-26 Time: 03:00:00 (IST) Venue: #001, SIT Building We say that two given polynomials $f, g in R[x_1, ldots, x_n]$, over a ring $R$, are equivalent under shifts if there exists a vector $(a_1, ldots, a_n)in R^N$ such that $f(x_1+a_1, ldots, x_n+a_n) = g(x_1, ldots, x_n)$. This is a special variant of the polynomial projection problem in Algebraic Complexity Theory. That is, instead of being given two polynomials $f$ and $g$ as input as described before, we are just given a polynomial $f$ and a parameter $t$ and we are interested in studying a more general problem of testing equivalence of $f$ to any of the polynomials in $R[x_1, ldots, x_n]$ which have at most $t$ many monomials with non-zero coefficients.
Grigoriev and Karpinski (FOCS 1990), Lakshman and Saunders (SIAM J. Computing, 1995), and Grigoriev and Lakshman (ISSAC 1995) studied the problem of testing polynomial equivalence of a given polynomial to any $t$-sparse polynomial, over the rational numbers, and gave exponential time algorithms. In the past two decades, these exponential time algorithms could not be improved and this is a major motivation behind our study of hardness of this problem.
We show that $SparseShift_R$ is at least as hard as checking if a given system of polynomial equations over $R[x_1,ldots, x_n]$ has a solution (Hilbert's Nullstellensatz). We also study the gap versions of this problem and show NP-hardness for certain regime of parameters.
Our results to some extent throws a light on why this problem in general has been evading the efforts to provide efficient algorithms.
Joint work with Coral Grichener (Google, Israel) and Amir Shpilka (Tel Aviv University).
Link: https://drops.dagstuhl.de/opus/volltexte/2023/17674/
Bio:Suryajith Chillara (https://suryajith.github.io/) IIIT Hyderabad
- Some results in the Intersection of Game Theory and Logic
Abstract:Speaker: Ramit Das
Date: 2023-06-27 Time: 16:00:00 (IST) Venue: Bharti Bldg. #404 + Team Links We shall address the issues of modelling or formalising game theoretic properties like Nash Equilibrium, Finite Improvement Property, Weak Acyclicity of various game forms in various kinds of logic. We shall investigate the expressive powers offered by each logic, the model checking theorems and also a completeness proof of a decidable logic variant. We hope that this investigation would have an impact on the formalisation of game theory and its allied areas like computational social choice theory.
Bio:Ramit Das is a researcher in Theoretical Computer Science about to get his PhD from the Institute of Mathematical Sciences, Chennai. He is interested in understanding the nature of computation in its various forms. For his PhD, he trained in Mathematical Logic and applied it to aspects of strategic games. His academic interests lie in trying to build bridges in Game Theory, Logic and areas of Complexity Theory like Descriptive Complexity Theory.
- Approximate Model Counting: Is SAT Oracle More Powerful than NP Oracle?
Abstract:Speaker: Gunjan Kumar
Date: 2023-06-15 Time: 11:00:00 (IST) Venue: Bharti Bldg. #404 + Team Links Given a Boolean formula $phi$ over $n$ variables, the problem of model counting is to compute the number of solutions of $phi$. Model counting is a fundamental problem in computer science with wide-ranging applications in domains such as quantified information leakage, probabilistic reasoning, network reliability, neural network verification, and more. Owing to the #P-hardness of the problems, Stockmeyer initiated the study of the complexity of approximate counting and showed that $log n$ calls to an NP oracle are necessary and sufficient to achieve tight guarantees.
It is well known that an NP oracle does not fully capture the behavior of SAT solvers, as SAT solvers are also designed to provide satisfying assignments when a formula is satisfiable, without additional overhead. Accordingly, the notion of SAT oracle has been proposed to capture the behavior of SAT solver wherein given a Boolean formula, an SAT oracle returns a satisfying assignment if the formula is satisfiable or returns unsatisfiable otherwise.
The primary contribution of this work is to study the relative power of the NP oracle and SAT oracle in the context of approximate model counting. We develop a new methodology to achieve the main result: a SAT oracle is no more powerful than an NP oracle in the context of approximate model counting.
(To appear in ICALP 2023. Joint work with Diptarka Chakraborty, Sourav Chakraborty, and Kuldeep S Meel).
Bio:Gunjan Kumar did his B.Tech in Computer Science and Engineering from the Indian Institute of Technology, Guwahati. Thereafter, he pursued his MS and Ph.D. from Tata Institute of Fundamental Research, Mumbai, and currently, he is a postdoctoral researcher at the National University of Singapore. His broad area of interest is Algorithms and Complexity with a focus on sublinear algorithms.
- Measuring and Improving the Internal Conceptual Representations of Deep Learning
Abstract:Speaker: Ramakrishna Vedantam
Online (MS Teams): https://teams.microsoft.com/l/meetup-join/19%3ac00a05b5843f4486843ed7ca9c863eeb%40thread.tacv2/1685675828429?context=%7b%22Tid%22%3a%22624d5c4b-45c5-4122-8cd0-44f0f84e945d%22%2c%22Oid%22%3a%22d147ea6a-9288-4db2-9f47-d243d61e426a%22%7d
Date: 2023-06-08 Time: 12:00:00 (IST) Venue: #501, Bharti Building Endowing machines with abstract, flexible conceptual representations and the ability to combine known concepts to make novel, "conceptual-leaps" is a long-standing goal of artificial intelligence (AI). In pursuit of this goal, I will discuss my works on the foundations of concept learning for deep learning models. In particular I will focus on: multimodal learning (to ground concept representations more precisely into the world), quantifying robustness (to assess if atomic concepts are learnt correctly) and machine reasoning (to combine known atomic concepts into novel, emergent ones). Finally, I will speculate on important research directions to pursue for realizing the promise of general, robust and human interpretable AI systems.
Bio:Ramakrishna Vedantam received the Ph.D. Degree in Computer Science from the Georgia Institute of Technology in 2018, before joining Facebook AI Research (FAIR) in New York. Currently, he is a visiting researcher at the New York University (NYU) center for data science (CDS). Rama's current research interests are around the foundations of robustness, multimodal learning and reasoning with large-scale deep learning models. At Georgia Tech, Rama's Ph.D. research was supported by the highly competitive Google Ph.D. fellowship. During his Ph.D. Rama also spent time at Google Research in Mountain View, Facebook AI Research in Menlo Park, Microsoft Research in Cambridge, UK and Ecole Centrale in Paris working on various topics at the intersection of probabilistic deep learning, multimodal learning, and reasoning. Rama developed the CIDEr metric popularly used in the AI community for evaluating vision and language models, and has published his research at various top-tier AI/ML venues such as ICML, NeurIPS, ICLR, CVPR, ICCV and EMNLP.
- Semi-nonparametric Demand Estimation in the Presence of Unobserved Factors
Abstract:Speaker: Ashwin Venkataraman
Date: 2023-05-29 Time: 15:10:00 (IST) Venue: SIT-001 Discrete choice models are commonly used to model customer demand because of their ability to capture substitution patterns in customer choices.
Demand predictions from these models are then used as inputs in key operational decisions for firms such as what collection of products to show to customers or what prices to charge for different products in order to maximize revenues. In many applications of discrete choice modeling, there exist unobserved factors (UFs) driving the consumer demand that are not included in the model. Ignoring such UFs when fitting the choice model can produce biased parameter estimates, leading to poor demand predictions and suboptimal decisions. At the same time, accounting for UFs during estimation is challenging since we typically have only partial or indirect information about them. Existing approaches such as the classical BLP estimator (Berry et al. 1995) make strong parametric assumptions to deal with this challenge, and therefore can suffer from model misspecification issues when the assumptions are not met in practice.In this talk, I'll present a novel semi-nonparametric estimator for dealing with UFs in the widely used mixture of logit choice model that does not impose any parametric assumptions on the mixing distribution or the underlying mechanism generating the UFs. We theoretically characterize the benefit of using our estimator over the BLP estimator, and leverage the alternating minimization framework to design an efficient algorithm that implements our proposed estimator. Using a simulation study, we demonstrate that our estimator is robust to different ground-truth settings, whereas the performance of the BLP estimator suffers significantly under model misspecification. Finally, using real-world grocery sales data, we show that accounting for product and store-level UFs can significantly improve the accuracy of predicting weekly demand at an individual product and store level, with an avg. 57% improvement across 12 product categories over a state-of-the-art benchmark that ignores UFs during estimation.
Joint work with Prof. Srikanth Jagabathula and Sandeep Chitla, both from NYU Stern School of Business.
Bio:Ashwin Venkataraman is an assistant professor of operations management at the Naveen Jindal School of Management at the University of Texas at Dallas (UTD). His research interests lie at the intersection of machine learning, operations management, and marketing, with a focus on developing novel models and methodologies that can leverage the vast amounts of customer data that firms have access to nowadays. Prior to joining UTD, Ashwin received an MS and PhD in computer science from the Courant Institute of Mathematical Sciences at New York University, and his doctoral thesis won an honorable mention (joint-second place) in the 2019 INFORMS Dantzig Dissertation Award. Before joining graduate school, Ashwin completed a B.Tech in Computer Science and Engineering from IIT Delhi.
- The Road Not Taken: Exploring Alias Analysis Based Optimizations Missed by the Compiler
Abstract:Speaker: Dr. Piyush Kedia
Date: 2023-04-21 Time: 03:00:00 (IST) Venue: #113, SIT Building The alias analysis aims to answer whether two pointers can overlap during runtime. However, static alias analysis is imprecise. Because the alias analysis is used by many compiler optimizations, including loop transformations, the program's performance may suffer, especially in the presence of loops, due to the imprecision of alias analysis.
In this talk, I'll present our tool, Scout, which can disambiguate two-pointers at runtime using single memory access. The key idea is to constrain the allocation size and alignment during memory allocations to enable fast disambiguation checks. Our technique enabled new opportunities for loop-invariant code motion, dead store elimination, loop vectorization, and load elimination in an already optimized code. Our performance improvements are up to 51.11% for Polybench benchmarks and up to 0.89% for SPEC benchmarks.
Bio:Piyus Kedia is an assistant professor at IIIT Delhi. He received his Ph.D. from IIT Delhi. He works in the area of programming languages and systems security.
- On The Membership Problem for Hypergeometric Sequences with Rational Parameters
Abstract:Speaker: Klara Nosan.
Date: 2023-04-19 Time: 03:00:00 (IST) Venue: #001, SIT Building We investigate the Membership Problem for hypergeometric sequences: given a hypergeometric sequence ⟨u_n⟩ of rational numbers and a rational value t, decide whether t occurs in the sequence. We show decidability of this problem under the assumption that in the defining recurrence f(n) u_{n+1} = g(n) u_n, the roots of the polynomials f and g are all rational numbers. We further show the problem remains decidable if the splitting fields of the polynomials f and g are distinct or if f and g are monic polynomials that both split over a quadratic number field.
Our proof relies on bounds on the density of primes in arithmetic progressions. We also observe a relationship between the decidability of the Membership problem (and variants) and the Rohrlich-Lang conjecture in transcendence theory.
This talk is based on works done in collaboration with George Kenison, Amaury Pouly, Mahsa Shirmohammadi and James Worrell.
Bio:https://www.irif.fr/~nosan/
- Backdoor Attacks in Computer Vision: Challenges in Building Trustworthy Machine Learning Systems
Abstract:Speaker: Dr. Aniruddha Saha
Date: 2023-04-19 Time: 12:00:00 (IST) Venue: #001, SIT Building Deep Neural Networks (DNNs) have become the standard building block in numerous machine learning applications. The widespread success of these networks has driven their deployment in sensitive domains like health care, finance, autonomous driving, and defense-related applications.
However, DNNs are vulnerable to adversarial attacks. Research has shown that an adversary can tamper with the training process of a model by injecting misrepresentative data (poisons) into the training set. The manipulation is done in a way that the victim's model will malfunction only when a trigger modifies a test input. These are called backdoor attacks. For instance, a backdoored model in a self-driving car might work accurately for days before it suddenly fails to detect a pedestrian when the adversary decides to exploit the backdoor.
In this talk, I will show ways in which state-of-the-art deep learning methods for computer vision are vulnerable to backdoor attacks and a few defense methods to remedy the vulnerabilities. Optimizing only for accuracy is not enough when we are developing machine learning systems for high stakes domains. Making machine learning systems trustworthy is our biggest challenge in the next few years.
Bio:Aniruddha Saha is currently a Postdoctoral Associate with the Center for Machine Learning (CML) in the University of Maryland Institute for Advanced Computer Studies (UMIACS). He received his PhD in Computer Science from the University of Maryland, Baltimore County. His research interests include Computer Vision, Adversarial Robustness, Data Poisoning, Backdoor Attacks and Trustworthy Machine Learnin
- Towards effective human-robot collaboration in shared autonomy systems
Abstract:Speaker: Raunak Bhattacharyya
Date: 2023-03-31 Time: 12:00:00 (IST) Venue: #501, Bharti Building Automated agents have the potential to augment human capabilities in safety-critical applications such as driving, service and inspection, and smart manufacturing. As the field of robotics and AI is quickly emerging, one critical and challenging problem is ensuring that autonomous agents can collaborate and interact with humans. In this talk, I will present our work on how automated agents can model human decision making, plan around human operators, and explain their decisions. First, I will present an approach based on imitation learning to model real-world human behavior and demonstrate its application to model human driving trajectories. Second, I will present a hybrid data-driven and rule-based approach to generate novel scenarios which can be used for planning. Third, I will present ongoing work on explainable automated agents. Finally, I will discuss my future research plan centered around shared autonomous systems which includes optimally allocating authority between automated and human controllers, learning from imperfect demonstrations, metacognition for human-robot collaboration, and safe autonomous planning in the presence of humans.
Bio:Dr. Raunak Bhattacharyya is a Postdoctoral Research Associate with the Oxford Robotics Institute, University of Oxford. His research focuses on human-autonomy interaction in shared autonomy systems. Raunak completed his Ph.D. at Stanford University, where he was a doctoral researcher in the Stanford Intelligent Systems Lab. He earned two Master's Degrees, in Computer Science and in Aerospace Engineering from Georgia Tech, and an undergraduate degree in Aerospace Engineering from IIT Bombay. Raunak received the Postdoctoral Enrichment Award from the Alan Turing Institute, UK, and the Graduate Research Award from the Transportation Research Board, USA.
Online Link (MS Teams): https://teams.microsoft.com/l/meetup-join/19%3a859e0622905d4a7980e595706e31fa0d%40thread.tacv2/1679902599494?context=%7b%22Tid%22%3a%22624d5c4b-45c5-4122-8cd0-44f0f84e945d%22%2c%22Oid%22%3a%22d147ea6a-9288-4db2-9f47-d243d61e426a%22%7d
- Security for the Internet of Things: Challenges and Prospects
Abstract:Speaker: Dr. Shantanu Pal, Assistant Professor, School of Information Technology, Deakin University, Melbourne, Australia
Date: 2023-03-29 Time: 12:00:00 (IST) Venue: Online (MS Teams Link) This talk aims to report security mechanisms for large-scale Internet of Things (IoT) systems, in particular, the need for access control, identity management, delegation of access rights and the provision of trust within such systems. The talk will discuss the design and development of an access control architecture for the IoT. How the policy-based approach provides a fine-grained access for authorized users to services while protecting valuable resources from unauthorized access will be discussed in detail. The talk will also explore an identity-less, asynchronous and decentralized delegation model for the IoT leveraging the advantage of blockchain technology. This further calls for better designing the IoT infrastructures, optimizing human engagement, managing IoT identity, and advocating lightweight access control solutions in the broad context of IoT to create a fertile ground for research and innovation. This talk will also discuss various challenges, including the propagation of uncertainty in IoT networks and prospects of IoT access control mechanisms using emerging technologies, e.g., blockchain.
Bio:Dr. Shantanu Pal is an Assistant Professor in the School of Information Technology, Deakin University, Melbourne, Australia. Shantanu holds a PhD in Computer Science from Macquarie University, Sydney, Australia. He was a Research Fellow at the Queensland University of Technology (QUT), Brisbane, Australia. He was also an associate researcher working with CSIRO's Data61, Australia. Shantanu's research interests are the Internet of Things (IoT), access control, blockchain technology, big data and distributed applications for cyber-physical systems, mobile and cloud computing, uncertainty propagation in IoT networks, emerging technologies, e.g., machine learning and artificial intelligence, etc. Shantanu is listed in the world's top 2% of scientists according to the recently released list by Stanford University, USA, in 2022 in Computer Networking and Communications.
- Repeatedly Matching Items to Agents Fairly and Efficiently
Abstract:Speaker: Shivika Narang (PhD student at IISc)
Date: 2023-01-27 Time: 16:00:00 (IST) Venue: bharti-501 We consider a novel setting where a set of items are matched to the same set of agents repeatedly over multiple rounds. Each agent gets exactly one item per round, which brings interesting challenges to finding efficient and/or fair repeated matchings. A particular feature of our model is that the value of an agent for an item in some round depends on the number of rounds in which the item has been used by the agent in the past. We present a set of positive and negative results about the efficiency and fairness of repeated matchings. For example, when items are goods, a variation of the well-studied fairness notion of envy-freeness up to one good (EF1) can be satisfied under certain conditions. Furthermore, it is intractable to achieve fairness and (approximate) efficiency simultaneously, even though they are achievable separately. For mixed items, which can be goods for some agents and chores for others, we propose and study a new notion of fairness that we call swap envy-freeness (swapEF).
Joint work with Prof Ioannis Caragiannis.
https://arxiv.org/abs/2207.01589
Bio:Shivika Narang is a PhD student, and recipient of the Tata Consultancy Services (TCS) Research Scholarship at the Indian Institute of Science, Bengaluru, where she is a member of the Game Theory Lab. She is being advised by Prof Y Narahari. She is broadly interested in Algorithmic Game Theory and Approximation Algorithms. Her current work is focused on fairness in matchings and allocations.
- Fusing AI and Formal Methods for Automated Synthesis.
Abstract:Speaker: Priyanka Golia (IITK & NUS)
Date: 2023-01-17 Time: 15:00:00 (IST) Venue: bharti-501 We entrust large parts of our daily lives to computer systems, which are becoming increasingly more complex. Developing scalable yet trustworthy techniques for designing and verifying such systems is an important problem. In this talk, our focus will be on automated synthesis, a technique that uses formal specifications to automatically generate systems (such as functions, programs, or circuits) that provably satisfy the requirements of the specification. I will introduce a state-of-the-art synthesis algorithm that leverages artificial intelligence to provide an initial guess for the system, and then uses formal methods to repair and verify the guess to synthesize probably correct system. I will conclude by exploring the potential for combining AI and formal methods to address real-world scenarios.
Bio:Priyanka Golia is a final year Ph.D. candidate at NUS, Singapore and IIT Kanpur. Her research interests lie at the intersection of formal methods and artificial intelligence. In particular, her dissertation work has focused on designing scalable automated synthesis and testing techniques. Her work has been awarded Best Paper Nomination at ICCAD-21 and Best Paper Candidate at DATE-23. She was named one of the EECS Rising Stars in 2022. She has co-presented a tutorial on Automated Synthesis: Towards the Holy Grail of AI at AAAI-22 and IJCAI-22, and She is co-authoring an upcoming book (on invitation from NOW publishers) on functional synthesis.
- Selection in the Presence of Biases
Abstract:Speaker: Prof. Nisheeth Vishnoi (Yale University)
Date: 2023-01-09 Time: 15:00:00 (IST) Venue: SIT-001 In selection processes such as hiring, promotion, and college
admissions, biases toward socially-salient attributes of candidates
are known to produce persistent inequality and reduce aggregate
utility for the decision-maker. Interventions such as the Rooney Rule
and its generalizations, which require the decision maker to select at
least a specified number of individuals from each affected group, have
been proposed to mitigate the adverse effects of such biases in
selection.
In this talk, I will discuss recent works which have established that
such lower-bound constraints can be effective in improving aggregate
utility.
Papers:
https://arxiv.org/abs/2001.08767
https://arxiv.org/abs/2010.10992
https://arxiv.org/abs/2202.01661
Bio:Nisheeth Vishnoi is a professor of computer science and a co-founder of the Computation and Society Initiative at Yale University. His research focuses on foundational problems in computer science, machine learning, and optimization. He is also broadly interested in understanding and addressing some of the key questions that arise in nature and society from a computational viewpoint. Here, his current focus is on physics-inspired algorithms and algorithmic fairness. He is the author of two monographs and the book Algorithms for Convex Optimization.
He was the recipient of the Best Paper Award at IEEE FOCS in 2005, the IBM Research Pat Goldberg Memorial Award in 2006, the Indian National Science Academy Young Scientist Award in 2011, the IIT Bombay Young Alumni Achievers Award in 2016, and the Best Technical Paper award at ACM FAT* in 2019. He was elected an ACM Fellow in 2019. - Towards Next-Generation ML/AI: Robustness, Optimization, Privacy.
Abstract:Speaker: Krishna Pillutla, visiting researcher (postdoc) at Google Research, USA
Date: 2023-01-06 Time: 12:00:00 (IST) Venue: bharti-501 Two trends have taken hold in machine learning and artificial intelligence: a move to massive, general-purpose, pre-trained models and a move to small, on-device models trained on distributed data. Both these disparate settings face some common challenges: a need for (a) robustness to deployment conditions that differ from training, (b) faster optimization, and (c) protection of data privacy.
As a result of the former trend, large language models have displayed emergent capabilities they have not been trained for. Recent models such as GPT-3 have attained the ability to generate remarkably human-like long-form text. I will describe Mauve, a measure to quantify the goodness of this emergent capability. It measures the gap between the distribution of generated text and that of human-written text. Experimentally, Mauve correlates the strongest with human evaluations of the generated text and can quantify a number of its qualitative properties.
The move to massively distributed on-device federated learning of models opens up new challenges due to the natural diversity of the underlying user data and the need to protect its privacy. I will discuss how to reframe the learning problem to make the model robust to natural distribution shifts arising from deployment on diverse users who do not conform to the population trends. I will describe a distributed optimization algorithm and show how to implement it with end-to-end differential privacy.
To conclude, I will discuss my ongoing efforts and future plans to work toward the next generation of ML/AI by combining the best of both worlds with applications to differentially private language models and text generation to decentralized learning.
Bio:Krishna Pillutla is a visiting researcher (postdoc) at Google Research, USA in the Federated Learning team. He obtained his Ph.D. at the University of Washington where he was advised by Zaid Harchaoui and Sham Kakade. Before that, he received his M.S. from Carnegie Mellon University and B.Tech. from IIT Bombay where he was advised by Nina Balcan and J. Saketha Nath respectively. Krishna's research has been recognized by a NeurIPS outstanding paper award (2021) and a JP Morgan Ph.D. fellowship (2019-20).