# Theoretical CS Reading Group

The reading group meets once a week
usually, Wednesday 11:30am-1:00pm 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. |

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 |

# Fall 2018

** Friday, 24th August 2018** —
Theory Seminar - Hemanta Maji, Purdue University

A Result in Discrete-time Martingales

**Click to view Abstract**

We study discrete-time martingales (X0, X1, ... Xn), where Xn is either 0 or 1. Intuitively, such martingales model processes where, over n press releases, we release information regarding the occurrence of a particular event, which occurs with an a priori probability of X0. Our objective is to stop the evolution of this martingale and maximize the expected change in the martingale just before stopping. For example, we can naturally model an n-round coin-tossing protocol in this framework by defining Xk as the probability that the outcome is Heads conditioned on the first k messages of the protocol. The maximum expected-change in the martingale just before stopping translates directly into an adversarial party's attack on the coin-tossing protocol by prematurely aborting the protocol. For any X0 and n, we prove a lower bound on the expected change in any martingale. The only previous result was known only for X0=1/2 by Cleve and Impagliazzo (1993). For X0=1/2, our lower bound improves the previous state-of-the-art by two orders of magnitude. To complement this result, we construct martingales such that the expected change for any stopping strategy (roughly) matches our lower-bound. In particular, for X0=1/2, our upper and lower bounds are within a factor of 1.41 of each other. The martingale that we construct is, surprisingly, different from the ubiquitous ``majority martingale'' (Cleve, 1986). The preciseness of our lower and upper bounds is a consequence of our new geometric approach to this fundamental problem in theoretical computer science, which is of potential independent interest.

** Wednesday, 29th August 2018** —
Minshen Zhu, Purdue University

An Introduction to Quantum Computation

**Click to view Abstract**

This talk starts with some basic elements and principles of quantum computation, including quantum operations, quantum circuits, and the class BQP. Then we move on to some interesting quantum algorithms, including Grover's algorithm for Circuit-SAT and Simon's algorithm for finding the period of a function. We might touch a bit on Shor's algorithm for factoring integers.

** Wednesday, 5th September 2018** —
Greg Frederickson, Purdue University

Hidden in Plane Sight: the Extraordinary Vision of Ernest Irving Freese

**Click to view Abstract**

A geometric dissection is a cutting of a geometric figure into pieces that you can rearrange to form another figure. Dissections have had a surprisingly rich history, reaching back to Islamic mathematicians a millennium ago and Greek mathematicians more than two millennia ago. Following the death of Los Angeles architect Ernest Irving Freese in 1957, his precious 200-page manuscript, chock-full of gorgeous geometric dissections, “disappeared” and wasn't recovered for more than four decades. Hidden within many of its dissections are remarkable uses of plane tessellations, nifty instantiations of mathematical identities, amazing forays into the structure of regular polygons, and spectacular hingings of the dissection pieces. Based on the speaker's recent book [1], this talk will illuminate a number of Freese's lovely insights, and outgrowths. Reference [1] Frederickson, G.N., 2017. Ernest Irving Freese's `Geometric Transformations': the Man, the Manuscript, the Magnificent Dissections. World Scientific: New Jersey.

** Monday, 10th September 2018** —
Yuval Peres, Microsoft Research

Communication Cost of Consensus for Nodes with Limited Memory

**Click to view Abstract**

Consensus protocols are useful in distributed systems with limited power and bandwidth (e.g., miniature sensors, robot swarms, blockchains). We consider a model of n nodes trying to reach consensus. Each node is initially assigned a bit and we assume that the majority bit b is more common than 1-b by some constant factor > 1. Nodes communicate asynchronously: when a node’s Poisson clock rings, the node can choose to either exchange information with a randomly selected node, or remain silent. The former action costs 1, and the latter costs 0. The goal is for all nodes to arrive at $b$ with high probability. Previous work has focused on minimizing the time to consensus; our aim is minimizing communication. We show that for reaching consensus at linear communication cost, order logloglog(n) bits of memory are necessary and sufficient. The best algorithms we know intrinsically select a set of “expert” nodes that learn the majority bit, and then disseminate this knowledge. A key step in the proofs is to distinguish when nodes can become “aware” of reaching the majority bit and stop communicating; this is impossible if their memory is too low. (Joint work with Giulia Fanti, Nina Holden and Gireeja Ranade).

** Wednesday, 12th September 2018** —
Akash Kumar, Purdue University

Finding Minors in Sublinear time in Bounded degree graphs with (almost) optimal one-sided query complexity

**Click to view Abstract**

Let G be an undirected, bounded degree graph with n vertices. Fix a finite graph H, and suppose one must remove \varepsilon n edges from G to make it H-minor free (for some small constant \varepsilon > 0). We give an n^{1/2+o(1)}-time randomized procedure that, with high probability, finds an H-minor in such a graph. For an example application, suppose one must remove \varepsilon n edges from a bounded degree graph G to make it planar. This result implies an algorithm, with the same running time, that produces a K_{3,3} or K_5 minor in G. No sublinear time bound was known for this problem, prior to this result. By the graph minor theorem, we get an analogous result for any minor-closed property. Up to n^{o(1)} factors, this resolves a conjecture of Benjamini-Schramm-Shapira (STOC 2008) on the existence of one-sided property testers for minor-closed properties. Furthermore, our algorithm is nearly optimal, by an \Omega(\sqrt{n}) lower bound of Czumaj et al (RSA 2014). Prior to this work, the only graphs H for which non-trivial property testers were known for H-minor freeness are the following: H being a forest or a cycle (Czumaj et al, RSA 2014), K_{2,k}, (k\times 2)-grid, and the k-circus (Fichtenberger et al, Arxiv 2017). (Joint work with C. Seshadhri and Andrew Stolman).

** Wednesday, 19th September 2018** —
Akash Kumar, Purdue University

Finding Minors in Sublinear time in Bounded degree graphs with (almost) optimal one-sided query complexity

**Click to view Abstract**

Let G be an undirected, bounded degree graph with n vertices. Fix a finite graph H, and suppose one must remove \varepsilon n edges from G to make it H-minor free (for some small constant \varepsilon > 0). We give an n^{1/2+o(1)}-time randomized procedure that, with high probability, finds an H-minor in such a graph. For an example application, suppose one must remove \varepsilon n edges from a bounded degree graph G to make it planar. This result implies an algorithm, with the same running time, that produces a K_{3,3} or K_5 minor in G. No sublinear time bound was known for this problem, prior to this result. By the graph minor theorem, we get an analogous result for any minor-closed property. Up to n^{o(1)} factors, this resolves a conjecture of Benjamini-Schramm-Shapira (STOC 2008) on the existence of one-sided property testers for minor-closed properties. Furthermore, our algorithm is nearly optimal, by an \Omega(\sqrt{n}) lower bound of Czumaj et al (RSA 2014). Prior to this work, the only graphs H for which non-trivial property testers were known for H-minor freeness are the following: H being a forest or a cycle (Czumaj et al, RSA 2014), K_{2,k}, (k\times 2)-grid, and the k-circus (Fichtenberger et al, Arxiv 2017). (Joint work with C. Seshadhri and Andrew Stolman).

** Wednesday, 26th September 2018** —
Elena Grigorescu, Purdue University

Communication-Efficient Distributed Learning of Discrete Distributions

**Click to view Abstract**

We initiate a systematic investigation of distribution learning 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. Joint work with Ilias Diakonikolas, Jerry Li, Abhiram Natarajan, Krzysztof Onak, Ludwig Schmidt

** Wednesday, 26th September 2018** —
Simina Brânzei, Purdue University

Online Learning with an Almost Perfect Expert

**Click to view Abstract**

We study the online learning problem where a forecaster makes a sequence of predictions using the advice of n experts. Our main contribution is to analyze the regime where the best expert makes at most b mistakes and to show that when b = o(log4(n)), the expected number of mistakes made by the optimal forecaster is at most log4(n) + o(log4(n)). We also describe an adversary strategy showing that this bound is tight. Joint with Yuval Peres.

** Wednesday, 17th October 2018** —
Jugal Garg, UIUC

Fisher Markets and Nash Social Welfare

**Click to view Abstract**

Fisher market equilibrium is a powerful solution concept that has found several surprising applications even in non-market settings which do not involve any exchange of money but only require the remarkable fairness and efficiency properties of equilibria, e.g., scheduling, auctions, mechanism design, fair division, etc. A very recent new application is approximation algorithms for maximizing the Nash social welfare (NSW) when allocating a set of indivisible items to a set of agents. In this talk, I will start with the Fisher market model and its connection with the NSW problem. Then, I will show how to design constant-factor approximation algorithms for maximizing the NSW using this connection.

** Tuesday, 23th October 2018** —
Tamalika Mukherjee, Purdue University

Pseudo-Deterministic Proofs

**Click to view Abstract**

I will present the paper titled "Pseudo-Deterministic Proofs" by Goldwasser, Grossman, and Holden published in ITCS 2018. Briefly, pseudo-deterministic proofs are interactive proof systems for search problems in which the verifier is guaranteed to get the same output with high probability on different executions. This talk will introduce the concept of pseudo-deterministic interactive proofs, an overview of their results and discuss open problems.

** Wednesday, 31st October 2018** —
Shai Vardi, Purdue University

On the probe complexity of Local Computation Algorithms

**Click to view Abstract**

The Local Computation Algorithms (LCA) model is a computational model aimed at problem instances with huge inputs and output. For graph problems, the input graph is accessed using probes: strong probes (SPs) specify a vertex $v$ and receive as a reply a list of $v$'s neighbors, and weak probes (WP) specify a vertex $v$ and a port number $i$ and receive as a reply $v$'s $i^{th}$ neighbor. Given a local query (e.g., ``is a certain vertex in the vertex cover of the input graph?''), an LCA should compute the corresponding local output (e.g., ``yes'' or ``no'') while making only a small number of probes, with the requirement that all local outputs form a single global solution (e.g., a legal vertex cover). We study the probe complexity of LCAs that are required to work on graphs that may have arbitrarily large degrees. In particular, such LCAs are expected to probe the graph a number of times that is significantly smaller than the maximum, average or even minimum degree. In this talk, I will focus on some results for strong probes. Our negative results include showing that there are graphs for which finding a \emph{maximal} matching requires $\Omega(\sqrt{n})$ strong probes. On the positive side, we design an LCA that finds a $(1-\eps)$ approximation to \emph{maximum} matching using a constant number probes in regular graphs. Joint work with Uri Feige and Boaz Patt-Shamir

** Tuesday, 23th October 2018** —
Tamalika Mukherjee, Purdue University

Pseudo-Deterministic Proofs

**Click to view Abstract**

I will present the paper titled "Pseudo-Deterministic Proofs" by Goldwasser, Grossman, and Holden published in ITCS 2018. Briefly, pseudo-deterministic proofs are interactive proof systems for search problems in which the verifier is guaranteed to get the same output with high probability on different executions. This talk will introduce the concept of pseudo-deterministic interactive proofs, an overview of their results and discuss open problems.

** Friday, 16th November 2018** —
Palma London, CIT

Frameworks for High Dimensional Parallel and Distributed Optimization

**Click to view Abstract**

In this talk we present frameworks for solving high dimensional optimization problems, in which both the number of variables and the amount of data are huge. In these settings, practical applications require solvers to work at extreme scales and despite decades of work, existing solvers do not scale as desired in many cases. We present black-box acceleration frameworks for speeding up convex solvers, which can be used in either parallel or distributed settings. Given a huge problem, we develop dimension reduction techniques that allow the problem to be solved in a fraction of the original time, and make the computation more amenable to distributed or parallel computation. We present worst-case guarantees on both the quality of the solution and the speedup provided. In particular, we consider two settings of interest. First, we consider packing linear programming (LP). LP solvers are fundamental to many learning and inference problems. We present a framework that can speedup linear programming solvers, such as Cplex and Gurobi, by orders of magnitude, while maintaining nearly optimal solutions. The framework can be used for both linear programs and integer linear programs. Secondly, we consider convex problems with linear constraints, defined with respect to a graph, where the problem data is distributed across the nodes. We present a framework that uses far less communication than existing distributed techniques require and is robust to link failures in the graph. We show both theoretically and numerically that the approach uses orders of magnitude less communication than existing approaches, while maintaining nearly optimal solutions.

** Friday, 30th November 2018** —
Kent Quanrud, UIUC

Submodular function maximization in parallel via the multilinear relaxation

**Click to view Abstract**

Balkanski and Singer recently initiated the study of adaptivity (or parallelism) for constrained submodular function maximization, and studied the setting of a cardinality constraint. Subsequent improvements for this problem by Balkanski, Rubinstein, and Singer and by Ene and Nguyen resulted in a near-optimal $(1-1/e-\eps)$-approximation in $O(\log n/\eps^2)$ rounds of adaptivity. Partly motivated by the goal of extending these results to more general constraints, we describe parallel algorithms for approximately maximizing the multilinear relaxation of a monotone submodular function subject to multiple packing constraints. We obtain a near-optimal $(1-1/e-\eps)$-approximation in polylogarithmic rounds of adaptivity. Our algorithm takes a continuous view point and combines several ideas ranging from the continuous greedy algorithm, its adaptation to the MWU framework for packing constraints, and parallel algorithms for packing LPs. Time permitting we will discuss some recent and ongoing work on this topic.