Blog

In the age of multicore computing, developers face the challenge of designing data structures that efficiently utilize the available hardware parallelism. One of the most important data structures is the priority queue, which is used in a variety of applications ranging from graph algorithms to data compression. Computer scientists often get taught some heap-based design of priority queues during university, where smart incremental updates enable good performance. However, trying to parallelize these designs is complex, as strictly incremental algorithms often are. In this post, we will investigate the MultiQueue, which is a relaxed priority queue which trades strict sequential semantics for massively increased scalability.

There is something about graph algorithms - they are just always fun to think about! With that said, Graph Neural Netorks (GNN) are no exception. These are a form of neural network, but designed in a way to learn things about graphs. They have proven to be usefull for a plethora of graph learning problems in fields such as drug discovery, recommender systems, and protein folding. In this post, I will present the difficulty of directly applying neural networks (NN) to graphs, how message passing NN solves this, and end by looking at the expressive power of such GNN.

This was my fourth year doing Advent of Code, my second year trying to compete, and my first year appearing on the top 100 leaderboard (if only for a single day). Last year lit a fire in me to become faster, and since then I have built my programming language Zote, practiced some competitive programming, and learned to touch type using Colemak. This will be a short retrospective on this year's event, as well as my preparation leading up to it.

Do you lay awake at night contemplating the best scheme for variable bindings? Neither do I. However, I have thought a bit about it recently and realized it is not as simple or obvious as I once thought. In this post I give a short introduction to the late and early binding schemes and discuss their respective advantages and disadvantages.

The first time I really programmed was a month or two into university, where I got assigned to do some array calculations in MatLab. During my first and second years, I further took two courses in Java which I found enjoyable, completing the labs when I needed a break from the other courses. At the end of my third year, I took two more programming courses (extra credit to Jonas Skeppstedt for his Algorithms & Data structures course), and from there I spiraled deeper into computer science, ending up as a PhD student. This post will be a small retrospective about what I think gave me the appetite for programming: Puzzle games!

Although spending way too much time in front of the computer, I have always been bad at typing, being both slow and having to constantly look at the keyboard. When confronted about being slow, my response was always that it did not really matter, as most time spent programming is thinking about what to write, not the actual writing. But last year I started to waver.

In the middle of a flurry of work on relaxed semantics, Henzinger et al. published the paper Quantitative Relaxation of Concurrent Data Structures in 2013. Its primary contribution is ironing out a framework for the theory of relaxed semantics. The idea is to allow incorrect transitions between states in the data structure specification while being able to associate different paths or transitions with different costs. Furthermore, they create a relaxed out-of-order stack. Here we will concisely but informally present the theory, and in the end, quickly outline the stack.

I don't think I will ever completely understand Rust lifetimes. Every time I think I get them, they come right back and hit me in the face. The other day I wanted to implement scoped variable bindings for my new programming language Zote, and it took me several hours to figure out why it did not work as I expected. So let's talk a bit about lifetimes, for both of our sakes.