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.

The Computer Science Division at Northwestern University welcomes new faculty member Dr. Konstantin (Kostya) Makarychev as an Associate Professor, beginning immediately. Dr. Makarychev’s position is one of the ten new faculty lines in CS which were announced in June 2016.

Dr. Makarychev is a theoretical computer scientist working on approximation algorithms, beyond worst-case analysis, applications of high-dimension geometry to computer science, and combinatorial optimization for designing efficient algorithms for computationally hard problems.

Dr. Makarychev joins Northwestern from Microsoft Research in Redmond, WA (2012-2016) and IBM Research Labs in Yorktown Heights, NY (2007-2012). Further details of his background can be found on his personal webpage.

Please click here for details, and the announcement on Northwestern homepage.

TCS Prof. Anindya De had a joint paper with Michael Saks (Rutgers) and Sijian Tang (Rutgers) in 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 16). The paper “Noisy population recovery in polynomial time” addresses the problem of recovering an unknown distribution on binary strings under noise. This problem is related to well-studied problems in learning such as learning mixtures of spherical Gaussians and product distributions. A manuscript of the paper can be found here.

Theory PhD students Abhratanu Dutta and Yiding Feng along with their teammate Ruohong Zhang finished first at the ACM-ICPC Midcentral Regional Programming Contest this year. They finished in 1st place out of 156 teams representing 56 different schools in total and have advanced to the ACM-ICPC World Finals in Rapid City, South Dakota from May 20-25, 2017.

The ACM-ICPC (Association for Computing Machinery – International Collegiate Programming Contest) is a multi-tier, team-based, programming competition. Headquartered at Baylor University, Texas, it operates according to the rules and regulations formulated by the ACM. The contest participants come from over 2,000 universities that are spread across 80 countries and six continents.

Details can be found here.