[acm  dblp  scholar  orcid]
[articles  books  chapters  theses  misc]

Maximum And vs. EvenSAT
(with T.V. Nakajima), submitted for publication.
[arXiv]

Maximum bipartite vs. trianglefree subgraph
(with T.V. Nakajima), submitted for publication.
[arXiv]

The periodic structure of local consistency
(with L. Ciardo), submitted for publication.
[arXiv]

Satisfiability of commutative vs. noncommutative CSPs
(with A. Bulatov), submitted for publication.
[arXiv]

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

A logarithmic approximation of linearlyordered colourings
(with J. Håstad, B. Martinsson, and T.V. Nakajima),
Proceedings of APPROX'24.
[doi  pdf  arXiv]
Invited to APPROXRANDOM'24 Theory Comput. special issue.

Algebraic approach to approximation
(with L. Barto, S. Butti, A. Kazda, and C. Viola).
[arXiv]
An extended abstract appeared in Proceedings of LICS'24.
[doi  pdf]

1in3 vs. NotAllEqual: Dichotomy of a broken promise
(with L. Ciardo, M. Kozik, A. Krokhin, and T.V. Nakajima),
Proceedings of LICS'24.
[doi  pdf  arXiv]

Semidefinite programming and linear equations vs. homomorphism problems
(with L. Ciardo), submitted for journal publication.
[arXiv]
An extended abstract appeared in Proceedings of STOC'24.
[doi  pdf]

Counting answers to unions of conjunctive queries: natural tractability criteria and metacomplexity
(with J. Focke, L. Goldberg, and M. Roth), submitted for journal publication.
[arXiv]
An extended abstract appeared in Proceedings of PODS'24.
[doi  pdf]

A strongly polynomialtime algorithm for weighted general factors with three feasible degrees
(with S. Shao), submitted for journal publication.
[arXiv]
An extended appeared in Proceedings of ISAAC'23.
[doi  pdf]

Approximate graph colouring and the crystal with a hollow shadow
(with L. Ciardo), submitted for journal publication.
[arXiv]
A full version of two extended abstracts:

Approximate graph colouring and the hollow shadow
(with L. Ciardo), Proceedings of STOC'23.
[doi  pdf  arXiv]

Approximate graph colouring and crystals
(with L. Ciardo), Proceedings of SODA'23.
[doi  pdf  arXiv]

Hierarchies of minion tests for PCSPs through tensors
(with L. Ciardo), submitted for journal publication.
[arXiv]
An extended abstract appeared in Proceedings of SODA'23.
[doi  pdf]

Solving promise equations over monoids and groups
(with A. Larrauri),
ACM Trans. Comput. Log.
[doi  pdf  arXiv]
An extended abstract appeared in Proceedings of ICALP'24.
[doi  pdf]

Approximately counting answers to conjunctive queries with disequalities and negations
(with J. Focke, L. Goldberg, and M. Roth), ACM Trans. Algorithms.
[doi  pdf  arXiv]
An extended abstract appeared in Proceedings of PODS'22.
[doi  pdf]

On the complexity of symmetric vs. functional PCSPs
(with T.V. Nakajima), ACM Trans. Algorithms 20(4), Article No. 33, 2024.
[doi  pdf  arXiv]
An extended abstract (with a slightly different title) appeared in Proceedings of LICS'23.
[doi  pdf]

Pliability and approximating MaxCSPs
(with M. Romero and M. Wrochna),
J. ACM 70(6), Article No. 41, 2023.
[doi  pdf  arXiv]
An extended abstract (with a slightly different title) appeared in Proceedings of SODA'21.
[doi  pdf]

Additive sparsification of CSPs
(with E. Pelleg),
ACM Trans. Algorithms 20(1), Article No. 1, 2024.
[doi  pdf  arXiv]
An extended abstract appeared in Proceedings of ESA'21.
[doi  pdf]
Based on (a part of) E. Pelleg's master dissertation.

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  pdf  eccc  arXiv]
A full version of two extended abstracts, a FOCS'19 paper [doi  arXiv] by A. Krokhin and J. Opršal and the following:

Improved hardness for Hcolourings of Gcolourable graphs
(with M. Wrochna),
Proceedings of SODA'20.
[doi  pdf  arXiv]
Contains small results about category theory not included in the merged journal version.

CLAP: A new algorithm for promise CSPs
(with L. Ciardo),
SIAM J. Comput. 52(1), pp. 137, 2023.
[doi  pdf  arXiv]
An extended abstract appeared in Proceedings of SODA'22.
[doi  pdf]

PTAS for sparse generalvalued CSPs
(with B. Mezei and M. Wrochna),
ACM Trans. Algorithms 19(2), Article No. 14, 2023.
[doi  pdf  arXiv]
An extended abstract appeared in Proceedings of LICS'21.
[doi  pdf]

Linearly ordered colourings of hypergraphs
(with T.V. Nakajima),
ACM Trans. Comput. Theory 14(34), Article No. 12, pp. 119, 2023.
[doi  pdf  arXiv]
An extended abstract appeared in Proceedings of ICALP'22.
[doi  pdf]

Beyond PCSP(1in3,NAE)
(with A. Brandts), Inf. Comput. Volume 289, part A, 104954, 2022.
[doi  pdf  arXiv]
An extended abstract appeared in Proceedings of ICALP'21.
[doi  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.
[doi  pdf  arXiv]
An extended abstract appeared in Proceedings of ESA'21.
[doi  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.
[doi  pdf  arXiv]
An extended abstract appeared in Proceedings of FOCS'18.
[doi  pdf]

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.
[doi  pdf  arXiv]
An extended abstract appeared in Proceedings of SODA'21.
[doi  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.
[doi  pdf  arXiv]
An extended abstract appeared in Proceedings of ICALP'20.
[doi  pdf]

On rainbowfree colourings of uniform hypergraphs
(with R. Groot Koerkamp), Theor. Comput. Sci. 885(11), pp. 6976, 2021.
[doi  pdf  arXiv]
Based on (a part of) R. Groot Koerkamp's master dissertation.

The complexity of approximately counting retractions to squarefree graphs
(with J. Focke and L. Goldberg),
ACM Trans. Algorithms 17(3), Article No. 22, 2021.
[doi  pdf  arXiv]

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.
[doi  pdf  arXiv]
An extended abstract appeared in Proceedings of MFCS'20.
[doi  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.
[doi  pdf  eccc  arXiv]
An extension of a SODA'20 paper [doi  arXiv] by J. Brakensiek and V. Guruswami.

Pointwidth and MaxCSPs
(with C. Carbonnel and M. Romero),
ACM Trans. Algorithms 16(4), Article No. 54, 2020.
[doi  pdf  arXiv]
An extended abstract appeared in Proceedings of LICS'19.
[doi  pdf]

Using a mincut generalisation to go beyond Boolean surjective VCSPs
(with G. Matl),
Algorithmica, 82, pp. 34923520, 2020.
[doi  pdf  arXiv]
An extended abstract (with a slightly different title) appeared in Proceedings of STACS'19.
[doi  pdf]
Based on G. Matl's master dissertation.

The complexity of approximately counting retractions
(with J. Focke and L. Goldberg), ACM Trans. Comput. Theory 12(3), Article No. 15, 2020.
[doi  pdf  arXiv]
An extended abstract appeared in Proceedings of SODA'19.
[doi  pdf]

Approximate counting CSP seen from the other side
(with A. Bulatov), ACM Trans. Comput. Theory 12(2), Article No. 11, 2020.
[doi  pdf  arXiv]
An extended abstract appeared in Proceedings of MFCS'19.
[doi  pdf]

Sparsification of binary CSPs
(with S. Butti), SIAM J. Discret. Math. 34(1), pp. 825842, 2020.
[doi  pdf  arXiv]
An extended abstract appeared in Proceedings of STACS'19.
[doi  pdf]
Based on (a part of) S. Butti's master dissertation.

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.
[doi  pdf  arXiv]

Galois connections for patterns: An algebra of labelled graphs
(with D. Cohen, M. Cooper, and P. Jeavons),
Proceedings of GKR'20.
[doi  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.
[doi  pdf  arXiv]
An extended abstract (with a slightly different title) appeared in Proceedings of STACS'18.
[doi  pdf]

The complexity of counting surjective homomorphisms and compactions
(with J. Focke and L. Goldberg), SIAM J. Discret. Math. 33(2), pp. 10061043, 2019.
[doi  pdf  arXiv]
An extended abstract appeared in Proceedings of SODA'18.
[doi  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.
[doi  pdf  arXiv]
An extended abstract appeared in Proceedings of STACS'18.
[doi  pdf]

Binary constraint satisfaction problems defined by excluded topological minors
(with D. Cohen, M. Cooper, and P. Jeavons), Inf. Comput. 264, pp. 1231, 2019.
[doi  pdf  arXiv]
An extended abstract (with a slightly different title) appeared in Proceedings of IJCAI'15.
[doi  pdf]

The complexity of Boolean surjective generalvalued CSPs
(with P. Fulla and H. Uppman), ACM Trans. Comput. Theory 11(1), Article No. 4, 2019.
[doi  pdf  arXiv]
An extended abstract (with P. Fulla only) appeared in Proceedings of MFCS'17.
[doi  pdf]

The limits of SDP relaxations for generalvalued CSPs
(with J. Thapper), ACM Trans. Comput. Theory 10(3), Article No. 12, 2018.
[doi  pdf  arXiv]
An extended abstract appeared in Proceedings of LICS'17.
[doi  pdf]

Discrete convexity in joint winner property
(with Y. Iwamasa and K. Murota), Discret. Optim. 28, pp. 7888, 2018.
[doi  pdf  arXiv]

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.
[doi  pdf  arXiv]
An extended abstract appeared in Proceedings of LICS'16.
[doi  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.
[doi  pdf  arXiv]
An extended abstract (with a slightly different title and with D. Cohen, M. Cooper, and P. Jeavons only) appeared in Proceedings of AAAI'15.
[doi  pdf]

The power of SheraliAdams relaxations for generalvalued CSPs
(with J. Thapper), SIAM J. Comput. 46(4), pp. 12411279, 2017.
[doi  pdf  arXiv]
An extended abstract (with a slightly different title) appeared in Proceedings of ICALP'15.
[doi  pdf  arXiv]

Functional clones and expressibility of partition functions
(with A. Bulatov, L. Goldberg, M. Jerrum, and D. Richerby), Theor. Comput. Sci. 687, pp. 1139, 2017.
[doi  pdf  arXiv]

On planar valued CSPs
(with P. Fulla), J. Comput. Syst. Sci. 87, pp. 104118, 2017.
[doi  pdf  arXiv]
An extended abstract appeared in Proceedings of MFCS'16.
[doi  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.
[doi  pdf  arXiv]
An extended abstract appeared in Proceedings of AAAI'14.
[doi  pdf]

The complexity of finitevalued CSPs
(with J. Thapper), J. ACM 63(4), Article No. 37, 2016.
[doi  pdf  arXiv]
An extended abstract appeared in Proceedings of STOC'13.
[doi  pdf]

Maximizing ksubmodular functions and beyond
(with J. Ward), ACM Trans. Algorithms 12(4), Article No. 47, 2016.
[doi  pdf  arXiv]
An extended abstract (with a slightly different title) appeared in Proceedings of SODA'14.
[doi  pdf]

A Galois connection for weighted (relational) clones of infinite size
(with P. Fulla), ACM Trans. Comput. Theory 8(3), Article No. 9, 2016.
[doi  pdf  arXiv]
An extended abstract (with a slightly different title) appeared in Proceedings of ICALP'15.
[doi  pdf]

Minimal weighted clones with Boolean support
(with P. Jeavons and A. Vaicenavičius), Proceedings of ISMVLâ€™16.
[doi  pdf]
Based on A. Vaicenavičius' master dissertation.

Necessary conditions for tractability of valued CSPs
(with J. Thapper), SIAM J. Discret. Math. 29(4), pp. 23612384, 2015.
[doi  pdf  arXiv]

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.
[doi  pdf  arXiv]
An extended abstract (with a slightly different title) appeared in Proceedings of IJCAI'13.
[doi  pdf]

The power of linear programming for generalvalued CSPs
(with V. Kolmogorov and J. Thapper), SIAM J. Comput. 44(1), pp. 136, 2015.
[doi  pdf  arXiv]
A full version of two extended abstracts, an ICALP'13 paper [doi  arXiv] by V. Kolmogorov and the following:

The power of linear programming for valued CSPs
(with J. Thapper),
Proceedings of FOCS'12.
[doi  pdf  arXiv]

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.
[doi  pdf  arXiv]
A full version of three extended abstracts, a CP'06 paper [doi] by D. Cohen, M. Cooper, and P. Jeavons and the following:

An algebraic theory of complexity for valued constraints: Establishing a Galois connection
(with D. Cohen, P. Creed, and P. Jeavons), Proceedings of MFCS'11.
[doi  pdf]

On minimal weighted clones
(with P. Creed), Proceedings of CP'11.
[doi  pdf]

The complexity of conservative valued CSPs
(with V. Kolmogorov), J. ACM 60(2), Article No. 10, 2013.
[doi  pdf  arXiv]
An extended abstract appeared in Proceedings of SODA'12.
[doi  pdf]
Partial results appeared on arXiv as arXiv:1008.1555 and arXiv:1008.3104.

Tractable combinations of global constraints
(with D. Cohen, P. Jeavons, and E. Thorstensen), Proceedings of CP'13.
[doi  pdf]

Tractable triangles and crossfree convexity in discrete optimisation
(with M. Cooper), J. Artif. Intell. Res. 44, pp. 455490, 2012.
[doi  pdf  arXiv]
A full version of two extended abstracts:

Hierarchically nested convex VCSP
(with M. Cooper), Proceedings of CP'11.
[doi  pdf]

Tractable triangles
(with M. Cooper), Proceedings of CP'11.
[doi  pdf]

Relating proof complexity measures and practical hardness of SAT
(with M. Järvisalo, A. Matsliah, and J. Nordström), Proceedings of CP'12.
[doi  pdf]

A characterisation of the complexity of forbidding subproblems in binary MaxCSP
(with M. Cooper and G. Escamocher), Proceedings of CP'12.
[doi  pdf]

Hybrid tractability of valued constraint problems
(with M. Cooper), Artif. Intell. 175(910), pp. 15551569, 2011.
[doi  pdf  arXiv]
An extended abstract (with a different title) appeared in Proceedings of CP'10.
[doi  pdf]

Classes of submodular constraints expressible by graph cuts
(with P. Jeavons), Constraints 15(3), pp. 430452, 2010.
[doi  pdf]
An extended abstract appeared in Proceedings of CP'08.
[doi  pdf]

The expressive power of binary submodular functions
(with D. Cohen and P. Jeavons), Discret. Appl. Math. 157(15), pp. 33473358, 2009.
[doi  pdf  arXiv]
An extended abstract appeared in Proceedings of MFCS'09.
[doi  pdf]

Structural properties of oracle classes
Inf. Process. Lett. 109(19), pp. 11311135, 2009.
[doi  pdf]

A note on some collapse results of valued constraints
(with B. Zanuttini), Inf. Process. Lett. 109(11), pp. 534538, 2009.
[doi  pdf]

Samerelation constraints
(with C. Jefferson, S. Kadioglu, K. Petrie, and M. Sellmann),
Proceedings of CP'09.
[doi  pdf]

The complexity of valued constraint models
(with P. Jeavons), Proceedings of CP'09.
[doi  pdf]

The expressive power of valued constraints: Hierarchies and collapses
[doi  pdf]
(with D. Cohen and P. Jeavons), Theor. Comput. Sci. 409(1), pp. 137153, 2008.
An extended abstract appeared in Proceedings of CP'07.
[doi  pdf]
 The Constraint Satisfaction Problem: Complexity and Approximability
(with A. Krokhin), Dagstuhl FollowUps Series, Volume 7, Schloss Dagstuhl  LeibnizZentrum fuer Informatik, 2017.
[isbn]
 The complexity of valued constraint satisfaction problems
Springer, 2012.
[isbn  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  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  pdf]

The complexity of valued constraint satisfaction
(with P. Jeavons and A. Krokhin), Algorithmics Column of the Bulletin of EATCS, Number 113, 2155, 2014.
[doi  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  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  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 dissertation, Vrije Universiteit in Amsterdam, 2005.

Relation between accepting languages and complexity of questions on oracle
Master's dissertation, Charles University in Prague, 2005.

An approximation algorithm for maximum dicut vs. cut
(with T.V. Nakajima), unpublished.
[arXiv]
Subsumed by the this paper above.

Sparsification of monotone ksubmodular functions of low curvature
(with J. Kudla), unpublished.
[arXiv]
Based on (a part of) J. Kudla's master dissertation.

The SheraliAdams hierarchy for promise CSPs through tensors
(with L. Ciardo), unpublished.
[arXiv]
Section 6 is subsumed by the this paper above; all other sections (apart from Section 7) are subsumed by this paper above.
 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]