Publications of Standa Živný

[acm | dblp | scholar | orcid]

[articles | books | chapters | theses | misc]

Research Articles

• 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.  [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 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 K₄-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]
  

Books

• 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]
  

Book Chapters

• 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]
  

Theses

• 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.

Miscellaneous

• 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]