(Also available as a pdf file. Apologies for the many footnotes, feel free to skip them.) Computational problems come in all different types and from all kinds of applications, arising from engineering as well the mathematical, natural, and social sciences, and involving abstractions such as graphs, strings, numbers, and more. The universe of potential algorithms … Continue reading Structure vs. Combinatorics in Computational Complexity
Author: Boaz Barak
Reasons to care: In honor of Scott Aaronson
Update (5/7): This post earned me a spot on the not-so-exclusive club of people called names such as a "narrow-minded" "biased" "religious worshiper" "who doesn't want to learn something difficult and new" by Luboš Motl. Interestingly, he mostly takes issue with my discounting the possibility that the complexity of SAT is something like $latex n^{1000}$ or $latex … Continue reading Reasons to care: In honor of Scott Aaronson
The New Yorker on P vs NP
A new review is out for Lance Fortnow's new book "The Golden Ticket: P, NP and the Search for the Impossible". In another piece of news: congratulations to new members of the National Academy of Science Éva Tardos and Avi Wigderson!
Alt Equals
I recently discovered that some colleagues are unaware of the math typesetting capabilities in PowerPoint, and so as a responsible Microsoft employee I thought it my duty to inform the public of these potentially time-saving and slides-beautifying features. This is also for my own benefit, as I seem to always forget where to find the … Continue reading Alt Equals
Occupy ACM: We are the 99%
A typical computer science paper might represent the work of 2-4 authors over a year. Even though these authors don't spend 100% of that year working on the paper, just counting their salaries, benefits, etc.. we see that the total cost to produce a paper can still easily amount to several tens of thousands of … Continue reading Occupy ACM: We are the 99%
STOC deadline extended till Monday 5pm EST
Due to the effects of Hurricane Sandy, the deadline for STOC 2013 has been extended to Monday, November 5, 5pm EST, see http://stoc.cs.yale.edu/stoc2013/
Postdoc positions at MSR
This is the season for academic job searches, and if you are looking for a postdoc in theoretical Computer Science, we hope you consider applying for a position at Microsoft Research. The various MSR labs are looking for postdocs in many scientific fields, including all areas of theoretical Computer Science. You can apply for postdoc … Continue reading Postdoc positions at MSR
Truth vs Proof: The Unique Games Conjecture and Feige’s Hypothesis
Theoretical Computer Science is blessed (or cursed?) with many open problems. For some of these questions, such as the $latex {P}&fg=000000$ vs $latex {NP}&fg=000000$ problem, it seems like it could be decades or more before they reach resolution. So, if we have no proof either way, what do we assume about the answer? We could … Continue reading Truth vs Proof: The Unique Games Conjecture and Feige’s Hypothesis
Aleksander Madry and David Steurer win ACM honorable mention
Every year the ACM gives out an award for the best doctoral dissertation, as well as up to 3 honorable mentions. This year, both honorable mentions were given to CS theorists: Aleksander Madry and David Steurer (the dissertation award was given to Seth Cooper for his work on protein folding games). Both Aleksander's and David's … Continue reading Aleksander Madry and David Steurer win ACM honorable mention
Building the Swiss Army Knife
Guest post by Boaz Barak and Zvika Brakerski (part 2) In the previous post, we demonstrated the versatility of fully homomorphic encryption and its applicability for multiple applications. In this post we will demonstrate (not too painfully, we hope) how fully homomorphic encryption is constructed. Our goal is to present the simplest solution that (we … Continue reading Building the Swiss Army Knife
Windows On Theory 