thxg

Then in January 2022, the NYT bought Wordle, and started tweaking both lists, first shrinking the secret word list to 2309 entries, but leaving the logic otherwise intact. Fast forward to today, I looked up the current code [1], and it seems that there are now 14855 allowed words. The first 12546 are ordered alphabetically (0: "aahed", 12545: "zymic"), and the next 2309 are not. This may suggest that the latter are the secret words, but the logic for picking them has changed: I found no obvious sequence, when compared to the last few days' secret words. So it's either a more complex sequence, or the secret word is picked server-side.

In any case, I guess they decided to re-shuffle the list now at day 1689 / 2309 in order to avoid giving particularly assiduous player an additional bit of information: they can exclude all previous secret words. (To be accurate, I think this would be 1.897 bits, but my information theory is rusty.)

PDLP is targeted at instances for which factorizations won't fit in memory. I think their idea for now is to give acceptable solutions for gigantic instances when other solvers crash.

> Note that the top 56 bits in rax are not zeroed – they contain junk. This is fine b/c the compiler will only make callers check the lowest bit of a register for boolean operations. This is why changing the compiler’s “understanding” (ie the cast) is necessary.

... and yet, the function ABI is clearly i386 (fetching arguments from stack) and indeed everything is compiled with -m32 [2] (i.e. 32-bit SysV ABI). This is a strange contradiction in 2023. On the Intel/AMD side, x86_64 has been prevalent (and the default) for... more than 15 years?

It does not invalidate the article's point. But it is slightly confusing....

- a single array of floats with all the nonzero matrix entries, ordered row-by-row:

  double values[nnz];

  int columns[nnz];

  int start[m + 1];

  for (int i = 0; i < m; i++) {
    index = start[i]; // where
    count = start[i + 1] - start[i]; // number of nonzeros in row i
    
    for (int t = 0; t < count; t++) {
       j = columns[index + t];
       v = values[index + t];
       printf("element (%d, %d) has value %g\n", i, j, v);
    }

- the quality of the solutions found (in the best case: optimal solutions)

- the presence or absence of optimality guarantees (for example, some algorithms provide optimal solutions very often, but cannot guarantee it 100%)

- the time (or computational cost) needed to find such solutions

Furthermore, the state-of-the-art (SOTA) is well known for most types of optimization problems. In this article, they present a list of real and practical applications, so let us have a look at them one by one:

1.1 Traffic flow optimization

Simple flow problems can be solved in polynomial time (and quickly in practice), so there is no need for anything fancy. Once you introduce additional constraints or discrete variable, the SOTA is mixed-integer programming for offline problems. For online problems it's more complicated. In both cases, I am not aware of any application in which MemComputing can reach SOTA.

1.2 Vehicle routing & scheduling

Here, depending on your computing time constraints, needs for solution quality and/or optimality guarantees, the SOTA can be constraint programming (gecode, OptaPlanner), local search heuristics (LocalSolver), or mixed-integer programming (CPLEX/XPress/Gurobi) with column generation. MemComputing is nowhere to be seen again.

1.3 Supply chain optimization

This is a very broad field, but in general mixed-integer programming is king here.

2.1 Protein folding

Here there is quite an objective measure: the biennal CASP competition. This is where AlphaFold made a splash in 2022. MemComputing has never participated.

2.2 Genome sequencing

I am not knowledgeable enough to comment here.

2.3 Radiotherapy treatment

I am not very knowledgeable here either, but last I looked mixed-integer programming approaches were favored.

3.1 Portfolio risk optimization

Various types of branch-and-bound solvers. Mixed-integer linear/quadratic/convex programming. No MemComputing.

3.2 Detecting market instabilities

No idea.

3.3 Optimizing trading trajectories

No idea.

4.1 Training neural networks

Many people here know how this is done. Stochastic gradient descent on GPUs or TPUs. No MemComputing involved. How can they even claim to be active in this field?

4.2 Detecting statistical anomalies

Vague.

4.3 Classifying unstructured datasets

No idea.

The problem is that if you invent a new optimization algorithm, it is very easy to find one instance of one problem for which your algorithm works well. They did literally that in a paper [1]: They took a library of mixed-integer programming problem instances containing 270 benchmark problems, and published a whitepaper showing that they beat a SOTA solver on one of them. A single instance out of 270!

The really hard part is the opposite: given a class of problems, find an algorithm that beats the SOTA. MemComputing has never done that. Combined with their propensity for grand claims backed by misleading evidence, MemComputing have accumulated a lot of badwill from the academic community over the years. My suspicion is that, while on the surface this post seems to put their approach in contrast to quantum computing, what they really try to do here is ride on the quantum computing hype wave.

Before people draw links to recent large language model breakthroughs: Although they do use techniques from computational linguistics, there are no neural networks involved. This is more like old-school AI.

They have essentially a giant optimization problem, and they (approximately) model it as a lattice parsing problem, with a stochastic context-free grammar. They can solve that to optimality in O(n^3), which is too slow for some applications. So they propose a O(n) heuristic (hence no optimality guarantees, but the model was approximate to begin with anyways, and the heuristic is a lot faster), which is the reason for the name of their code: "LinearDesign".

Working link in case you are interested:

This shortcut in explaining NP-completeness is frustratingly widespread. It is also very wrong. A 49-city TSP was solved (to provable optimality) by hand by 1954 [1]. Concorde [2] can solve TSP instances with more than a hundred thousand cities [3]. In practice, for a graph with a few hundred points, you will most likely find an optimal tour in minutes on an iPhone (yes, there is an app for that [4]).

And it's not just about TSP. SATs [5] and MIPs [6] with hundreds of thousands of variables are solved every day to provable optimality. How? Well, sure, the best-known algorithms for NP-complete problems are of course exponential in the worst-case. But they are definitely not "essentially searching for a solution from all possible answers", that would indeed be prohibitively costly. We have algorithms that perform much better on practical instances (dynamic programming, backtracking, branch-and-bound, etc.).