Logic Society of Delhi

January 29 2025, Ashoka University:

Seminar: Testing correctness of samplers using property testing: from theory to practice and back again.
Speaker: Sourav Chakraborty, Professor, Indian Statistical Institute, Kolkata.
(abstract, How can one test the correctness of a program that is supposed to output an element from a large universe according to a certain distribution? These kinds of programs are heavily used in real life but are rarely tested for correctness. This problem can be framed as a problem in property testing. Property testing is a subject that deals with these challenges. It tries to design sub-linear algorithms for testing various properties of inputs. The key lies in the way the data is accessed by the algorithm.

One of the central problems in property testing and many other related subjects is testing if a distribution has a certain property - say whether a distribution on a finite set is uniform. The conventional way of accessing the distributions is by drawing samples according to the distributions. Unfortunately, in this setting the number of samples that are necessary for testing properties of distribution (for most natural properties) is polynomial in the size of support of the distribution. Thus when the support is relatively big the algorithms become impractical in real life applications.

We introduced a new way of accessing the distribution using ``conditional-sampling oracle". This oracle can be used to design much faster algorithms for testing properties of distribution and thus makes the algorithm useful in practical scenarios. We show that the conditional oracle can be implemented in many real life problems and we have been able to show the usefulness of this model and our algorithms in practical purposes and in other areas of research - like testing of probabilistic verification. This model also throws a number of interesting theoretical questions. about the speaker Sourav Chakraborty is a Professor in the Advanced Computing and Microelectronics Unit (ACMU) of the Computer and Communication Sciences Division (CCSD) at the Indian Statistical Institute (ISI) , Kolkata, India. Before joining ISI on July 2018 he was a faculty member at Chennai Mathematical Institute , India, from September 2010. Before that he was a postdoc at the Algorithms and Complexity department of Centrum Wiskunde & Informatica (CWI), Amsterdam, Netherlands from September 2009 to August 2010. From October 2008 to August 2009 he was a postdoc at the Computer Science Department of Technion, Israel. In June 2008 he finished his PhD in Computer Science from University of Chicago under the supervision of Prof. László Babai.

His field of research is Theoretical Computer Science. His focus has been in the classical and quantum complexity of Boolean functions (including property testing, sensitivity and block sensitivity of Boolean functions and quantum database search), in electronic commerce, in graph algorithms and in coding theory. )

January 27 2025, IIT Delhi:

Seminar: Distinct Elements in Streams and the Klee's Measure Problem.
Speaker: Sourav Chakraborty, Professor, Indian Statistical Institute, Kolkata.
(abstract, 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 problem: A stream of elements (a1, a2,...,am) is input, one at a time, and we want to know how many of them are distinct. In other words, if A = {a1, a2,...,am} is the set of elements in the stream, with multiplicities ignored, we want to know |A|, the size of that set. But we don't have much memory; in fact, |A| is probably a lot larger than the number of elements that we can hold in memory at any one time. What is a good strategy for computing an unbiased estimate of |A|?

Their algorithm is not only interesting, it is extremely simple. Furthermore, it's wonderfully suited to teaching students who are learning the basics of computer science. (Indeed, ever since I saw it, a few days ago, I've been unable to resist trying to explain the ideas to just about everybody I meet.) Therefore I'm pretty sure that something like this will eventually become a standard textbook topic. This note is an initial approximation to what I might write about it, if I were preparing a textbook about data streams."

This simple algorithm comes out of the first ever "efficient" streaming algorithm (from PODS 21) for the Klee's Measure problem, which was a big open problem in the world of streaming for many years. about the speaker Sourav Chakraborty is a Professor in the Advanced Computing and Microelectronics Unit (ACMU) of the Computer and Communication Sciences Division (CCSD) at the Indian Statistical Institute (ISI) , Kolkata, India. Before joining ISI on July 2018 he was a faculty member at Chennai Mathematical Institute , India, from September 2010. Before that he was a postdoc at the Algorithms and Complexity department of Centrum Wiskunde & Informatica (CWI), Amsterdam, Netherlands from September 2009 to August 2010. From October 2008 to August 2009 he was a postdoc at the Computer Science Department of Technion, Israel. In June 2008 he finished his PhD in Computer Science from University of Chicago under the supervision of Prof. László Babai.

His field of research is Theoretical Computer Science. His focus has been in the classical and quantum complexity of Boolean functions (including property testing, sensitivity and block sensitivity of Boolean functions and quantum database search), in electronic commerce, in graph algorithms and in coding theory. )

January 15-22 2025, Virtual and in New Delhi:

World Logic Day Celebrations.
Join us for a series of virtual talks, followed by an in-person reception. More details, abstracts, conferencing links, and reception details are here.

November 27 2024, Ashoka University:

Seminar: Proving Security Protocols Correct.
Speaker: Vaishnavi Sundararajan, Chandruka New Faculty Fellow and Assistant Professor at IIT Delhi.
(abstract, Security protocols underpin most aspects of our digital lives nowadays, with finance, health, and even citizenship requiring some online interaction. Mere testing does not suffice for such critical systems, since even one missed test-case could prove to be incredibly costly. So we turn to formal verification, which converts the system into some “abstract” model, casts properties as statements over this model, and then checks if the model satisfies those statements. Formal verification has been done for many security protocols (including TLS, and the Signal messaging protocol) and even found many bugs. The standard verification framework was proposed by Danny Dolev and Andy Yao in a 1983 paper, where the network is assumed to be adversarial, and all communicated messages are modelled as terms in an algebra. We will see a few examples of how this model can be used to find logical flaws in protocols. We recently extended this model to deal with protocols for the internet age which involve certification, by distinguishing between “normal” messages (like encrypted or hashed terms) and “assertions” (statements of the form “this message is an encryption of a 0 or a 1”) using two different algebras. This allows us to better represent such security protocols and avoid human errors in the modelling phase, as well as make the resultant protocol description more readable. We will see some examples of protocols modelled using assertions, and if time permits, briefly discuss that this expressivity comes at no extra cost, i.e. protocol verification is no harder in the presence of an actively malicious adversary in this new model than it was in the original Dolev-Yao model. about the speaker Vaishnavi Sundararajan is a Chandruka New Faculty Fellow and Assistant Professor in the Department of Computer Science and Engineering at the Indian Institute of Technology Delhi. She is also associated with the Center of Excellence in Cyber Systems and Information Assurance (CSIA). She is interested in applying formal methods and logic to various fields, primarily security. Vaishnavi completed her PhD at the Chennai Mathematical Institute, where she was advised by R Ramanujam and S P Suresh. She has also done postdoctoral stints at CNRS (IRISA), Ericsson Research, and UC Santa Cruz. )