nixCraft đ§đ
i'll let you know when P != NP is proved (and when it's not)
| website | http://people.csail.mit.edu/rrw/ |
Ryan Williams
@rrwilliams
- 814 Followers
- 135 Following
- 80 Posts
professor of EECS at MIT, currently visiting IAS. working in theoretical computer science namely algorithm design, complexity theory, circuit complexity, etc.
i'll let you know when P != NP is proved (and when it's not)
i'll let you know when P != NP is proved (and when it's not)
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!
https://www.youtube.com/watch?v=ThLvLewiRnQ
https://www.youtube.com/watch?v=ThLvLewiRnQ
Simulating Time With Square-Root Space (And With Details) - Ryan Williams
Martin EscardoMathematical notions of existence.
1. Explicit existence: we have one, and here it is for you to see.
2. Truncated or anonymous existence: we have one, it doesn't matter what it is, and we won't tell you what it is, not because we are mean, but because we want to emphasize that we don't care which one is chosen.
3. Classical existence. It is impossible that it doesn't exist. We won't tell you what it is, not because we are mean, but because we have no clue.
1/
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. https://www.computationalcomplexity.org/travelAllowance/travelAllowance2025.php
Lance FortnowThe 2025 Gödel Prize is given to Eshan Chattopadhyay and David Zuckerman, âExplicit two-source extractors and resilient functionsâ.
Paper: https://doi.org/10.4007/annals.2019.189.3.1
Favorite Theorems Blog Post: https://blog.computationalcomplexity.org/2024/07/favorite-theorems-extracting-ramsey.html
Peter GleickThis is just a partial glimpse of the destruction of American science by Trump and the GOP.
STOC Theory Fest in Prague June 23-27.
Registration now open. Early deadline is May 6.
https://acm-stoc.org/stoc2025/registration.html
You can apply for student support. Deadline April 27.
https://acm-stoc.org/stoc2025/travel-support.html
New paper: Simulating Time With Square-Root Space
https://people.csail.mit.edu/rrw/time-vs-space.pdf
It's still hard for me to believe it myself, but I seem to have shown that TIME[t] is contained in SPACE[sqrt{t log t}].
To appear in STOC. Comments are very welcome!
0xDEThe lists of accepted papers are now public from the 2025 Symposium on Theory of Computing, STOC (https://acm-stoc.org/stoc2025/accepted-papers.html), to be held late June in Prague (https://acm-stoc.org/stoc2025/) and from the 2025 Symposium on Computational Geometry, SoCG (https://docs.google.com/document/d/1CNcyz56XkgsYcDpAdDF0lDtugKofPFT4/edit), to be held late June in Kanazawa (https://socg25.github.io/socg.html). My integer distance paper (https://arxiv.org/abs/2401.06328) got into SoCG, so that's where I'm heading.