Tamio-Vesa Nakajima

Doing a DPhil in CS (2021-) at Trinity College, Oxford.

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

tamio dash vesa dot nakajima at cs dot ox dot ac dot uk

0000-0003-3684-9412

Research

My main interest is in Promise Constraint Satisfaction Problems, which I research together with my supervisor Standa Živný. In the past I also worked a bit on steganography. More generally I am interested in Algorithms and Complexity.

Publications

Name Authors arXiv Conference Journal
Complexity of approximate conflict-free, linearly-ordered, and nonmonochromatic hypergraph colourings Nakajima, Verwimp, Wrochna and Živný 2501.12062 icalp '25 (accepted)
Maximum And- vs. Even-SAT Nakajima and Živný 2409.07837
Maximum Bipartite vs. Triangle-Free Subgraph Nakajima and Živný 2406.20069 icalp '25 (accepted)
A logarithmic approximation of linearly-ordered colourings Håstad, Martinsson, Nakajima and Živný 2404.19556 approx '24
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
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

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 🇷🇴
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)

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.

Presented at: Participated in:

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. I also compose classical music, which I put on my youtube channel.

This website uses Libertinus and Inconsolata. The licenses for these fonts can be found here and here