1.2   Research

My main research interests lie in the interplay between mathematical foundations and computation theory. The fields I am most enthusiastic about include complexity theory, computability theory, automata and formal languages and logic.

I am part of Theory Lab 5 at EDIC, the computer science department of EPFL, where I am a doctoral candidate under Mika Göös. Our group works on areas in concrete complexity theory, where we ask the following questions.

• Query Complexity: How many things do I need to look at to determine … ?
• Communication Complexity: How much do we need to talk to jointly solve … ?
• Proof Complexity: How long is the shortest proof of … ?
• Circuit Complexity: How large is the smallest circuit that computes … ?
• TFNP: For what reason can we always find a solution to … ?

Publications

1. Sign-Rank of k-Hamming Distance is Constant (FOCS 2025)
   with Mika Göös, Nathan Harms and Dmitry Sokolov.
   arχiv, ECCC, slides
   —————————————————–
   In a nutshell: Determining if two points on a cube are very close requires far less communication than everyone thought.

Once Upon a Time

1. Transfinite Context-Free Generative Grammars

Other Research Interests

Other research areas that fascinate me include

• Reverse Mathematics and New Foundations
• Non-standard Analysis
• Large Cardinal Axioms
• Automated Theorem Proving and Computer Formalisation
• Tiling Problems

I am also loosely affiliated with a research effort led by Timothy Gowers on Human Oriented Automated Theorem Proving