This list of FOCS accepts are out, with abstracts, with PDF links (via Kintali) and in Algorithmic Game Theory (Nisan) and Algorithms (Eppstein). The FOCS Conference will be held October 23-25 in Palm Springs.
Looks like a strong collection of papers. Lots of tight bounds. I'm a sucker for tight bounds because it means you have the right answer and less chance of follow-up papers.
Here are a few of the papers that caught my eye.
Randomness buys depth for approximate counting by Emanuele Viola. Buys you exactly two layers of AND-OR gates. Viola has another nice paper Extractors for circuit sources.
A Small PRG for Polynomial Threshold Functions of Gaussians by Daniel Kane. I like Gaussians because you can look at them at any angle and the distribution doesn't change.
Optimal bounds for quantum bit commitment by André Chailloux and Iordanis Kerenidis. Perfect quantum bit commitment is impossible but you can do better than classical. This paper shows exactly how well you can do.
Information Equals Amortized Communication by Mark Braverman and Anup Rao. A nice connection between information theory and communication complexity. I wonder if this can be tied into Kolmogorov complexity.
If there exists somewhere a link for Aharonov, Arad, Landau and Vazirani's The Complexity of Quantum States – a Combinatorial Approach, this would be helpful to me and many ... does the FOCS paper cover pretty much the same material as arXiv:1011.3445?
ReplyDeletethis is indeed, quite interesting.
ReplyDelete