The FOCS program is now online here.Congratulations to Yin Tat Lee and Aaron Sidford for winning the best paper and the best student paper awards for their paper "Solving Linear Programs in O˜(√rank) Iterations and Faster Algorithms for Maximum Flow". They made an important advance in the theory of interior point methods by showing that you can actually … Continue reading FOCS 2014 program is online

[Boaz's note: videos of all ICM 2014 talks, including Mark's talk discussed below, as well as the talks of  Candes and Bhargava I mentioned before are available online here. In particular, if you still don't know how one constructs a fully homomorphic encryption scheme then you should (a) be ashamed of yourself and (b) watch Craig Gentry's … Continue reading ICM 2014: Mark Braverman on interactive information theory

The Simons Institute for the Theory of Computing at UC Berkeley invites applications for Research Fellowships for the research program on Cryptography that will take place in Summer, 2015. These Fellowships are open to outstanding junior scientists (at most 6 years from PhD by 1 May, 2015). Further details and application instructions can be found … Continue reading Simons-Ber​keley Research Fellowship​s in Cryptograp​hy for Summer 2015

This week I'm at the International Congress of Mathematicians  (ICM) 2014 in Seoul, and thought I would post a quick update from a TCS perspective. See Tim Gowers's blog for a much more comprehensive account. There are several other TCS folks here, and I hope some would also post their impressions and recommendations as well. For TCS the … Continue reading Updates from ICM 2014

I am delighted by the news that Subhash Khot was awarded the Rolf Nevanlinna Prize. I am reminded of a time (many years ago) when Robert Krauthgamer and I were arguing about one of Subhash’s papers if it is more of a Complexity Theory paper or more of an Algorithms paper. While this was a … Continue reading Congratulations to Subhash Khot for Nevanlinna Prize

Guest post by Craig Gentry The 2014 International Congress of Mathematicians (ICM 2014) is coming up in a few days, and (like Boaz said) we have a great collection of speakers in the "Mathematical Aspects of Computer Science" section. As it is the weekend, and I am sure that you are looking for excuses to … Continue reading ICM survey: Computing on the edge of chaos

As Boaz discussed, there is an excellent collection of papers to be presented at the upcoming FOCS in Philadelphia. These would be spread over three of the days of the conference. Before this though, there will be an exciting day of workshops and tutorials. It is your chance to reach hundreds of people from across … Continue reading FOCS 2014: Call for Workshops and Tutorials

Emanuele Viola started a new series of posts which is related to the research life-stories project. In his words: "the series “behind the paper” collects snapshots of the generation of papers. For example, did you spend months proving an exciting bound, only to discover it was already known? Or what was the key insight which made … Continue reading Emanuele Viola presents: “behind the paper”

The accepted papers list for FOCS 2014 is now posted online. I am always amazed by the depth and breadth of works in the TCS community, and this FOCS is no exception. Whether you are a physicist interested in the possibility of general "area law" governing entanglement between different parts of systems, a geometer interested in Gromov's topological notion of … Continue reading FOCS 2014 Accepted papers list is online