How to write statements of purpose for graduate admission (slides). Presentation from talk in COLT virtual mentoring workshop
Work with what you’ve got, Nature Physics, January 21. (About experiments running the QAOA algorithm on near-term intermediate-scale noisy quantum devices (NISQ).
ML Theory with bad drawings - blog post.
How to use mathematical models for Covid-19 (in Hebrew) - with Shachar Artzi, Janni Yuval, Mor Nitzan, and Neta Ravid.
Puzzles of modern machine learning - blog post.
The different forms of quantum computing skepticsm - blog post.
The Complexity of Public-Key Cryptography - survey/tutorial on the computational assumptions landscape of cryptogrpahy. Written in honor of Oded Goldreich’s 60th birthday.
Men in Computer Science - blog post, August 2017.
Bayesianism, frequentism, and the planted clique, or do algorithms believe in unicorns?, April 2016. See also blog post on windows of theory blog and video of a talk at Northwestern.
The iPhones of Terrorists. Blog post on the Windows on Theory blog, March 2016.
Advice for the budding theorist, blog post on the Windows on Theory blog, November 2015
A different type of pseudo, blog post on the Windows on Theory blog, October 2015
Is computational hardness the rule or the exception?, blog post on Windows on Theory blog, September 2015
Tips for future FOCS/STOC program chairs, blog post on Windows on Theory blog, March 2015
Erdős’s Book and the Asymptotic Religion, blog post on Windows on Theory blog, January 2015
Sum-of-squares proofs and the quest toward optimal algorithms with David Steurer. Survey, also appeared in proceedings of ICM 2014. See also my seminar on this topic, as well as a video of a related talk at Harvard.
Structure vs Combinatorics in Computational Complexity, Windows on Theory blog, October 2013. See also adapted version in the bulletin of the European Association for Theoretical Computer Science.
Truth vs. Proof - the Unique Games Conjecture and Feige’s Hypothesis, Windows on Theory blog, July 2012`. See also adapted version in logic in computer science column of the bulletin of the European Association for Theoretical Computer Science.
Frequently Asked Questions on the paper Computational Complexity and Information Asymmetry in Financial Products by Arora, Barak, Brunnermeier, and Ge (ITCS 2010).
Barriers in Cryptography and Complexity Theory - PowerPoint Presentation, 2009.
Opening the Black-Box: New Techniques in Cryptography. My 2004 Princeton “job-talk” in Powerpoint XP format
Can We Obfuscate Programs? - What do the results of Barak et al (CRYPTO’ 01) mean? (Note that there have been many new developments in this area since this was written. In particular, I mentioned there that “there are several interesting concepts related to obfuscators, and for many of them we have more open questions than results.” - one of them - indistinguishable obfuscation - turned out to be both achievable and hugely important.)