cevi

"Semidefinite programming is still far from being a mature technology like linear or quadratic programming."

[1] https://link.springer.com/article/10.1007/s10957-021-01896-x [2] https://www.annualreviews.org/doi/pdf/10.1146/annurev-contro...

(not having much money is no obstacle to reading books on math, so long as you are aware of Library Genesis)

[1] https://mathoverflow.net/questions/85314/can-anyone-analyze-...

The purpose of the subject is, roughly speaking, to exhaustively characterize all types of reliable reasoning which can be carried out efficiently - some people say they are searching for "a logic for P". The techniques used are a mix of ideas from model theory, universal algebra, Ramsey theory, and computer science. Given the ridiculously ambitious scope of the project, I think the rate of progress (especially in the past few years) is astounding.

[1] https://arxiv.org/pdf/1201.0856.pdf

"In each round the processors may perform unbounded computations on their respective local state variables and subsequently exchange of messages of arbitrary size along the links given by the underlying input graph."

Given this setup, it should be possible to solve any problem in O(n) rounds, and indeed they point this out in the introduction:

"If the chromatic number of G is χ, in this setting it is trivial to find a χ-coloring in T = O(n) rounds, as in O(n) rounds all nodes can learn the full topology of their own connected component and they can locally find an optimal coloring by brute force without any further communication."

While this paper is very interesting from a theoretical perspective, it is saying more about the LOCAL model of distributed computing than it is about quantum computing. Nobody should come away from this with the conclusion that we have somehow proved that quantum algorithms are useless for real-world problems.

[1] https://arxiv.org/abs/1811.00970

As for how actual physical qubits are maintained, that topic is tough to find a good explainer for, since every group has a different approach. Some groups use trapped ions, some use two-dimensional quasiparticles, some use spin states of photons... and no one has a clue which approach will be most practical in the end. It's analogous to not knowing whether clockwork or vacuum tubes will be the better way to implement a Turing machine.

Your ability to catch errors tends to be closely linked to the amount of time you've spent working in a particular area - because you build up a mental suite of test cases to check every claim against. One mistake I see occasionally is jumping into a brand new area of math and moving just as quickly as you would in the old area where you had more expertise, making huge blunders every step of the way. When you enter a new area, you have to go really excruciatingly slowly as you build up the intuition and suite of examples.

Almost every math paper contains an error or two - they are usually easy for an expert to fix (the equivalent of leaving out a semicolon at the end of a line in C++, takes only a moment to fix if you have familiarity with the language - but incredibly frustrating to a user who doesn't know how to make the easy fix).

It's a bit shocking that they got Transformers to actually learn the theoretical low depth algorithms for simulating automata, but looking closer at their results we can see that the parts that I would intuitively think are hard to learn (i.e. learning parity) are fairly brittle.

[0] https://us.metamath.org/mpeuni/mmset.html

A wacky alternative implementation of probability theory can be found in Nelson's book "Radically Elementary Probability Theory" - I highly recommend it as a way to see how little the underlying framework matters.

1. Winning Ways for Your Mathematical Plays

2. A Singular Mathematical Promenade, available for free online: https://perso.ens-lyon.fr/ghys/promenade/

There are many other math books I really like - over the years I've collected a long list of reading recommendations: https://notzeb.com/rec.html (most of them won't fit as answers to this question)

There is a version of "locality" that is based on classical mechanics and classical probability - this version corresponds to hidden variable theories, and is fairly definitively ruled out. Given that this definition has a false model of reality baked into its core, I have a hard time taking it seriously.

However, there is a more flexible, and in my opinion more correct, definition of "locality" that applies to generalized probability theories. This definition basically says that if I am on Earth and you are in Andromeda, then there is nothing I can do to affect the results of your experiments in any way that you can detect before you first meet up with my future light cone. Sure, we can meet up in the far future and compare notes to see that there were some unexpected statistical correlations between our experimental results - but we can only ever notice that after we meet up later.

According to the second definition of locality, quantum mechanics is a local theory, while to the extent that we try to take the pilot wave seriously the Bohmian picture is nonlocal. (And faster than light communication is nonlocal according to either definition.)

Practically, local theories have an important distinction from nonlocal theories - you can simulate what is going to happen in a small region of space a day from now while only knowing what was true today in a larger but finite region today. For instance, Newtonian gravity fails to have this property, which makes it hard to properly simulate an infinite universe following Newtonian gravity without making strong assumptions about how homogeneously matter is distributed throughout the universe at huge scales. On the other hand, the Game of Life is a local theory, which is the basis of the famous Hashlife algorithm.

[1] https://arxiv.org/pdf/1704.01914.pdf [2] https://arxiv.org/pdf/1703.03021.pdf

[0] https://www.cs.umd.edu/~gasarch/BLOGPAPERS/belaxioms1.pdf [1] https://www.cs.umd.edu/~gasarch/BLOGPAPERS/belaxioms2.pdf [2] https://www.logicmatters.net/tyl/ [3] https://plato.stanford.edu/entries/settheory-alternative/ [4] https://plato.stanford.edu/entries/platonism-mathematics/ [5] https://lawrencecpaulson.github.io/papers/Scott-Models.pdf

This used to be my personal academic website, but I'm no longer in academia so I recently had to figure out a new hosting solution. (Not much to see if you don't enjoy math or puzzle-solving.)

The standard Linear Programming relaxation of the constraint "the nine variables x_1, ..., x_9 are a permutation of 1, ..., 9" is defined in the following way. First we make real variables p_ij which we think of as representing the "probability" that x_i is equal to j. Each p_ij has to be between 0 and 1, of course, and they have to satisfy the following system of linear equations:

- for each i, the sum over j of p_ij is equal to 1 (since every x_i has to have some value), and

- for each j, the sum over i of p_ij is equal to 1 (since every value from 1, ..., 9 has to show up in the list of x_is somewhere).

The fact that this system of equations, together with the inequalities 0 <= p_ij <= 1, corresponds exactly to the "convex hull" of the constraint that the x_i are a permutation of 1, ..., 9 is a fairly famous early result from the theory of the Linear Programming relaxation of the bipartite matching problem.

To describe the full Linear Programming relaxation of Sudoku, instead of just having 9 variables x_i you have 81 variables x_ab, which leads to 729 real "probability" variables p_abj between 0 and 1, and for each row, column, and square of the Sudoku these probabilities have to satisfy the equations listed above (applied to the relevant variables). That gives you a system of 324 (slightly redundant) linear equations in 729 unknown real variables p_abj, each of which is constrained to be between 0 and 1 - a piece of cake for a computer.

For a human, you don't want to write down that entire system of equations - you want to use just a few of them to quickly figure out some piece of the puzzle. The technique of set equivalence theory does just this: instead of focusing on all of the probabilities p_abj, you just use the fact that the sum of the probabilities p_ab1 along every row/column is 1, and add/subtract the equations you get from some rows and columns to notice that the sum of the p_ab1s for the (ab)s corresponding to the corners is equal to the sum of the p_ab1s for the (ab)s corresponding to the ring around the center. Then you do the same for the 2s, and so on.

Essentially, the Linear Programming relaxation of a puzzle is a standard way of approximating the solution space with a system of linear equations and inequalities, replacing discrete yes/no answers to questions like "is the digit inside this box a 7?" with real numbers between 0 and 1 (which can be interpreted as probabilities, if you like). This system of linear inequalities and equations can then be solved efficiently with techniques from convex optimization.

Even the example from the Cracking the Cryptic video, with the conclusion that those three boxes at the bottom have to be 1, 2, and 3 in some order, would be deduced immediately from the Linear Programming relaxation of Sudoku. You don't need ontological remodeling when you know how to apply convex optimization :)

Someone who is genuinely interested in understanding the way the world works ends up asking questions about what goes into the calculations - what's the Lagrangian, how many degrees of freedom (i.e. quantum fields) are there, what symmetries or constraints are satisfied by the laws of physics, how can we set up the math to avoid pathological situations where the results of our computations are infinite, and so on. Philosophically motivated interpretations of quantum mechanics shed exactly zero light on these questions.

Well.. there is a caveat. If quantum mechanics was somehow incorrect - that is, if unitary evolution of a state vector in a Hilbert space didn't actually describe reality at all - then all of the above would be wrong. But in that case, every single interpretation of quantum mechanics would be wrong as well. Quantum computers would just flat out not work.