compiler crimes!!

Hi there! Depending on where you look, I go by mei or Maja Kądziołka. I'm a queer weirdo who's into computers; currently an undergraduate student at the University of Warsaw. Following my contribution to the BB(5) collaboration, I'm looking for a place for myself in academia.

it's a creature! legend has it it has autism

Figure 1: me irl (artist's rendition)

My research interests include:

  • automata theory, with a recent focus on Vector Addition Systems and related models,
  • metatheory of dependent types, with a focus on unresolved theoretical questions underlying existing implementations, as well as on features which would enable usability improvements in proof assistants,
  • formalization of undecidability and computational complexity results within interactive theorem provers,
  • computational combinatorics,
  • constructive mathematics,
  • automated static analysis of machine code, with applications in reverse-engineering tooling, and
  • theoretical foundations of the Rust programming language.

I've been known to have a soft spot in my heart for e-graphs — legend has it I'm always on the look out for reasons to use one.

In the long term, I have the following primary goals:

  • help push forwards the correctness guarantees we can make at the bedrock layers of computing, by building formally verified compilers, proof assistant kernels, operating systems, hypervisors, language runtimes, and hardware;
  • improve the usability of proof assistants, to allow for their adoption by a wider group of professionals, make existing users more productive, as well as to make them a feasible medium for learning materials in mathematics and computer science.

Publications

Contact

Blog

Bruteforcing the Bitwarden master password I forgor 💀

The human mind is a fascinating thing. It's a miracle it works at all, let alone how well it does. The corollary is that sometimes it doesn't, I suppose.…

Read more

Terminating the terminal case of Linux

A response of sorts to Amos's "A terminal case of Linux", in which I explain why a short async Rust program would fail to terminate sometimes. Read more

Bootstrapping

What if all software suddenly disappeared? What's the minimum you'd need to bootstrap a practical system? I decided to start with a 512-byte seed that fits in the boot sector, and find out how far I can get.

Go to series overview

Compiling Rust is NP-hard

...though it's not the flagship borrow checking that's at fault. What I noticed, and would like to share with you today, is that the exhaustiveness checking performed by the Rust compiler on match patterns is a superset of the SAT problem.…

Read more