[Update 5/20/14: Feel free to borrow or adapt any part of this text for future conferences. In retrospect, perhaps I should have given some more concrete guidance: in a typical TCS paper, by page 5 or 6 you should be done with the introduction, which means that you have already clearly stated your main result, explained why … Continue reading Advice for FOCS authors
Author: Boaz Barak
Structure vs. Combinatorics in Computational Complexity
(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
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
