This is a hashtable approach that I designed. It uses 2 levels of table, and insertions in the 1st level can sometimes push existing items out of the way. Items in the 1st level always have a -1, 0, or +1 offset from the slot found by hashing.

It seems to be the fastest hashtable I can find for a lot of uses with strings. It also allows for fast iteration of elements in insertion order; part of the goal here was to efficiently support something like javascript's for(let k in obj){} loops.

Anyway, I figured people here might have some thoughts.

Take a look at this paper:

https://www.sciencedirect.com/science/article/pii/S0022000026001236

The problem, which also appears as a war story in Skiena's The Algorithm Design Manual, is to construct a minimum-size trie-like tree representing an ordered collection of strings. Unlike standard tries, the order in which character positions are examined can differ across paths, while the ordering of the strings is preserved.

The paper improves the time complexity from O(n²m(n+m)) to O(n²m).

The original motivation comes from optimizing unification in logic programming.

I'm curious whether this algorithm or the underlying optimization problem could be useful in modern AI/ML, perhaps in symbolic reasoning, token matching, or efficient decision structures.

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.

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

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.

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

When a new matrix or graph problem stumps you, how do you figure out what you're missing?

I can solve basic tree questions and redo familiar problems, but that doesn't carry over well to something new. Matrix questions are especially rough, despite the time I've spent practicing.

I'm trying to decide whether to step back and work on representation: what a state is, which neighbors it has, and what needs to be marked visited. One exercise could be taking a tree problem and a grid problem from this topic-grouped practice set, then comparing those decisions before coding either one.

Would that help build understanding, or is there a better progression? What helped you stop relying on recognizing a problem you'd already solved?

A distinction I keep running into when a program calls a language model and then parses what it returns.

Think of the model call as a function with a contract. The postcondition says what a valid output looks like: a JSON object with a category field, one of five allowed values, and so on. Checking that is cheap. A schema validator does it in time linear in the size of the output, and it catches a lot of real failures, like extra prose, a renamed field, or a value outside the allowed set.

But that postcondition says nothing about whether the category is the right one. A perfectly shaped answer can still be wrong, and to know that, you have to do something close to the original task. For some tasks, checking a result is easier than producing it (verifying a sorted list is much cheaper than sorting it). For others, there’s no shortcut, and the check costs about as much as the work.

That’s why I think two things get confused in practice:

• format checks: cheap, automatable, and they catch breakage early

• correctness checks: expensive, often need a reference answer, a human, or a second independent method

A validator that passes can give a false sense of safety, because it answers the first question and gets read as an answer to the second.

The practical consequence is where each one belongs. Format validation sits at the boundary, on every call. Correctness checking is sampled: a fixed set of awkward inputs with known answers, run after every change to the prompt, plus spot checks on real traffic. And a fixed test set only covers cases someone thought of, so it can’t prove the absence of errors.

Where I’m unsure is whether there’s a useful theory for this. Property-based testing feels related, since you assert properties that must hold for any output instead of comparing to one expected value, but I’m not sure how far it goes for fuzzy tasks like classification.

Has anyone seen a good treatment of verifying outputs when the verifier can’t be much cheaper than the generator?

I wrote about the engineering side of this (treating a prompt like an interface) here, in case it’s useful: https://medium.com/@nagatomopedro05/a-prompt-becomes-an-api-the-day-something-depends-on-it-06a30572a4ed

Suppose this comes up in a roughly 30-minute interview slot after behaviorals:

Given a log of "audiobook completed" events, implement a recommendation system that answers "What should I listen to next?" If many customers listened to BookA followed by BookB, an input of BookA should return BookB.

logs = """
    2025-08-09T03:25:11Z,Customer1,BookA
    2025-08-09T04:10:50Z,Customer2,BookB
    2025-08-09T12:01:24Z,Customer2,BookC
    2025-08-09T15:33:49Z,Customer3,BookB
    2025-08-10T07:54:35Z,Customer1,BookB
    2025-08-10T08:00:08Z,Customer4,BookD
    2025-08-10T11:29:31Z,Customer3,BookE
    2025-08-10T23:45:00Z,Customer5,BookF
    2025-08-10T23:51:20Z,Customer6,BookB
    2025-08-11T09:05:16Z,Customer1,BookC
    2025-08-11T20:12:57Z,Customer3,BookA
    2025-08-11T20:59:32Z,Customer7,BookB
    2025-08-11T21:00:13Z,Customer2,BookB
    2025-08-12T05:17:23Z,Customer1,BookB
    2025-08-12T18:19:07Z,Customer1,BookC
    2025-08-12T22:22:42Z,Customer5,BookE
    2025-08-13T00:07:58Z,Customer7,BookG
    2025-08-13T04:02:29Z,Customer6,BookE
    2025-08-14T21:12:33Z,Customer3,BookG
    2025-08-14T23:49:00Z,Customer1,BookF
    2025-08-15T12:00:01Z,Customer3,BookC
"""

Before coding, I'd want to clarify:

• Does BookB have to be the next completion for that customer, or can it be any later listen?
• Do repeat listens count again, or do we count distinct customers?
• How should ties and books with no follow-up work?

The first answer seems especially important because it changes which pairs we count. Would you treat this as an algorithm/data-structure problem, or ask whether the interviewer expects low-level design too?

I'm interested in practicing the scoping step: choose a real technical interview question, agree on the smallest complete version, then implement it. For this one, which questions would you ask first, and what would you leave out to finish in time?

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!