In December I participated in the wonderful "PCP Fest" workshop in Tel Aviv. The videos from these workshops are now online on their youtube channel. The channel contains not just videos of talks but also two wide ranging interviews of Alon Rosen with Avi Wigderson and Christos Papadimitriou, as well as a discussion between them. … Continue reading PCP Fest videos

(As you're working on your FOCS papers, an announcement about STOC 2019 from Eric Allender --Boaz) STOC registration is now open acm-stoc.org/stoc2019/. The deadline to apply for travel grants is April 22 . Apply on acm-stoc.org/stoc2019/travel-support.html There is also travel support available via TCS Women (deadline April 25), see sigact.org/tcswomen/

The website for the FOCS 2019 conference is http://focs2019.cs.jhu.edu/ , and the submission server is https://focs19.cs.utexas.edu/ The deadline is 3:00pm PDT, April 5, 2019. The reason I am posting this is that there is a fake FOCS website that ranks first or second on searches for "FOCS 2019". The website is under the domain "aconf … Continue reading FOCS 2019 Real website and submission server

In the Fall, Boaz and I co-taught a grad seminar on physics and computation (see here for some of the original press coverage). We were lucky to attract an intrepid group of students from multiple fields, with representatives from computer science, physics, math and biology. As part of the course, we asked our students to … Continue reading Physics & Computation Blog Post Round-up

[Guest post by Aleksander Mądry] To me, one of the best things about working in theoretical computer science has always the exciting rate of progress we make as a community. On (what appears to be) a regular basis, we produce breakthroughs on problems that are absolutely fundamental to our field. Problems that often look impossible to tackle, right … Continue reading Nominate TCS papers for research highlights

If, like others following the pace of modern life, you're the kind of person that needs to get just on time updates on the state of theoretical computer science, consider signing up for the newsletter of CATCS. You can get information about funding opportunities, advocacy efforts, and more. Sure, at the hectic rate of two … Continue reading News addicts: Sign up for the CATCS newsletter

[Posted at the request of Craig Gentry. I think this is actually a great idea that should be imitated by other sub-areas of TCS as well. --Boaz] Update: The Conference for Failed Approaches and Insightful Losses in cryptology is celebrating our first failure early: the failure to keep a deadline! We are extending the submission … Continue reading Submit your failures to CFAIL 2019

Guest post by Chi-Ning Chou and Parth Mehta from the physics and computation seminar. Abstract The firewall paradox (introduced here) is a bewitching thought experiment that mandates a deeper understanding of our reality. As luck would have it, QFT predictions seem sound, GR calculations appear valid, and semi-classical approximations look reasonable: no one is willing … Continue reading Black Holes, a Complexity Theory perspective

There's a lot of discussion and (possibly well-deserved) hype nowadays about quantum computation and its potential for computation at speeds we simply can't reach with the classical computers we're used to today. The excitement about this has been building for years, even decades, but it's only very recently that we've really been approaching a solid … Continue reading Quantum circuits and their role in demonstrating quantum supremacy

This is the season that people are applying for postdoc positions. Unlike student and faculty hiring, which each have a fairly fixed schedule, postdoc availability can change from time to time, with new opportunities opening up all the time. So, I encourage everyone looking for a postdoc position to periodically check out https://cstheory-jobs.org/ . (For … Continue reading Looking a postdoc opportunity?