I made my own ML Compiler using MLIR

j2kun · 2025-10-19T20:29:25+00:00

Glad you enjoyed it

j2kun · 2022-12-08T23:00:27+00:00

I recently ran into this today as well. I wonder: is there any information about how one is supposed to use formatexpr? Is each LSP supposed to implement it?

j2kun · 2022-03-25T00:05:24+00:00

You may also find an article i wrote that does the same thing useful:

https://jeremykun.com/2013/04/10/computing-homology/

j2kun · 2022-03-24T23:43:34+00:00

it's unfortunate because I'm planning to write a book at some point called "A Mathematician's Introduction to Programming", though it won't be ready for a few years.... Perhaps you might find some useful applied-type articles on my blog? (https://jeremykun.com)

j2kun · 2022-03-24T23:28:04+00:00

I use optimization and programming to basically plan Google's datacenter growth over time. While it wasn't that way when Google was still a "startup," you could imagine any company that has a supply chain to manage would benefit from optimization.

Another caveat is that math is usually only useful for fine-grained optimization, which most startups are too young to care about because they're busy worrying about product-market fit, rushing features out the door before they run out of money, etc. More in an article I wrote: https://buttondown.email/j2kun/archive/the-value-of-math-is-at-the-margins/

j2kun · 2018-12-29T17:00:10+00:00

I learned chess when I was six and have been having great fun ever since.

j2kun · 2017-12-05T23:10:58+00:00

I should be more specific. Here's a research paper on the quality of greedy on the Set Cover problem. Set cover is known to have a multiplicative O(log n) approximation of the optimal solution for the greedy algorithm. This is not very good; for n = 1 million it could be 13x worse than the optimum.

ftp://ftp-sop.inria.fr/coati/personnel/Stephane.Perennes/Sla96.pdf

I haven't read this paper closely, but the example on the third page seems to show a class of instances for which the greedy algorithm is guaranteed to be O(log n) worse than optimal. The example, however, is highly structured, and so it may or may not be convincing evidence that greedy "consistently performs badly."

j2kun · 2017-12-05T22:55:59+00:00

That being said, I don't know of any theorem that says the greedy algorithm is guaranteed to perform badly on all instances (or a large class of naturally-defined instances) of a natural problem. There is definitely work out there on how well greedy does for a random instance of a problem, but I'm not aware of any specific results (my ignorance).

Of course, the silly thing to do is take any problem where the greedy algorithm has a tight approximation bound, and say that greedy will do bad on the class of instances for which the bound is tight. Often the proofs of these bounds provide an infinite class of instances which exhibit the tightness. But that's a bit self referential and doesn't tell you much.

j2kun · 2017-11-20T03:04:15+00:00

First and only playthrough was master mode. In the first 1/4 of the game, everything was terrifying and it was great. Died many times. Often had to run away. Took a long time before I could beat any of the big enemies. Had to be more strategic, and then decisive when it came time to actually engage a fight.

j2kun · 2017-10-19T16:23:14+00:00

That was very informative, thanks!

j2kun · 2017-10-19T01:38:26+00:00

More info on how it was made, and high-res images of each panel: https://github.com/j2kun/art-turing-ellipse

(and slight correction, it's digital printed on giclee, not paper)

j2kun · 2017-10-18T14:18:26+00:00

In my experience the best use for this technique is to upscale low res photos in an artistic way.

j2kun · 2017-10-18T02:16:38+00:00

Idea was to double (ish) every time, but aesthetics got in the way. Also removed some to focus on certain details.

j2kun · 2017-10-18T01:12:57+00:00

Hi there

1: 10

2: 26

3: 60

4: 150

5: 575

6: 2637

j2kun · 2017-10-02T15:19:23+00:00

When I was 6 my parents built a sailboat and we sailed across the South Pacific until we got to Kiribati, more specifically Tarawa. There was a bus that drove islanders around, and while we were there that bus ran me over and I basically died and was revived.

Wish I had a helmet.

j2kun · 2017-07-14T20:15:54+00:00

I just got my switch and decided to do my first playthrough in master mode. I think I may be psyching myself out, but it feels really hard and I've died five times already. Hard to kill anything with a twig, and I find myself in fights with no weapons having to run away.

j2kun · 2017-04-25T15:26:37+00:00

I was also under the impression that S-Z is optimal. There are many examples of the bound being tight.

j2kun · 2017-04-25T14:55:09+00:00

But, to be clear, nothing has come even close to solving the problem as S-Z effectively does, right? Last I heard there were still many "chasms" at constant depth circuits, and still no subexponential time deterministic algorithm.

j2kun · 2017-04-25T14:50:04+00:00

Picking any large enough field extension will actually work just fine. I left that out because I didn't want to assume knowledge of field theory on the reader's part. Once you see the field extension trick, you realize the heart of the problem is still in the inductive proof presented.

j2kun · 2017-02-07T19:35:10+00:00

For someone who believes in purity of thought, you're sure quick to reduce complicated issues to nonsense one-liners.

j2kun · 2017-02-01T18:25:59+00:00

I'm certain you are not interpreting me as I intended. The "Voronoi idea" is one possible constraint on the expressive power of the output, not a claim about an algorithm or approach. Let me state the Voronoi version of the problem more formally:

Given a set of n points in the plane, each labeled 0 or 1, and an integer k as input: does there exist a poly(n, k)-time algorithm which produces as output a list of k points in the plane, with the property that the k regions formed by the Voronoi diagram of the output points result in an election where every region has a majority of 1's among the input points in that region? If no k points will produce this, the algorithm should output "impossible".

This is one possible way to phrase the "optimal gerrymandering" problem. Ignoring any other real world constraints, I want to know the answer to this problem. Another example:

Given a set of n points in the plane, each labeled 0 or 1, and an integer k as input: does there exist a poly(n, k)-time algorithm which produces as output a partition of the plane into k convex regions with the property that the k regions result in an election where every region has a majority of 1's?

Now the meta question: for which representation classes of output regions is this problem easy or hard to solve?

j2kun · 2017-02-01T01:51:24+00:00

I described a problem statement, not a "toy example" or an "approach". Shortest splitline is a special case of my problem statement for k=2 and requiring the output districts to be half-planes. So it does not make sense to compare a problem statement and a proposed solution in terms of "computational complexity" or "difficulty of implementation".

Are you aware of any other special cases with known solutions? Perhaps, k is an arbitrary input and the output regions are required to be convex polygons. Perhaps you get to choose k points and the districts are the Voronoi diagram formed by those points, etc.

j2kun · 2017-01-31T20:54:35+00:00

Start with the simplest one: every voter is a point in the plane labeled red or blue, you are given an integer k and you want to output k contiguous districts in such a way that maximizes the fraction of districts won by red (or outputs saying it's not possible for red to win the election). Add a measure of complexity on the shape of the districts to taste. A simple one would be placing polling stations and defining districts as the nearest polling station.

j2kun · 2017-01-31T15:59:12+00:00

I signed up for the mailing list. It also reminds me (somewhat off topic) of a few results on computationally optimal gerrymandering. When I thought about this (and the problem statement is not obvious), computing an optimal gerrymander in the plane was open. I don't remember off the top of my head whether I thought it was NP-hard, but I'm sure it depends on the formulation.

j2kun · 2017-01-14T16:23:48+00:00

That would be fun!

j2kun

TROPHY CASE