# 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** —
Brett Hemenway, Rafail Ostrovsky, and Mary Wootters

Local Correctability of Expander Codes

**Presenter:** Samson Zhou

** Monday, 25th September 2017** —
Swastik Kopparty and Shubhangi Saraf

Local Testing and Decoding of High-Rate Error-Correcting Codes

**Presenter:** GV

** Monday, 2nd October 2017** —
Theory Seminar - Alexander Block, Purdue University

A Sublinear Upper Bound on Our Combinatorial Problem

** Wednesday, 11th October 2017** —
TCS+ Talk - Moses Charikar, Stanford

Hashing-based-Estimators for Kernel Density in High Dimensions

** Monday, 16th October 2017** —
Luna Frank-Fischer, Venkatesan
Guruswami, and Mary Wootters

**Presenter:** Minshen Zhu

** Monday, 23rd October 2017** —
Theory Seminar - Evgenia-Maria Kontopoulou, Purdue University

Towards Randomized Algorithms for the Estimation of Log-Determinants and Von-Neumann Entropies

**Click to view Abstract**

In the first part, we introduce a novel randomized algorithm for approximating the log-determinant of a Symmetric Positive Definite (SPD) matrix. The algorithm approximates the trace of a small number of matrix powers of a specially constructed matrix, using a method from [1]. We will present theoretical and empirical results for our algorithm when the eigenvalues of the matrix lie in the interval (theta, 1), with 0 < theta < 1. In the second part we will briefly introduce a randomized algorithm to approximate the Von- Neumann entropy of Density matrices that is constructed along similar lines with the one for approximating the log-determinant of SPD matrices. We will present theoretical and preliminary experimental results. [1] H. Avron, S. Toledo (2011), "Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix," J. ACM 58(2)8 [2] C. Boutsidis, P. Drineas, P. Kambadur, E. Kontopoulou, A. Zouzias (2017) "A randomized algorithm for approximating the log determinant of a symmetric positive definite matrix," Elsevier Journal of Linear Algebra and its Applications 533:95-117

** Wednesday, 25th October 2017** —
TCS+ Talk - Seth Pettie, Michigan

A Time Hierarchy Theorem for the LOCAL Model

**Monday, 6th November 2017**— Theory Seminar - Abhiram Natarajan, Purdue University

Communication-efficient distributed learning of discrete probability distributions

**Click to view Abstract**

**Tuesday, 14th November 2017**— Theory Seminar - Peng Zhang, Georgia Tech

Hardness Results for Structured Linear Systems

**Click to view Abstract**

Spielman and Teng (2004) showed that linear systems in Laplacian matrices can be solved in nearly-linear time. Since then, a major research goal has been to develop fast solvers for linear systems in other classes of matrices, e.g., connection Laplacians (Kyng et al., 2016), directed Laplacians (Cohen et al., 2017), etc. Connection Laplacians are a special case of PSD-Graph-Structured Block Matrices (Spielman, 2016), block matrices whose non-zero structure corresponds to a graph, and which additionally can be expressed as a sum of positive semi-definite matrices each corresponding to an edge in the graph. A major open question is whether fast solvers can be obtained for all PGSBMs (Spielman, 2016). Other important families of matrices in the PGSBM class include truss stiffness matrices, multi-commodity Laplacians, and total variation matrices, etc. In this talk, we show that if we can solve linear systems in just slightly larger families in PGSBMs, e.g., truss stiffness matrices, multi-commodity Laplacians, total variation matrices, then we can quickly solve all systems of linear equations over the reals. This result can be viewed either positively or negatively: either we will develop nearly-linear time algorithms for solving all real systems of linear equations, or progress on the families we can solve in nearly linear time will soon halt. Joint work with Rasmus Kyng.

**Friday, 1st December 2017**— Theory Seminar - Madhur Tulsani, TTI-C

From Weak to Strong LP Gaps for all CSPs

**Click to view Abstract**

We study the approximability of constraint satisfaction problems (CSPs) by linear programming (LP) relaxations. We show that for every CSP, the approximation obtained by a basic LP relaxation, is no weaker than the approximation obtained using relaxations given by \Omega( log n / (log log n)) levels of the of the Sherali-Adams hierarchy on instances of size n. It was proved by Chan et al. [FOCS 2013] that any polynomial size LP extended formulation is no stronger than relaxations obtained by a super-constant levels of the Sherali-Adams hierarchy.. Combining this with our result also implies that any polynomial size LP extended formulation is no stronger than the basic LP, which can be thought of as the base level of the Sherali-Adams hierarchy. This essentially gives a dichotomy result for approximation of CSPs by polynomial size LP extended formulations. Using our techniques, we also simplify and strengthen the result by Khot et al. [STOC 2014] on (strong) approximation resistance for LPs. They provided a necessary and sufficient condition under which \Omega(log log n) levels of the Sherali-Adams hierarchy cannot achieve an approximation better than a random assignment. We simplify their proof and strengthen the bound to \Omega(log n / (log log n)) levels. Joint work with Mrinalkanti Ghosh.