Theoretical CS Reading Group

The reading group meets once a week usually, Monday 1:30-2:30pm 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
Theory Seminar.

Fall 2017
Spring 2017
Fall 2016
Spring & Summer 2016
Fall 2015
Spring & Summer 2015
Fall 2014
Spring 2014
Summer & Fall 2013

Fall 2017

Tuesday, 5th September 2017 — Theory Seminar - Clayton Thomas, Purdue University
Maximally Recoverable Codes: the Bounded Case

Click to view Abstract

Modern distributed storage systems employ Maximally Recoverable codes that aim to bal- ance failure recovery capabilities with encoding/decoding efficiency tradeoffs. Recent works of Gopalan et al [SODA 2017] and Kane et al [FOCS 2017] show that the alphabet size of grid-like topologies of practical interest must be large, a feature that hampers decoding efficiency. To bypass such shortcomings, in this work we initiate the study of a weaker version of recoverability, where instead of being able to correct all correctable erasure patterns (as is the case for maximal recoverability), we only require to correct all erasure patterns of bounded size. The study of this notion reduces to a variant of a combinatorial problem studied in the literature, which is interesting in its own right. We study the alphabet size of codes withstanding all erasure patterns of small (constant) size. We believe the questions we propose are relevant to both real storage systems and combinatorial analysis, and merit further study. Joint work with Venkata Gandikota, Elena Grigorescu, Minshen Zhu.

Monday, 11th September 2017 — Theory Seminar - Young-San Lin, Purdue University
On Variants of Network Flow Stability

Click to view Abstract

We present a variant of the stable flow problem. Instead of the traditional flow problem that obeys Kirchhoff law, for each vertex, the outflow is monotone and piecewise linear to the inflow. In a directed and capacitated network, each vertex has strict preference over their incident edges. A stable flow assignment does not allow a group of vertices to benefit from privately rerouting along a path. In this paper, we first show the existence of flow stability by reducing this variant of stable flow problem to Scarf's Lemma, then introduce a path augmenting algorithm that runs in polynomial time.

Monday, 18th September 2017 — Topic TBA
Presenter: Samson Zhou

Monday, 25th September 2017 — Topic TBA
Presenter: GV

Monday, 2nd October 2017 — Topic TBA
Presenter: Alexander Block