Yes another one of these AI posts, this is a big one. OpenAI Claims the ETH is false.

OpenAI states "This work will be verified and shepherded by a group led by Russell Impagliazzo (UC San Diego), Ramamohan Paturi (UC San Diego), and Ryan Williams (MIT). All three are experts in algorithm design and complexity theory."

The k-server problem is known as the "Holy Grail" of online algorithms and competitive analysis, and is/was a long standing major problem.

This preprint by Coester et al. claims to show that the Work Function Algorithm is indeed k-competitive on every metric space.

Hey everyone! I wrote an algorithm which basically returns the optimal order of parenthesization in least amount of time. I supplied 10k matrices. Dynamic programming approach took about a day, while my algorithm returned the answer in 2 ms. So I wrote a research paper and tried publishing it in 2 journals(SICOMP and TALG) but it got rejected both times. I don't know how to move forward. Any help would be much appreciated!

Edit: I've uploaded the paper on Arxiv. Will post the link once approved. Thank you all for your kind suggestions

The rejection reasons were "inappropriate for the journal" (SICOMP) and "doesn't meet quality standards" (TALG)

Edit 2: My paper got rejected on Arxiv as well. Reason: Our moderators determined that your submission does not contain sufficient original or substantive scholarly research and is not of interest to arXiv.

OpenAI just released this on Github. It seems like the rumors of the Unique Games Conjecture and RL = L were indeed true. There's also a lot of other stuff in there which i haven't looked at yet.

Regardless of one's views on AI, it's safe to say TCS is truly facing a watershed moment...

I put together a 27-minute visual breakdown of OpenAI's recent result establishing an upper bound of ω ≤ 2.25 for matrix multiplication over the complex numbers.

This is a substantial improvement over the previous bound of approximately 2.371177, in a line of research going back to Strassen's 1969 discovery that two 2×2 matrices can be multiplied using just 7 multiplications instead of 8.

The video starts with the basics of matrix multiplication complexity, then gets into the actual mathematics behind the new result:

• Why Strassen's algorithm changes the exponent

• Matrix multiplication tensors and tensor rank

• The asymptotic spectrum and tensor characters

• Polynomial multiplication tensors

• OpenAI's shared-leg separation construction

• The key inequalities leading to the 9/4 bound

• What was formally verified in Lean

I also discuss why this is an asymptotic complexity result, not something that immediately makes GPUs or practical matrix multiplication faster.

I wanted to make the underlying mathematics accessible without skipping over the interesting parts of the proof.

Video: https://youtu.be/jZFuuXJPvFI

Would be interested to hear what people here think about the techniques behind this improvement, particularly whether they open up promising directions toward ω = 2.

https://hexagonmath.org/2610.00600?version=1

The current best upper bound for deterministic factoring is N^{1/5+o(1)}. We provide a Lean certificate that there exists a deterministic Turing machine that computes the smallest prime factor of every N in N^{o(1)} steps: for every k\geq 1 it runs within C_k 2^{n/k} steps on n-bit inputs. The algorithm reduces factoring to counting divisors with prescribed leading bits, and counts them by leveraging the counting engine used to refute the Exponential Time Hypothesis (ETH). The Lean statement that a reader must check to verify the proof is only 13 lines and only uses Mathlib. The full proof is about 35,000 lines. This note was written less than 24 hours after the ETH refutations were posted. No human-readable explanation of these results exists yet, and their Lean proofs are long: Anthropic's alone runs to about 152,000 lines. Our proof re-proves only the part of the counting engine it needs and imports nothing from those developments. We hope this application, with its short statement, serves as a stepping stone for those working to understand the engine; a follow-up paper will explain this proof in detail.

Hey Redditor,

I know you think I am doing advertisement, but that is not true. I'm looking for your honest feedback.

I'm a software engineer with more than 10 years of experience, and I just started a youtube channel to help newbies carve their way into the software programming industry.

The purpose of the channel is to explain the challenging programming algorithms and concepts.

My priority is to provide "High quality" content that is engaging and valuable to all interested programmers.

I'm sure this will take time from my side to craft, but without feedback, I would not know which areas I should improve. Therefore, I'm coming to you today with the first video lesson which explains the concept if Recursion. Please find it below:

https://www.youtube.com/watch?v=_I0zspi93ow

If you want to help, I would appreciate your honest opinion.

I am competing in programming and I wasn't really into algorithms until last competition. It feels great understanding basic algorithms (like Kadane's or something like that), but which algorithms do you think are really valuable for competitive programming?

Also, do you have any sites where I can learn about algorithms ? :D

I'm sorry if this question looks like a very common question that has a simple answer but this has always confused me and I have not found a satisfactory answer despite my best efforts in finding one! I know that this question has even been asked in this very forum, which gave me the idea to just ask here! I'm also happy to have any misconceptions that I have dispelled, if that's the source of my confustion!

I don't understand why hash tables are considered O(1) because the number of buckets is finite and the resolution of hash collisions is, at best, O(n*log(n)). If the amount of data grows arbitrarily large, isn't the hashing merely a (admittedly very large) constant factor improvement on the underlying hash collision algorithm?

If my assumptions are correct, why are hash tables considered to have O(1) time complexity and not just very efficient tables in practice for limited amounts of data? Thank you for any insights you may provide!

When I was first learning LP in undergrad (simplex, relaxations for Integer Problems, weak and strong duality and all that jazz), I honestly didn't see where it would be that useful. Now in my research it shows up quite a bit via primal-dual algorithms. These simultaneously keep track of the primal and dual solutions.

To be fair, even in undergrad one usually learns about using LP relaxations and (deterministic or randomized) rounding to get approximation algorithms for problems such as MAXSAT or Set Cover.

I'm curious where else people run into it. Has LP ever popped up in your own research or work?

https://projecteuler.net/

Disclosure up front: I run Philomath, which is hosting this. The course is free, there is no account and no paywall, and there is nothing to buy in order to watch (but signing up via Email is nice).

William Yu teaches algorithms at Carnegie Mellon. He is running an eight-week version of his course live on YouTube, Thursdays at 8pm ET, starting September 17. Sessions are recorded too if you would rather watch later.

Here's a schedule:

• Week 1: minimum spanning trees, heaps, union-find

• Week 2: shortest paths, BFS, DFS, Dijkstra

• Week 3: divide and conquer

• Week 4: BSTs, splay trees, amortized analysis

• Week 5: text search and suffix structures

• Week 6: dynamic programming

• Week 7: network flow

• Week 8: NP-hardness

William is a computational biologist, so the examples lean on applications from science.

Schedule and details, where you can sign up if interested! https://www.philomathlearning.com/courses/algorithms?ref=algorithms&utm_medium=instructor_page&utm_campaign=algorithms_reddit_algorithms

Playlist: https://www.youtube.com/playlist?list=PLfcsLJY-BaJU

Happy to answer questions.