This recurring thread will be for general discussion on whatever algorithm-related projects, problems, or topics you have been or will be working on this week. This can be anything, including:

* theoretical computer science and algorithm design,

* books, papers, or articles you are reading,

* coursework or self-study (what you have been learning recently),

* competitive programming or interview prep,

* preparing a talk, presentation, or project demo.

All backgrounds and levels of experience are welcome!

This preprint by Virginia Williams and Or Zamir claims to refute the long-standing k-Clique conjecture.

This result was announced by Or Zamir on Twitter yesterday, but now it's formally on Arxiv.

Binary search is easy to describe and famously easy to get wrong. I find it helps to stop thinking in terms of “+1 or -1” and write down the invariant first, then let the code follow from it.

The invariant (for “first index where a[i] >= x**” in a sorted array):**

• Everything before lo is < x.

• Everything at or after hi is >= x.

• The answer lies in [lo, hi].

Using a half-open range [lo, hi) and starting with lo = 0, hi = len(a), the invariant is true before the loop. Now each branch has one job: keep it true while shrinking the range.

def lower_bound(a, x):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if a[mid] < x:
            lo = mid + 1      # a[mid] is < x, so everything up to mid is < x
        else:
            hi = mid          # a[mid] is >= x, so hi can move down to mid
    return lo                 # lo == hi, the invariant pins the answer

Why each line is what it is:

• lo = mid + 1: we just learned a[mid] < x, so mid itself can be excluded. Setting lo = mid would keep it in play.

• hi = mid (not mid - 1): a[mid] >= x means mid could be the answer, so it must stay inside the range.

• Termination: when lo < hi, mid < hi, so hi = mid shrinks the range, and lo = mid + 1 does too.

The classic bug, as a counterexample:
Change the first branch to lo = mid. With lo = 0, hi = 1 and a[0] < x, we get mid = 0, so lo stays 0, and the loop never ends. The invariant didn’t break; the progress argument did.

A side note on mid**:** in languages with fixed-width integers, (lo + hi) / 2 can overflow for very large arrays, which is why lo + (hi - lo) / 2 is commonly recommended. In Python it doesn’t matter, but it’s a good habit.

Limits of this view:

• It assumes a sorted array and a consistent comparison. With duplicates the invariant gives you the first position of x, not any position.

• Closed-interval versions [lo, hi] work too, but need different update rules, and mixing the two conventions is where I think many bugs come from.

How do you structure your own binary searches? Do you stick to one interval convention, or derive from the invariant each time?

After working on estimating time of arrivals I thought I'd write a post about some if its challenges. Check it out to see why this is a billion dollar problem.

https://mehrdadmahabadi.com/blog/eta-at-scale.html

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.

I have been experimenting with a simple encoding idea that I call as '9-to-5 Encoding'.

The concept is applicable only to a sequence of integer digits, for example, digits of π without the decimal point.

Method:

Start from the leftmost digit and take every block of 9 decimal digits, interpret them as an integer, and represent that integer using just 5 characters from a 64-character alphabet.

For example:

314159265 → IkR2X

The reason I chose 9 and 5 combination is because the max value of 9 decimal digits is closest to max value of 5 Base-64 digits when converted to decimal, as compared to other combinations between decimal and Base-64. So, we waste a minimum number of empty mappings between the two.

I tested the approach on 10 million digits of π.

The interesting result:

• ZIP of original decimal text: 4,693,723 bytes

• ZIP of 9-to-5 encoded text: 4,205,187 bytes

That's approximately 10.41% less compressed storage.

It is well-known that binary representation is shortest for numbers, and this is not a claim of a new compression algorithm.

However, if it is text representation of the numbers, this '9 to 5' scheme seems to offer an advantage after zipping the text representation for 10 million digits of π. I have also found a similar advantage for 1 million digits of π.

I am thinking to explore other number datasets and compare against binary representations, especially after zipping.

I'm curious:

Has anyone come across a similar fixed-block encoding scheme? And what other experiments would you recommend?

I'd particularly appreciate feedback from people working in data compression, information theory and numerical representation.

paper: https://arxiv.org/abs/2610.24273

has anyone looked into this? i would like to know if the techniques could be useful for other offline problems

J'ai réalisé un projet GitHub nommé SymReg portant sur la régression symbolique : https://github.com/Julien-Livet/SymReg. Le package Python est disponible sur PyPI : https://pypi.org/project/symregpy/ (pour tester : pip install symregpy). J'ai testé l'outil sur plusieurs équations de benchmarks dans le domaine. Je serais ravi d'avoir des retours techniques sur le sujet, notamment vis-à-vis des autres outils comme PySR en Python.

If you search a large space with an evolutionary algorithm or any strong optimizer, the fitness function is the attack surface, and the optimizer will probe it systematically. Here’s a short threat model, organized by what the “attacker” can touch. The cases are documented in the literature on evolutionary computation, and I’ve kept the claims to what those write-ups report.

Attack 1: the score is a proxy
Case: a boat racing agent rewarded for hitting targets circled a lagoon where three targets respawned and scored about 20 percent above human players without finishing the race. An evolved-creature experiment that scored maximum height of the center of gravity produced tall creatures that never moved.
Defenses: score the thing you actually care about; use several objectives that pull against each other; inspect top individuals, not just their scores.

Attack 2: the evaluation harness is gameable
Case: in automated program repair scored by passing tests, a sort function that returned an empty list passed, because the tests only checked that the output was in order.
Defenses: test the tests with degenerate candidates; check properties that rule out vacuous solutions (for sorting, that the output is a permutation of the input, not only ordered).

Attack 3: the simulator is wrong in a way you didn’t consider
Case: swimmers twitched very fast because integration error accumulated into extra energy; in a carrier-landing simulation an overflow made the force read as zero, scoring as a gentle landing.
Defenses: bound state and actions, assert physical invariants (energy conservation, plausible ranges), cross-check top individuals in a second simulator or integrator.

Attack 4: resource limits and the environment
Case: an agent playing tic-tac-toe on an unbounded board placed moves far from the center, and opponents ran out of memory and forfeited.
Defenses: bound the environment and each evaluation’s resources (memory, time), and count a resource failure as a failure of the candidate that caused it only if you intend it to be.

Attack 5: detecting the evaluation
Case: in a digital evolution setup, organisms learned to recognize test inputs and stopped replicating during the test; after the inputs were randomized, they used random numbers to misbehave only some of the time.
Defenses: randomize and rotate evaluation instances, evaluate on instances held out from selection, and compare behavior in selection and in validation.

Attack 6: the result depends on the substrate
Case: Thompson’s evolved circuit on a programmable chip distinguished two tones, but some cells with no wired connection to the output still affected it, and moving the population to a different region of the same chip cost the best individual about 7 percent of its fitness before evolution recovered it. The paper didn’t test other physical chips.
Defense: validate on a different instance of the environment before you trust the result.

What I’d always do: read the behavior of top individuals, ask what’s the cheapest way to score well, and keep a separate validation that the optimizer never sees. Techniques such as novelty-based search or multi-objective formulations change what gets rewarded, but they have their own proxies, so I wouldn’t treat them as a fix.

I wrote the cases up in more detail, in case it’s useful as a complement: https://medium.com/@nagatomopedro05/field-notes-on-machines-that-followed-the-rules-too-well-98ebae3eea51

What other attack would you add, and what does your own validation look like?

https://sigact-stoc.github.io/stoc2027/

For the first time, all of the submissions and author affiliations for STOC have been made public.

There are lot of very cool results are claimed (these are just submissions, haven't been accepted yet) there! E.g. There seem to be (crank) submissions claiming to have resolved P vs NP.

Hello fellow algorithms comrades, recently I got project on my university about finding best algorithm for (in title). Currently I'm working with algorithm that builds path from random dfs and increases its weight by rotations, restarting, rebuilding fragments and adding nodes to solution. Does anyone have a better approach to such solution? I'm not asking for any finished algorithm but just thoughts that could help me improve my algorithm and maybe come up with something new
If you know any research papers worth reading in this topic, please give their names

Graph is general and can have cycles, I know that it is NP-Hard thats why I'm asking about any ideas

Thank you all in advance

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.

Hi everyone!

I'm looking for help solving an algorithmic problem involving wildcard digits and modular arithmetic. I would really appreciate any hints, explanations, or suggestions for an efficient algorithm!

I've been thinking about this problem for a while, particularly about using dynamic programming over remainders, modular arithmetic, and possibly the Meet in the Middle technique.

Problem description

We are given a string a representing a non-negative integer and a positive integer b.

The string a consists of decimal digits (0–9) and wildcard characters (x). Each occurrence of x can be independently replaced with any digit from 0 to 9.

For example, x1x could become 212, 010, or 919.

Our task is to determine whether there exists a replacement of all occurrences of x such that the resulting number:

• Is divisible by b.

• Is not equal to zero.

Leading zeros are allowed.

We need to return a Boolean value:

• true if at least one valid replacement exists.

• false otherwise.

Examples

Example 1

Input:

a = "4x"
b = 5

Output:

true

Explanation: Replacing x with 0 gives 40, which is divisible by 5 and is not zero.

Example 2

Input:

a = "xx2"
b = 10

Output:

false

Explanation: Every possible number ends in 2, so none can be divisible by 10.

Constraints

• 1 <= len(a) <= 9

• 1 <= b < 10^9

• Leading zeros are allowed.

• Different occurrences of x can be replaced independently.

My approach so far

I suspect this problem can be solved using dynamic programming over possible remainders modulo b.

If the current prefix has remainder r, appending digit d gives:

python

new_remainder = (r * 10 + d) % b

However, a standard DP array of size b is impractical when b can be close to 10^9.

My questions

1. Is there an efficient algorithm that avoids enumerating all possible remainders modulo b?

2. Is there a mathematical observation that makes this problem simpler?

3. What would be the optimal time and space complexity?

I'd be particularly interested in an explanation of the algorithm, rather than just code.

Any help, hints, or alternative approaches would be greatly appreciated. Thanks in advance!

Here's a nice lecture by Ryan O'Donnell on BLR linearity testing [BLR93] and a proof using Fourier Analysis [BCHKS96]. As he says in his lecture, it seems like this problem was almost tailor-made for Fourier stuff. Was working through it yesterday and thought it would be nice to share.

Off-by-one errors in binary search mostly come from not stating what the loop maintains. Here’s the version I find easiest to argue about: finding the first index i with a[i] >= x in a sorted array (lower_bound), with the search interval half-open, [lo, hi).

def lower_bound(a, x):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo

Invariant: every a[i] with i < lo is < x, and every a[i] with i >= hi is >= x.

Initialization: lo = 0 and hi = n. There are no indices below 0 or at or above n, so both parts hold vacuously.

Maintenance: lo < hi, so mid is in [lo, hi).

• If a[mid] < x: since the array is sorted, every index up to mid has a value < x, so setting lo = mid + 1 keeps the first part true, and the second part is untouched.

• Otherwise a[mid] >= x: every index from mid onward has a value >= x, so setting hi = mid keeps the second part true.

Termination: each iteration strictly shrinks hi - lo, because either lo increases to mid + 1 > lo, or hi decreases to mid < hi. The loop ends when lo == hi. By the invariant, everything before lo is < x and everything from lo onward is >= x, so lo is the first index with a[i] >= x, or n if there is none. With duplicates it returns the leftmost one.

Cost: the interval roughly halves each step, so O(log n) comparisons.

Two details worth noting:

• mid = lo + (hi - lo) // 2 instead of (lo + hi) // 2. In languages with fixed-width integers, lo + hi can overflow for very large arrays. This was a known bug in widely used library code, reported around 2006. In Python integers don’t overflow, but the habit carries over.

• With a closed interval [lo, hi] the loop condition becomes lo <= hi and the updates become mid + 1 and mid - 1. It works too, but I find the half-open version has fewer special cases because an empty interval is just lo == hi.

Where this is less obvious: variants like “last index with a[i] <= x” or binary search on a monotone predicate over the answer (not an array) are the same invariant with a different condition, and it’s easy to flip a comparison and silently get the wrong side with duplicates.

Do you prefer half-open or closed intervals, and do you state the invariant in a comment when you write these?

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."

This recurring thread will be for general discussion on whatever algorithm-related projects, problems, or topics you have been or will be working on this week. This can be anything, including:

* theoretical computer science and algorithm design,

* books, papers, or articles you are reading,

* coursework or self-study (what you have been learning recently),

* competitive programming or interview prep,

* preparing a talk, presentation, or project demo.

All backgrounds and levels of experience are welcome!

This thread is meant for users to share cool recently discovered facts, observations, proofs, algorithms, or concepts that might not warrant their own posts. Please be encouraging and share as much detail as possible, as we’d like this to be a good place for people to learn!

I created a function that turns any text ("hello world", your name, a random phrase) into a landscape image, images themselves are not LLM generated, but algorithmically rendered. Here is the white paper https://beautifulhash.com/algorithm

I ran the three on the DIMACS Florida road network (1.07M junctions, 2.7M segments), Tallahassee to Coral Gables by travel time:

- Dijkstra settles 1,029,617 junctions, 99 ms

- A* settles 840,138, 121 ms. Exactness caps the straight-line estimate at 67% of the true distance (112 road segments are shorter than the straight line between their ends), so the guidance is weak and A* ends up slower than Dijkstra on the longest routes

- CCH touches 346 junctions, 0.039 ms

CCH moves the work to preprocessing: nested dissection order (17 junctions cut Florida in two, 28 more cut it in four), contraction with shortcuts, then a weight-only customization step. A traffic change re-prices only the arcs above the changed edge, which took 0.8 ms in my implementation. It does not work on graphs without small separators (social networks, supernodes), where the hierarchy would be many times larger than the graph.

The implementation is open source (Apache 2.0, pure Java), inside ArcadeDB, with a write-up, numbers and a docker compose to reproduce them:

https://arcadedb.com/route-planning.html?utm_source=reddit&utm_campaign=cch-route-planning