Theory Coffee

• Friday, June 4th, Gilbert Maystre A majority lemma for randomised query complexity
  An interesting challenge in the area of boolean function complexity is to understand how function composition behaves under different models. In this talk, I will recall some recent results that show the intricacy of this question in the randomized query complexity setting and present a new one that proves that whenever the outer function is fixed to be the majority one, then the naïve algorithm that solves each inner function with reduced error in parallel is essentially optimal.
  
  Joint work with Mika Göös.

• Friday, May 14th, Haotian Jiang Minimizing Convex Functions with Integral Minimizers
  Given a separation oracle SO for a convex function f that has an integral minimizer inside a box with radius R, we show how to find an exact minimizer of f using at most O(n (n + \log(R))) calls to SO and \poly(n, \log(R)) arithmetic operations, or O(n \log(nR)) calls to SO and \exp(O(n)) \poly(\log(R)) arithmetic operations. When the set of minimizers of $f$ has integral extreme points, our algorithm outputs an integral minimizer of f. This improves upon the previously best oracle complexity of O(n^2 (n + \log(R))) for polynomial time algorithms obtained by [Grötschel, Lovász and Schrijver, Prog. Comb. Opt. 1984, Springer 1988] over thirty years ago.
  For the Submodular Function Minimization problem, our result immediately implies a strongly polynomial algorithm that makes at most O(n^3) calls to an evaluation oracle, and an exponential time algorithm that makes at most O(n^2 \log(n)) calls to an evaluation oracle. These improve upon the previously best O(n^3 \log^2(n)) oracle complexity for strongly polynomial algorithms given in [Lee, Sidford and Wong, FOCS 2015] and [Dadush, Végh and Zambelli, SODA 2018], and an exponential time algorithm with oracle complexity O(n^3 \log(n)) given in the former work.
  Our result is achieved via a reduction to the Shortest Vector Problem in lattices. We show how an approximately shortest vector of certain lattice can be used to effectively reduce the dimension of the problem. Our analysis of the oracle complexity is based on a potential function that captures simultaneously the size of the search set and the density of the lattice, which we analyze via convex geometry tools. Paper available at https://arxiv.org/abs/2007.01445.

• Friday, May 7th, Andreas Maggiori The Primal-Dual method for Learning Augmented Algorithms
  The extension of classical online algorithms when provided with ML predictions is a new and active research area. In this area, the goal is to design learning augmented online algorithms which: incorporate predictions in a black-box manner (without making assumptions regarding the quality of the predictions) outperform any online algorithm when the predictions are accurate maintain reasonable worst case guarantees if the predictions are misleading
  In this talk, I will show how to extend the primal-dual method for online algorithms in the learning augmented setting. Using this method, I will focus on how to design algorithms that use predictions for the ski rental problem and the online set cover problem.
  
  Co-authors: Etienne Bamas and Ola Svensson
  Link to the paper: https://arxiv.org/pdf/2010.11632.pdf (accepted as an oral talk at NeurIPS 2020)

• Friday, April 30th, David Saulpic New Coreset Framework for Clustering
  Given a metric space, the (k,z)-clustering problem consists of finding k centers such that the sum of the of distances raised to the power z of every point to its closest center is minimized. This encapsulates the famous k-median (z=1) and k-means (z=2) clustering problems. Designing small-space sketches of the data that approximately preserves the cost of the solutions, also known as coresets, has been an important research direction over the last 15 years.
  In this talk, I will present a new, simple coreset framework that simultaneously improves upon the best known bounds for a large variety of settings, ranging from Euclidean space, doubling metric, minor-free metric, and the general metric cases.
  This is joint work with Vincent Cohen-Addad and Chris Schwiegelshohn.

• Friday, April 23rd, Buddhima Gamlath Single-Sample Prophet Inequalities
  In the classical single choice prophet inequality, n values are independently drawn from n known distributions and revealed to an online algorithm in an adversarial order. The task of the algorithm is to irrevocably pick one of the values and stop before seeing the remaining values, so as to maximize the picked value. The performance is measured compared to the maximum value in the hindsight, and it is known that the optimal competitive ratio is 1/2.
  In the single-sample case, the algorithm does not get to know the distributions but instead gets a single sample drawn from each of the distributions. In the talk, I will first go over a simple and elegant proof (by Rubinstein et al. https://arxiv.org/abs/1911.07945) that the optimal competitive ratio for the single sample case is also 1/2.
  Then I will present a recent single-sample prophet inequality (by DŸtting et al. https://arxiv.org/abs/2104.02050) for weighted matching in general graphs where each edge weight w_e is independently drawn from a distribution D_e and the algorithm only has one sample value per each edge to begin with. (A similar result was also shown recently by Caramanis et al. https://arxiv.org/abs/2103.13089).

• Friday, April 16th, Kshiteej Sheth Algorithms for k-median clustering with outliers
  Clustering is a fundamental task studied by various communities and one of the most well-studied formulations of it is the k-Median problem. Given a set of n clients and facilities in a metric space, the goal is to open a set of k facilities such that the sum over every client of the client's distance to the nearest open facility is minimized. A practically motivated and algorithmically challenging generalization is the k-Median with outliers problem, in which you only need to connect m(<n) clients (m is given in the input). In this talk, I will mainly explain the beautiful iterative rounding framework of Krishnaswamy, Li, and Sandeep that appeared in STOC'18, which gets a constant approximation for this problem. If time permits, I will discuss some ongoing work with Xinrui Jia, Lars Rohwedder and Ola Svensson on extensions of this problem.

• Friday, April 9th, Jan Hazla On codes decoding errors on the BEC and BSC
  I will talk about how to use a recent inequality on Boolean functions by Samorodnitsky to obtain a result in coding theory. Namely, assume that a linear code successfully corrects errors on the binary erasure channel (BEC) under optimal (maximum a posteriori, or MAP) decoding. Then, this code is also successful on a range of other channels with somewhat smaller capacities, including binary symmetric channel (BSC).
  
  One previously unknown consequence is that constant-rate Reed--Muller codes correct errors on BSC(p) for some constant p > 0.
  
  Joint work with Alex Samorodnitsky and Ori Sberlo.

• Friday, April 6th, Akash Kumar, Partition oracles for bounded degree planar graphs
  Take a planar graph with maximum degree d. These graphs admit a hyperfinite decompositions, where, for a sufficiently small \epsilon > 0, one removes \epsilon dn edges to get connected components of size independent of n. An important tool for sublinear algorithms and property testing for such classes is the partition oracle. A partition oracle is a local procedure that gives consistent access to a hyperfinite decomposition, without any preprocessing. Given a query vertex v, the partition oracle outputs the component containing v in time independent of n. All the answers are consistent with a single hyperfinite decomposition. In this talk, I will describe a partition oracle that runs in time poly(d/\epsilon).
  Joint work with C. Seshadhri and Andrew Stolman.

• Friday, March 19th, Xinrui Jia, Fair Colorful k-Center Clustering
  An instance of the colorful k-center problem consists of points in a metric space that are colored red or blue, along with an integer k and a coverage requirement for each color. The goal is to find the smallest radius r such that there exist balls of radius r around k of the points that meet the coverage requirements. In this talk, I will first present a pseudo-approximation of S. Bandyapadhyay, T. Inamdar, S. Pai, and K. Varadarajan that uses k+1 centers. Then I will explain how we can obtain a true approximation using clustering and subset-sum ideas that arise from the pseudo-approximation.
  This is joint work with Kshiteej Sheth and Ola Svensson.

• Friday, March 12th, Jakab Tardos, Spectral Sparsification of Hypergraphs
  Cut and spectral sparsification of graphs have numerous applications, including e.g. speeding up algorithms for cuts and Laplacian solvers. These powerful notions have recently been extended to hypergraphs. In this talk, I will define spectral sparsifiers for hypergraphs, and present a technique for producing spectral sparsifiers of size O*(nr) for hypergraphs with hyperedge size bounded by r. Our main tool is a new concentration inequality for the (non-linear) Laplacian of a subsampled expander hypergraph. On the lower bound side, I will show that the hypergraph cut function of an r-uniform hypergraph with n vertices in general requires \Omega(n r) bits to represent, even approximately.
  Joint work with Michael Kapralov, Robert Krauthgamer, and Yuichi Yoshida.

• Friday, March 5th, Paritosh Garg, Robust Algorithms against Adversarial Injections
  I will present a new model that we study that is sandwiched somewhere between adversarial-order streams and random-order streams with the motivation of designing robust algorithms. Then, I will present results on two problems namely maximum matching and submodular maximization in this model. Eventually, I will discuss some interesting open problems that arise.
  This is a joint work with Sagar Kale, Lars Rohwedder and Ola Svensson.

• Friday, February 26th, Navid Nouri, Graph Spanners by Sketching in Dynamic Streams and the Simultaneous Communication Model
  Graph sketching is a powerful technique in dynamic graph streams that has enjoyed considerable attention in the literature in recent years, and has led to near optimal dynamic streaming algorithms for many fundamental problems such as connectivity, cut and spectral sparsifiers. In the first part of this talk, we are going to talk about the first algorithm that achieves sub-linear stretch in a single pass, using almost linear space. Then, we are going to discuss the space-stretch trade-offs when more space is allowed. Finally, we will talk about the simultaneous communication model and propose and analyze the guarantees of our protocol, where each player can communicate small messages.
  Joint work with Arnold Filtser and Michael Kapralov

• Friday, February 19th, Lars Rohwedder, A (2 + epsilon)-approximation algorithm for preemptive weighted flow time on a single machine
  In a recent breakthrough in scheduling, Batra, Garg, and Kumar gave the first constant approximation algorithm for minimizing the sum of weighted flow times. Wiese and I (STOC'21) managed to improve this large unspecified constant to 2 + epsilon. I will give a very graphic presentation of the algorithmic techniques behind this.

• Friday, February 12th, Aida Mousavifar, Spectral Clustering Oracles in Sublinear Time
  Given a graph G that can be partitioned into k disjoint expanders with outer conductance upper bounded by eps, can we efficiently construct a small space data structure that allows quickly classifying vertices of G according to the expander (cluster) they belong to? Formally, we would like an efficient local computation algorithm that misclassifies at most an O(eps) fraction of vertices in every expander. We refer to such a data structure as a spectral clustering oracle. In this talk, first I will explain how to design a sublinear time oracle that provides dot product access to the spectral embedding of G. Then I will show how to design a spectral clustering oracle with sublinear time using the dot product oracle.

• Friday, February 5th, at 1.15pm (note unusual time) Siddhartha Jain, Unambiguous DNFs from Hex
  I'll be talking about my work for my semester project supervised by Mika Göös, in collaboration with Shalev Ben-David & Robin Kothari. We exhibit an unambiguous k-DNF formula that requires CNF width \tOmega(k^{1.5}). Our construction is inspired by the board game Hex and it is vastly simpler than previous ones, which achieved at best an exponent of 1.22. Our result is known to imply several other improved separations in query and communication complexity.