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
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 |
Other activities
Service
On the program committee for the Theory of Computing track of synasc '24.
Reviewed for:
- sidma '23
- sosfem '24
- stoc '24
- csl '25
- stacs '25
- ipco '25
Project participations
Participated onTeaching
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:- wifs 2020
- bctcs 2022
- Dagstuhl Seminar 22201
- icalp 2022
- lse phd Seminar on Combinatorics, Games and Optimisation, 04/11/2022
- acid seminar, 25/04/2023
- lics 2023
- Romanian algorithm days 2023 (Talk recording here)
- csp World Congress 2023
- lics 2024
- approx 2024
- Birmingham tcs seminar, 11/10/2024
- epit 2023: Le Kaléidoscope de la Complexité
- csp World Congress 2022, 2024
- Czech Summer School on Discrete Mathematics, 2024
- lms Computer Science Colloquium 2024
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:
- boi: 2018 (Timișoara), 2022 (Bucharest)
- jboi: 2022 (Dorohoi), 2023 (Strumica)
- InfO(1)Cup: 2019
- rmi: 2020, 2021 2022 2023, 2024
- ejoi 2021
- Romanian National Olympiad in Informatics (several years)