Lightnews — Scholar-powered news

Lance Fortnow @lance.fortnow.com · 6h

Taking meditation lessons from René Descartes, why I don't believe that humans are just high-powered computers.

A few comments to last week's post Computers Don't Want suggested that human brains are just advanced computers, yet still possess agency a...

blog.computationalcomplexity.org

1

Reposted by Lance Fortnow

Simons Institute for the Theory of Computing @simonsinstitute.bsky.social · 2d

Congratulations to Thomas Rothvoss and Lang Liu, the inaugural winners of the Trevisan Prize at Bocconi University.

cs.unibocconi.eu/trevisan-pri...

Trevisan Prize 2025 – Winners

cs.unibocconi.eu

1 7 21

Lance Fortnow @lance.fortnow.com · 3d

Bill asks "If you use AI in your work do you brag about it or hide it?"

blog.computationalco...

My thought: If you would have acknowledged a human doing the same thing, you should acknowledge the AI.

If you use AI in your work do you brag about it or hide it?

You used AI in your work. Do you hide it or brag about it? 1) In 2002 there was a movie Simone about an actress who is really an AI. The...

blog.computationalcomplexity.org

Lance Fortnow @lance.fortnow.com · 5d

One of my kids told me that there are sides on the Internet, and that I'm on the wrong one.

1

Lance Fortnow @lance.fortnow.com · 7d

In their new book "If Anyone Builds It, Everyone Dies," Yudkowsky and Soares argue that we can view an Artificially Super Intelligent agent as though it has its own agency and desires. But computers are a different beast.

Computers Don't Want

I read through the new book If Anyone Builds It, Everyone Dies by Eliezer Yudkowsky and Nate Soares. "It" refers to Artificial Super Intell...

blog.computationalcomplexity.org

1

Lance Fortnow @lance.fortnow.com · 8d

Blog is back up!

1

Lance Fortnow @lance.fortnow.com · 8d

Looks like blog.computationalco... is down. Hope to get it back up soon.

1

Lance Fortnow @lance.fortnow.com · 9d

We went to a great new exhibit at the Chicago Field Museum about what happened after the asteroid hit that killed the dinosaurs.

www.fieldmuseum.org/...

Suppose you had the opportunity to go back in time to redirect that asteroid. Would you?

2

Lance Fortnow @lance.fortnow.com · 9d

Clyde Kruskal remembers the 100th anniversary of the birth of his father Martin in a guest post.

Clyde Kruskal talks about his Father Martin on Martin's 100th birthday

Martin Kruskal was born Sept 28, 1925 and passed away on Dec 26, 2006, at the age of 81 (we did two posts for his memorial, here and here...

blog.computationalcomplexity.org

2

Lance Fortnow @lance.fortnow.com · 12d

Because of zero-knowledge SNARKs that rely on our sumcheck protocol, Algebraic Methods for Interactive Proof Systems (1992) with Lund, Karloff and Nisan is now my most cited paper edging out NEXP = MIP (1991) with Babai and Lund.

Good to see the old paper getting some new love.

8

Lance Fortnow @lance.fortnow.com · 13d

15 years ago I predicted self-driving cars five years ago. Better late than never.

Self-Driving Cars

A few weeks ago I took an Uber to a regional airport and was picked up by a Tesla. The driver used FSD, so-called Full Self-Driving, never t...

blog.computationalcomplexity.org

1 1

Lance Fortnow @lance.fortnow.com · 14d

Whenever someone tells me "wait until you see what quantum and AI will do together", I'm reminded of this passage from the book Harry Potter and the Deathly Hallows.

9

Lance Fortnow @lance.fortnow.com · 16d

Bill talks about collecting research papers to be read later and how new technologies, like copy machines, have changed that process.

We can find more papers on the web than we used to. Are we reading them?

STUDENT: What did you do before the web to find papers? BILL: We went to the library and copied papers to read later. STUDENT: Did you rea...

blog.computationalcomplexity.org

1 5

Reposted by Lance Fortnow

FOCS 2025 @focs2025.bsky.social · 19d

⏰ The 🧑‍🎓 travel support application and 👶 childcare support applications are both due in ~25h!

The former is open to all students and postdocs (not necessarily authors of a paper). The latter provides financial support (to be used in any childcare-related way) to conference attendees!

Links below↴

1 6 5

Lance Fortnow @lance.fortnow.com · 20d

When I went to college in the early 80's, it was a faux pas to wear a backpack using both straps. Four decades later I still find myself slinging my backpack over one shoulder.

Four college students each wearing a backpack over one shoulder

2 5

Lance Fortnow @lance.fortnow.com · 21d

Sam Altman claimed that GPT-5 had "PhD-level" expertise. Before we can debate that point, what does it even mean?

What is "PhD-Level Intelligence"?

When announcing Open-AI's latest release last month, Sam Altman said "GPT-5 is the first time that it really feels like talking to an expert...

blog.computationalcomplexity.org

1

Lance Fortnow @lance.fortnow.com · 21d

Took my own advice and rewatched Sneakers. This line aged well.

There's a war out there, old friend. A world war. And it's not about who's got the most bullets. It's about who controls the information. What we see and hear, how we work, what we think. It's all about the information!

1 1

Lance Fortnow @lance.fortnow.com · 22d

Here's the answer to yesterday's question.

Q: Suppose we have a Turing machine with a stay-put option, δ:QxΓ→QxΓx{L,R,S}. Can you create an equivalent Turing machine with only L,R moves without enlarging Q or Γ ?

Answer in the picture. Formatted by AI.

See https://chatgpt.com/share/68c97b37-1b7c-800e-86ba-1278378c9534

1 3

Reposted by Lance Fortnow

Dr Buki Fatona @bukifatona.bsky.social · 22d

Happy Pythagorean Triple Square Day!

3² + 4² = 5² (9/16/25)

The next one is in one hundred years!

NPR @npr.org · 22d

Pythagorean Triple Square Day, as one man affectionately calls 9/16/25, is a day like no other this century.

On 9/16/25, celebrate a date of mathematical beauty

Pythagorean Triple Square Day, as one man affectionately calls 9/16/25, is a day like no other this century.

n.pr

23 48

Lance Fortnow @lance.fortnow.com · 22d

Want to remember Robert Redford - Sneakers, the 1992 movie where his character led a professional hacking team going after a device that will break any code. Better than it sounds.

3

Lance Fortnow @lance.fortnow.com · 23d

I gave a homework bonus question that even AI couldn't solve. Can you?

Suppose we have a Turing machine with a stay-put option, δ:QxΓ→QxΓx{L,R,S}. Can you create an equivalent Turing machine with only L,R moves without enlarging Q or Γ ?

3

Lance Fortnow @lance.fortnow.com · 23d

Bill needs to learn how to disconnect when he is away.

``I'm on vacation so I won't be checking email'' will sound funny soon. Maybe it already does.

"I'll be on vacation so I won't be checking email.'' "I can't be at the meeting since I will be out of town'' Technology has made it so tha...

blog.computationalcomplexity.org

Lance Fortnow @lance.fortnow.com · 27d

Bill asks what counts as counting. Not the probabilistic method.

blog.computationalco...

[Ed note: Not information theory or Kolmogorov complexity either]

Is the Prob Method `Just Counting'- I say no and HELL NO

(After I wrote this post Lance tweeted a pointer to a great talk by Ronald de Wolf with more examples, and also examples of quantum proofs, ...

blog.computationalcomplexity.org

3

Lance Fortnow @lance.fortnow.com · Sep 8

I thought tenure was the goal of my academic journey, but instead it was the catalyst for a life in constant transition.

A Restless Soul

When I first became a professor I had it all planned out, I would do research, teach and supervise students, get tenure and do more research...

blog.computationalcomplexity.org

1 6

Lance Fortnow @lance.fortnow.com · Sep 4

We got a message saying we had a new campus staff license to ChatGPT. I'm thinking finally the university has realized that AI is a thing.

But no--it was a phishing test from our tech support.

1 4