Lightnews — Scholar-powered news

Ryan Williams @rrwilliams.bsky.social · 16d

They are doing some construction on the blackboards in the usual classroom, this was the backup

Ryan Williams @rrwilliams.bsky.social · 16d

Today at IAS, I gave a 2 hr 15 mins lecture on why TIME[t] is in SPACE[√(t log t)]. You can watch it here!
www.youtube.com/watch?v=ThLv...

Simulating Time With Square-Root Space (And With Details) - Ryan Williams

YouTube video by Institute for Advanced Study

www.youtube.com

1 7 37

Ryan Williams @rrwilliams.bsky.social · Aug 25

A related anecdote: as a PhD student, I was assigned to be a teaching assistant for my advisor's cryptography course. When I asked Manuel how I should prepare for this, he replied:

"Read every paper that Adi Shamir has written."

I tried to follow this advice. At least I read the abstracts :)

Marek @marek.onl · Mar 26

Adi Shamir's advice to young researchers:

1. Read, read, read. Back in the eighties, I read every cryptography paper out there. Once that became impossible, I read the abstract of every paper. Now I read at least every title.

20

Ryan Williams @rrwilliams.bsky.social · Aug 25

Nowadays, I think that slightly biasing your reading priority towards the top conferences/venues in your area makes sense. But I still believe that attempting to read every abstract in your area is good advice.

2

Reposted by Ryan Williams

Marek @marek.onl · Mar 26

Adi Shamir's advice to young researchers:

1. Read, read, read. Back in the eighties, I read every cryptography paper out there. Once that became impossible, I read the abstract of every paper. Now I read at least every title.

2 4 16

Ryan Williams @rrwilliams.bsky.social · Aug 17

Is it Bobby Fischer Teaches Chess?
en.m.wikipedia.org/wiki/Bobby_F...
As a kid, I thought that was such a fun book.

Bobby Fischer Teaches Chess - Wikipedia

en.m.wikipedia.org

4

Reposted by Ryan Williams

FOCS 2025 @focs2025.bsky.social · Aug 8

💡 For students, the yearly IEEE (or ACM) membership costs less than USD 20. And leads to a #FOCS2025 registration fee reduced by USD 80...

1 4 3

Reposted by Ryan Williams

Suresh Venkatasubramanian @geomblog.bsky.social · Aug 6

This is very impressive. Breaking the sorting barrier for directed single source shortest paths
search.app/wnEUo

New Method Is the Fastest Way To Find the Best Routes | Quanta Magazine

A canonical problem in computer science is to find the shortest route to every point in a network. A new approach beats the classic algorithm taught in textbooks.

search.app

1 5 20

Ryan Williams @rrwilliams.bsky.social · Aug 5

It's fun to publish something 20 years ago which refutes a recently published proof of P ≠ NP

Lance Fortnow @lance.fortnow.com · Aug 4

Springer publishes a P ≠ NP "proof" and Eric Allender has words to say.

blog.computationalco...

Some thoughts on journals, refereeing, and the P vs NP problem

A guest post by Eric Allender prompted by an (incorrect) P ≠ NP proof recently published in Springer Nature's Frontiers of Computer Scie...

blog.computationalcomplexity.org

1 5 53

Reposted by Ryan Williams

Lance Fortnow @lance.fortnow.com · Aug 4

Springer publishes a P ≠ NP "proof" and Eric Allender has words to say.

blog.computationalco...

Some thoughts on journals, refereeing, and the P vs NP problem

A guest post by Eric Allender prompted by an (incorrect) P ≠ NP proof recently published in Springer Nature's Frontiers of Computer Scie...

blog.computationalcomplexity.org

2 15 43

Reposted by Ryan Williams

Tom Gur @tomgur.bsky.social · Jul 19

Hirahara, Illango, and Loff posted on the arXiv a lovely result, showing that determining the communication complexity of a function f is NP-hard. A fundamental question first asked by Yao in '79. The proof is very clean and elegant. A fun read for the weekend!

arxiv.org/pdf/2507.104...

arxiv.org

3 30

Ryan Williams @rrwilliams.bsky.social · Jun 26

There is session 9C... But yeah not a lot of papers

1 2

Reposted by Ryan Williams

Ryan O'Donnell @booleananalysis.bsky.social · Jun 9

Spread the word: there is a new prize in Theoretical Computer Science in honor of Luca Trevisan--

cs.unibocconi.eu/call-nominat...

(Intent-to-nominate letters due by July 31.)

cs.unibocconi.eu

1 18 46

Ryan Williams @rrwilliams.bsky.social · Jun 11

CCC’25 will take place August 5-8 at the Fields Institute in Toronto! Students/postdocs (from any institution) are eligible to apply for a travel allowance. For full consideration, please apply by June 20; awards to be announced on June 25. www.computationalcomplexity.org/travelAllowa...

Computational Complexity Conference

www.computationalcomplexity.org

4

Reposted by Ryan Williams

Lance Fortnow @lance.fortnow.com · Jun 7

The 2025 Gödel Prize is given to Eshan Chattopadhyay and David Zuckerman, “Explicit two-source extractors and resilient functions”.

Paper: doi.org/10.4007/anna...

Favorite Theorems Blog Post: blog.computationalco...

8 34

Ryan Williams @rrwilliams.bsky.social · May 4

Yeah GP and I were arguing over this 😂 Eventually he believed my side, and proved it true by induction. We wanted to check what ChatGPT thought...

Ryan Williams @rrwilliams.bsky.social · May 4

ChatGPT 4o thinks 27 < 10

1 12

Reposted by Ryan Williams

Michael Nielsen @michaelnielsen.bsky.social · Apr 25

One strange thing about writing is that the harder you work, the easier many people think it was to do

3 2 50

Reposted by Ryan Williams

TCS+ @tcsplus.bsky.social · Apr 23

The link for Ryan Williams' talk (@rrwilliams.bsky.social) is now available on our website.

See you tomorrow, 1pm ET! www.tcsplus.org/welcome/next...

2 6

Reposted by Ryan Williams

TCS+ @tcsplus.bsky.social · Apr 21

Ryan's talk is this Wednesday!

forms.gle/fZa3ATXC7n14...

4 8

Ryan Williams @rrwilliams.bsky.social · Apr 11

If you take a photo of your whiteboard with the camscanner app, it will also do this

1

Reposted by Ryan Williams

Josh Alman @jalman.bsky.social · Mar 23

NY Theory Day is returning on Friday April 11 at Columbia! It's free to attend but you have to register on the website by April 4. We have a great speaker lineup:

Rachel Cummings (Columbia)
Bill Kuszmaul (CMU)
Nick Spooner (Cornell)
Ryan Williams (MIT)

sites.google.com/view/nyctheo...

4 15

Ryan Williams @rrwilliams.bsky.social · Apr 2

Cool. Just taught Rice's theorem yesterday!

1

Ryan Williams @rrwilliams.bsky.social · Apr 1

I can say for sure that this result has totally broken my intuition about what are "reasonable" time-space tradeoff lower bounds that we can assume for time-bounded computation!

2

Ryan Williams @rrwilliams.bsky.social · Mar 6

👀 ...

1