Abstract: We use volume sampling to obtain exact multiplicative loss bounds for linear regression. The learner is given a fixed set of n input vectors in R^d of a linear regression problem (aka fixed design). Each vector has a real hidden label. The goal is to approximately solve the linear least squares problem for all n labeled vectors while seeing only a small number of the labels. In our most basic setup, the learner selects a random subset of d vectors from the fixed set of n vectors (without knowing any of the labels). The learner is then given the labels of the chosen subset of d vectors. We show that if the random subset is chosen based on volume sampling, then the linear least squares solution for the subset of d labeled vectors:
Abstract:
This talk concerns the problem of quickly computing distances and shortest paths on distributed networks (the CONGEST model). There have been many developments for this problem in the last few year, resulting in tight approximation schemes. This left widely open whether exact algorithms can perform equally well. In this talk, we will discuss some recent progress in answering this question.
Based on joint work with Chien-Chung Huang and Thatchaphol Saranurak (FOCS 2017) and with Sebastian Krinninger (work in progress).
Abstract: The need to process increasingly large quantities of data has led to the emergence of graphs that are massive in scale. Processing such graphs poses unique algorithmic challenges because even linear time or linear working space can be prohibitively expensive. In this talk, I review several alternative models of computation that allow us to achieve sublinear time and/or space. I will then focus on two examples of fundamental graph problems -- shortest paths and matching -- and present new frameworks for approaching these problems that are naturally well suited to massive graphs, and that lead to improved algorithms in many models of computation.
Abstract:
How does computational learning change when one cannot store all the examples one sees in memory? This question has seen a burst of interest in the past couple of years, leading to the surprising theorem that there exist simple concepts (parities) that require an extraordinary amount of time to learn unless one has quite a lot of memory.
In this work we show that in fact most concepts cannot be learned without sufficient memory. This subsumes the aforementioned theorem and implies similar results for other concepts of interest. The new results follow from a general combinatorial framework that we developed to prove lower bounds for space bounded learning.
Joint work with Michal Moshkovitz, Hebrew University.
Abstract:
We give a constant-factor approximation algorithm for the asymmetric traveling salesman problem. Our approximation guarantee is analyzed with respect to the standard LP relaxation, and thus our result confirms the conjectured constant integrality gap of that relaxation.
Our techniques build upon the constant-factor approximation algorithm for the special case of node-weighted metrics. Specifically, we give a generic reduction to structured instances that resemble but are more general than those arising from node-weighted metrics. For those instances, we then solve Local-Connectivity ATSP, a problem known to be equivalent (in terms of constant-factor approximation) to the asymmetric traveling salesman problem.
This is joint work with Jakub Tarnawski and László Végh.
Abstract: We propose a new framework for constructing pseudorandom generators for n-variate Boolean functions. It is based on two new notions. First, we introduce fractional pseudorandom generators, which are pseudorandom distributions taking values in $[-1,1]^n$. Next, we use a fractional pseudorandom generator as steps of a random walk in $[-1,1]^n$ that converges to $\{-1,1\}^n$. We prove that this random walk converges fast (in time logarithmic in n) due to polarization. As an application, we construct pseudorandom generators for Boolean functions with bounded Fourier tails. We use this to obtain a pseudorandom generator for functions with sensitivity s, whose seed length is polynomial in s. Other examples include functions computed by branching programs of various sorts or by bounded depth circuits.
Abstract: A matrix is "rigid" if it is far in Hamming distance from all low rank matrices. A result of Valiant from the 70s shows that coming up with an explicit construction of highly rigid matrices will imply circuit lower bounds. Despite intense efforts, no such matrices have been found since (other than a random construction). In this talk I'll describe a recent result (joint with Ben Edelman) that shows that a large family of matrices that were previoulsy considered to be good candidates for rigidity are, in fact, not rigid at all. This complements a recent result of Alman and Williams who proved a similar statement for the Hadamard matrix (via different techniques). The main ingredient of the proof is a Lemma of Croot, Lev and Pach which played the main role in the recent solution of the cap-set conjecture and related problems. As much as time permits I will also describe some of these results.
Abstract:
In this talk, we present an explicit construction of a hitting set for read-once branching programs that has a near-optimal dependence on the error parameter. This yields the first improvement over the hitting set induced from Nisan's seminal work (Combinatorica'92).
Joint work with Mark Braverman and Sumegha Garg.
Abstract: We study the problem of testing conditional independence for discrete distributions. Specifically, given samples from a discrete random variable (X, Y, Z) on domain [L1]x[L2]x[n], we want to distinguish, with probability at least 2/3, between the case that X and Y are conditionally independent given Z from the case that (X, Y, Z) is eps-far, in total variation distance, from every distribution that has this property. Conditional independence is a concept of central importance in probability and statistics with a range of applications in various scientific domains. As such, the statistical task of testing conditional independence has been extensively studied in various forms within the statistics and econometrics communities for nearly a century. Rather surprisingly, this problem has not been previously considered in the framework of distribution property testing and in particular no tester with sublinear sample complexity is known, even for the important special case that the domains of X and Y are binary. The main algorithmic result of this work is the first conditional independence tester with /sublinear/ sample complexity for discrete distributions over [L1]x[L2]x[n]. To complement our upper bounds, we prove information-theoretic lower bounds establishing that the sample complexity of our algorithm is optimal, up to constant factors, for a number of settings (and in particular for the prototypical setting when L1, L2 = O(1)).
Abstract:
Is matching in NC, i.e., is there a deterministic fast parallel algorithm for it? This has been an outstanding open question in TCS for over three decades, ever since the discovery of Random NC matching algorithms. Within this question, the case of planar graphs has remained an enigma: On the one hand, counting the number of perfect matchings is far harder than finding one (the former is #P-complete and the latter is in P), and on the other, for planar graphs, counting has long been known to be in NC whereas finding one has resisted a solution!
The case of bipartite planar graphs was solved by Miller and Naor in 1989 via a flow-based algorithm. In 2000, Mahajan and Varadarajan gave an elegant way of using counting matchings to finding one, hence giving a different NC algorithm. However, non-bipartite planar graphs still didn't yield: the stumbling block being odd tight cuts. Interestingly enough, these are also a key to the solution: a balanced odd tight cut leads to a straight-forward divide and conquer NC algorithm. The remaining task is to find such a cut in NC. This requires several algorithmic ideas, such as finding a point in the interior of the minimum weight face of the perfect matching polytope and uncrossing odd tight cuts.
Paper available at: https://arxiv.org/pdf/1709.07822.pdf
Joint work with Nima Anari.
Abstract:
The 2-to-1 games conjecture is the weaker sibling of the famous and important Unique-games conjecture of [Khot02]. A recent sequence of four papers resolved a version of that former conjecture, which might count as a step towards a proof of the Unique-games conjecture, and in any case invalidates some approaches for refuting it. The proof relies crucially on some Expansion properties of the Grassmann-graph, an object that to our knowledge was not studied before in the context of theoretical Computer Science. In this talk I will explain the 2-to-1 and the Unique-games conjectures and their implications, the Grassman graph and its relevance, and hopefully also some key ideas of the proofs.
This is joint work with Irit Dinur, Subhash Khot, Dror Minzer, and Muli Safra
Abstract:
Suppose $\alpha$ and $\beta$ are two angles satisfying $\tan(\alpha) = r\tan(\beta) > 0$, for some rational number $r > 1$. Can both $\alpha$ and $\beta$ be rational multiples of $\pi$?
Let \[p(x,y) = x^5 - (2 y + 1) x^3 - (y^2 + 2) x^2 + y (y-1) x + y^3.\] Is it true that for every integer $y \ge 4$, $p(x, y)$ is an irreducible polynomial in $\mathbb{Q}[x]$, whereby we can determine its Galois group?
We encounter questions like this in our quest to achieve complexity classifications for counting problems. In this talk I will outline a proof to the first question (using character theory), and describeat a high level how answers to such questions lead to complexity dichotomy theorems. Then I will give an overview of the status of the Classification Program for Counting Problems, including all partition functions for graph homomorphisms, counting constraint satisfaction problems, and Holant problems.
Abstract:
We give an explicit pseudorandom generator with seed length poly(log m, 1/\delta) * log n that \delta-fools the class of all m-facet polytopes over {0,1}^n. The previous best seed length had linear dependence on m. As a corollary, we obtain a deterministic quasipolynomial time algorithm for approximately counting the number of feasible solutions of general {0,1}-integer programs.
Joint work with Ryan O'Donnell (CMU) and Rocco Servedio (Columbia)