[acmdblpscholarorcid]
[articlesbookschaptersthesesmisc]

A logarithmic approximation of linearlyordered colourings
(with J. Håstad, B. Martinsson, and T.V. Nakajima), submitted for publication.
arXiv: 2404.19556

Satisfiability of commutative vs. noncommutative CSPs
(with A. Bulatov)
arXiv: 2404.11709

An approximation algorithm for Maximum DiCut vs. Cut
(with T.V. Nakajima).
arXiv: 2402.07863

Maximum k vs. ℓcolourings of graphs
(with T.V. Nakajima), submitted for publication.
arXiv: 2311.00440

Algebraic approach to approximation
(with L. Barto, S. Butti, A. Kazda, and C. Viola).
arXiv: 2401.15186
An extended abstract to appear in Proceedings of LICS'24.
PDF

1in3 vs. NotAllEqual: Dichotomy of a broken promise
(with L. Ciardo, M. Kozik, A. Krokhin, and T.V. Nakajima).
arXiv: 2302.03456
An extended abstract to appear in Proceedings of LICS'24.
PDF

Solving promise equations over monoids and groups
(with A. Larrauri), submitted for journal publication.
arXiv: 2402.08434
An extended abstract to appear in Proceedings of ICALP'24.
PDF

Semidefinite programming and linear equations vs. homomorphism problems
(with L. Ciardo), submitted for journal publication.
arXiv: 2311.00882
An extended abstract appeared in Proceedings of STOC'24.
DOI: 10.1145/3618260.3649635
PDF

Counting answers to unions of conjunctive queries: natural
tractability criteria and metacomplexity
(with J. Focke, L. Goldberg, and M. Roth).
An extended abstract to appear in Proceedings of PODS'24.
arXiv: 2311.10634

A strongly polynomialtime algorithm for weighted general factors with three feasible degrees
(with S. Shao), submitted for journal publication.
arXiv: 2301.11761
An extended appeared in Proceedings of ISAAC'23.
DOI: 10.4230/LIPIcs.ISAAC.2023.57

Approximate graph colouring and the crystal with a hollow shadow
(with L. Ciardo), submitted for journal publication.
arXiv: 2211.03168
A full version of the following:

Hierarchies of minion tests for PCSPs through tensors
(with L. Ciardo), submitted for journal publication.
arXiv: 2207.02277
An extended abstract appeared in Proceedings of SODA'23.
DOI: 10.1137/1.9781611977554.ch25
PDF

Approximately counting answers to conjunctive queries with disequalities and negations
(with J. Focke, L. Goldberg, and M. Roth), submitted for journal publication.
arXiv: 2103.12468
An extended abstract appeared in Proceedings of PODS'22.
DOI: 10.1145/3517804.3526231
PDF

On the complexity of symmetric vs. functional PCSPs
(with T.V. Nakajima), ACM Trans. Algorithms, to appear.
arXiv: 2210.03343
PDF
An extended abstract (with a slightly different title) appeared in Proceedings of LICS'23.
DOI: 10.1109/LICS56636.2023.10175746
PDF

Pliability and approximating MaxCSPs
(with M. Romero and M. Wrochna),
J. ACM 70(6), Article No. 41, 2023.
DOI: 10.1145/3626515
arXiv: 1911.03204
PDF
An extended abstract (with a slightly different title) appeared in Proceedings of SODA'21.
DOI: 10.1137/1.9781611976465.29
PDF

Additive sparsification of CSPs
(with E. Pelleg),
ACM Trans. Algorithms 20(1), Article No. 1, 2024.
DOI: 10.1145/3625824
Based on (a part of) E. Pelleg's master dissertation.
arXiv: 2106.14757
PDF
An extended abstract appeared in Proceedings of ESA'21.
DOI: 10.4230/LIPIcs.ESA.2021.75
PDF

Topology and adjunction in promise constraint satisfaction
(with A. Krokhin, J. Opršal, and M. Wrochna),
SIAM J. Comput. 52(1), pp. 3879, 2023.
DOI: 10.1137/20M137822
arXiv: 2003.11351
ECCC: TR20040
PDF
A full version of a FOCS'19 paper by A. Krokhin and J. Opršal (arXiv: 1904.03214) and the following:

Improved hardness for Hcolourings of Gcolourable graphs
(with M. Wrochna).
An extended abstract appeared in Proceedings of SODA'20.
Contains small results about category theory not included in the merged journal version.
arXiv: 1907.00872
DOI: 10.1137/1.9781611975994.86
PDF

CLAP: A new algorithm for promise CSPs
(with L. Ciardo),
SIAM J. Comput. 52(1), pp. 137, 2023.
arXiv: 2107.05018
DOI: 10.1137/22M1476435
PDF
An extended abstract appeared in Proceedings of SODA'22.
DOI: 10.1137/1.9781611977073.46
PDF

PTAS for sparse generalvalued CSPs
(with B. Mezei and M. Wrochna),
ACM Trans. Algorithms 19(2), Article No. 14, 2023.
arXiv: 2012.12607
DOI: 10.1145/3569956
PDF
An extended abstract appeared in Proceedings of LICS'21.
DOI: 10.1109/LICS52264.2021.9470599
PDF

Linearly ordered colourings of hypergraphs
(with T.V. Nakajima),
ACM Trans. Comput. Theory 14(34), Article No. 12, pp. 119, 2023.
arXiv: 2204.05628
DOI: 10.1145/3570909
PDF
An extended abstract appeared in Proceedings of ICALP'22.
DOI: 10.4230/LIPIcs.ICALP.2022.128
PDF

Sparsification of monotone ksubmodular functions of low curvature
(with J. Kudla).
Based on (a part of) J. Kudla's master dissertation.
arXiv: 2302.03143
Unpublished.

Beyond PCSP(1in3,NAE)
(with A. Brandts), Inf. Comput. Volume 289, part A, 104954, 2022.
arXiv: 2104.12800
DOI: 10.1016/j.ic.2022.104954
PDF
An extended abstract appeared in Proceedings of ICALP'21.
DOI: 10.4230/LIPIcs.ICALP.2021.121
PDF

QCSP on reflexive tournaments
(with B. Larose, P. Marković, B. Martin, D. Palusma, and S. Smith),
ACM Trans. Comput. Log. 23(3), Article No. 14, 2022.
arXiv: 2104.10570
DOI: 10.1145/3508069
PDF
An extended abstract appeared in Proceedings of ESA'21.
DOI: 10.4230/LIPIcs.ESA.2021.58
PDF

The complexity of generalvalued CSPs seen from the other side
(with C. Carbonnel and M. Romero),
SIAM J. Comput. 51(1), pp. 1969, 2022.
arXiv: 1710.03148
DOI: 10.1137/19M1250121
PDF
An extended abstract appeared in Proceedings of FOCS'18.
DOI: 10.1109/FOCS.2018.00031
PDF

The SheraliAdams hierarchy for promise CSPs through tensors
(with L. Ciardo).
arXiv: 2203.02478
Unpublished.
Section 6 is subsumed by the arXiv:2211.03168 above; all other sections (apart from Section 7) are subsumed by the arXiv:2207.02277 above.

Counting homomorphisms to K_{4}minorfree graphs, modulo 2
(with J. Focke, L. Goldberg, and M. Roth),
SIAM J. Discret. Math. 35(4), pp. 27492814, 2021.
arXiv: 2006.16632
DOI: 10.1137/20M1382921
PDF
An extended abstract appeared in Proceedings of SODA'21.
DOI: 10.1137/1.9781611976465.137
PDF

The complexity of promise SAT on nonBoolean domains
(with A. Brandts and M. Wrochna),
ACM Trans. Comput. Theory 13(4), Article No. 26, pp. 120, 2021.
arXiv: 1911.09065
DOI: 10.1145/3470867
PDF
An extended abstract appeared in Proceedings of ICALP'20.
DOI: 10.4230/LIPIcs.ICALP.2020.17
PDF

On rainbowfree colourings of uniform hypergraphs
(with R. Groot Koerkamp), Theor. Comput. Sci. 885(11), pp. 6976, 2021.
Based on (a part of) R. Groot Koerkamp's master dissertation.
arXiv: 2106.07072
DOI: 10.1016/j.tcs.2021.06.022
PDF

The complexity of approximately counting retractions to squarefree graphs
(with J. Focke and L. Goldberg),
ACM Trans. Algorithms 17(3), Article No. 22, 2021.
arXiv: 1907.02319
DOI: 10.1145/3458040
PDF

The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains
(with C. Viola),
ACM Trans. Algorithms 17(3), Article No 21, 2021.
arXiv: 2007.01779
DOI: 10.1145/3458041
PDF
An extended abstract appeared in Proceedings of MFCS'20.
DOI: 10.4230/LIPIcs.MFCS.2020.85
PDF

The power of the combined basic LP and affine relaxation for promise CSPs
(with J. Brakensiek, V. Guruswami, and M. Wrochna),
SIAM J. Comput. 49(6), pp. 12321248, 2020.
arXiv: 1907.04383
ECCC: TR20004
DOI: 10.1137/20M1312745
PDF
An extension of a SODA'20 paper by J. Brakensiek and V. Guruswami.

Pointwidth and MaxCSPs
(with C. Carbonnel and M. Romero),
ACM Trans. Algorithms 16(4), Article No. 54, 2020.
arXiv: 1904.07388
DOI: 10.1145/3409447
PDF
An extended abstract appeared in Proceedings of LICS'19.
DOI: 10.1109/LICS.2019.8785660
PDF

Using a mincut generalisation to go beyond Boolean surjective VCSPs
(with G. Matl),
Algorithmica, 82, pp. 34923520, 2020.
Based on G. Matl's master dissertation.
arXiv: 1901.07107
DOI: 10.1007/s00453020007351
PDF
An extended abstract (with a slightly shorter title) appeared in Proceedings of STACS'19.
DOI: 10.4230/LIPIcs.STACS.2019.52
PDF

The complexity of approximately counting retractions
(with J. Focke and L. Goldberg), ACM Trans. Comput. Theory 12(3), Article No. 15, 2020.
arXiv: 1807.00590
DOI: 10.1145/3397472
PDF
An extended abstract appeared in Proceedings of SODA'19.
DOI: 10.1137/1.9781611975482.133
PDF

Approximate counting CSP seen from the other side
(with A. Bulatov), ACM Trans. Comput. Theory 12(2), Article No. 11, 2020.
arXiv: 1907.07922
DOI: 10.1145/3389390
PDF
An extended abstract appeared in Proceedings of MFCS'19.
DOI: 10.4230/LIPIcs.MFCS.2019.60
PDF

Sparsification of binary CSPs
(with S. Butti), SIAM J. Discret. Math. 34(1), pp. 825842, 2020.
Based on (a part of) S. Butti's master dissertation.
arXiv: 1901.00754
DOI: 10.1137/19M1242446
PDF
An extended abstract appeared in Proceedings of STACS'19.
DOI: 10.4230/LIPIcs.STACS.2019.17
PDF

Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic twospin
(with M. Backens, A. Bulatov, L. Goldberg, and C. McQuillan), J. Comput. Syst. Sci. 109, pp. 95125, 2020.
arXiv: 1804.04993
DOI: 10.1016/j.jcss.2019.12.003
PDF

Galois connections for patterns: An algebra of labelled graphs
(with D. Cohen, M. Cooper, and P. Jeavons).
Proceedings of GKR'20.
DOI: 10.1007/9783030723088_9
PDF

A tractable class of binary VCSPs via Mconvex intersection
(with H. Hirai, Y. Iwamasa, and K. Murota), ACM Trans. Algorithms 15(3), Article No. 44, 2019.
arXiv: 1801.02199
DOI: 10.1145/3329862
PDF
An extended abstract (with a slightly different title) appeared in Proceedings of STACS'18.
DOI: 10.4230/LIPIcs.STACS.2018.39
PDF

The complexity of counting surjective homomorphisms and compactions
(with J. Focke and L. Goldberg), SIAM J. Discret. Math. 33(2), pp. 10061043, 2019.
arXiv: 1706.08786
DOI: 10.1137/17M1153182
PDF
An extended abstract appeared in Proceedings of SODA'18.
DOI: 10.1137/1.9781611975031.116
PDF

On singleton arc consistency for CSPs defined by monotone patterns
(with C. Carbonnel, D. Cohen, and M. Cooper), Algorithmica 81(4), pp. 16991727, 2019.
arXiv: 1704.06215
DOI: 10.1007/s0045301804982
PDF
An extended abstract appeared in Proceedings of STACS'18.
DOI: 10.4230/LIPIcs.STACS.2018.19
PDF

Binary constraint satisfaction problems defined by excluded topological minors
(with D. Cohen, M. Cooper, and P. Jeavons), Inf. Comput. 264, pp. 1231, 2019.
arXiv: 1608.05358
DOI: 10.1016/j.ic.2018.09.013
PDF
An extended abstract (with a slightly different title) appeared in Proceedings of IJCAI'15.
LINK
PDF

The complexity of Boolean surjective generalvalued CSPs
(with P. Fulla and H. Uppman), ACM Trans. Comput. Theory 11(1), Article No. 4, 2019.
arXiv: 1702.04679
DOI: 10.1145/3282429
PDF
An extended abstract (with P. Fulla only) appeared in Proceedings of MFCS'17.
DOI: 10.4230/LIPIcs.MFCS.2017.4
PDF

The limits of SDP relaxations for generalvalued CSPs
(with J. Thapper), ACM Trans. Comput. Theory 10(3), Article No. 12, 2018.
arXiv: 1612.01147
DOI: 10.1145/3201777
PDF
An extended abstract appeared in Proceedings of LICS'17.
DOI: 10.1109/LICS.2017.8005087
PDF

Discrete convexity in joint winner property
(with Y. Iwamasa and K. Murota), Discret. Optim. 28, pp. 7888, 2018.
arXiv: 1701.07645
DOI: 10.1016/j.disopt.2018.01.001
PDF

The power of arc consistency for CSPs defined by partiallyordered forbidden patterns
(with M. Cooper), Log. Methods Comput. Sci. 13(4:26), pp. 132, 2017.
arXiv: 1604.07981
DOI: 10.23638/LMCS13(4:26)2017
PDF
An extended abstract appeared in Proceedings of LICS'16.
DOI: 10.1145/2933575.2933587
PDF

Binarisation for valued constraint satisfaction problems
(with D. Cohen, M. Cooper, P. Jeavons, A. Krokhin, and R. Powell), SIAM J. Discret. Math. 31(4), pp. 22792300, 2017.
arXiv: 1608.01628
DOI: 10.1137/16M1088107
PDF
An extended abstract (with a slightly different title and with D. Cohen, M. Cooper, and P. Jeavons only) appeared in Proceedings of AAAI'15.
LINK
PDF

The power of SheraliAdams relaxations for generalvalued CSPs
(with J. Thapper), SIAM J. Comput. 46(4), pp. 12411279, 2017.
arXiv: 1606.02577
DOI: 10.1137/16M1079245
PDF
An extended abstract (with a slightly different title) appeared in Proceedings of ICALP'15.
arXiv: 1502.05301
DOI: 10.1007/9783662476727_86
PDF

Functional clones and expressibility of partition functions
(with A. Bulatov, L. Goldberg, M. Jerrum, and D. Richerby), Theor. Comput. Sci. 687, pp. 1139, 2017.
arXiv: 1609.07377
DOI: 10.1016/j.tcs.2017.05.001
PDF

On planar valued CSPs
(with P. Fulla), J. Comput. Syst. Sci. 87, pp. 104118, 2017.
arXiv: 1602.06323
DOI: 10.1016/j.jcss.2017.03.005
PDF
An extended abstract appeared in Proceedings of MFCS'16.
DOI: 10.4230/LIPIcs.MFCS.2016.39
PDF

Backdoors into heterogeneous classes of SAT and CSP
(with S. Gaspers, N. Misra, S. Ordyniak, and S. Szeider), J. Comput. Syst. Sci. 85, pp. 3856, 2017.
arXiv: 1509.05725
DOI: 10.1016/j.jcss.2016.10.007
PDF
An extended abstract appeared in Proceedings of AAAI'14.
LINK
PDF

The complexity of finitevalued CSPs
(with J. Thapper), J. ACM 63(4), Article No. 37, 2016.
arXiv: 1210.2987
DOI: 10.1145/2974019
PDF
An extended abstract appeared in Proceedings of STOC'13.
DOI: 10.1145/2488608.2488697
PDF

Maximizing ksubmodular functions and beyond
(with J. Ward), ACM Trans. Algorithms 12(4), Article No. 47, 2016.
arXiv: 1409.1399
DOI: 10.1145/2850419
PDF
An extended abstract (with a slightly different title) appeared in Proceedings of SODA'14.
DOI: 10.1137/1.9781611973402.108
PDF

A Galois connection for weighted (relational) clones of infinite size
(with P. Fulla), ACM Trans. Comput. Theory 8(3), Article No. 9, 2016.
arXiv: 1502.05086
DOI: 10.1145/2898438
PDF
An extended abstract (with a slightly different title) appeared in Proceedings of ICALP'15.
DOI: 10.1007/9783662476727_42
PDF

Minimal weighted clones with Boolean support
(with P. Jeavons and A. Vaicenavičius), Proceedings of ISMVLâ€™16.
Based on A. Vaicenavičius' master dissertation.
DOI: 10.1109/ISMVL.2016.10
PDF

Necessary conditions for tractability of valued CSPs
(with J. Thapper), SIAM J. Discret. Math. 29(4), pp. 23612384, 2015.
arXiv: 1502.03482
DOI: 10.1137/140990346
PDF

Variable and value elimination in binary constraint satisfaction via forbidden patterns
(with D. Cohen, M. Cooper, and G. Escamocher), J. Comput. Syst. Sci. 81(7), pp. 11271143, 2015.
arXiv: 1502.03796
DOI: 10.1016/j.jcss.2015.02.001
PDF
An extended abstract (with a slightly different title) appeared in Proceedings of IJCAI'13.
LINK
PDF

The power of linear programming for generalvalued CSPs
(with V. Kolmogorov and J. Thapper), SIAM J. Comput. 44(1), pp. 136, 2015.
arXiv: 1311.4219
DOI: 10.1137/130945648
PDF
A full version of an ICALP'13 paper by V. Kolmogorov and the following:

An algebraic theory of complexity for discrete optimisation
(with D. Cohen, M. Cooper, P. Creed, and P. Jeavons), SIAM J. Comput. 42(5), pp. 19151939, 2013.
arXiv: 1207.6692
DOI: 10.1137/130906398
PDF
A full version of a CP'06 paper by D. Cohen, M. Cooper, and P. Jeavons and the following:

The complexity of conservative valued CSPs
(with V. Kolmogorov), J. ACM 60(2), Article No. 10, 2013.
arXiv: 1110.2809
DOI: 10.1145/2450142.2450146
PDF
An extended abstract appeared in Proceedings of SODA'12.
DOI: 10.1137/1.9781611973099.61
PDF
Partial results appeared on arXiv as 1008.1555 and 1008.3104.

Tractable combinations of global constraints
(with D. Cohen, P. Jeavons, and E. Thorstensen), Proceedings of CP'13.
DOI: 10.1007/9783642406270_20
PDF

Tractable triangles and crossfree convexity in discrete optimisation
(with M. Cooper), J. Artif. Intell. Res. 44, pp. 455490, 2012.
arXiv: 1401.5855
DOI: 10.1613/jair.3598
PDF
A full version of the following:

Relating proof complexity measures and practical hardness of SAT
(with M. Järvisalo, A. Matsliah, and J. Nordström), Proceedings of CP'12.
DOI: 10.1007/9783642335587_25
PDF

A characterisation of the complexity of forbidding subproblems in binary MaxCSP
(with M. Cooper and G. Escamocher), Proceedings of CP'12.
DOI: 10.1007/9783642335587_21
PDF

Hybrid tractability of valued constraint problems
(with M. Cooper), Artif. Intell. 175(910), pp. 15551569, 2011.
arXiv: 1008.4071
DOI: 10.1016/j.artint.2011.02.003
PDF
An extended abstract (with a different title) appeared in Proceedings of CP'10.
DOI: 10.1007/9783642153969_15
PDF

Classes of submodular constraints expressible by graph cuts
(with P. Jeavons), Constraints 15(3), pp. 430452, 2010.
DOI: 10.1007/s106010099078z
PDF
An extended abstract appeared in Proceedings of CP'08.
DOI: 10.1007/9783540859581_8
PDF

The expressive power of binary submodular functions
(with D. Cohen and P. Jeavons), Discret. Appl. Math. 157(15), pp. 33473358, 2009.
arXiv: 0811.1885
DOI: 10.1016/j.dam.2009.07.001
PDF
An extended abstract appeared in Proceedings of MFCS'09.
DOI: 10.1007/9783642038167_63
PDF

Structural properties of oracle classes
(single author), Inf. Process. Lett. 109(19), pp. 11311135, 2009.
DOI: 10.1016/j.ipl.2009.07.009
PDF

A note on some collapse results of valued constraints
(with B. Zanuttini), Inf. Process. Lett. 109(11), pp. 534538, 2009.
DOI: 10.1016/j.ipl.2009.01.018
PDF

Samerelation constraints
(with C. Jefferson, S. Kadioglu, K. Petrie, and M. Sellmann), Proceedings of CP'09.
DOI: 10.1007/9783642042447_38
PDF

The complexity of valued constraint models
(with P. Jeavons), Proceedings of CP'09.
DOI: 10.1007/9783642042447_64
PDF

The expressive power of valued constraints: Hierarchies and collapses
(with D. Cohen and P. Jeavons), Theor. Comput. Sci. 409(1), pp. 137153, 2008.
DOI: 10.1016/j.tcs.2008.08.036
PDF
An extended abstract appeared in Proceedings of CP'07.
DOI: 10.1007/9783540749707_57
PDF
 The Constraint Satisfaction Problem: Complexity and Approximability
(with A. Krokhin), Dagstuhl FollowUps Series, Volume 7, Schloss Dagstuhl  LeibnizZentrum fuer Informatik, 2017.
ISBN: 9783959770033
 The complexity of valued constraint satisfaction problems
(single author), Springer, 2012.
ISBN: 9783642339738
errata

Hybrid tractable classes of constraint problems
(with M. Cooper), Chapter 4 in The Constraint Satisfaction Problem: Complexity and Approximability, A. Krokhin and S. Živný (editors),
Dagstuhl FollowUps Series, Volume 7, 2017.
DOI: 10.4230/DFU.Vol7.15301.113
PDF

The complexity of valued CSPs
(with A. Krokhin), Chapter 9 in The Constraint Satisfaction Problem: Complexity and Approximability, A. Krokhin and S. Živný (editors),
Dagstuhl FollowUps Series, Volume 7, 2017.
DOI: 10.4230/DFU.Vol7.15301.233
PDF

The complexity of valued constraint satisfaction
(with P. Jeavons and A. Krokhin), Algorithmics Column of the Bulletin of EATCS, Number 113, 2155, 2014.
LINK
PDF
errata

The power of LP relaxaion for MAP inference
(with T. Werner and D. Průša), Chapter 2 in Advanced Structured Prediction, S. Nowozin, P. Gehler, J. Jancsary, and C. Lampert (editors), MIT Press, 2014.
ISBN: 9780262028370
PDF

Tractable valued constraints
(with P. Jeavons), Chapter 4 in Tractability: Practical Approaches to Hard Problemss, L. Bordeaux, Y. Hamadi, and P. Kohli (editors), Cambridge University Press, 2014.
ISBN: 9781107025196
PDF

The complexity and expressive power of valued constraints
Doctoral thesis, Department of Computer Science, University of Oxford, 2009.
ACP (Association for Constraint Programming) Doctoral Research Award 2011.
LINK
PDF

Properties of oracle classes that collapse or separate complexity classes
Master's thesis, Vrije Universiteit in Amsterdam, 2005.

Relation between accepting languages and complexity of questions on oracle
Masters's thesis, Charles University in Prague, 2005.
 Proceedings of the Doctoral Programme of the 18th CP
(cochair with M. Lombardi), 2012.
LINK
 Proceedings of the Doctoral Programme of the 16th CP
(cochair with P. Nightingale), 2010.
LINK
 Proceedings of the Student CS Conference, University of Oxford
(cochair with with S. Faily), 2008.
LINK