default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDStanislav Zivný
Standa Zivný – Stanislav Živný – Standa Živný
Person information
- unicode name: Stanislav Živný
- unicode name: Standa Živný
- affiliation: University of Oxford, Department of Computer Science, UK
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2025
[j53]Jacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Zivný:
Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations. ACM Trans. Algorithms 21(1): 8:1-8:29 (2025)- 2024
- [j52]Jacob Focke
, Leslie Ann Goldberg, Marc Roth, Stanislav Zivný:
Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity. Proc. ACM Manag. Data 2(2): 113 (2024) - [j51]Eden Pelleg, Stanislav Zivný:
Additive Sparsification of CSPs. ACM Trans. Algorithms 20(1): 1:1-1:18 (2024) - [j50]Tamio-Vesa Nakajima, Stanislav Zivný:
On the Complexity of Symmetric vs. Functional PCSPs. ACM Trans. Algorithms 20(4): 33:1-33:29 (2024) - [c60]Johan Håstad, Björn Martinsson, Tamio-Vesa Nakajima, Stanislav Zivný:
A Logarithmic Approximation of Linearly-Ordered Colourings. APPROX/RANDOM 2024: 7:1-7:6 - [c59]Alberto Larrauri, Stanislav Zivný:
Solving Promise Equations over Monoids and Groups. ICALP 2024: 146:1-146:18 - [c58]Libor Barto, Silvia Butti, Alexandr Kazda, Caterina Viola, Stanislav Zivný:
Algebraic Approach to Approximation. LICS 2024: 10:1-10:14 - [c57]Lorenzo Ciardo, Marcin Kozik, Andrei A. Krokhin, Tamio-Vesa Nakajima, Stanislav Zivný:
1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise. LICS 2024: 24:1-24:12 - [c56]Lorenzo Ciardo, Stanislav Zivný:
Semidefinite Programming and Linear Equations vs. Homomorphism Problems. STOC 2024: 1935-1943 - [i75]Libor Barto, Silvia Butti, Alexandr Kazda, Caterina Viola, Stanislav Zivný:
Algebraic Approach to Approximation. CoRR abs/2401.15186 (2024) - [i74]Tamio-Vesa Nakajima, Stanislav Zivný:
An approximation algorithm for Maximum DiCut vs. Cut. CoRR abs/2402.07863 (2024) - [i73]Alberto Larrauri, Stanislav Zivný:
Solving promise equations over monoids and groups. CoRR abs/2402.08434 (2024) - [i72]Andrei A. Bulatov, Stanislav Zivný:
Satisfiability of commutative vs. non-commutative CSPs. CoRR abs/2404.11709 (2024) - [i71]Johan Håstad, Björn Martinsson, Tamio-Vesa Nakajima, Stanislav Zivný:
A logarithmic approximation of linearly-ordered colourings. CoRR abs/2404.19556 (2024) - [i70]Lorenzo Ciardo, Stanislav Zivný:
The periodic structure of local consistency. CoRR abs/2406.19685 (2024) - [i69]Tamio-Vesa Nakajima, Stanislav Zivný:
Maximum Bipartite vs. Triangle-Free Subgraph. CoRR abs/2406.20069 (2024) - [i68]Tamio-Vesa Nakajima, Stanislav Zivný:
Maximum And- vs. Even-SAT. CoRR abs/2409.07837 (2024) - [i67]Silvia Butti, Alberto Larrauri, Stanislav Zivný:
Optimal Inapproximability of Promise Equations over Finite Groups. CoRR abs/2411.01630 (2024) - 2023
- [j49]Miguel Romero, Marcin Wrochna, Stanislav Zivný:
Pliability and Approximating Max-CSPs. J. ACM 70(6): 41:1-41:43 (2023) - [j48]Lorenzo Ciardo, Stanislav Zivný:
CLAP: A New Algorithm for Promise CSPs. SIAM J. Comput. 52(1): 1-37 (2023) - [j47]Andrei A. Krokhin, Jakub Oprsal, Marcin Wrochna, Stanislav Zivný:
Topology and Adjunction in Promise Constraint Satisfaction. SIAM J. Comput. 52(1): 38-79 (2023) - [j46]Balázs F. Mezei, Marcin Wrochna, Stanislav Zivný:
PTAS for Sparse General-valued CSPs. ACM Trans. Algorithms 19(2): 14:1-14:31 (2023) - [c55]Shuai Shao, Stanislav Zivný:
A Strongly Polynomial-Time Algorithm for Weighted General Factors with Three Feasible Degrees. ISAAC 2023: 57:1-57:17 - [c54]Tamio-Vesa Nakajima, Stanislav Zivný:
Boolean symmetric vs. functional PCSP dichotomy. LICS 2023: 1-12 - [c53]Lorenzo Ciardo, Stanislav Zivný:
Hierarchies of Minion Tests for PCSPs through Tensors. SODA 2023: 568-580 - [c52]Lorenzo Ciardo, Stanislav Zivný:
Approximate Graph Colouring and Crystals. SODA 2023: 2256-2267 - [c51]Lorenzo Ciardo, Stanislav Zivný:
Approximate Graph Colouring and the Hollow Shadow. STOC 2023: 623-631 - [i66]Shuai Shao, Stanislav Zivný:
A Strongly Polynomial-Time Algorithm for Weighted General Factors with Three Feasible Degrees. CoRR abs/2301.11761 (2023) - [i65]Jannik Kudla, Stanislav Zivný:
Sparsification of Monotone k-Submodular Functions of Low Curvature. CoRR abs/2302.03143 (2023) - [i64]Lorenzo Ciardo, Marcin Kozik, Andrei A. Krokhin, Tamio-Vesa Nakajima, Stanislav Zivný:
On the complexity of the approximate hypergraph homomorphism problem. CoRR abs/2302.03456 (2023) - [i63]Tamio-Vesa Nakajima, Stanislav Zivný:
Maximum k- vs. 𝓁-colourings of graphs. CoRR abs/2311.00440 (2023) - [i62]Lorenzo Ciardo, Stanislav Zivný:
Semidefinite programming and linear equations vs. homomorphism problems. CoRR abs/2311.00882 (2023) - [i61]Jacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Zivný:
Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity. CoRR abs/2311.10634 (2023) - 2022
- [j45]Alex Brandts, Stanislav Zivný:
Beyond PCSP(1-in-3, NAE). Inf. Comput. 289(Part): 104954 (2022) - [j44]Clément Carbonnel, Miguel Romero, Stanislav Zivný:
The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side. SIAM J. Comput. 51(1): 19-69 (2022) - [j43]Benoît Larose, Barnaby Martin, Petar Markovic, Daniël Paulusma, Siani Smith, Stanislav Zivný:
QCSP on Reflexive Tournaments. ACM Trans. Comput. Log. 23(3): 14:1-14:22 (2022) - [j42]Tamio-Vesa Nakajima, Stanislav Zivný:
Linearly Ordered Colourings of Hypergraphs. ACM Trans. Comput. Theory 14(3-4): 1-19 (2022) - [c50]Tamio-Vesa Nakajima, Stanislav Zivný:
Linearly Ordered Colourings of Hypergraphs. ICALP 2022: 128:1-128:18 - [c49]Jacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Zivný:
Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations. PODS 2022: 315-324 - [c48]Lorenzo Ciardo, Stanislav Zivný:
CLAP: A New Algorithm for Promise CSPs. SODA 2022: 1057-1068 - [i60]Lorenzo Ciardo, Stanislav Zivný:
The Sherali-Adams Hierarchy for Promise CSPs through Tensors. CoRR abs/2203.02478 (2022) - [i59]Tamio-Vesa Nakajima, Stanislav Zivný:
Linearly ordered colourings of hypergraphs. CoRR abs/2204.05628 (2022) - [i58]Lorenzo Ciardo, Stanislav Zivný:
Hierarchies of Minion Tests for PCSPs through Tensors. CoRR abs/2207.02277 (2022) - [i57]Tamio-Vesa Nakajima, Stanislav Zivný:
Boolean symmetric vs. functional PCSP dichotomy. CoRR abs/2210.03343 (2022) - [i56]Lorenzo Ciardo, Stanislav Zivný:
Approximate Graph Colouring and Crystals. CoRR abs/2210.08293 (2022) - [i55]Lorenzo Ciardo, Stanislav Zivný:
Approximate Graph Colouring and the Hollow Shadow. CoRR abs/2211.03168 (2022) - [i54]Martin Grohe, Venkatesan Guruswami, Dániel Marx, Stanislav Zivný:
The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 22201). Dagstuhl Reports 12(5): 112-130 (2022) - 2021
- [j41]Jacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Zivný:
Counting Homomorphisms to K4-Minor-Free Graphs, Modulo 2. SIAM J. Discret. Math. 35(4): 2749-2814 (2021) - [j40]Caterina Viola, Stanislav Zivný:
The Combined Basic LP and Affine IP Relaxation for Promise VCSPs on Infinite Domains. ACM Trans. Algorithms 17(3): 21:1-21:23 (2021) - [j39]Jacob Focke, Leslie Ann Goldberg, Stanislav Zivný:
The Complexity of Approximately Counting Retractions to Square-free Graphs. ACM Trans. Algorithms 17(3): 22:1-22:51 (2021) - [j38]Ragnar Groot Koerkamp, Stanislav Zivný:
On rainbow-free colourings of uniform hypergraphs. Theor. Comput. Sci. 885: 69-76 (2021) - [j37]Alex Brandts, Marcin Wrochna, Stanislav Zivný:
The Complexity of Promise SAT on Non-Boolean Domains. ACM Trans. Comput. Theory 13(4): 26:1-26:20 (2021) - [c47]Benoît Larose, Petar Markovic, Barnaby Martin, Daniël Paulusma, Siani Smith, Stanislav Zivný:
QCSP on Reflexive Tournaments. ESA 2021: 58:1-58:15 - [c46]Eden Pelleg, Stanislav Zivný:
Additive Sparsification of CSPs. ESA 2021: 75:1-75:15 - [c45]Alex Brandts, Stanislav Zivný:
Beyond PCSP(1-in-3, NAE). ICALP 2021: 121:1-121:14 - [c44]Balázs F. Mezei, Marcin Wrochna, Stanislav Zivný:
PTAS for Sparse General-Valued CSPs. LICS 2021: 1-11 - [c43]Miguel Romero, Marcin Wrochna, Stanislav Zivný:
Treewidth-Pliability and PTAS for Max-CSPs. SODA 2021: 473-483 - [c42]Jacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Zivný:
Counting Homomorphisms to K4-minor-free Graphs, modulo 2. SODA 2021: 2303-2314 - [i53]Jacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Zivný:
Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations. CoRR abs/2103.12468 (2021) - [i52]Benoît Larose, Petar Markovic, Barnaby Martin, Daniël Paulusma, Siani Smith, Stanislav Zivný:
QCSP on Reflexive Tournaments. CoRR abs/2104.10570 (2021) - [i51]Alex Brandts, Stanislav Zivný:
Beyond PCSP(1-in-3, NAE). CoRR abs/2104.12800 (2021) - [i50]Ragnar Groot Koerkamp, Stanislav Zivný:
On rainbow-free colourings of uniform hypergraphs. CoRR abs/2106.07072 (2021) - [i49]Eden Pelleg, Stanislav Zivný:
Additive Sparsification of CSPs. CoRR abs/2106.14757 (2021) - [i48]Lorenzo Ciardo, Stanislav Zivný:
CLAP: A New Algorithm for Promise CSPs. CoRR abs/2107.05018 (2021) - 2020
- [j36]Gregor Matl, Stanislav Zivný:
Using a Min-Cut Generalisation to Go Beyond Boolean Surjective VCSPs. Algorithmica 82(12): 3492-3520 (2020) - [j35]Miriam Backens, Andrei Bulatov, Leslie Ann Goldberg, Colin McQuillan, Stanislav Zivný:
Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin. J. Comput. Syst. Sci. 109: 95-125 (2020) - [j34]Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, Stanislav Zivný:
The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems. SIAM J. Comput. 49(6): 1232-1248 (2020) - [j33]Silvia Butti, Stanislav Zivný:
Sparsification of Binary CSPs. SIAM J. Discret. Math. 34(1): 825-842 (2020) - [j32]Clément Carbonnel, Miguel Romero, Stanislav Zivný:
Point-Width and Max-CSPs. ACM Trans. Algorithms 16(4): 54:1-54:28 (2020) - [j31]Andrei A. Bulatov, Stanislav Zivný:
Approximate Counting CSP Seen from the Other Side. ACM Trans. Comput. Theory 12(2): 11:1-11:19 (2020) - [j30]Jacob Focke, Leslie Ann Goldberg, Stanislav Zivný:
The Complexity of Approximately Counting Retractions. ACM Trans. Comput. Theory 12(3): 15:1-15:43 (2020) - [c41]David A. Cohen, Martin C. Cooper, Peter G. Jeavons, Stanislav Zivný:
Galois Connections for Patterns: An Algebra of Labelled Graphs. GKR 2020: 125-150 - [c40]Alex Brandts, Marcin Wrochna, Stanislav Zivný:
The Complexity of Promise SAT on Non-Boolean Domains. ICALP 2020: 17:1-17:13 - [c39]Caterina Viola, Stanislav Zivný:
The Combined Basic LP and Affine IP Relaxation for Promise VCSPs on Infinite Domains. MFCS 2020: 85:1-85:15 - [c38]Marcin Wrochna, Stanislav Zivný:
Improved hardness for H-colourings of G-colourable graphs. SODA 2020: 1426-1435 - [i47]Andrei A. Krokhin, Jakub Oprsal, Marcin Wrochna, Stanislav Zivný:
Topology and adjunction in promise constraint satisfaction. CoRR abs/2003.11351 (2020) - [i46]Jacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Zivný:
Counting Homomorphisms to K4-minor-free Graphs, modulo 2. CoRR abs/2006.16632 (2020) - [i45]Caterina Viola, Stanislav Zivný:
The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains. CoRR abs/2007.01779 (2020) - [i44]Balázs F. Mezei, Marcin Wrochna, Stanislav Zivný:
PTAS for Sparse General-Valued CSPs. CoRR abs/2012.12607 (2020) - [i43]Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, Stanislav Zivný:
The Power of the Combined Basic LP and Affine Relaxation for Promise CSPs. Electron. Colloquium Comput. Complex. TR20 (2020) - [i42]Andrei A. Krokhin, Jakub Oprsal, Marcin Wrochna, Stanislav Zivný:
Topology and adjunction in promise constraint satisfaction. Electron. Colloquium Comput. Complex. TR20 (2020)
2010 – 2019
- 2019
- [j29]Clément Carbonnel, David A. Cohen, Martin C. Cooper, Stanislav Zivný:
On Singleton Arc Consistency for CSPs Defined by Monotone Patterns. Algorithmica 81(4): 1699-1727 (2019) - [j28]David A. Cohen, Martin C. Cooper, Peter G. Jeavons, Stanislav Zivný:
Binary constraint satisfaction problems defined by excluded topological minors. Inf. Comput. 264: 12-31 (2019) - [j27]Jacob Focke, Leslie Ann Goldberg, Stanislav Zivný:
The Complexity of Counting Surjective Homomorphisms and Compactions. SIAM J. Discret. Math. 33(2): 1006-1043 (2019) - [j26]Hiroshi Hirai, Yuni Iwamasa, Kazuo Murota, Stanislav Zivný:
A Tractable Class of Binary VCSPs via M-Convex Intersection. ACM Trans. Algorithms 15(3): 44:1-44:41 (2019) - [j25]Peter Fulla, Hannes Uppman, Stanislav Zivný:
The Complexity of Boolean Surjective General-Valued CSPs. ACM Trans. Comput. Theory 11(1): 4:1-4:31 (2019) - [c37]Clément Carbonnel, Miguel Romero, Stanislav Zivný:
Point-width and Max-CSPs. LICS 2019: 1-13 - [c36]Andrei A. Bulatov, Stanislav Zivný:
Approximate Counting CSP Seen from the Other Side. MFCS 2019: 60:1-60:14 - [c35]Jacob Focke, Leslie Ann Goldberg, Stanislav Zivný:
The Complexity of Approximately Counting Retractions. SODA 2019: 2205-2215 - [c34]Silvia Butti, Stanislav Zivný:
Sparsification of Binary CSPs. STACS 2019: 17:1-17:8 - [c33]Gregor Matl, Stanislav Zivný:
Beyond Boolean Surjective VCSPs. STACS 2019: 52:1-52:15 - [i41]Silvia Butti, Stanislav Zivný:
Sparsification of Binary CSPs. CoRR abs/1901.00754 (2019) - [i40]Gregor Matl, Stanislav Zivný:
Beyond Boolean Surjective VCSPs. CoRR abs/1901.07107 (2019) - [i39]Clément Carbonnel, Miguel Romero, Stanislav Zivný:
Point-width and Max-CSPs. CoRR abs/1904.07388 (2019) - [i38]Marcin Wrochna, Stanislav Zivný:
Improved hardness for H-colourings of G-colourable graphs. CoRR abs/1907.00872 (2019) - [i37]Jacob Focke, Leslie Ann Goldberg, Stanislav Zivný:
The Complexity of Approximately Counting Retractions to Square-Free Graphs. CoRR abs/1907.02319 (2019) - [i36]Andrei A. Bulatov, Stanislav Zivný:
Approximate counting CSP seen from the other side. CoRR abs/1907.07922 (2019) - [i35]Miguel Romero, Marcin Wrochna, Stanislav Zivný:
Treewidth-Pliability and PTAS for Max-CSPs. CoRR abs/1911.03204 (2019) - [i34]Alex Brandts, Marcin Wrochna, Stanislav Zivný:
The complexity of promise SAT on non-Boolean domains. CoRR abs/1911.09065 (2019) - 2018
- [j24]Yuni Iwamasa, Kazuo Murota, Stanislav Zivný:
Discrete convexity in joint winner property. Discret. Optim. 28: 78-88 (2018) - [j23]Johan Thapper, Stanislav Zivný:
The Limits of SDP Relaxations for General-Valued CSPs. ACM Trans. Comput. Theory 10(3): 12:1-12:22 (2018) - [c32]Clément Carbonnel, Miguel Romero, Stanislav Zivný:
The Complexity of General-Valued CSPs Seen from the Other Side. FOCS 2018: 236-246 - [c31]Jacob Focke, Leslie Ann Goldberg, Stanislav Zivný:
The Complexity of Counting Surjective Homomorphisms and Compactions. SODA 2018: 1772-1781 - [c30]Clément Carbonnel, David A. Cohen, Martin C. Cooper, Stanislav Zivný:
On Singleton Arc Consistency for CSPs Defined by Monotone Patterns. STACS 2018: 19:1-19:15 - [c29]Hiroshi Hirai, Yuni Iwamasa, Kazuo Murota, Stanislav Zivný:
Beyond JWP: A Tractable Class of Binary VCSPs via M-Convex Intersection. STACS 2018: 39:1-39:14 - [i33]Hiroshi Hirai, Yuni Iwamasa, Kazuo Murota, Stanislav Zivný:
A tractable class of binary VCSPs via M-convex intersection. CoRR abs/1801.02199 (2018) - [i32]Miriam Backens, Andrei Bulatov, Leslie Ann Goldberg, Colin McQuillan, Stanislav Zivný:
Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin. CoRR abs/1804.04993 (2018) - [i31]Jacob Focke, Leslie Ann Goldberg, Stanislav Zivný:
The Complexity of Approximately Counting Retractions. CoRR abs/1807.00590 (2018) - [i30]Martin Grohe, Venkatesan Guruswami, Stanislav Zivný:
The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 18231). Dagstuhl Reports 8(6): 1-18 (2018) - 2017
- [j22]Serge Gaspers, Neeldhara Misra, Sebastian Ordyniak, Stefan Szeider, Stanislav Zivný:
Backdoors into heterogeneous classes of SAT and CSP. J. Comput. Syst. Sci. 85: 38-56 (2017) - [j21]Peter Fulla, Stanislav Zivný:
On planar valued CSPs. J. Comput. Syst. Sci. 87: 104-118 (2017) - [j20]Martin C. Cooper, Stanislav Zivný:
The Power of Arc Consistency for CSPs Defined by Partially-Ordered Forbidden Patterns. Log. Methods Comput. Sci. 13(4) (2017) - [j19]Johan Thapper, Stanislav Zivný:
The Power of Sherali-Adams Relaxations for General-Valued CSPs. SIAM J. Comput. 46(4): 1241-1279 (2017) - [j18]David A. Cohen, Martin C. Cooper, Peter G. Jeavons, Andrei A. Krokhin, Robert Powell, Stanislav Zivný:
Binarisation for Valued Constraint Satisfaction Problems. SIAM J. Discret. Math. 31(4): 2279-2300 (2017) - [j17]Andrei Bulatov, Leslie Ann Goldberg, Mark Jerrum, David Richerby, Stanislav Zivný:
Functional clones and expressibility of partition functions. Theor. Comput. Sci. 687: 11-39 (2017) - [c28]Johan Thapper, Stanislav Zivný:
The limits of SDP relaxations for general-valued CSPs. LICS 2017: 1-12 - [c27]Peter Fulla, Stanislav Zivný:
The Complexity of Boolean Surjective General-Valued CSPs. MFCS 2017: 4:1-4:14 - [p3]Martin C. Cooper, Stanislav Zivný:
Hybrid Tractable Classes of Constraint Problems. The Constraint Satisfaction Problem 2017: 113-135 - [p2]Andrei A. Krokhin, Stanislav Zivný:
The Complexity of Valued CSPs. The Constraint Satisfaction Problem 2017: 233-266 - [e1]Andrei A. Krokhin, Stanislav Zivný:
The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups 7, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2017, ISBN 978-3-95977-003-3 [contents] - [i29]Yuni Iwamasa, Kazuo Murota, Stanislav Zivný:
Discrete Convexity in Joint Winner Property. CoRR abs/1701.07645 (2017) - [i28]