Standa Živný : Publications

Books

• [1]

  The complexity of valued constraint satisfaction problems

  Stanislav Živný

  Springer. 2012.

  Details about The complexity of valued constraint satisfaction problems | BibTeX data for The complexity of valued constraint satisfaction problems | DOI (10.1007/978-3-642-33974-5)

Journal papers

• [1]

  The complexity of valued constraint satisfaction

  Peter Jeavons‚ Andrei Krokhin and Stanislav Živný

  In Bulletin of the European Association for Theoretical Computer Science (EATCS). Vol. 113. Pages 21−55. 2014.

  Errata can be found here.

  Details about The complexity of valued constraint satisfaction | BibTeX data for The complexity of valued constraint satisfaction | Link to The complexity of valued constraint satisfaction

• [2]

  An algebraic theory of complexity for discrete optimisation

  David A. Cohen‚ Martin C. Cooper‚ Páidí Creed‚ Peter Jeavons and Stanislav Živný

  In SIAM Journal on Computing. Vol. 42. No. 5. Pages 1915−1939. 2013.

  Details about An algebraic theory of complexity for discrete optimisation | BibTeX data for An algebraic theory of complexity for discrete optimisation | DOI (10.1137/130906398) | Download (pdf) of An algebraic theory of complexity for discrete optimisation

• [3]

  The complexity of conservative valued CSPs

  Vladimir Kolmogorov and Stanislav Živný

  In Journal of the ACM. Vol. 60. No. 2. 2013.

  Article No. 10

  Details about The complexity of conservative valued CSPs | BibTeX data for The complexity of conservative valued CSPs | DOI (10.1145/2450142.2450146) | Download (pdf) of The complexity of conservative valued CSPs

• [4]

  Tractable triangles and cross−free convexity in discrete optimisation

  Martin C. Cooper and Stanislav Živný

  In Journal of Artificial Intelligence Research. Vol. 44. Pages 455–490. 2012.

  Details about Tractable triangles and cross−free convexity in discrete optimisation | BibTeX data for Tractable triangles and cross−free convexity in discrete optimisation | DOI (10.1613/jair.3598) | Download (pdf) of Tractable triangles and cross−free convexity in discrete optimisation

• [5]

  Hybrid tractability of valued constraint problems

  Martin C. Cooper and Stanislav Živný

  In Artificial Intelligence. Vol. 175. No. 9−10. Pages 1555−1569. 2011.

  Details about Hybrid tractability of valued constraint problems | BibTeX data for Hybrid tractability of valued constraint problems | DOI (10.1016/j.artint.2011.02.003) | Download (pdf) of Hybrid tractability of valued constraint problems

• [6]

  Classes of Submodular Constraints Expressible by Graph Cuts

  Stanislav Živný and Peter G. Jeavons

  In Constraints. Vol. 15. No. 3. Pages 430−452. 2010.

  Details about Classes of Submodular Constraints Expressible by Graph Cuts | BibTeX data for Classes of Submodular Constraints Expressible by Graph Cuts | DOI (10.1007/s10601-009-9078-z) | Download (pdf) of Classes of Submodular Constraints Expressible by Graph Cuts

• [7]

  The Expressive Power of Binary Submodular Functions

  Stanislav Živný‚ David A. Cohen and Peter G. Jeavons

  In Discrete Applied Mathematics. Vol. 157. No. 15. Pages 3347–3358. 2009.

  Details about The Expressive Power of Binary Submodular Functions | BibTeX data for The Expressive Power of Binary Submodular Functions | DOI (10.1016/j.dam.2009.07.001) | Download (pdf) of The Expressive Power of Binary Submodular Functions

• [8]

  Structural properties of oracle classes

  Stanislav Živný

  Vol. 109. No. 19. Pages 1131–1135. 2009.

  Details about Structural properties of oracle classes | BibTeX data for Structural properties of oracle classes | DOI (10.1016/j.ipl.2009.07.009) | Download (pdf) of Structural properties of oracle classes

• [9]

  A note on some collapse results of valued constraints

  Bruno Zanuttini and Stanislav Živný

  In Information Processing Letters. Vol. 109. No. 11. Pages 534–538. 2009.

  Details about A note on some collapse results of valued constraints | BibTeX data for A note on some collapse results of valued constraints | DOI (10.1016/j.ipl.2009.01.018) | Download (pdf) of A note on some collapse results of valued constraints

• [10]

  The expressive power of valued constraints: Hierarchies and collapses

  David A. Cohen‚ Peter G. Jeavons and Stanislav Živný

  In Theoretical Computer Science. Vol. 409. No. 1. Pages 137–153. 2008.

  Details about The expressive power of valued constraints: Hierarchies and collapses | BibTeX data for The expressive power of valued constraints: Hierarchies and collapses | DOI (10.1016/j.tcs.2008.08.036) | Download (pdf) of The expressive power of valued constraints: Hierarchies and collapses

Conference papers

• [1]

  Tractable Classes of Binary CSPs Defined by Excluded Topological Minors

  David A. Cohen‚ Martin C. Cooper‚ Peter Jeavons and Stanislav Živný

  In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI'15). Pages 1945–1951. AAAI Press. 2015.

  Details about Tractable Classes of Binary CSPs Defined by Excluded Topological Minors | BibTeX data for Tractable Classes of Binary CSPs Defined by Excluded Topological Minors | Download (pdf) of Tractable Classes of Binary CSPs Defined by Excluded Topological Minors

• [2]

  Binarisation via dualisation for valued constraints

  David A. Cohen‚ Martin C. Cooper‚ Peter Jeavons and Stanislav Živný

  In Proceedings of the Twenty−Ninth AAAI Conference on Artificial Intelligence. Pages 3731–3737. AAAI Press. 2015.

  Details about Binarisation via dualisation for valued constraints | BibTeX data for Binarisation via dualisation for valued constraints | Link to Binarisation via dualisation for valued constraints

• [3]

  Tractable Combinations of Global Constraints

  David A. Cohen‚ Peter G. Jeavons‚ Evgenij Thorstensen and Stanislav Živný

  In Christian Schulte, editor, Principles and Practice of Constraint Programming − 19th International Conference‚ CP 2013‚ Uppsala‚ Sweden‚ September 16−20‚ 2013. Proceedings. Vol. 8124 of Lecture Notes in Computer Science. Pages 230−246. Springer. 2013.

  Details about Tractable Combinations of Global Constraints | BibTeX data for Tractable Combinations of Global Constraints | DOI (10.1007/978-3-642-40627-0_20) | Download (pdf) of Tractable Combinations of Global Constraints

• [4]

  Variable elimination in binary CSP via forbidden patterns

  David A. Cohen‚ Martin C. Cooper‚ Guillaume Escamoche and Stanislav Živný

  In Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI'13). Pages 517–523. 2013.

  Details about Variable elimination in binary CSP via forbidden patterns | BibTeX data for Variable elimination in binary CSP via forbidden patterns | Download (pdf) of Variable elimination in binary CSP via forbidden patterns

• [5]

  The complexity of finite−valued CSPs

  Johan Thapper and Stanislav Živný

  In Proceedings of the 45th ACM Symposium on the Theory of Computing (STOC'13). Pages 695−704. ACM. 2013.

  Details about The complexity of finite−valued CSPs | BibTeX data for The complexity of finite−valued CSPs | DOI (10.1145/2488608.2488697) | Download (pdf) of The complexity of finite−valued CSPs

• [6]

  Tractable Valued Constraints

  Peter G. Jeavons and Stanislav Živný

  In Lucas Bordeaux‚ Youssef Hamadi and Pushmeet Kohli, editors, Tractability: Practical Approaches to Hard Problems. Cambridge University Press. 2013.

  This work is in copyright. The draft is for personal use only. No further distribution without permission.

  Details about Tractable Valued Constraints | BibTeX data for Tractable Valued Constraints

• [7]

  The power of linear programming for valued CSPs

  Johan Thapper and Stanislav Živný

  In Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'12). Pages 669–678. IEEE. 2012.

  Details about The power of linear programming for valued CSPs | BibTeX data for The power of linear programming for valued CSPs | DOI (10.1109/FOCS.2012.25) | Download (pdf) of The power of linear programming for valued CSPs

• [8]

  A Characterisation of the Complexity of Forbidding Subproblems in Binary Max−CSP

  Martin C. Cooper‚ Guillaume Escamoche and Stanislav Živný

  In Proceedings of the 18th International Conference on Principles and Practice of Constraint Programming (CP'12). Vol. 7514 of Lecture Notes in Computer Science. Pages 265–273. Springer. 2012.

  Details about A Characterisation of the Complexity of Forbidding Subproblems in Binary Max−CSP | BibTeX data for A Characterisation of the Complexity of Forbidding Subproblems in Binary Max−CSP | DOI (10.1007/978-3-642-33558-7_21) | Download (pdf) of A Characterisation of the Complexity of Forbidding Subproblems in Binary Max−CSP

• [9]

  Relating Proof Complexity Measures and Practical Hardness of SAT

  Matti Järvisalo‚ Arie Matsliah‚ Jakob Nordström and Stanislav Živný

  In Proceedings of the 18th International Conference on Principles and Practice of Constraint Programming (CP'12). Vol. 7514 of Lecture Notes in Computer Science. Pages 316–331. Springer. 2012.

  Details about Relating Proof Complexity Measures and Practical Hardness of SAT | BibTeX data for Relating Proof Complexity Measures and Practical Hardness of SAT | DOI (10.1007/978-3-642-33558-7_25) | Download (pdf) of Relating Proof Complexity Measures and Practical Hardness of SAT

• [10]

  The complexity of conservative valued CSPs

  Vladimir Kolmogorov and Stanislav Živný

  In Proceedings of the 23rd Annual ACM−SIAM Symposium on Discrete Algorithms (SODA'12). Pages 750–759. SIAM. 2012.

  Full version available on arXiv:1110.2809.

  Details about The complexity of conservative valued CSPs | BibTeX data for The complexity of conservative valued CSPs | Link to The complexity of conservative valued CSPs

• [11]

  On minimal weighted clones

  Páidí Creed and Stanislav Živný

  In Proceedings of the 17th International Conference on Principles and Practice of Constraint Programming (CP'11). Vol. 6876 of Lecture Notes in Computer Science. Pages 210−224. Springer. 2011.

  Details about On minimal weighted clones | BibTeX data for On minimal weighted clones | DOI (10.1007/978-3-642-23786-7_18) | Link to On minimal weighted clones

• [12]

  Tractable triangles

  Martin C. Cooper and Stanislav Živný

  In Proceedings of the 17th International Conference on Principles and Practice of Constraint Programming (CP'11). Vol. 6876 of Lecture Notes in Computer Science. Pages 195–209. Springer. 2011.

  Details about Tractable triangles | BibTeX data for Tractable triangles | DOI (10.1007/978-3-642-23786-7_17) | Link to Tractable triangles

• [13]

  Hierarchically nested convex VCSP

  Martin C. Cooper and Stanislav Živný

  In Proceedings of the 17th International Conference on Principles and Practice of Constraint Programming (CP'11). Vol. 6876 of Lecture Notes in Computer Science. Pages 187–194. Springer. 2011.

  Details about Hierarchically nested convex VCSP | BibTeX data for Hierarchically nested convex VCSP | DOI (10.1007/978-3-642-23786-7_16) | Download (pdf) of Hierarchically nested convex VCSP

• [14]

  An algebraic theory of complexity for valued constraints: Establishing a Galois connection

  David A. Cohen‚ Páidí Creed‚ Peter G. Jeavons and Stanislav Živný

  In Proceedings of the 36th International Symposium on Mathematical Foundations of Computer Science (MFCS'11). Vol. 6907 of Lecture Notes in Computer Science. Pages 231–242. Springer. 2011.

  Details about An algebraic theory of complexity for valued constraints: Establishing a Galois connection | BibTeX data for An algebraic theory of complexity for valued constraints: Establishing a Galois connection | DOI (10.1007/978-3-642-22993-0_23) | Download (pdf) of An algebraic theory of complexity for valued constraints: Establishing a Galois connection

• [15]

  A new hybrid tractable class of soft constraint problems

  Martin C. Cooper and Stanislav Živný

  In Proceedings of the 16th International Conference on Principles and Practice of Constraint Programming (CP'10). Vol. 6308 of Lecture Notes in Computer Science. Pages 152–166. Springer. 2010.

  Details about A new hybrid tractable class of soft constraint problems | BibTeX data for A new hybrid tractable class of soft constraint problems | DOI (10.1007/978-3-642-15396-9_15) | Download (pdf) of A new hybrid tractable class of soft constraint problems

• [16]

  Same−relation constraints

  Christopher Jefferson‚ Serdar Kadioglu‚ Karen E. Petrie‚ Meinolf Sellmann and Stanislav Živný

  In Proceedings of the 15th International Conference on Principles and Practice of Constraint Programming (CP'09). Vol. 5732 of Lecture Notes in Computer Science. Pages 470–485. Springer. 2009.

  Details about Same−relation constraints | BibTeX data for Same−relation constraints | DOI (10.1007/978-3-642-04244-7_38) | Download (pdf) of Same−relation constraints

• [17]

  The complexity of valued constraint models

  Stanislav Živný and Peter G. Jeavons

  In Proceedings of the 15th International Conference on Principles and Practice of Constraint Programming (CP'09). Vol. 5732 of Lecture Notes in Computer Science. Pages 833–841. Springer. 2009.

  Details about The complexity of valued constraint models | BibTeX data for The complexity of valued constraint models | DOI (10.1007/978-3-642-04244-7_64) | Download (pdf) of The complexity of valued constraint models

• [18]

  The Expressive Power of Binary Submodular Functions

  Stanislav Živný‚ David A. Cohen and Peter G. Jeavons

  In Proceedings of the 34th International Symposium on Mathematical Foundations of Computer Science (MFCS'09). Vol. 5734 of Lecture Notes in Computer Science. Pages 744–757. Springer. 2009.

  Details about The Expressive Power of Binary Submodular Functions | BibTeX data for The Expressive Power of Binary Submodular Functions | DOI (10.1007/10.1007/978-3-642-03816-7_63) | Download (pdf) of The Expressive Power of Binary Submodular Functions

• [19]

  Classes of Submodular Constraints Expressible by Graph Cuts

  Stanislav Živný and Peter G. Jeavons

  In Proceedings of the 14th International Conference on Principles and Practice of Constraint Programming (CP'08). Vol. 5202 of Lecture Notes in Computer Science. Pages 112–127. Springer. 2008.

  Details about Classes of Submodular Constraints Expressible by Graph Cuts | BibTeX data for Classes of Submodular Constraints Expressible by Graph Cuts | DOI (10.1007/978-3-540-85958-1_8) | Download (pdf) of Classes of Submodular Constraints Expressible by Graph Cuts

• [20]

  The Expressive Power of Valued Constraints: Hierarchies and Collapses

  David A. Cohen‚ Peter G. Jeavons and Stanislav Živný

  In Proceedings of the 13th International Conference on Principles and Practice of Constraint Programming (CP'07). Vol. 4741 of Lecture Notes in Computer Science. Pages 798–805. Springer. 2007.

  Details about The Expressive Power of Valued Constraints: Hierarchies and Collapses | BibTeX data for The Expressive Power of Valued Constraints: Hierarchies and Collapses | DOI (10.1007/978-3-540-74970-7_57) | Download (pdf) of The Expressive Power of Valued Constraints: Hierarchies and Collapses

Technical reports

• [1]

  The power of linear programming for valued CSPs

  Johan Thapper and Stanislav Živný

  April, 2012.

  arXiv:1204.1079v2

  Details about The power of linear programming for valued CSPs | BibTeX data for The power of linear programming for valued CSPs | Link to The power of linear programming for valued CSPs

• [2]

  An algebraic theory of complexity for discrete optimisation

  David A. Cohen‚ Martin C. Cooper‚ Páidí Creed‚ Peter Jeavons and Stanislav Živný

  July, 2012.

  arXiv:1207.6692

  Details about An algebraic theory of complexity for discrete optimisation | BibTeX data for An algebraic theory of complexity for discrete optimisation | Link to An algebraic theory of complexity for discrete optimisation

• [3]

  The complexity of conservative valued CSPs

  Vladimir Kolmogorov and Stanislav Živný

  August, 2011.

  Details about The complexity of conservative valued CSPs | BibTeX data for The complexity of conservative valued CSPs | Link to The complexity of conservative valued CSPs

• [4]

  An algebraic theory of complexity for valued constraints: Establishing a Galois connection

  D.A. Cohen‚ P. Creed‚ P.G. Jeavons and S. Živný

  No. CS−RR−10−16. Oxford‚ UK. November, 2010.

  Details about An algebraic theory of complexity for valued constraints: Establishing a Galois connection | BibTeX data for An algebraic theory of complexity for valued constraints: Establishing a Galois connection | Download (pdf) of An algebraic theory of complexity for valued constraints: Establishing a Galois connection

• [5]

  Generalising tractable VCSPs defined by symmetric tournament pair multimorphisms

  Vladimir Kolmogorov and Stanislav Živný

  August, 2010.

  arXiv:1008.3104

  Details about Generalising tractable VCSPs defined by symmetric tournament pair multimorphisms | BibTeX data for Generalising tractable VCSPs defined by symmetric tournament pair multimorphisms | Link to Generalising tractable VCSPs defined by symmetric tournament pair multimorphisms

• [6]

  The complexity of conservative finite−valued CSPs

  Vladimir Kolmogorov and Stanislav Živný

  August, 2010.

  arXiv:1008.1555

  Details about The complexity of conservative finite−valued CSPs | BibTeX data for The complexity of conservative finite−valued CSPs | Link to The complexity of conservative finite−valued CSPs

• [7]

  Hybrid tractability of soft constraint problems

  Martin C. Cooper and Stanislav Živný

  August, 2010.

  Details about Hybrid tractability of soft constraint problems | BibTeX data for Hybrid tractability of soft constraint problems | Link to Hybrid tractability of soft constraint problems

• [8]

  PROCEEDINGS OF THE OXFORD UNIVERSITY COMPUTING LABORATORY STUDENT CONFERENCE 2008

  Programme Co−Chairs: Shamal Faily‚ Stanislav Živný Conference Co−Chairs: Christo Fogelberg‚ Andras Salamon and Max Schafer

  No. RR−08−10. OUCL. October, 2008.

  Details about PROCEEDINGS OF THE OXFORD UNIVERSITY COMPUTING LABORATORY STUDENT CONFERENCE 2008 | BibTeX data for PROCEEDINGS OF THE OXFORD UNIVERSITY COMPUTING LABORATORY STUDENT CONFERENCE 2008 | Download  (pdf) of PROCEEDINGS OF THE OXFORD UNIVERSITY COMPUTING LABORATORY STUDENT CONFERENCE 2008

• [9]

  PROCEEDINGS OF THE OXFORD UNIVERSITY COMPUTING LABORATORY STUDENT CONFERENCE 2008

  Programme Co−Chairs: Shamal Faily‚ Stanislav Živný Conference Co−Chairs: Christo Fogelberg‚ Andras Salamon and Max Schafer

  No. RR−08−10. OUCL. October, 2008.

  Details about PROCEEDINGS OF THE OXFORD UNIVERSITY COMPUTING LABORATORY STUDENT CONFERENCE 2008 | BibTeX data for PROCEEDINGS OF THE OXFORD UNIVERSITY COMPUTING LABORATORY STUDENT CONFERENCE 2008 | Download (pdf) of PROCEEDINGS OF THE OXFORD UNIVERSITY COMPUTING LABORATORY STUDENT CONFERENCE 2008

• [10]

  The Expressive Power of Binary Submodular Functions

  Stanislav Živný‚ David A. Cohen and Peter G. Jeavons

  November, 2008.

  arXiv:0811.1885

  Details about The Expressive Power of Binary Submodular Functions | BibTeX data for The Expressive Power of Binary Submodular Functions | Link to The Expressive Power of Binary Submodular Functions

• [11]

  Which submodular functions are expressible using binary submodular functions?

  Stanislav Živný and Peter G. Jeavons

  No. CS−RR−08−08. Computing Laboratory‚ University of Oxford. Oxford‚ UK. June, 2008.

  Details about Which submodular functions are expressible using binary submodular functions? | BibTeX data for Which submodular functions are expressible using binary submodular functions? | Download (pdf) of Which submodular functions are expressible using binary submodular functions?

• [12]

  The expressive power of valued constraints: Hierarchies and collapses

  D.A. Cohen‚ P.G. Jeavons and S. Živný

  No. CS−RR−07−03. Computing Laboratory‚ University of Oxford. Oxford‚ UK. April, 2007.

  Details about The expressive power of valued constraints: Hierarchies and collapses | BibTeX data for The expressive power of valued constraints: Hierarchies and collapses | Download (pdf) of The expressive power of valued constraints: Hierarchies and collapses

• [13]

  The complexity of finite−valued CSPs

  Johan Thapper and Stanislav Živný

  arXiv:1210.2977

  Details about The complexity of finite−valued CSPs | BibTeX data for The complexity of finite−valued CSPs | Link to The complexity of finite−valued CSPs

Theses

• [1]

  The Complexity and Expressive Power of Valued Constraints

  Stanislav Živný

  PhD Thesis University of Oxford. 2009.

  Details about The Complexity and Expressive Power of Valued Constraints | BibTeX data for The Complexity and Expressive Power of Valued Constraints | Link to The Complexity and Expressive Power of Valued Constraints

• [2]

  Properties of oracle classes that collapse or separate complexity classes

  Stanislav Živný

  Master's Thesis Vrije Universiteit in Amsterdam. The Netherlands. July, 2005.

  Details about Properties of oracle classes that collapse or separate complexity classes | BibTeX data for Properties of oracle classes that collapse or separate complexity classes | Link to Properties of oracle classes that collapse or separate complexity classes

• [3]

  Relation between accepting languages and complexity of questions on oracle

  Stanislav Živný

  Master's Thesis Charles University in Prague. Czech republic. April, 2005.

  Details about Relation between accepting languages and complexity of questions on oracle | BibTeX data for Relation between accepting languages and complexity of questions on oracle

Miscellaneous

• [1]

  Expressibility of valued constraints

  Stanislav Živný and Peter Jeavons

  September, 2007.

  Details about Expressibility of valued constraints | BibTeX data for Expressibility of valued constraints