Computer Science and Discrete Mathematics (CSDM)

We will discuss a model of distributed learning in the spirit of Yao's communication complexity model. We consider a two-party setting, where each of the players gets a list of labelled examples and they communicate in order to jointly perform a...

The hypergraph regularity lemma — the extension of Szemeredi's graph regularity lemma to the setting of k-graphs — is one of the most celebrated combinatorial results obtained in the past decade. By now there are various (very different) proofs of...

In a sequence of extremely fundamental results in the 80's, Kaltofen showed that any factor of n-variate polynomial with degree and arithmetic circuit size poly(n) has an arithmetic circuit of size poly(n). In other words, the complexity class VP is...

The Random Fourier Features (RFF) method (Rahimi, Recht, NIPS 2007) is one of the most practically successful techniques for accelerating computationally expensive nonlinear kernel learning methods. By quickly computing a low-rank approximation for...

We develop efficient algorithms for estimating low-degree moments of unknown distributions in the presence of adversarial outliers. The guarantees of our algorithms improve in many cases significantly over the best previous ones, obtained in recent...

An error-correcting code is called locally repairable if any coordinate of a codeword can be recovered by accessing only few other coordinates. For locally repairable codes over small alphabets (such as binary), the optimal trade-off between...

I will show an explicit construction of a binary error correcting code with relative distance $\frac{1-\epsilon}{2}$ and relative rate $\epsilon^{2+o(1)}$. This comes close to the Gilbert-Varshamov bound that shows such codes with rate $\epsilon^2$...

I will show an explicit construction of a binary error correcting code with relative distance $\frac{1-\epsilon}{2}$ and relative rate $\epsilon^{2+o(1)}$. This comes close to the Gilbert-Varshamov bound that shows such codes with rate $\epsilon^2$...

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

We show that the perfect matching problem in general graphs is in Quasi-NC. That is, we give a deterministic parallel algorithm which runs in polylogarithmic time on quasi-polynomially many processors. The result is obtained by a derandomization of...