Quarterly Theory Workshop: 2021 Junior Theorists Workshop

Synopsis

The 2021 Junior Theorists Workshop is part of the Northwestern CS Quarterly Theory Workshop Series. The focus of this workshop will be on junior researchers in all areas of theoretical computer science. The speakers for this workshop are:

Titles and Abstracts

Speaker: Maximilian Probst Gutenberg
Title: Faster Flow Algorithms via Dynamic Graph Data Structures
Abstract: Recently, a lot of progress has been made by solving combinatorial problems using a mix of techniques from convex optimization, spectral graph theory, and dynamic data structures. In this talk, we present some very recent developments that are centered around the development of a very powerful dynamic data structure that maintains single-source shortest paths in a graph undergoing edge deletions.

Speaker: Talya Eden
Title: Approximating the arboricity in sublinear time
Abstract: We consider the problem of approximating the arboricity of a graph $G=(V,E)$, which we denote by $arb(G)$, in sublinear time, where the arboricity of a graph is the minimal number of forests required to cover its edges. An algorithm for this problem may perform degree and neighbor queries, and is allowed a small error probability. We design an algorithm that outputs an estimate $\hat{\alpha}$, such that with probability $1-1/poly(n)$, $arb(G)/c log2 n \leq   \hat{\alpha} \leq \arb(G)$ , where $n=|V|$ and $c$ is a constant. The expected query complexity and running time of the algorithm are $O(n/arb(G))\cdot \poly(\log n)$, and this upper bound also holds with high probability. This bound is optimal for such an approximation up to a $poly(log n)$ factor. This result has important implications as many sublinear-time algorithms are parameterized by the arboricity, and rely on getting its value as input.

Based on joint work with Saleet Mossel and Dana Ron.

Speaker: Sai Sandeep Pallerla
Title: Almost optimal inapproximability of multidimensional packing problems
Abstract: Multidimensional packing problems generalize the standard packing problems such as Bin Packing, Multiprocessor Scheduling by allowing the jobs to be d-dimensional vectors. While the approximability of the scalar problems is well understood, there has been a significant gap between the approximation algorithms and the hardness results for the multidimensional variants. We close this gap by giving almost optimal inapproximability results for the multidimensional problems, namely, Vector Bin Packing, Vector Scheduling, and Vector Bin Covering.

For the Vector Bin Packing problem, our hardness result goes via the hardness of the set cover problem using a notion of packing dimension of set families. For the Vector Scheduling and Vector Bin Covering problems, we obtain our hardness results via variants of graph and hypergraph coloring problems.

Speaker: Nathan Klein
Title: A (Slightly) Improved Approximation Algorithm for Metric TSP
Abstract: I will discuss work in which we obtain a randomized $3/2-\epsilon$ approximation algorithm for metric TSP, for some $\epsilon>10^{-36}$. This slightly improves over the classical 3/2 approximation algorithm due to Christofides [1976] and Serdyukov [1978]. The talk will focus on giving an overview of the key ideas involved in our proof, such as properties of random spanning trees and the structure of near minimum cuts. This is joint work with Anna Karlin and Shayan Oveis Gharan.

Speaker: Jess Banks
Title: Smoothed Analysis of Approximate Matrix Diagonalization
Abstract: Right now, countless practitioners across every field of quantitative scientific research are computing the eigenvectors and eigenvalues of a matrix. In practice, state-of-the-art numerical linear algebra packages can solve this approximate diagonalization problem quickly and accurately in finite precision arithmetic – typically using the shifted QR algorithm of Francis and Kublanovskaya. For Hermitian matrices, this practical behavior is accompanied by well-known theoretical guarantees due originally to Wilkinson, Hoffman, and Parlett in the 1960’s and 70’s. However, in the non-Hermitian case, our theoretical understanding of algorithms for approximate diagonalization remains incomplete, in large part due to the related phenomena of non-diagonalizability (matrices with eigenvectors that fail to form a basis, or form an arbitrarily ill-conditioned basis) and spectral instability (sensitivity of eigenvalues to small additive perturbations).

In this talk I will present two recent results on the smoothed analysis of approximate diagonalization. The first is a regularization result from random matrix theory, quantifying the classical fact that the non-diagonalizable matrices have Lebesgue measure zero: every matrix, after a small Gaussian perturbation, has a well-conditioned basis of eigenvectors, gapped eigenvalues, and is itself insensitive to small additional perturbations. The second is a full analysis, in finite precision arithmetic, of the well-studied Spectral Bisection algorithm of Beavers and Denman for computing eigenvectors and eigenvalues – on matrices which have been regularized in the above sense. Together, these results imply that every matrix can be approximately diagonalized in nearly matrix multiplication time. Time permitting, I’ll mention recent and forthcoming work on the shifted QR algorithm.

Speaker: Chi-Ning Chou
Title: Approximability of all Finite CSPs with Linear Sketches
Abstract: Approximating constraint satisfaction problems (CSPs) is one of the central problems in complexity theory. People are interested in understanding what’s the best approximation ratio that can be achieved by efficient algorithms for problems such as Max-Cut. While in the past 30 years there has been exciting progress in the polynomial time regime with conditional hardness (e.g, NP-hardness, UG-hardness), recently there is a growing interest studying unconditional hardness of approximating CSPs through the streaming models.

In this talk, I am going to present a recent work with Alexander Golovnev, Madhu Sudan, and Santhoshini Velusamy in which we consider the approximability of CSPs in the context of sketching algorithms (which is a special family of streaming algorithms) and give a dichotomy result. Specifically, for every constraint function family and every \beta < \gamma,  we show that either a linear sketching algorithm solves the (\beta,\gamma)-approximation problem in polylogarithmic space, or the problem is not solvable by any sketching algorithm in o(\sqrt{n}) space. In the end of the talk, I will also provide several frontier open problems about approximating CSP in the streaming models.

Speaker: Bento Natura
Title: On circuit imbalance measures for linear programming
Abstract: Recent years have seen tremendous progress in approximate solvers for Linear Programs (LP) based on Interior-Point Methods (IPM). In this talk we show how to leverage these algorithms to design algorithms that solve LPs exactly. The running time of these algorithms depends on circuit imbalances of the constraint matrix only. We will present these algorithms in two different regimes: In the first, we use approximate LP solvers in a blackbox manner, extending Tardos\u2019s Framework (Oper. Res. \u201986). In the second, we design an exact IPM, using ideas of the recent approximate IPMs to improve the running time. Based on joint work with Daniel Dadush, Sophie Huiberts and László Végh.

Speaker: Aditi Laddha
Title: Algorithms for Sampling Convex Bodies
Abstract: We discuss two Markov chain Monte Carlo algorithms for uniformly sampling convex bodies. The first is Gibbs sampling, also known as Coordinate Hit-and-Run (CHAR). In each step, the algorithm selects a random coordinate and re-samples that coordinate from the distribution induced by fixing all the other coordinates. This is joint work with Santosh Vempala. The second, weighted Dikin Walk, uses a convex barrier function, via its Hessian, to define an ellipsoid centered at each interior point of a convex body. At each step, it picks a uniformly random point in the ellipsoid centered at the current point. This is joint work with Yin Tat Lee and Santosh Vempala.

Speaker: Gal Vardi
Title: Complexity-theoretic barriers to depth separation in neural networks
Abstract: When studying the expressiveness of neural networks, an important question is whether there is depth separation, namely, functions which can only be approximated by sufficiently deep networks, assuming their size is polynomially-bounded. However, for separation between constant depths, existing results are limited to depths 2 and 3, and achieving separation for higher depths has been an open question. Moreover, for separation between constant and non-constant depths, existing results use functions with an extremely large Lipschitz constant, which are less “natural” from a practical viewpoint.

In this talk, I will show fundamental barriers to proving depth-separation results, by reductions from open problems in circuit complexity.

Based on joint works with Daniel Reichman, Toniann Pitassi and Ohad Shamir.

Speaker: Kangning Wang
Title: Approximately Efficient Bilateral Trade
Abstract: We study bilateral trade between two strategic agents. The celebrated result of Myerson and Satterthwaite states that in general, no incentive-compatible, individually rational and weakly budget balanced mechanism can be efficient. I.e., no mechanism with these properties can guarantee a trade whenever buyer value exceeds seller cost. Given this, a natural question is whether there exists a mechanism with these properties that guarantees a constant fraction of the first-best gains-from-trade, namely a constant fraction of the gains-from-trade attainable whenever buyer’s value weakly exceeds seller’s cost. In this work, we positively resolve this long-standing open question on constant-factor approximation, mentioned in several previous works, using a simple mechanism. This is joint work with Yuan Deng, Jieming Mao, and Balasubramian Sivan from Google Research.

Speaker: Samson Zhou
Title: Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators
Abstract: We introduce difference estimators for data stream computation, which provide approximations to F(v)-F(u) for frequency vectors v,u and a given function F. We show how to use such estimators to carefully trade error for memory in an iterative manner. We give the first difference estimators for the frequency moments F_p for p between 0 and 2, as well as for integers p>2. Using these, we resolve a number of central open questions in adversarial robust streaming and sliding window models. For both models, we obtain algorithms for norm estimation whose dependence on the accuracy parameter \(\epsilon\) is \(1/\epsilon^2\), which shows, up to logarithmic factors, that there is no overhead over the standard insertion-only data stream model for these problems. Joint work with David P. Woodruff.

Speaker: Kiran Shiragur
Title: Efficient universal estimators for symmetric property estimation
Abstract: Given i.i.d samples from an unknown distribution, estimating its symmetric properties is a classical problem in information theory, statistics and computer science. Symmetric properties are those that are invariant to label permutations and include popular functionals such as entropy and support size. Early work on this question dates back to the 1940s when R. A. Fisher and A. S. Corbet studied this to estimate the number of distinct butterfly species in Malaysia. Over the past decade, this question has received great attention leading to computationally efficient and sample optimal estimators for various symmetric properties. All these estimators were property specific and the design of a single estimator that is sample optimal for any symmetric property remained a central open problem in the area.

In a recent breakthrough, Acharya et. al. showed that computing an approximate profile maximum likelihood (PML), a distribution that maximizes the likelihood of the observed multiset of frequencies, allows statistically optimal estimation of any symmetric property. However, since its introduction by Orlitsky et. al. in 2004, efficient computation of an approximate PML remained a well known open problem.

In our work, we resolved this question by designing the first efficient algorithm for computing an approximate PML distribution. In addition, our investigations have led to a deeper understanding of various computational and statistical aspects of PML and universal estimators.

 About the Quarterly Theory Workshop Series