Blog Profile / Shtetl-Optimized

Filed Under:Academics / Physics
Posts on Regator:174
Posts / Week:0.5
Archived Since:December 19, 2008

Blog Post Archive

“Is There Something Mysterious About Math?”

When it rains, it pours: after not blogging for a month, I now have a second thing to blog about in as many days.  Aeon, an online magazine, asked me to write a short essay responding to the question above, so I did.  My essay is here.  Spoiler alert: my thesis is that yes, there’s […]

Two papers

Just to get myself back into the habit of blogging: For those of you who don’t read Lance’s and Bill’s blog, there was a pretty significant breakthrough in complexity theory announced last week.  (And yes, I’m now spending one of the two or so uses of the word “breakthrough” that I allow myself per year.) […]

The ultimate physical limits of privacy

Somewhat along the lines of my last post, the other day a reader sent me an amusing list of questions about privacy and fundamental physics.  The questions, and my answers, are below. 1. Does the universe provide us with a minimum level of information security? I’m not sure what the question means. Yes, there are […]

The flow of emails within the block inbox

As a diversion from the important topics of shaming, anti-shaming, and anti-anti-shaming, I thought I’d share a little email exchange (with my interlocutor’s kind permission), which gives a good example of what I find myself doing all day...Show More Summary

How can we fight online shaming campaigns?

Longtime friend and colleague Boaz Barak sent me a fascinating New York Times Magazine article that profiles people who lost their jobs or otherwise had their lives ruined, because of a single remark that then got amplified a trillionfold in importance by social media.  (The author, Jon Ronson, also has a forthcoming book on the topic.)  The article opens with Justine […]

“The Man Who Tried to Redeem the World with Logic”

No, I’m not talking about me! Check out an amazing Nautilus article of that title by Amanda Gefter, a fine science writer of my acquaintance.  The article tells the story of Walter Pitts, who [spoiler alert] grew up on the mean streets of Prohibition-era Detroit, discovered Russell and Whitehead’s Principia Mathematica in the library at age 12 while hiding […]


(in which I bring this blog back to the “safe, uncontroversial” territory of arguing with people who think they can solve NP-complete problems) A few people have asked my opinion about “memcomputing”: a computing paradigm that’s being advertised, by its developers, as a way to solve NP-complete problems in polynomial time. Show More Summary

Quantum Machine Learning Algorithms: Read the Fine Print

So, I’ve written a 4-page essay of that title, which examines the recent spate of quantum algorithms for clustering, classification, support vector machines, and other “Big Data” problems that grew out of a 2008 breakthrough on solving...Show More Summary

Happy Second Birthday Lily

Two years ago, I blogged when Lily was born.  Today I can blog that she runs, climbs, swims (sort of), constructs 3-word sentences, demands cake and cookies, counts to 10 in both English and Hebrew, and recognizes colors, letters, shapes, animals, friends, relatives, the sun, and the moon.  To all external appearances she’s now conscious as you and I […]

BQP/LHC collision

This afternoon, I gave my usual spiel about Quantum Computing and the Limits of the Efficiently Computable at the CERN Colloquium.  Beforehand, Dana and I got to join a tour of the CMS detector at the Large Hadron Collider—one of the very last tours, before CMS shuts down (as ATLAS already has) to get ready for collisions at the LHC’s new, […]

Quantum computing news items (by reader request)

Within the last month, there was a major milestone in the quest to build a scalable quantum computer, and also a major milestone in the quest to figure out what you would do with a quantum computer if you had one.  As I’ve admitted many times, neither of those two quests is really the reason […]

What I believe

Two weeks ago, prompted by a commenter named Amy, I wrote by far the most personal thing I’ve ever made public—what’s now being referred to in some places as just “comment 171.”  My thinking was: I’m giving up a privacy that I won’t regain for as long as I live, opening myself to ridicule, doing the blog equivalent of a queen-and-two-rook sacrifice. […]

Quantum Complexity Theory Student Project Showcase 3

Merry Christmas (belatedly)!  This year Quanta Claus has brought us eight fascinating final project reports from students in my 6.845 Quantum Complexity Theory class, covering everything from interactive proofs to query and communication complexity to quantum algorithms to quantum gates (and one project even includes a web-based demo you can try!). Show More Summary

The Turing movie

Last week I finally saw The Imitation Game, the movie with Benedict Cumberbatch as Alan Turing. OK, so for those who haven’t yet seen it: should you?  Here’s my one paragraph summary: imagine that you told the story of Alan Turing—one greatest triumphs and tragedies of human history, needing no embellishment whatsoever—to someone who only sort-of understood it, and […]

Walter Lewin

Yesterday I heard the sad news that Prof. Walter Lewin, age 78—perhaps the most celebrated physics teacher in MIT’s history—has been stripped of his emeritus status and barred from campus, and all of his physics lectures removed from OpenCourseWare, because an internal investigation found that he had been sexually harassing students online.  I don’t anything […]

PostBQP Postscripts: A Confession of Mathematical Errors

tl;dr: This post reveals two errors in one of my most-cited papers, and also explains how to fix them.  Thanks to Piotr Achtinger, Michael Cohen, Greg Kuperberg, Ciaran Lee, Ryan O’Donnell, Julian Rosen, Will Sawin, Cem Say, and others for their contributions to this post. If you look at my Wikipedia page, apparently one of […]

Lens of Computation on the Sciences

This weekend, the Institute for Advanced Study in Princeton hosted a workshop on the “Lens of Computation in the Sciences,” which was organized by Avi Wigderson, and was meant to showcase theoretical computer science’s imperialistic ambitions to transform every other field.  I was proud to speak at the workshop, representing CS theory’s designs on physics.  But videos […]

Kuperberg’s parable

Recently, longtime friend-of-the-blog Greg Kuperberg wrote a Facebook post that, with Greg’s kind permission, I’m sharing here. A parable about pseudo-skepticism in response to climate science, and science in general. Doctor: You ought to stop smoking, among other reasons because smoking causes lung cancer. Patient: Are you sure? I like to smoke. It also creates jobs. […]

What does the NSA think of academic cryptographers? Recently-declassified document provides clues

Brighten Godfrey was one of my officemates when we were grad students at Berkeley.  He’s now a highly-successful computer networking professor at the University of Illinois Urbana-Champaign, where he studies the wonderful question of how we could get the latency of the Internet down to the physical limit imposed by the finiteness of the speed of light.  (Right now, […]

Der Quantencomputer

Those of you who read German (I don’t) might enjoy a joint interview of me and Seth Lloyd about quantum computing, which was conducted in Seth’s office by the journalist Christian Meier, and published in the Swiss newspaper Neue Zürcher Zeitung.  Even if you don’t read German, you can just feed the interview into Google Translate, […]

Copyright © 2015 Regator, LLC