Theoretical CS Reading Group

The reading group meets once a week usually, Thursday 2.30 pm-3.30 pm to discuss a particular paper or topic.

Please join our mailing list to get notifications about the weekly meetings and discussions.

You might also be interested in the
Purdue Theory Seminar.

Upcoming talks will be listed on this webpage regularly. If you wish to give a talk or present a paper please send an email to tmukherj at, and rohanvgarg at

Fall 2021
Spring 2021
Fall 2020
Spring 2019
Fall 2018
Spring 2018
Fall 2017
Spring 2017
Fall 2016
Spring & Summer 2016
Fall 2015
Spring & Summer 2015
Fall 2014
Spring 2014
Summer & Fall 2013

Spring 2022

Thursday, 3rd February 2022
``The Primal-Dual method for Learning Augmented Algorithms'', Etienne Bamas, Andreas Maggiori, Ola Svensson
Presenter: Raymond Song

The extension of classical online algorithms when provided with predictions is a new and active research area. In this paper, we extend the primal-dual method for online algorithms in order to incorporate predictions that advise the online algorithm about the next action to take. We use this framework to obtain novel algorithms for a variety of online covering problems. We compare our algorithms to the cost of the true and predicted offline optimal solutions and show that these algorithms outperform any online algorithm when the prediction is accurate while maintaining good guarantees when the prediction is misleading.

Thursday, 17th February 2022
``Parallel Algorithms for Predicate Detection'', Rohan Garg, Vijay K. Garg
Presenter: Rohan Garg

Given a trace of a distributed computation and a desired predicate, the predicate detection problem is to find a consistent global state that satisfies the given predicate. The predicate detection problem has many applications in the testing and runtime verification of parallel and distributed systems. We show that many problems related to predicate detection are in the parallel complexity class NC, the set of decision problems decidable in polylogarithmic time on a parallel computer with a polynomial number of processors. Given a computation on n processes with at most m local states per process, our parallel algorithm to detect a given conjunctive predicate takes O(log mn) time and O(m^3n^3 log mn) work. The sequential algorithm takes O(mn^2) time. For data race detection, we give a parallel algorithm that takes O(log mn log n) time, also placing that problem in NC. This is the first work, to the best of our knowledge, that places the parallel complexity of such predicate detection problems in the class NC.

Thursday, 24th February 2022
Presenter: Ji Hun Hwang


Thursday, 3rd March 2022
Presenter: Nithish Kumar


Thursday, 10th March 2022
Presenter: Paritosh Verma