Mon Sept 5	Clay Thomas Purdue	Title: Maximally Recoverable Codes: the Bounded Case HAAS 111, 1:30pm Abstract: Modern distributed storage systems employ Maximally Recoverable codes that aim to balance 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. Joint work with Venkata Gandikota, Elena Grigorescu, Minshen Zhou
Mon Sept 12	Young-San Lin Purdue	Title: On Variants of Network Flow Stability HAAS 111, 1pm Abstract: We consider a general stable flow problem in a directed and capacitated network, where each vertex has strict preference lists over the incoming and going edges. A flow is stable if no group of vertices can mutually benefit by rerouting the flow along a path contained in the group. Motivated by applications in supply chains, we generalize the traditional stable flow problem by relaxing Kirchhoff's law (the outflow is equal to the inflow) to a requirement that the outflow is monotone and piecewise linear to the inflow at each vertex of the network. We show the existence of a stable flow using Scarf's Lemma, and provide a polynomial time algorithm to find such a stable flow. Joint work with Thanh Nguyen.
Mon Oct 2	Alex Block Purdue	Title: A Sublinear Upper Bound on Our Combinatorial Problem" LWSN 3102, 1:30-2:30 Abstract: In this talk, we discuss an additive-combinatorics problem and its connections to the well-know 3-Free Set problem, the Tri-Colored Sum-Free Set problem, and Szemerédi Regularity Lemma. Joint work with Hemanta Maji and Hai Nguyen.
Mon Oct 23	Evgenia-Maria Kontopoulou Purdue	Title: Towards Randomized Algorithms for the Estimation of Log-Determinants and Von-Neumann Entropies" LWSN 3102, 1:30-2:30 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 (phi, 0). 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.
Mon Oct 23	Mike Atallah Purdue	Title: Opportunities and Perils of the Cyber Revolution ARDEN BEMENT DISTINGUISHED LECTURE
Mon Nov 6	Abhiram Natarajan Purdue	Title: Communication-efficient distributed learning of discrete probability distributions LWSN 3102, 1:30-2:30 Abstract: We initiate a systematic investigation of distribution learning (density estimation) when the data is distributed across multiple servers. The servers must communicate with a referee and the goal is to estimate the underlying distribution with as few bits of communication as possible. We focus on non-parametric density estimation of discrete distributions with respect to the l1 and l2 norms. We provide the first non-trivial upper and lower bounds on the communication complexity of this basic estimation task in various settings of interest. Our results provide insights on the interplay between structure and communication efficiency for a range of fundamental distribution estimation tasks. Joint work with Ilias Diakonikolas, Elena Grigorescu, Jerry Li, Krzysztof Onak, Ludwig Schmidt
Mon Nov 14	Peng Zhang GaTech	Title: Hardness Results for Structured Linear Systems 10-11am LWSN 3102 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. Joint work with Rasmus Kyng.
Fri Dec 1	Madhur Tulsiani TTI-C	Title: From Weak to Strong LP Gaps for all CSPs 2:30-3:30 am LWSN 3102 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. Bio Madhur Tulsiani is an assistant professor at the Toyota Technological Institute at Chicago (TTIC). He received a BTech in computer science and engineering from IIT Kanpur in 2005 and a PhD in computer science from UC Berkeley in 2009, advised by Luca Trevisan. He spent two years as a postdoc at the Institute for Advanced Study and Princeton University, before joining TTIC in 2011. Madhur's interests include complexity theory, approximation algorithms, hardness of approximation and pseudorandomness. His research is funded by an NSF Career Award.

Link to schedule for Spring 2017, Fall 2016, Spring 2016, Fall 2015, Spring 2015, Fall 2014. Spring 2014, Fall 2013. Spring 2013. Fall 2012.