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.

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.

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.

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).

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).

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).

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

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.

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.

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.

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

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.

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.

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.