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