Theory Coffee

• Thursday, December 16th, Adam Polak Memoryless Worker-Task Assignment with Polylogarithmic Switching Cost
  I'll talk about the basic problem of assigning memoryless workers to tasks with dynamically changing demands. Given a set of w workers and a multiset T \subset [t] of w tasks, a memoryless worker-task assignment function is any function f that assigns the workers [w] to the tasks T based only on the current value of T. The assignment function f is said to have switching cost at most k if, for every task multiset T, changing the contents of T by one task changes f(T) by at most k worker assignments. The problem of memoryless worker task assignment is to construct an assignment function with the smallest possible switching cost.
  
  In past work, it has been posed as an open question what the optimal switching cost is: there are no known sub-linear upper bounds, and after considerable effort, the best known lower bound remains 4.
  
  In this talk, I'll show that it is possible to achieve polylogarithmic O(log(w)log(wt)) switching cost. I'll also prove a super-constant Omega(log*(t)) lower bound. Finally, I'll present an application of the worker-task assignment problem to a metric embedding problem into Hamming space.
  
  The talk will be based on joint work with Aaron Berger, William Kuszmaul, Jonathan Tidor, and Nicole Wein.

• Thursday, December 9th, Weronika Wrzos-Kaminska Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities
  The literature on online Bayesian selection typically focuses on prophet inequalities, which compare the gain of an online algorithm to that of a "prophet" who knows the future. An equally natural, though significantly less well-studied benchmark is the optimum online algorithm. What is the computational complexity of the optimum online? How well can a polynomial-time algorithm approximate it?
  
  In this talk, I will present a recent paper by Christos Papadimitriou, Tristan Pollner, Amin Saberi and David Wajc (https://arxiv.org/abs/2102.10261) in which they consider the online stochastic maximum-weight matching problem under vertex arrivals. In the paper, they give a polynomial-time algorithm which approximates the optimal online algorithm within a factor of 0.51, beating the best-possible prophet inequality for this problem. In contrast, they also show that it is PSPACE-hard to approximate this problem within some constant \alpha<1.

• Thursday, December 2nd, Mikhail Makarov Motif Cut Sparsifiers
  A motif M is a frequently occurring subgraph of a given directed or undirected graph G. Motifs capture higher order organizational structure of G beyond edge relationships, and, therefore, have found wide applications such as in graph clustering, community detection, and analysis of biological and physical networks to name a few.
  
  In this talk, we will show the possibility of constructing a motif cut sparsifier. More precisely, we will show that one can compute in polynomial time a sparse weighted subgraph G' of G with only \tO(n/\epsilon^2) edges such that for every cut, the weighted number of copies of M crossing the cut in G' is within a 1+\epsilon factor of the number of copies of M crossing the cut in G, for every constant size motif M. In addition, we will present a strong lower bound ruling out a similar result for sparsification with respect to induced occurrences of motifs.
  
  This is a joint work with Michael Kapralov, Sandeep Silwal, Christian Sohler and Jakab Tardos.

• Thursday, November 25th, Weiqiang Yuan Log-rank and Lifting for AND-Functions
  Let f: {0, 1}^n -> {0, 1} be a boolean function, and let f_/\(x, y) = f(x /\ y) denote the AND-function of f, where x /\ y denotes bit-wise AND. We study the deterministic communication complexity of f_/\ and show that, up to a log n factor, it is bounded by a polynomial in the logarithm of the real rank of the communication matrix of f_/\. This comes within a log n factor of establishing the log-rank conjecture for AND-functions with no assumptions on f. Our result stands in contrast with previous results on special cases of the log-rank conjecture, which needed significant restrictions on f such as monotonicity or low F_2-degree. Our techniques can also be used to prove (within a log n factor) a lifting theorem for AND-functions, stating that the deterministic communication complexity of f_/\ is polynomially related to the AND-decision tree complexity of f.
  The results rely on a new structural result regarding boolean functions f: {0, 1}^n -> {0, 1} with a sparse polynomial representation, which may be of independent interest. We show that if the polynomial computing f has few monomials then the set system of the monomials has a small hitting set, of size poly-logarithmic in its sparsity. We also establish extensions of this result to multi-linear polynomials f: {0, 1}^n -> R with a larger range.

• Thursday, November 18th, Marina Drygala A Simple LP-Based Approximation Algorithm for the Matching Augmentation Problem
  The Matching Augmentation Problem (MAP) has recently received significant attention as an important step towards better approximation algorithms for finding cheap 2-edge connected subgraphs. This has culminated in a 5/3-approximation algorithm. However, the algorithm and its analysis are fairly involved and do not compare against the problem's well-known LP relaxation called the cut LP.
  
  We propose a simple algorithm that, guided by an optimal solution to the cut LP, first selects a DFS tree and then finds a solution to MAP by computing an optimum augmentation of this tree. Using properties of extreme point solutions, we show that our algorithm always returns (in polynomial time) a better than 2-approximation when compared to the cut LP. We thereby also obtain an improved upper bound on the integrality gap of this natural relaxation.

• Thursday, November 11th, Gilbert Maystre TFNP meets proof complexity
  Subclasses of TFNP aims at classifying the difficulty of search problems that have no satisfactory decision counterpart. For instance, given a graph with constant degree 3 and some Hamiltonian circuit, deciding whether another disjoint Hamiltonian circuit exists is a trivial task because its existence is guaranteed by some combinatorial lemma. On the other hand, actually finding this circuit seems intuitively hard. Proof complexity addresses a different question: Given a boolean formula which is unsatisfiable, is there a succint way to prove that it admits no satisfying assignment? While proof complexity and TFNP seem to share little common ground at first sight, surprisingly strong connections have been exhibited allowing transfer of results from one domain to the other.
  
  In this talk, I will give an overview of both areas, exemplify the existing connections by showing how PLS is related to resolution width and discuss some exciting open problems. The content is borrowed from known results and motivated by ongoing work with Mika Göös, Alexandros Hollender, Siddhartha Jain, William Pires, Robert Robere, and Ran Tao.

• Thursday, November 4th, Agastya Vibhuti Approximating the Center Ranking under Ulam
  We study the problem of approximating a center under the Ulam metric. The Ulam metric, defined over a set of permutations over n, is the minimum number of move operations (deletion plus insertion) to transform one permutation into another. The Ulam metric is a simpler variant of the general edit distance metric. It provides a measure of dissimilarity over a set of rankings/permutations. In the center problem, given a set of permutations, we are asked to find a permutation (not necessarily from the input set) that minimizes the maximum distance to the input permutations. This problem is also referred to as maximum rank aggregation under Ulam. So far, we only know of a folklore 2-approximation algorithm for this NP-hard problem. Even for constantly many permutations, we do not know anything better than an exhaustive search over all n! permutations.
  We achieve a (3/2 - 1/(3m))-approximation of the Ulam center in time O(n^(m^2 \ln m)), for m input permutations over [n]. We therefore get a polynomial time bound while achieving better than a 3/2-approximation for constantly many permutations. This problem is of special interest even for constantly many permutations because under certain dissimilarity measures over rankings, even for four permutations, the problem is NP-hard.
  In proving our result, we establish a surprising connection between the approximate Ulam center problem and the closest string with wildcard problem (the center problem over the Hamming metric, allowing wildcards). We further study the closest string with wildcards problem and show that there cannot exist any $(2-\epsilon)$-approximation algorithm (for any $\epsilon >0$) for it unless P = NP. This inapproximability result is in sharp contrast with the same problem without wildcards, where we know of a PTAS.
  
  This is joint work with Dr. Diptarka Chakraborty and Dr. Kshitij Gajjar.

• Thursday, October 28th, Jakab Tardos Spectral Hypergraph Sparsifiers of Nearly Linear Size
  Graph sparsification has been studied extensively over the past two decades, culminating in spectral sparsifiers of optimal size (up to constant factors). Spectral hypergraph sparsification is a natural analogue of this problem, for which optimal bounds on the sparsifier size were unknown until recently, mainly because the hypergraph Laplacian is non-linear, and thus lacks the linear-algebraic structure and tools that have been so effective for graphs.
  
  In the talk I will introduce our algorithm for constructing \eps-spectral sparsifiers for hypergraphs with O_*(n) hyperedges; the size of the sparsifier is independent of the rank of the hypergraph (the maximum cardinality of a hyperedge), and is essentially best possible. This result is obtained by introducing two new tools. First, a new proof of spectral concentration bounds for sparsifiers of graphs which avoids linear-algebraic methods, replacing the usual application of the matrix Bernstein inequality, and therefore applies to the (non-linear) hypergraph setting. Second, an extension of the weight assignment techniques of Chen, Khanna and Nagda [FOCS'20] to the spectral sparsification setting.

• Thursday, October 14th, Alexandra Lassota Tightness of Sensitivity and Proximity Bounds for Integer Linear Programs
  We consider Integer Linear Programs (ILPs). The distance between an optimal fractional solution and an optimal integral solution (called the proximity) is an important measure. A classical result by Cook et al. (Math. Program., 1986) shows that it is at most n*subDet(A), where subDet(A) is the largest subdeterminant in the constraint matrix A and n is the number of columns in A. Another important measure studies the change in an optimal solution if the right-hand side b is replaced by another right-hand side b'. The distance between an optimal solution x w.r.t. b and an optimal solution x' w.r.t. b' (called the sensitivity) is similarly bounded, i.e., ||b-b'||_1 n*subDet(A) as also shown by Cook et al. (Math. Program., 1986).
  Even after more than thirty years, these bounds are essentially the best known bounds for these measures. While some lower bounds are known for these measures, they either only work for very small values of Delta, require negative entries in the constraint matrix, or have fractional right-hand sides. Hence, these lower bounds often do not correspond to instances from algorithmic problems. This work presents for each n > 0 and arbitrary large entries in the constraint matrix ILPs of the above type with non-negative constraint matrices such that their proximity and sensitivity is at least n*subDet(A).
  
  This is joint work with Sebastian Berndt and Klaus Jansen.

• Thursday, October 7th, Akash Kumar The complexity of testing all properties of planar graphs and the role of isomorphism
  Consider property testing on bounded degree graphs and let \eps > 0 denote the proximity parameter. A remarkable theorem of Newman-Sohler asserts that all properties of planar graphs (more generally hyperfinite) are testable with query complexity only depending on \eps. Recent advances in testing minor-freeness have proven that all additive and monotone properties of planar graphs can be tested in poly(1/\eps) queries. Moreover, a recent work of Levi-Shoshan presents poly(1/\eps) testers for Hamiltonicity under the promise that the graph is planar. Motivated by these results, we ask: can all properties of planar graphs can be tested in poly(1/\eps) queries? In this talk, I will show that such hopes unfortunately meet a roadblock. The natural property of testing isomorphism to a fixed graph requires exp(Omega(1/\eps^2)) queries. We also show by a straightforward adapation of the Newman-Sohler analysis that isomorphism is the "hardest" property of planar graphs. Namely, all properties of planar graphs can be tested within the budget of \exp(Omega(1/\eps^2)) queries.
  
  Joint work with Sabyasachi Basu and C. Seshadhri

• Thursday, September 30th, Kshiteej Sheth Towards Non-Uniform k-Center with Constant Types of Radii
  In the Non-Uniform k-Center problem we need to cover a finite metric space using k balls of different radii that can be scaled uniformly. The goal is to minimize the scaling factor. If the number of different radii is unbounded, the problem does not admit a constant-factor approximation algorithm but it has been conjectured that such an algorithm exists if the number of radii is constant. Yet, this is known only for the case of two radii. Our first contribution is a simple black box reduction which shows that if one can handle the variant of t-1 radii with outliers, then one can also handle t radii. Together with an algorithm by Chakrabarty and Negahbani for two radii with outliers, this immediately implies a constant-factor approximation algorithm for three radii; thus making further progress on the conjecture. Furthermore, using algorithms for the k-center with outliers problem, that is the one radii with outliers case, we also get a simple algorithm for two radii. The algorithm by Chakrabarty and Negahbani uses a top-down approach, starting with the larger radius and then proceeding to the smaller one. Our reduction, on the other hand, looks only at the smallest radius and eliminates it, which suggests that a bottom-up approach is promising. In this spirit, we devise a modification of the Chakrabarty and Negahbani algorithm which runs in a bottom-up fashion, and in this way we recover their result with the advantage of having a simpler analysis.
  
  This is joint work with Xinrui Jia, Lars Rohwedder and Ola Svensson.

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