[acm | dblp | scholar | orcid]
[articles | books | chapters | theses | misc]
-
Optimal inapproximability of promise equations over finite groups
(with S. Butti and A. Larrauri).
[arXiv]
-
Maximum And- vs. Even-SAT
(with T.-V. Nakajima), submitted for publication.
[arXiv]
-
Maximum bipartite vs. triangle-free 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. non-commutative 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 linearly-ordered colourings
(with J. Håstad, B. Martinsson, and T.-V. Nakajima),
Proceedings of APPROX'24.
[doi | pdf | arXiv]
Invited to APPROX-RANDOM'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]
-
1-in-3 vs. Not-All-Equal: 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 meta-complexity
(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 polynomial-time 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. 26(1), Article No. 3, 2024.
[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 21(1), Article No. 8, 2024.
[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 Max-CSPs
(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. 38-79, 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 H-colourings of G-colourable 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. 1-37, 2023.
[doi | pdf | arXiv]
An extended abstract appeared in Proceedings of SODA'22.
[doi | pdf]
-
PTAS for sparse general-valued 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(3-4), Article No. 12, pp. 1-19, 2023.
[doi | pdf | arXiv]
An extended abstract appeared in Proceedings of ICALP'22.
[doi | pdf]
-
Beyond PCSP(1-in-3,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 general-valued CSPs seen from the other side
(with C. Carbonnel and M. Romero),
SIAM J. Comput. 51(1), pp. 19-69, 2022.
[doi | pdf | arXiv]
An extended abstract appeared in Proceedings of FOCS'18.
[doi | pdf]
-
Counting homomorphisms to K4-minor-free graphs, modulo 2
(with J. Focke, L. Goldberg, and M. Roth),
SIAM J. Discret. Math. 35(4), pp. 2749-2814, 2021.
[doi | pdf | arXiv]
An extended abstract appeared in Proceedings of SODA'21.
[doi | pdf]
-
The complexity of promise SAT on non-Boolean domains
(with A. Brandts and M. Wrochna),
ACM Trans. Comput. Theory 13(4), Article No. 26, pp. 1-20, 2021.
[doi | pdf | arXiv]
An extended abstract appeared in Proceedings of ICALP'20.
[doi | pdf]
-
On rainbow-free colourings of uniform hypergraphs
(with R. Groot Koerkamp), Theor. Comput. Sci. 885(11), pp. 69-76, 2021.
[doi | pdf | arXiv]
Based on (a part of) R. Groot Koerkamp's master dissertation.
-
The complexity of approximately counting retractions to square-free 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. 1232-1248, 2020.
[doi | pdf | eccc | arXiv]
An extension of a SODA'20 paper [doi | arXiv] by J. Brakensiek and V. Guruswami.
-
Point-width and Max-CSPs
(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 min-cut generalisation to go beyond Boolean surjective VCSPs
(with G. Matl),
Algorithmica, 82, pp. 3492-3520, 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. 825-842, 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 two-spin
(with M. Backens, A. Bulatov, L. Goldberg, and C. McQuillan), J. Comput. Syst. Sci. 109, pp. 95-125, 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 M-convex 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. 1006-1043, 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. 1699-1727, 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. 12-31, 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 general-valued 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 general-valued 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. 78-88, 2018.
[doi | pdf | arXiv]
-
The power of arc consistency for CSPs defined by partially-ordered forbidden patterns
(with M. Cooper), Log. Methods Comput. Sci. 13(4:26), pp. 1-32, 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. 2279-2300, 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 Sherali-Adams relaxations for general-valued CSPs
(with J. Thapper), SIAM J. Comput. 46(4), pp. 1241-1279, 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. 11-39, 2017.
[doi | pdf | arXiv]
-
On planar valued CSPs
(with P. Fulla), J. Comput. Syst. Sci. 87, pp. 104-118, 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. 38-56, 2017.
[doi | pdf | arXiv]
An extended abstract appeared in Proceedings of AAAI'14.
[doi | pdf]
-
The complexity of finite-valued 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 k-submodular 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. 2361-2384, 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. 1127-1143, 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 general-valued CSPs
(with V. Kolmogorov and J. Thapper), SIAM J. Comput. 44(1), pp. 1-36, 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. 1915-1939, 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 cross-free convexity in discrete optimisation
(with M. Cooper), J. Artif. Intell. Res. 44, pp. 455-490, 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 Max-CSP
(with M. Cooper and G. Escamocher), Proceedings of CP'12.
[doi | pdf]
-
Hybrid tractability of valued constraint problems
(with M. Cooper), Artif. Intell. 175(9-10), pp. 1555-1569, 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. 430-452, 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. 3347-3358, 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. 1131-1135, 2009.
[doi | pdf]
-
A note on some collapse results of valued constraints
(with B. Zanuttini), Inf. Process. Lett. 109(11), pp. 534-538, 2009.
[doi | pdf]
-
Same-relation 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. 137-153, 2008.
An extended abstract appeared in Proceedings of CP'07.
[doi | pdf]
- The Constraint Satisfaction Problem: Complexity and Approximability
(with A. Krokhin), Dagstuhl Follow-Ups Series, Volume 7, Schloss Dagstuhl - Leibniz-Zentrum 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 Follow-Ups 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 Follow-Ups 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, 21-55, 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 k-submodular functions of low curvature
(with J. Kudla), unpublished.
[arXiv]
Based on (a part of) J. Kudla's master dissertation.
-
The Sherali-Adams 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
(co-chair with M. Lombardi), 2012.
[link]
- Proceedings of the Doctoral Programme of the 16th CP
(co-chair with P. Nightingale), 2010.
[link]
- Proceedings of the Student CS Conference, University of Oxford
(co-chair with with S. Faily), 2008.
[link]