## Shorties!

(1) Since I didn’t blog about this before: huge congratulations to David Deutsch, Charles Bennett, Gilles Brassard, and my former MIT colleague Peter Shor, and separately to Dan Spielman, for their well-deserved Breakthrough Prizes! Their contributions are all so epochal, so universally known to all of us in quantum information and theoretical computer science, that there’s little I can write to gild the lily, except to say how much I’ve learned by interacting with all five of them personally. I did enjoy this comment on the Breakthrough Prizes by someone on Twitter: “As long as that loudmouth Scott Aaronson keeps getting ignored, I’ll be happy.”

(2) My former UT colleague Ila Fiete brought to my attention an important scientists’ petition to the White House. The context is that the Biden administration has announced new rules requiring federally-funded research papers to be freely available to the public without delay. This is extremely welcome—in fact, I’ve advocated such a step since I first became aware of the scourge of predatory journals around 2004. But the looming danger is that publishers will just respond by leaning more heavily on the “author pays” model—i.e., hitting up authors or their institutions for thousands of dollars in page fees—and we’ll go from only the credentialed few being able to read papers that aren’t on preprint archives or the like, to only the credentialed few being able to publish them. The petition urges the White House to build, or fund the research community to build, an infrastructure that will make scientific publishing truly open to everyone. I’ve signed it, and I hope you’ll consider signing too.

(3) Bill Gasarch asked me to announce that he, my former MIT colleague Erik Demaine, and Mohammad Hajiaghayi have written a brand-new book entitled Computational Intractability: A Guide to Algorithmic Lower Bounds, and a free draft is available online. It looks excellent, like a Garey & Johnson for the 21st century. Bill and his coauthors are looking for feedback. I was happy to help them by advertising this—after all, it’s not as if Bill’s got his own complexity blog for such things!

(4) Back when Google was still a novelty—maybe 2000 or so—I had my best friend, the now-famous computer security researcher Alex Halderman, over for Rosh Hashanah dinner with my family. Alex and I were talking about how Google evaded the limitations of all the previous decades’ worth of information retrieval systems. One of my relatives, however, misheard “Google” as “kugel” (basically a dense block of noodles held together with egg), and so ended up passing the latter to Alex. “What is this?” Alex asked. Whereupon my uncle deadpanned, “it’s a noodle retrieval system.” Since then, every single Rosh Hashanah dinner, I think about querying the kugel to retrieve the noodles within, and how the desired search result is just the trivial “all of them.”

### 23 Responses to “Shorties!”

1. I Says:

How’s the work on alignment coming along Scott? Got any interesting research directions? Have you found any core difficulties to the problem? It would be interesting to see your version of “a list of lethalities”, or something like Paul’s response to Eliezer.

Also, people have been doing some horrific things to the kugel recipe based off Google image search results. And kugel didn’t look appetizing to begin with.

2. matt Says:

Am I missing something? There already is an infrastructure that makes all research openly accessible to everyone. In case you are having trouble finding it, the URL is http://arxiv.org. About 20 years ago, some physics journals refused to allow people to publish on the arxiv. The physics community basically just ignored these requirements, scofflaw style, until the journals gave up. If people can’t find someone’s research freely available, that’s the author’s fault, or perhaps the community’s fault in some fields (i.e., if a junior author is afraid to publish on arxiv for fear of offending some journal and hurting their career, it is up to the senior people to scoff at this and publish everything on arxiv). Some older, pre-1995 papers are harder to find, true, but current legislation won’t change that.

3. Rainer Says:

The online book looks very interesting. But the “draft” watermark drives me crazy. Could you please ask your former colleague to remove it?

4. Scott Says:

I #1: I’ll post an alignment update soon! Lots to talk about!

Noodle kugel is basically a carbohydrate bomb, but is absolutely delicious (or at least my mom’s is).

5. Scott Says:

matt #2: What you’re missing, I think, is that biology, medicine, and other hugely important fields have lagged ~25 years behind physics, math, and CS in putting everything on preprint servers (although COVID appears to have given a big boost to the bioRxiv). If done well, the new policy on federally funded research could provide just the right kick-in-the-pants to make the obviously correct thing happen.

6. Scott Says:

Rainer #3: They obviously put it there because they were afraid of the draft being confused for their eventual final product. But feel free to make a case to them directly!

7. Jon Awbrey Says:

Happy ䷪ Everybody !!!

8. matt Says:

Scott #5: yeah, I know that, and that’s exactly what I meant by it being the responsibility of the senior people in the field. Tenured people in the fields you mention should place all their works in a public repository, either scoffing at journals that refuse to allow it or simply not publishing in those journals, and they should warn any incoming junior members of their group that the group policy is everything is going in a public repository. Stuff would change without government intervention. Journals in other fields tried to stop it and failed. Minor anecdote on how journals really just accept things: I had a paper in a Springer math journal; in between our first version and acceptance they adopted a very draconian publishing agreement that said no arxiv updates in response to referee remarks would be allowed (our first version was already on arxiv). I told them “oh, sorry, just updated the arxiv before I read the agreement; do you still want to accept the paper? btw, the arxiv version includes 1 additional sentence change beyond the accepted version”. They replied “ok, that counts as a different version, it is fine.”

9. SR Says:

This is the second time I’ve heard of kugel, the first being a scene from ‘The Big Bang Theory’:

Raj Koothrappali: Okay, so we’ve got 3 briskets, 4 meat loafs, one lasagna…
Howard Wolowitz: No, that’s noodle kugel.
Raj Koothrappali: One Jewish lasagna…

Given the science focus of the show, I feel like your uncle’s joke would have been an even better fit for this scene. 🙂

10. Helen Suzman Says:

Scott, do you know what kugel means in South African?

11. Scott Says:

Helen Suzman #10: No, but I just googled it. It means “Jewish American Princess,” except South African?

12. Anonymous Says:

Scott, I’m a CS grad student and I could really use your help with a situation I landed myself in (not comfortable revealing identity yet). Anything you can do for me would be appreciated.

Mike

13. Scott Says:

14. True Feminist Says:

Scott, could you please post something about the situation of women’s rights in Iran right now? University students are being attacked in their dorms by police for standing up for women’s freedom. You’ve already posted donation drives for western feminist causes, so it only seems fair you would do something to help the Iranian protesters as well.

15. Helen Suzman Says:

Scott #11: Yeah, that’s right. Have an easy and/or meaningful fast.

16. fred Says:

Congrats to Alain Aspect (and co) for winning the Nobel for the work on measuring the Bell violation.
I remember reading a book about it (can’t find the reference), that working on this was considered career suicide at the time.

17. Scott Says:

True Feminist #14: I hope you like today’s post, which I’d already started writing when I saw your comment! Do you have any organization to which you’d recommend donating?

18. asdf Says:

The book by Demaine and Hajiaghayi looks nice, but it says almost nothing about quantum complexity classes or algorithms. Just a brief mention related to Shor’s factoring algorithm, more or less.

19. Scott Says:

asdf #18: This might surprise people, but I’m OK with there being books in the world that are not about quantum complexity theory! 😀

20. asdf Says:

Scott #19, I don’t expect the whole book to be about QC, but it’s an omnibus book describing a lot of complexity classes, so it’s odd that BQP is barely mentioned. Maybe they will add something later.

21. T Says:

Hey Scott,

Dan Spielman once wrote a paper on quantum random walks on graphs with Andrew Childs. Just wondering about your thoughts on that work and if there any current interesting directions related to that.

Spielman himself, seems to have made lots of contributions to network problems on graphs. Just wondering if there are any quantum analogues of these.

Best,
T

22. Scott Says:

T #21: Spielman has tons of great work, mostly in classical algorithms and complexity but a bit in quantum too, and has been rightly celebrated for it.

(When you ask a question at such a high level of generality, expect a general answer! 🙂 )

23. T Says:

Scott #22: No worries, my question was a lazy one. I think you actually address the work I was referring to in section 6 your recent writing “How Much Structure Is Needed for Huge Quantum Speedups?”

You can use rich HTML in comments! You can also use basic TeX, by enclosing it within  for displayed equations or  for inline equations.

Comment Policies:

1. All comments are placed in moderation and reviewed prior to appearing.
2. You'll also be sent a verification email to the email address you provided.
YOU MUST CLICK THE LINK IN YOUR VERIFICATION EMAIL BEFORE YOUR COMMENT CAN APPEAR. WHY IS THIS BOLD, UNDERLINED, ALL-CAPS, AND IN RED? BECAUSE PEOPLE ARE STILL FORGETTING TO DO IT.
3. Comments can be left in moderation for any reason, but in particular, for ad-hominem attacks, hatred of groups of people, snide and patronizing tone, trollishness, disingenuousness, or presumptuousness (e.g., linking to a long paper or article and challenging me to respond to it).
4. Even when no individual comment violates policy, when there are dozens of comments from a single commenter hammering home the same few themes, and the commenter shows no interest in changing their views or learning from anyone else, the commenter will receive a warning followed by a 3-month ban.
5. Whenever I'm in doubt, I'll forward comments to Shtetl-Optimized Committee of Guardians, and respect SOCG's judgments on whether those comments should appear.
6. I sometimes accidentally miss perfectly reasonable comments in the moderation queue, or they get caught in the spam filter. If you feel this may have been the case with your comment, shoot me an email.