The Northwestern CS Theory group had two papers at the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2017), which was recently held in Berkeley, CA.

TCS Postdoc Huck Bennett had a joint paper with Alexander Golovnev (Columbia and Yahoo Research) and Noah Stephens-Davidowitz (Princeton). The paper, “On The Quantitative Hardness of CVP,” initiates the study of the fine-grained complexity of lattice problems, a study which is important to the rapidly developing field of lattice-based cryptography. As its main result, the paper shows strong hardness of the Closest Vector Problem (CVP) with certain parameters assuming the Strong Exponential Time Hypothesis (SETH).

TCS Prof. Aravindan Vijayaraghavan had a joint paper with Oded Regev
(NYU). The paper, “Learning Mixtures of Well-Separated Gaussians,”
studies the classic problem of learning a mixture of k spherical
Gaussian distributions. The paper tries to characterize the
minimum amount of separation needed between the components to
estimate the parameters (means) of the Gaussians, and presents lower
bounds and upper bounds towards this end.