Strings over Σ

Linux: The good, the bad and the ugly

I’ve been working on system-level software for Linux for some time now, which is a job that makes you much more likely to encounter the odd corner of an operating system…

Automatic Org-Mode

With the unprecedented en vogue¹ right now, I have taken the unprecedented step of trying out Emacs after having been a loyal Vim user for years. This is not going to be…

Analysing regexp with Golang

programming

DISCLAIMER: Let me say this first. Google’s regular expression implementations are known for not implementing features that make them, well, not regular. Both re2 and…

More Turing Completeness, or: Somebody is wrong on the Internet

computer-science

Hello, I am Florian and you might remember me from posts such as Turing Completeness. Today I am going to return to the topic of Turing Completeness, in a post in similar…

Fun with Operator Overloading

python

The other day I was asked to take a look at code I had written years ago that basically allowed the user to build up logical formulas while always keeping them in CNF…

Completeness and decidability

logic

The subtle difference between incompleteness (of a theory), completeness (of a proof system) and indecidability (of a logical system) are a common source of confusion. How…

A Paper a Whatever #15: Keystroke Recognition Using WiFi Signals

apaw

This paper is about detecting a user’s keypresses using the interference the movements of the fingers cause in WiFi signals. This sounds scary and like something out of a…

Turing Completeness

theoretical-cs

This is one of my pet peeves: I have heard many people describe Turing-complete as “a language you can do everything with”. That is untrue and this is a very short post to…

A Paper a Week-ish #14: GraphLab: A New Framework for Parallel Machine Learning

apaw

It has been a long time since I last posted one of those, apologies! I have been fairly busy with various things and the time I had for this blog I spent on non…

Using theorem proving to cheat in logic puzzles

logic

I recently got the book What is the Name of this Book? by the excellent Raymon Smullyan, who is also the author of a book about Gödel’s Incompleteness Theorems I could not…

Theorem Proving in Haskell

programming

For some reason that is not completely clear to me either, I decided to go about and implement the sequent calculus technique for theorem proving this weekend. Because that…

A Paper a Week-ish #13: Propositions as Types

apaw

Even though week-ish is an intentionally vague concept, I should apologize for this week-ish to take particularly long. The last month has been very busy and exhausting for…

A Paper a Week-ish #12: Arithmetical Hierarchy and Complexity of Computation

apaw

The paper in question covers something that I have been meaning to read up for months: the arithmetical hierarchy, which was sadly not covered in the university courses I…

A Paper a Week-ish #11: Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services

apaw

This paper was more discovered than chosen. I decided to write this week-ish’s post sitting in a train without Internet connection, so I scanned my Download folder for the…

A Paper a Week-ish #10: In Search of an Understandable Consensus Algorithm

apaw

I have been meaning to read this paper for quite some time, but for some reason, even though its entire point is proposing an understandable consensus algorithm, Paxos’ (the…

A Paper a Week-ish #9: Two Simplified Algorithms for Maintaining Order in a List

apaw

Looking around for papers to cover in this series, I remember a talk about folding algorithms one Erik Demaine gave at my former university as the annual Vienna Gödel…

A Paper a Week-ish #8: Reflections on Trusting Trust

apaw

So, I feel like cheating a bit again as this paper is only three pages long, but I guess it is an ACM Turing Award lecture paper, so it deserves a spot here, at least for…

A Paper a Week-ish #7: The Complexity of Theorem-Proving Procedures

apaw

First of all, sorry for the delay! I have moved this weekend (with a few complications) and am currently without Internet at home, and Three are actively trying to prevent…

A Paper a Week #6: Differential Privacy

apaw

First, I will, for the coming few weeks, reduce the frequency of these posts to one a fortnight – for one, fortnight is an amazing word, and also I am rather busy with…

A Paper a Week #5: Temporal Synchronization of multiple Audio Signals

apaw

This week’s paper was published by Google and concerns itself with finding methods of combining overlapping audio streams that were recorded from different locations, which…

A Paper a Week #4: Parameterized Model Checking of Fault-tolerant Distributed Algorithms by Abstraction

apaw

First of all, sorry for this post being delayed. But with moving to London and starting a new job, I guess it is not the worst week to give myself a break. Anyway, while…

A Paper a Week #3: SoundWave: Using the Doppler Effect to Sense Gestures

apaw

I almost feel like I cheated by picking such a short paper – it has been a busy week, though. As the paper is only 4 pages long, this post won’t be particularly long, either.

A Paper a Week #2: DPLL(T): Fast Decision Procedures

apaw

If you are not interested in reading about I paper I meant to read and cover here but eventually gave up doing so, skip the next two paragraphs.

A Paper a Week #1: OpenJDK’s java.util.Collection.sort() is broken: The good, the bad and the worst case

apaw

I’m planning to read at least one paper a week about computer science or logic related topics and comment a bit on this blog. This is the first post in the series (let’s see…