Wednesday, November 30, 2016

A Few Interesting Computer Science Papers

Probabilistic Rank and Matrix Rigidity by Josh Alman and Ryan Williams

Leslie Valiant outlined an approach to proving circuit lower bounds from matrix rigidity. A matrix is rigid if you need to change many entries to significantly reduce the rank. Valiant showed that one could create a function with high algebraic circuit complexity from a rigid matrix. Of course one needs a rigid matrix and the Hadamard matrices (rows are Hadamard codes) seemed the perfect candidate. Alman and Williams say not so fast, in fact the Hadamard matrices are not that rigid and won't work for Valiant's program.

Ryoan: A Distributed Sandbox for Untrusted Computation on Secret Data by Tyler Hunt, Zhiting Zhu, Yuanzhong Xu, Simon Peter, and Emmett Witchel

You want to use Intuit's TurboTax to prepare your taxes but you don't want to actually let Intuit or their cloud provider to see your income sources. Sounds like a job for homomorphic encryption, a good solution in theory but not yet practical. Ryoan, an OSDI best paper awardee, takes a systems approach to the same problem, creating a computing sandbox where one can do secure computation without allowing the cloud or software provider access.

Google's Multilingual Neural Machine Translation System: Enabling Zero-Shot Translation (and related blog post) by Melvin Johnson, Mike Schuster, Quoc V. Le, Maxim Krikun, Yonghui Wu, Zhifeng Chen, Nikhil Thorat, Fernanda Viégas, Martin Wattenberg, Greg Corrado, Macduff Hughes and Jeffrey Dean

Google now using a single system to translate between different pairs of languages, even pairs of languages for which it has no examples. Their analysis shows a potential internal representation of the language and the beginning of a universal translator.

No comments:

Post a Comment