COLT deadline is approaching fast, don’t forget to send your awesome learning theory paper(s) before Friday 7th! Also recall that if you get a paper into COLT it will (i) give you an excuse to spend a few days in Barcelona at the best time of the year and (ii) you could stay a few more days to attend our awesome Foundations of Learning Theory workshop.
In other news I attended ITCS in Princeton last month and it was absolutely great. Here are a few papers that I really liked:
- Amir Shpilka, Avishay Tal and Ben Lee Volk, On the Structure of Boolean Functions with Small Spectral Norm
- Andrew Wan, John Wright and Chenggang Wu. Decision Trees, Protocols, and the Fourier Entropy-Influence Conjecture
- Cristopher Moore and Leonard Schulman, Tree Codes and a Conjecture on Exponential Sums
- Fernando Brandao, Aram Harrow, James Lee and Yuval Peres, Adversarial hypothesis testing and a quantum Stein’s Lemma for restricted measurements
- Yossi Azar, Uriel Feige, Michal Feldman and Moshe Tennenholtz, Sequential Decision Making with Vector Outcomes
- Manor Mendel and Assaf Naor, Expanders with respect to Hadamard spaces and random graphs
- David Gamarnik and Madhu Sudan, Limits of local algorithms over sparse random graphs
- Rishi Gupta, Tim Roughgarden and C. Seshadhri, Decompositions of Triangle-Dense Graphs
During my visit to the Theory Group at MSR I also learned about the following topics which my readers will probably like too: Tucker’s lemma (see also the related Borsuk-Ulam theorem), the lamplighter graph and random walks on it, sparse regularity lemma, and algorithmic applications of evolving sets.