[acm|dblp|scholar|orcid]
[articles|books|chapters|theses|misc]
-
Solving promise equations over monoids and groups
(with A. Larrauri).
arXiv: 2402.08434
-
An approximation algorithm for Maximum DiCut vs. Cut
(with T.-V. Nakajima).
arXiv: 2402.07863
-
Algebraic approach to approximation
(with L. Barto, S. Butti, A. Kazda, and C. Viola).
arXiv: 2401.15186
-
Maximum k- vs. ℓ-colourings of graphs
(with T.-V. Nakajima).
arXiv: 2311.00440
-
On the complexity of the approximate hypergraph homomorphism problem
(with L. Ciardo, M. Kozik, A. Krokhin, and T.-V. Nakajima).
arXiv: 2302.03456
-
Semidefinite programming and linear equations vs. homomorphism problems
(with L. Ciardo).
arXiv: 2311.00882
An extended abstract will appear in Proceedings of STOC'24.
PDF
-
Counting answers to unions of conjunctive queries: natural
tractability criteria and meta-complexity
(with J. Focke, L. Goldberg, and M. Roth).
An extended abstract to appear in Proceedings of PODS'24.
arXiv: 2311.10634
-
A strongly polynomial-time algorithm for weighted general factors with three feasible degrees
(with S. Shao).
arXiv: 2301.11761
An extended appeared in Proceedings of ISAAC'23.
DOI: 10.4230/LIPIcs.ISAAC.2023.57
-
Boolean symmetric vs. functional PCSP dichotomy
(with T.-V. Nakajima), submitted for journal publication.
arXiv: 2210.03343
An extended abstract appeared in Proceedings of LICS'23.
DOI: 10.1109/LICS56636.2023.10175746
PDF
-
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
-
Pliability and approximating Max-CSPs
(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. 38-79, 2023.
DOI: 10.1137/20M137822
arXiv: 2003.11351
ECCC: TR20-040
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 H-colourings of G-colourable 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. 1-37, 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 general-valued 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(3-4), Article No. 12, pp. 1-19, 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
-
Beyond PCSP(1-in-3,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 general-valued CSPs seen from the other side
(with C. Carbonnel and M. Romero),
SIAM J. Comput. 51(1), pp. 19-69, 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
-
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.
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 non-Boolean domains
(with A. Brandts and M. Wrochna),
ACM Trans. Comput. Theory 13(4), Article No. 26, pp. 1-20, 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 rainbow-free colourings of uniform hypergraphs
(with R. Groot Koerkamp), Theor. Comput. Sci. 885(11), pp. 69-76, 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 square-free 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. 1232-1248, 2020.
arXiv: 1907.04383
ECCC: TR20-004
DOI: 10.1137/20M1312745
PDF
An extension of a SODA'20 paper 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.
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 min-cut generalisation to go beyond Boolean surjective VCSPs
(with G. Matl),
Algorithmica, 82, pp. 3492-3520, 2020.
Based on G. Matl's master dissertation.
arXiv: 1901.07107
DOI: 10.1007/s00453-020-00735-1
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. 825-842, 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 two-spin
(with M. Backens, A. Bulatov, L. Goldberg, and C. McQuillan), J. Comput. Syst. Sci. 109, pp. 95-125, 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/978-3-030-72308-8_9
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.
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. 1006-1043, 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. 1699-1727, 2019.
arXiv: 1704.06215
DOI: 10.1007/s00453-018-0498-2
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. 12-31, 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 general-valued 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 general-valued 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. 78-88, 2018.
arXiv: 1701.07645
DOI: 10.1016/j.disopt.2018.01.001
PDF
-
The power of arc consistency for CSPs defined by partially-ordered forbidden patterns
(with M. Cooper), Logical Methods in Computer Science 13(4:26), pp. 1-32, 2017.
arXiv: 1604.07981
DOI: 10.23638/LMCS-13(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. 2279-2300, 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 Sherali-Adams relaxations for general-valued CSPs
(with J. Thapper), SIAM J. Comput. 46(4), pp. 1241-1279, 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/978-3-662-47672-7_86
PDF
-
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.
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. 104-118, 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. 38-56, 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 finite-valued 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 k-submodular 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/978-3-662-47672-7_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. 2361-2384, 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. 1127-1143, 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 general-valued CSPs
(with V. Kolmogorov and J. Thapper), SIAM J. Comput. 44(1), pp. 1-36, 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. 1915-1939, 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/978-3-642-40627-0_20
PDF
-
Tractable triangles and cross-free convexity in discrete optimisation
(with M. Cooper), J. Artif. Intell. Res. 44, pp. 455-490, 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/978-3-642-33558-7_25
PDF
-
A characterisation of the complexity of forbidding subproblems in binary Max-CSP
(with M. Cooper and G. Escamocher), Proceedings of CP'12.
DOI: 10.1007/978-3-642-33558-7_21
PDF
-
Hybrid tractability of valued constraint problems
(with M. Cooper), Artif. Intell. 175(9-10), pp. 1555-1569, 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/978-3-642-15396-9_15
PDF
-
Classes of submodular constraints expressible by graph cuts
(with P. Jeavons), Constraints 15(3), pp. 430-452, 2010.
DOI: 10.1007/s10601-009-9078-z
PDF
An extended abstract appeared in Proceedings of CP'08.
DOI: 10.1007/978-3-540-85958-1_8
PDF
-
The expressive power of binary submodular functions
(with D. Cohen and P. Jeavons), Discret. Appl. Math. 157(15), pp. 3347-3358, 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/978-3-642-03816-7_63
PDF
-
Structural properties of oracle classes
(single author), Inf. Process. Lett. 109(19), pp. 1131-1135, 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. 534-538, 2009.
DOI: 10.1016/j.ipl.2009.01.018
PDF
-
Same-relation constraints
(with C. Jefferson, S. Kadioglu, K. Petrie, and M. Sellmann), Proceedings of CP'09.
DOI: 10.1007/978-3-642-04244-7_38
PDF
-
The complexity of valued constraint models
(with P. Jeavons), Proceedings of CP'09.
DOI: 10.1007/978-3-642-04244-7_64
PDF
-
The expressive power of valued constraints: Hierarchies and collapses
(with D. Cohen and P. Jeavons), Theor. Comput. Sci. 409(1), pp. 137-153, 2008.
DOI: 10.1016/j.tcs.2008.08.036
PDF
An extended abstract appeared in Proceedings of CP'07.
DOI: 10.1007/978-3-540-74970-7_57
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: 978-3-95977-003-3
- The complexity of valued constraint satisfaction problems
(single author), Springer, 2012.
ISBN: 978-3-642-33973-8
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: 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 Follow-Ups 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, 21-55, 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.
-
Sparsification of monotone k-submodular functions of low curvature
(with J. Kudla).
Based on (a part of) J. Kudla's master dissertation.
arXiv: 2302.03143
-
The Sherali-Adams 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.
- 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