English
Ryan Williams @rrwilliams.bsky.social
Report

Ryan Williams @rrwilliams.bsky.social

@rrwilliams

Professor @MITEECS and @MIT_CSAIL. Complexity, algorithms, and related math. I'll let you know when P != NP (and when it's not)

502 Following14.6K Followers2.2K Posts
  1. Ryan Williams @rrwilliams.bsky.social@rrwilliams
    A number of people (grad students in particular) said they enjoyed my talk at ICALP. So maybe you'll like it too. A little unusual, it's about how/why I ended up working on circuit complexity. (Skipping the ceremonial stuff that happened before the talk)
    22217096.5K
  2. Ryan Williams @rrwilliams.bsky.social@rrwilliams
    I'll try. ETH claims 3SAT cannot be solved in 1.000... 01^n time for some number of zeroes. They claim ETH is false, giving an algorithm that is "sub-exponential" time for 3SAT. That would be surprisingly faster than brute force, the 2^n time.
    Sughu @sughanthans1
    @rrwilliams thanks for the post ryan. i know you might be under immense work load but could you explain to someone who is reasonably intelligent but have not researched this field - what are the implications of these findings?
    162445353.6K
  3. Sughu✓@sughanthans1
    Posts @rrwilliams
    @rrwilliams thanks for the post ryan. i know you might be under immense work load but could you explain to someone who is reasonably intelligent but have not researched this field - what are the implications of these findings?
    503668.9K
  4. Ryan Williams @rrwilliams.bsky.social@rrwilliams
    Posts @rrwilliams
    If true, their claim implies a variety of other NP problems now all have faster algorithms as well. Since 3SAT is NP complete, this should make every computer scientist put at least a little more weight on the possibility of P = NP.
    53126920.7K
  5. Ryan Williams @rrwilliams.bsky.social@rrwilliams
    Posts @rrwilliams
    In fact, one of the first things I wanted OpenAI to check is that no existing cryptosystems are compromised by the result. Apparently they are safe...
    141325546.8K
  6. Ryan Williams @rrwilliams.bsky.social@rrwilliams
    Here's a direct link to OpenAI's PDF claiming a refutation of ETH. In particular, it's claimed that 3SAT on n variables is in about exp(n/(log n)^{1/2+o(1)}) time
    843092.1K864K
  7. Ryan Williams @rrwilliams.bsky.social@rrwilliams
    Posts @rrwilliams
    Our letter to the community invites ideas for organizing this effort and, separately, for addressing the broader questions raised by AI-generated results: OpenAI's announcement is here:
    18411.1K329K
  8. Ryan Williams @rrwilliams.bsky.social@rrwilliams
    An internal model at OpenAI has produced a claimed refutation of ETH! Russell Impagliazzo, Mohan Paturi, and I have been asked to help organize an open and independent examination of this claim. 1/4
    2877277K3.5M
  9. Ryan Williams @rrwilliams.bsky.social@rrwilliams
    Posts @rrwilliams
    We've signed no NDAs and will receive no compensation, so we are free to share our ongoing findings with the community, which we intend to do throughout the process. We've asked OpenAI to publicly release ASAP all their raw data regarding ETH, including PDFs and Lean source. 2/4
    4331.5K274K
  10. Ryan Williams @rrwilliams.bsky.social@rrwilliams
    Posts @rrwilliams
    We have also asked OpenAI to commit to sponsoring a conference for the benefit of the entire community affected by this work. They agreed to both. 3/4
    6241.2K270K
  11. Ryan Williams @rrwilliams.bsky.social@rrwilliams
    Funny, I've been calling it the mathslopcalypse. To each their own. Can anyone honestly say they found a paper among the hundreds in the release that's *not* a huge pain to read (without AI assistance)?
    161922217.9K
  12. Ryan Williams @rrwilliams.bsky.social@rrwilliams
    Posts @rrwilliams
    It's beyond amazing to see so many big problems solved in some form, but this feels like a DDOS attack on mathematicians. Sure, I can iterate Astra/Opus to simplify proofs and get all the notation properly defined, but why? Never had to before; we would just reject the paper.
    1071439.1K
  13. Ryan Williams @rrwilliams.bsky.social@rrwilliams
    For what it's worth, OpenAI's one-tape TM simulation (assuming correct) immediately implies RAM time t is in SPACE[t^{4/5}] Not sure why they didn't mention this corollary! That was the whole point of my question.
    123835433.1K
  14. Ryan Williams @rrwilliams.bsky.social@rrwilliams
    Yeah, page 63 of the paper should have been page 2 or 3
    Gautam Kamath @thegautamkamath
    A very interesting result, and a very interesting release scheme.
    2811814.7K
  15. Gautam Kamath@thegautamkamath
    A very interesting result, and a very interesting release scheme.
    Download
    32118778.8K
  16. Ryan Williams @rrwilliams.bsky.social@rrwilliams
    The Alon-Yuster-Zwick color coding trick can be used to get 2^{O(sqrt(n))} size depth-3 AC circuits for every symmetric Boolean function!! Just the latest exhibit that "circuit lower bounds are hard to prove because they are false"
    52818117.2K
  17. Ryan Williams @rrwilliams.bsky.social@rrwilliams
    Posts @rrwilliams
    I've used the AYZ trick in so many papers, even tried to use it to get this circuit bound about two years ago (a simpler version of the trick lets you compute "At-Least-k" with e^k*poly(n) size depth 3 circuits), but I gave up too quickly. Wow.
    01183.8K
  18. Ryan Williams @rrwilliams.bsky.social@rrwilliams
    PSA: If you put your name on a paper claiming a breakthrough, you damn well better write a paper that other people can read. Otherwise, you will likely not get the kind of attention you seek. (Advice I've always given to my PhD students. Applies regardless of AI usage.)
    62933917.5K
  19. Ryan Williams @rrwilliams.bsky.social@rrwilliams
    I agree, P/NP seems unlikely to be resolved soon. There's been essentially zero direct progress on P!=NP, so there's not much for an advanced model (or 10k parallel advanced models) to work with unless P=NP. But I could see L/NP, BPP/NEXP, P/PSPACE, etc falling not long from now
    Lance Fortnow @fortnow
    While P vs NP will remain out of the reach of AI, there are other complexity problems, like separating NP from L (log space) or BPP from NEXP, that might be more tractable and would still make an incredible splash.
    154739951.6K
  20. Lance Fortnow@fortnow
    While P vs NP will remain out of the reach of AI, there are other complexity problems, like separating NP from L (log space) or BPP from NEXP, that might be more tractable and would still make an incredible splash.
    121623562.7K
  22. Ryan Williams @rrwilliams.bsky.social@rrwilliams
    Nice😎
    Download
    Lance Fortnow @fortnow
    Isik Ulusan, a U Mass student, created Complexle, like Wordle but you guess complexity classes. For each guess you get hints (set-theoretic inclusion, the type of model it is defined on, uniformity, etc.) for a total of 6 guesses. Give it a try.
    115910.1K
  23. Lance Fortnow@fortnow
    Isik Ulusan, a U Mass student, created Complexle, like Wordle but you guess complexity classes. For each guess you get hints (set-theoretic inclusion, the type of model it is defined on, uniformity, etc.) for a total of 6 guesses. Give it a try.
    52311120.7K
  24. Ryan Williams @rrwilliams.bsky.social@rrwilliams
    Wow x2!
    Data Structures and Algorithms Papers @AlgorithmPapers
    Breaking the 2ⁿ barrier for graph k-coloring Kevin Pratt [𝚌𝚜.𝙳𝚂]
    22579.5K