| Towards infinite PCSP: a dichotomy for monochromatic cliques |
Banakh, Barsukov, Nakajima |
In preparation |
lics '26 (accepted) |
|
| 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 and Živný |
2507.17878 |
focs '25 |
|
| Complexity of approximate conflict-free,
linearly-ordered, and nonmonochromatic hypergraph
colourings |
Nakajima, Verwimp, Wrochna and Živný |
2501.12062
|
icalp '25 |
acm toct (accepted w/ min. revs.) |
| 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
|
acm toct '25†
|
| 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
|
|