Tamio-Vesa Nakajima

Research Fellow at Philipps University, Marburg (2025-), in the group of Sebastian Wild

Recently defended my DPhil in CS (2021-2025), on the topic of Promise Constraint Satisfaction Problems, done under the supervision of Standa Živný, at Trinity College, Oxford.

MCompSci in CS (2017-2021) at University College, Oxford.

mail at tamionv dot ro

0000-0003-3684-9412

Research

I am currently working on Efficient Algorithms and Data Structures. During my doctorate, I studied Promise Constraint Satisfaction Problems. Before that I also worked a bit on steganography. More generally I am interested in Algorithms and Complexity.

Publications

Name Authors arXiv Conference Journal
Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa Bedert, Nakajima, Okrasa and Živný 2507.17878 focs '25 (accepted)
Complexity of approximate conflict-free, linearly-ordered, and nonmonochromatic hypergraph colourings Nakajima, Verwimp, Wrochna and Živný 2501.12062 icalp '25
Maximum And- vs. Even-SAT Nakajima and Živný 2409.07837 approx '25
A Dichotomy for Maximum PCSPs on Graphs* Nakajima and Živný 2406.20069 icalp '25
A logarithmic approximation of linearly-ordered colourings Håstad, Martinsson, Nakajima and Živný 2404.19556 approx '24 toc† (to appear)
An approximation algorithm for Maximum DiCut vs. Cut Nakajima and Živný 2402.07863
Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs Filakovský, Nakajima, Opršal, Tasinato and Wagner 2312.12981 stacs '24 toct† (accepted)
Maximum k- vs. l-colourings of graphs Nakajima and Živný 2311.00440
1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise* Ciardo, Kozik, Krokhin, Nakajima and Živný 2302.03456 lics '24 acm tocl '25
On the complexity of symmetric vs. functional PCSPs* Nakajima and Živny 2210.03343 lics '23 acm talg '24
Linearly Ordered Colourings of Hypergraphs Nakajima and Živny 2204.05628 icalp '22 acm toct '22
The Syndrome-Trellis Sampler for Generative Steganography Nakajima and Ker wifs '20
† Invited special issue. * Has previous version with other name

Honours, Awards

Academic

I was awarded a Clarendon Scholarship in order to read for a DPhil at Oxford. I was also awarded a Scholarship by Trinity College in 2024 for outstanding work in 2023-2024.

The following awards were received during my Undergraduate degree at Oxford; they are also listed here.

  • Microsoft Prize for best Computer Science project 2021 (Part C) (joint winner)
  • Hoare Prize for best overall performance in Computer Science 2020 (Part A+B)
  • bcs Prize in Computer Science 2018 for the best performance in Computer Science papers (Prelims)

Competitive programming

Contest Year Location Prize Team
ioi 2017 Tehran 🇮🇷 Gold 🥇 RO 🇷🇴
ceoi 2017 Ljubljana 🇸🇮 Gold 🥇 RO 🇷🇴
InfO(1)Cup 2017 Online Gold 🥇 RO 🇷🇴
boi 2016 Nikosia 🇨🇾 Silver 🥈 RO 🇷🇴
acm icpc wf 2018 Beijing 🇨🇳 Participation Tractor_Specialists
nwerc 2017 Bath 🇬🇧 Gold 🥇 Tractor_Specialists
hashcode wf 2020 Online Participation Rust Team
hashcode wf 2019 Dublin 🇮🇪 Participation Steaklovers
hashcode wf 2018 Dublin 🇮🇪 Participation Tractor_Specialists
rnoi 2017 Brașov 🇷🇴 Bronze 🥉 Bihor
rnoi 2016 Craiova 🇷🇴 Gold (3rd place) 🥇 Bihor
rnoi 2015 Târgoviște 🇷🇴 Silver 🥈 Bihor
rnoi 2014 Pitești 🇷🇴 Bronze 🥉 Bihor

(wf = World finals, rnoi = Romanian National Informatics Olympiad)

For more details see this and this.

Other activities

Service

On the program committee for the Theory of Computing track of synasc '24.

Reviewed for:

Project participations

Participated on

Teaching

Taught classes for Combinatorial Optimization at Oxford in 2022-2023, and in 2024-2025.

Taught tutorials for Imperative programming 1 & 2 and Imperative programming 3 at University College, Oxford in 2022.

Helped with undergraduate admission interviews for University College in 2021 and 2022, and for Exeter College in 2024.

Research seminars, etc.

Conference talks: Workshop/seminar talks: Other event participations:

Competitive programming

Deputy team leader for Romania at:

Scientific committee executive chairman for InfO(1)Cup: 2020, 2021, 2022, 2023, 2024, 2025

Scientific committee member for:

Personal details

I am Romanian, from Beiuș. I usually go by just Tamio, not Tamio-Vesa. Tamio and Nakajima are Japanese names (I have Japanese heritage on my father's side); they are written 中島 民夫 in Japanese. I also compose classical music, which I put on my youtube channel and my soundcloud.