Vijay V. Vazirani , University of California, Irvine. 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… Read More »A Theory of Alternating Paths and Blossoms, from the Perspective of Minimum Length

Rajeev Barua, University of Maryland. 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… Read More »Cybersecurity: Why its hard, solutions, and careers

Allan Borodin, University of Toronto What can and cannot be computed by “conceptually simple algorithms"? In this regard, my primary interest is in 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… Read More »Online, greedy, and conceptually simple algorithms

Sourav Chakraborty  (Indian Statistical Institute) We will present a very simple streaming algorithm on F0 estimation that also caught the eye of Donald E. Knuth.  In a recent article, Donald E. Knuth started with the following two paragraphs:   "Sourav Chakraborty, N. V. Vinodchandran, and Kuldeep S. Meel have recently proposed an interesting algorithm for the following… Read More »Distinct Elements in Streams and the Klee’s Measure Problem

Speaker: Raghuvansh Saxena (Tata Institute of Fundamental Research) We show how to convert any circuit of poly-logarithmic depth and polynomial size into a functionally equivalent circuit of polynomial size (and polynomial depth) that is resilient to adversarial short-circuit errors. Specifically, the resulting circuit computes the same function even if up to $epsilon d$ gates on… Read More »Polynomial Size, Short-Circuit Resilient Circuits for NC

Sameer Chauhan, Director-General of the United Nations International Computing Centre (UNICC) is visiting India from 15 February- 21 February and will  deliver a talk and interact with faculty and students at IIT Delhi on the 19th of February at 3PM Venue SIT-001 . Tech for Good in the Age of Quantum and AI The convergence… Read More »Tech for Good in the Age of Quantum and AI : Sameer Chauhan

Speaker: Navajit Singh Baban (Division of Engineering, Center for Cybersecurity, NYU Abu Dhabi)   Abstract: Microfluidic biochips (MBs), a transformative class of lab-on-a-chip devices, are reshaping clinical diagnostics, point-of-care testing, and biomedical research. However, their rapid commercialization and complex global supply chain have made them increasingly vulnerable to three major security threats: structural attacks, material… Read More »Cyber-Physical Security of Microfluidic Biochips: Safeguarding Healthcare in the Era of Global Pandemics and Point-of-Care Testing

Speaker: Kuldeep S. Meel (Georgia Institute of Technology) Abstract:  The dominant guiding philosophy in the first sixty years of Computer Science was for designers to design systems that were always correct, and to accept nothing less as users. But times have changed: Users and designers are accustomed to systems with statistical components and behaviors. What does it… Read More »Distribution Testing: The New Frontier for Formal Methods

Speaker: Kuldeep S. Meel (Georgia Institute of Technology)   Abstract:  The dominant guiding philosophy in the first sixty years of Computer Science was for designers to design systems that were always correct, and to accept nothing less as users. But times have changed: Users and designers are accustomed to systems with statistical components and behaviors. What… Read More »Distribution Testing: The New Frontier for Formal Methods

Prof. Venkata Koppula will be giving a talk on Wednesday, March 19th, in Bharti 501. Please note that this is not our usual Monday slot. The talk will begin at 12:00 PM, with refreshments served at 11:50 AM, prior to the talk. Below are the details: Abstract: Consider a resource-bounded client that wants to outsource some… Read More »Delegation and Verification of Quantum Computation