## Schedule

For Spring 2018, the Theory Seminar will meet on Fridays from 2:00-3:00pm in GDC 4.302 unless otherwise noted. This schedule is being updated throughout the semester.

1/12/2018 – Keerti Choudhary, Weizmann Institute: “Fault Tolerant Structures for Reachability and Strong-connectivity”

1/19/2018 – Ryan Williams, MIT: "Circuit Lower Bounds for Nondeterministic Quasi-Polytime"

2/02/2018 – Adam Klivans, University of Texas at Austin: "Learning Discrete Markov Random Fields with Nearly Optimal Runtime and Sample Complexity"

2/09/2018 – Chandra Chekuri, University of Illinois: "Speeding up MWU Based Approximation Schemes for Positive LPs and Some Applications"

2/16/2018 – Avishay Tal, Stanford University: "Improved Pseudorandomness for Unordered Branching Programs through Local Monotonicity"

3/2/2018 – Alexandros Dimakis, University of Texas at Austin: "Generative Models and Compressed Sensing"

3/23/2018 – Li-Yang Tan, TTI-Chicago: "Fooling Polytopes"

3/30/2018 - Seth Pettie, University of Michigan: "A Time Hierarchy Theorem for the LOCAL Model"

**1/12/2018Keerti Choudhary, Weizmann Institute:
Fault Tolerant Structures for Reachability and Strong-Connectivity**

In this talk, we look at the problems of single-source-reachability (SSR) and strongly-connected-components (SCC) in presence of failures of vertices and edges. In the static setting, these problems can be solved in O(|V|+|E|) time, for any directed graph G=(V, E). To model the scenario of a faulty network, we associate a parameter k with the network such that there are at most k vertices (or edges) that are failed at any stage. The goal is to preprocess the graph G and compute a compact data structure, that, given any set F of at most k vertices (or edges), efficiently solves the SSR and SCC problems for the graph G\F.

We show that, given a directed graph G with n vertices, and a positive integer k, we can obtain a fault tolerant data structure that solves the SSR and SCC problems for G\F in O(2^k n polylog n) time for any set F of size at most k. For the problem of SSR, we show a much stronger result, i.e., for every positive integer k, there is a subgraph (sparse certificate) H of G with at most (2^k n) edges such that vertices reachable from source in G\F and H\F are identical, for every F of size at most k. Our results makes an interesting usage of the simple techniques like max-flows, farthest min-cuts, and heavy path decomposition.

**1/19/2018Ryan Williams, MIT:
Circuit Lower Bounds for Nondeterministic Quasi-Polytime**

I will give an overview of the recent proof (with my PhD student Cody Murray) that the class NQP = NTIME(n^{polylog n}) does not have ACC circuits of n^{log n} size (even with a layer of threshold gates at the bottom). This is achieved by strengthening a key component of the proof of NEXP not in ACC; in particular, we prove a new "Easy Witness Lemma" for NQP.

**2/02/2018****Adam Klivans, University of Texas at Austin
Learning Discrete Markov Random Fields with Nearly Optimal Runtime and Sample Complexity**

We give an algorithm for learning the structure of an undirected graphical model over any finite alphabet that has nearly optimal runtime and sample complexity. We make no assumptions on the structure of the graph. For Ising models, this subsumes and improves on all prior work. For higher-order MRFs, these are the first results of their kind.

Our approach is new and uses a multiplicative-weight update algorithm. Our algorithm-- Sparsitron-- is easy to implement (has only one parameter) and holds in the online setting. It also gives the first provably efficient solution to the problem of learning sparse Generalized Linear Models (GLMs).

Joint work with Raghu Meka

**2/09/2018Chandra Chekuri, University of Illinois:
Speeding up MWU Based Approximation Schemes for Positive LPs and Some Applications**

One of the recent exciting directions in algorithms is developing faster algorithms for various problems in discrete and combinatorial optimization via sophisticated continuous optimization methods. The multiplicative weight update (MWU) method is an older technique and has been used to approximately solve positive linear programs (packing, covering and mixed packing and covering LPs) starting from the early 90s. MWU based methods have some advantages when dealing with implicit linear programs that arise frequently in combinatorial optimization. We build upon several existing ideas and propose some new ones to obtain significantly faster algorithms for several problems. The talk will illustrate some examples including Metric-TSP, spanning tree packing, and geometric packing and covering problems.

Based on joint work with Kent Quanrud.

**2/16/2018****Avishay Tal, Stanford University
Improved Pseudorandomness for Unordered Branching Programs through Local Monotonicity**

We present an explicit pseudorandom generator with polylog(n) seed length for read-once constant-width branching programs that can read their $n$ input bits in any order. This improves upon the work of Impagliazzo, Meka, and Zuckerman (FOCS, 2012), where they required seed length $n^{1/2+o(1)}$.

A central ingredient in our work is a bound on the Fourier spectrum of constant-width branching programs, settling a conjecture posed by Reingold, Steinke, and Vadhan (RANDOM, 2013).

Our analysis crucially uses a notion of local monotonicity on the edge labeling of the branching program. We carry critical parts of our proof under the assumption of local monotonicity and show how to deduce our results for unrestricted branching programs.

Joint work with Eshan Chattopadhyay, Pooya Hatami, and Omer Reingold

**3/2/2018****Alexandros Dimakis, University of Texas at Austin
Generative Models and Compressed Sensing**

The goal of compressed sensing is to estimate a vector from an underdetermined system of noisy linear measurements, by making use of prior knowledge. For most results in the literature, the structure is represented by sparsity in a well-chosen basis. We show how to achieve guarantees similar to standard compressed sensing but without employing sparsity at all. Instead, we assume that the unknown vectors lie near the range of a generative model, e.g. a GAN or a VAE. We show how the problems of image inpainting and super-resolution are special cases of our general framework.

We show how to generalize the RIP condition for generative models and that random gaussian measurement matrices have this property with high probability. A Lipschitz condition for the generative neural network is the key technical issue for our results. Time permitting we will discuss how this method can be used to protect from adversarial examples.

(Based on collaborations with Ashish Bora, Ajil Jalal and Eric Price)

**3/23/2018Li-Yang Tan, TTI-Chicago
Fooling Polytopes **

We give an explicit pseudorandom generator with seed length poly(log m,1/delta) log(n) that delta-fools intersections of m halfspaces over {0,1}^n (equivalently, m-facet polytopes). Joint work with Ryan O'Donnell (CMU) and Rocco Servedio (Columbia).

**3/30/2018Seth Pettie, University of Michigan
A Time Hierarchy Theorem for the LOCAL Model**

The celebrated "Time Hierarchy Theorem" for Turing machines states, informally,

that more problems can be solved given more time. The extent to which a time hierarchy-type theorem

holds in the classic distributed LOCAL model has been open for many years. In particular, it is consistent

with previous results that all natural problems in the LOCAL model can be classified according

to a small constant number of complexities, such as $O(\log^* n), O(\log n), 2^{O(\sqrt{\log n})}$, etc.

We establish the first time hierarchy theorem for the LOCAL model and prove that several gaps exist in the

LOCAL time hierarchy. One of the gap results can be interpreted as showing that the distributed Lovasz

local lemma is complete for randomized sublogarithmic time.

Joint work with Yi-Jun Chang. Extended abstract appeared in FOCS 2017. Full version at arXiv:1704.06297.