Standa Živný : Publications
Click here to download all publications in a single bibtex file
@inproceedings{ccjz15:ijcai,
title = "Tractable Classes of Binary {C}{S}{P}s Defined by Excluded Topological Minors",
author = "David A. Cohen and Martin C. Cooper and Peter Jeavons and Stanislav \v{Z}ivn\'y",
year = "2015",
booktitle = "Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI'15)",
pages = "1945--1951",
publisher = "AAAI Press",
url = "http://ijcai.org/papers15/Papers/IJCAI15-276.pdf",
}
@inproceedings{ccjz15:aaai,
title = "Binarisation via dualisation for valued constraints",
author = "David A. Cohen and Martin C. Cooper and Peter Jeavons and Stanislav \v{Z}ivn\'y",
year = "2015",
booktitle = "Proceedings of the Twenty-Ninth {AAAI} Conference on Artificial Intelligence",
pages = "3731--3737",
publisher = "AAAI Press",
url = "http://www.aaai.org/ocs/index.php/AAAI/AAAI15/paper/view/9328/9699",
}
@article{jkz14:survey,
title = "The complexity of valued constraint satisfaction",
author = "Peter Jeavons and Andrei Krokhin and Stanislav \v{Z}ivn\'y",
year = "2014",
journal = "Bulletin of the European Association for Theoretical Computer Science (EATCS)",
note = "Errata can be found <a href="http://community.dur.ac.uk/andrei.krokhin/papers/BEATCScolumnerrata.txt">here</a>.",
pages = "21-55",
url = "http://eatcs.org/beatcs/index.php/beatcs/article/view/266/249",
volume = "113",
}
@article{cccjz13:sicomp,
title = "An algebraic theory of complexity for discrete optimisation",
author = "David A. Cohen and Martin C. Cooper and P\'aid\'i Creed and Peter Jeavons and Stanislav \v{Z}ivn\'y",
year = "2013",
journal = "SIAM Journal on Computing",
number = "5",
pages = "1915-1939",
url = "http://zivny.cz/publications/cccjz13sicomp-preprint.pdf",
volume = "42",
doi = "10.1137/130906398",
}
@article{kz13:jacm,
title = "The complexity of conservative valued {C}{S}{P}s",
author = "Vladimir Kolmogorov and Stanislav \v{Z}ivn\'y",
year = "2013",
journal = "Journal of the ACM",
note = "Article No. 10",
number = "2",
url = "http://zivny.cz/publications/kz13jacm-preprint.pdf",
volume = "60",
doi = "10.1145/2450142.2450146",
}
@inproceedings{DBLP:conf/cp/CohenJTZ13,
title = "Tractable Combinations of Global Constraints",
author = "David A. Cohen and Peter G. Jeavons and Evgenij Thorstensen and Stanislav \v{Z}ivn\'{y}",
year = "2013",
booktitle = "Principles and Practice of Constraint Programming - 19th International Conference, CP 2013, Uppsala, Sweden, September 16-20, 2013. Proceedings",
editor = "Christian Schulte",
pages = "230-246",
publisher = "Springer",
series = "Lecture Notes in Computer Science",
url = "http://zivny.cz/publications/cjtz13cp-preprint.pdf",
volume = "8124",
doi = "10.1007/978-3-642-40627-0_20",
}
@inproceedings{ccez13:ijcai,
title = "Variable elimination in binary CSP via forbidden patterns",
author = "David A. Cohen and Martin C. Cooper and Guillaume Escamoche and Stanislav \v{Z}ivn\'y",
year = "2013",
booktitle = "Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI'13)",
pages = "517--523",
url = "http://ijcai.org/papers13/Papers/IJCAI13-084.pdf",
}
@inproceedings{tz13:stoc,
title = "The complexity of finite-valued {C}{S}{P}s",
author = "Johan Thapper and Stanislav \v{Z}ivn\'y",
year = "2013",
booktitle = "Proceedings of the 45th ACM Symposium on the Theory of Computing (STOC'13)",
pages = "695-704",
publisher = "ACM",
url = "http://zivny.cz/publications/tz13stoc-preprint.pdf",
doi = "10.1145/2488608.2488697",
}
@inproceedings{jz13:cup,
title = "Tractable {V}alued {C}onstraints",
author = "Peter G. Jeavons and Stanislav \v{Z}ivn\'y",
year = "2013",
booktitle = "{T}ractability: {P}ractical {A}pproaches to {H}ard {P}roblems",
editor = "Lucas Bordeaux and Youssef Hamadi and Pushmeet Kohli",
note = "This work is in copyright. The draft is for personal use only. No further distribution without permission.",
publisher = "Cambridge University Press",
}
@techreport{cccjz12:arxiv-algebraic,
title = "An algebraic theory of complexity for discrete optimisation",
author = "David A. Cohen and Martin C. Cooper and P\'aid\'i Creed and Peter Jeavons and Stanislav \v{Z}ivn\'y",
year = "2012",
month = "July",
note = "arXiv:1207.6692",
url = "http://arxiv.org/abs/1207.6692",
}
@techreport{tz12:arxiv-lp,
title = "The power of linear programming for valued {C}{S}{P}s",
author = "Johan Thapper and Stanislav \v{Z}ivn\'y",
year = "2012",
month = "April",
note = "arXiv:1204.1079v2",
url = "http://arxiv.org/abs/1204.1079",
}
@book{z12:complexity,
title = "The complexity of valued constraint satisfaction problems",
author = "Stanislav \v{Z}ivn\'y",
year = "2012",
isbn = "978-3-642-33973-8",
publisher = "Springer",
series = "Cognitive Technologies",
doi = "10.1007/978-3-642-33974-5",
}
@article{cz12:jair,
title = "Tractable triangles and cross-free convexity in discrete optimisation",
author = "Martin C. Cooper and Stanislav \v{Z}ivn\'y",
year = "2012",
journal = "Journal of Artificial Intelligence Research",
pages = "455--490",
url = "http://zivny.cz/publications/cz12jair-preprint.pdf",
volume = "44",
doi = "10.1613/jair.3598",
}
@inproceedings{tz12:focs,
title = "The power of linear programming for valued {C}{S}{P}s",
author = "Johan Thapper and Stanislav \v{Z}ivn\'y",
year = "2012",
booktitle = "Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'12)",
pages = "669--678",
publisher = "IEEE",
url = "http://zivny.cz/publications/tz12focs-preprint.pdf",
doi = "10.1109/FOCS.2012.25",
}
@inproceedings{cez12:cp-subproblems,
title = "{A} {C}haracterisation of the {C}omplexity of {F}orbidding {S}ubproblems in {B}inary {M}ax-{C}{S}{P}",
author = "Martin C. Cooper and Guillaume Escamoche and Stanislav \v{Z}ivn\'y",
year = "2012",
booktitle = "{P}roceedings of the 18th {I}nternational {C}onference on {P}rinciples and {P}ractice of {C}onstraint {P}rogramming ({C}{P}'12)",
pages = "265--273",
publisher = "Springer",
series = "Lecture Notes in Computer Science",
url = "http://zivny.cz/publications/cez12cp-subproblems-preprint.pdf",
volume = "7514",
doi = "10.1007/978-3-642-33558-7_21",
}
@inproceedings{jmnz12:cp-sat,
title = "{R}elating {P}roof {C}omplexity {M}easures and {P}ractical {H}ardness of {S}{A}{T}",
author = "Matti J\"arvisalo and Arie Matsliah and Jakob Nordstr\"om and Stanislav \v{Z}ivn\'y",
year = "2012",
booktitle = "{P}roceedings of the 18th {I}nternational {C}onference on {P}rinciples and {P}ractice of {C}onstraint {P}rogramming ({C}{P}'12)",
pages = "316--331",
publisher = "Springer",
series = "Lecture Notes in Computer Science",
url = "http://zivny.cz/publications/jmnz12cp-sat-preprint.pdf",
volume = "7514",
doi = "10.1007/978-3-642-33558-7_25",
}
@inproceedings{kz12:soda,
title = "The complexity of conservative valued {C}{S}{P}s",
author = "Vladimir Kolmogorov and Stanislav \v{Z}ivn\'y",
year = "2012",
booktitle = "Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'12)",
note = "Full version available on arXiv:1110.2809.",
pages = "750--759",
publisher = "SIAM",
url = "http://dl.acm.org/citation.cfm?id=2095177",
}
@techreport{kz11:arxiv-cons,
title = "The complexity of conservative valued {C}{S}{P}s",
author = "Vladimir Kolmogorov and Stanislav \v{Z}ivn\'y",
year = "2011",
month = "August",
url = "http://arxiv.org/abs/1110.2809",
}
@article{cz11:ai,
title = "Hybrid tractability of valued constraint problems",
author = "Martin C. Cooper and Stanislav \v{Z}ivn\'y",
year = "2011",
journal = "Artificial Intelligence",
number = "9-10",
pages = "1555-1569",
url = "http://zivny.cz/publications/cz11aij-preprint.pdf",
volume = "175",
doi = "10.1016/j.artint.2011.02.003",
}
@inproceedings{cz11:cp-mwc,
title = "On minimal weighted clones",
author = "P\'aid\'i Creed and Stanislav \v{Z}ivn\'y",
year = "2011",
booktitle = "{P}roceedings of the 17th {I}nternational {C}onference on {P}rinciples and {P}ractice of {C}onstraint {P}rogramming ({C}{P}'11)",
pages = "210-224",
publisher = "Springer",
series = "Lecture Notes in Computer Science",
url = "http://zivny.cz/publications/cz11cp-mwc-preprint",
volume = "6876",
doi = "10.1007/978-3-642-23786-7_18",
}
@inproceedings{cz11:cp-triangles,
title = "Tractable triangles",
author = "Martin C. Cooper and Stanislav \v{Z}ivn\'y",
year = "2011",
booktitle = "{P}roceedings of the 17th {I}nternational {C}onference on {P}rinciples and {P}ractice of {C}onstraint {P}rogramming ({C}{P}'11)",
pages = "195--209",
publisher = "Springer",
series = "Lecture Notes in Computer Science",
url = "http://zivny.cz/publications/cz11cp-triangles-preprint",
volume = "6876",
doi = "10.1007/978-3-642-23786-7_17",
}
@inproceedings{cz11:cp-convex,
title = "Hierarchically nested convex {V}{C}{S}{P}",
author = "Martin C. Cooper and Stanislav \v{Z}ivn\'y",
year = "2011",
booktitle = "{P}roceedings of the 17th {I}nternational {C}onference on {P}rinciples and {P}ractice of {C}onstraint {P}rogramming ({C}{P}'11)",
pages = "187--194",
publisher = "Springer",
series = "Lecture Notes in Computer Science",
url = "http://zivny.cz/publications/cz11cp-convex.pdf",
volume = "6876",
doi = "10.1007/978-3-642-23786-7_16",
}
@inproceedings{ccjz11:mfcs,
title = "An algebraic theory of complexity for valued constraints: {E}stablishing a {G}alois connection",
author = "David A. Cohen and P\'aid\'i Creed and Peter G. Jeavons and Stanislav \v{Z}ivn\'y",
year = "2011",
booktitle = "Proceedings of the 36th International Symposium on Mathematical Foundations of Computer Science (MFCS'11)",
pages = "231--242",
publisher = "Springer",
series = "Lecture Notes in Computer Science",
url = "http://zivny.cz/publications/ccjz11mfcs-preprint.pdf",
volume = "6907",
doi = "10.1007/978-3-642-22993-0_23",
}
@techreport{kz10:arxiv-alg,
title = "Generalising tractable {V}{C}{S}{P}s defined by symmetric tournament pair multimorphisms",
author = "Vladimir Kolmogorov and Stanislav \v{Z}ivn\'y",
year = "2010",
month = "August",
note = "arXiv:1008.3104",
url = "http://arxiv.org/abs/1008.3104",
}
@techreport{kz10:arxive-finitecons,
title = "The complexity of conservative finite-valued {C}{S}{P}s",
author = "Vladimir Kolmogorov and Stanislav \v{Z}ivn\'y",
year = "2010",
month = "August",
note = "arXiv:1008.1555",
url = "http://arxiv.org/abs/1008.1555",
}
@techreport{cz10:arxiv-hybrid,
title = "Hybrid tractability of soft constraint problems",
author = "Martin C. Cooper and Stanislav \v{Z}ivn\'y",
year = "2010",
month = "August",
url = "http://arxiv.org/abs/1008.4071",
}
@techreport{ccjz10:tr-galois,
title = "An algebraic theory of complexity for valued constraints: {E}stablishing a {G}alois connection",
author = "Cohen, D.A. and Creed, P. and Jeavons, P.G. and \v{Z}ivn\'y, S.",
year = "2010",
address = "Oxford, UK",
month = "November",
number = "CS-RR-10-16",
url = "http://www.cs.ox.ac.uk/files/3564/RR-10-16.pdf",
}
@article{zj10:constraints,
title = "{C}lasses of {S}ubmodular {C}onstraints {E}xpressible by {G}raph {C}uts",
author = "Stanislav \v{Z}ivn\'y and Peter G. Jeavons",
year = "2010",
journal = "Constraints",
number = "3",
pages = "430-452",
url = "http://zivny.cz/publications/zj10constraints-preprint.pdf",
volume = "15",
doi = "10.1007/s10601-009-9078-z",
}
@inproceedings{cz10:cp,
title = "A new hybrid tractable class of soft constraint problems",
author = "Martin C. Cooper and Stanislav \v{Z}ivn\'y",
year = "2010",
booktitle = "{P}roceedings of the 16th {I}nternational {C}onference on {P}rinciples and {P}ractice of {C}onstraint {P}rogramming ({C}{P}'10)",
pages = "152--166",
publisher = "Springer",
series = "Lecture Notes in Computer Science",
url = "http://zivny.cz/publications/cz10cp-preprint.pdf",
volume = "6308",
doi = "10.1007/978-3-642-15396-9_15",
}
@article{zcj09:dam,
title = "The {E}xpressive {P}ower of {B}inary {S}ubmodular {F}unctions",
author = "Stanislav \v{Z}ivn\'y and David A. Cohen and Peter G. Jeavons",
year = "2009",
journal = "Discrete Applied Mathematics",
number = "15",
pages = "3347--3358",
url = "http://zivny.cz/publications/zcj09dam-preprint.pdf",
volume = "157",
doi = "10.1016/j.dam.2009.07.001",
}
@article{z09:ipl,
title = "{S}tructural properties of oracle classes",
author = "Stanislav \v{Z}ivn\'y",
year = "2009",
number = "19",
pages = "1131--1135",
url = "http://zivny.cz/publications/z09ipl-preprint.pdf",
volume = "109",
doi = "10.1016/j.ipl.2009.07.009",
}
@article{zz09:ipl,
title = "{A} note on some collapse results of valued constraints",
author = "Bruno Zanuttini and Stanislav {\v{Z}}ivn\'y",
year = "2009",
journal = "Information Processing Letters",
number = "11",
pages = "534--538",
url = "http://zivny.cz/publications/zz09ipl-preprint.pdf",
volume = "109",
doi = "10.1016/j.ipl.2009.01.018",
}
@inproceedings{ckpsz09:cp,
title = "Same-relation constraints",
author = "Christopher Jefferson and Serdar Kadioglu and Karen E. Petrie and Meinolf Sellmann and Stanislav \v{Z}ivn\'y",
year = "2009",
booktitle = "{P}roceedings of the 15th {I}nternational {C}onference on {P}rinciples and {P}ractice of {C}onstraint {P}rogramming ({C}{P}'09)",
pages = "470--485",
publisher = "Springer",
series = "Lecture Notes in Computer Science",
url = "http://zivny.cz/publications/jkpsz09cp-preprint.pdf",
volume = "5732",
doi = "10.1007/978-3-642-04244-7_38",
}
@inproceedings{zj09:cp,
title = "The complexity of valued constraint models",
author = "Stanislav \v{Z}ivn\'y and Peter G. Jeavons",
year = "2009",
booktitle = "{P}roceedings of the 15th {I}nternational {C}onference on {P}rinciples and {P}ractice of {C}onstraint {P}rogramming ({C}{P}'09)",
pages = "833--841",
publisher = "Springer",
series = "Lecture Notes in Computer Science",
url = "http://zivny.cz/publications/zj09cp-preprint.pdf",
volume = "5732",
doi = "10.1007/978-3-642-04244-7_64",
}
@inproceedings{zcj09:mfcs,
title = "The {E}xpressive {P}ower of {B}inary {S}ubmodular {F}unctions",
author = "Stanislav \v{Z}ivn\'y and David A. Cohen and Peter G. Jeavons",
year = "2009",
booktitle = "Proceedings of the 34th International Symposium on Mathematical Foundations of Computer Science (MFCS'09)",
pages = "744--757",
publisher = "Springer",
series = "Lecture Notes in Computer Science",
url = "http://zivny.cz/publications/zcj09mfcs-preprint.pdf",
volume = "5734",
doi = "10.1007/10.1007/978-3-642-03816-7_63",
}
@phdthesis{z09:phdthesis,
title = "The Complexity and Expressive Power of Valued Constraints",
author = "Stanislav \v{Z}ivn\'y",
year = "2009",
school = "University of Oxford",
url = "http://ora.ouls.ox.ac.uk/objects/uuid:63facf22-7c2b-4d4a-8b6f-f7c323759ca0",
}
@techreport{zj08:tr-sub,
title = "Which submodular functions are expressible using binary submodular functions?",
author = "Stanislav \v{Z}ivn\'y and Peter G. Jeavons",
year = "2008",
address = "Oxford, UK",
institution = "Computing Laboratory, University of Oxford",
month = "June",
number = "CS-RR-08-08",
url = "http://www.cs.ox.ac.uk/files/628/RR-08-08.pdf",
}
@techreport{zcj08:arxiv-sub,
title = "The Expressive Power of Binary Submodular Functions",
author = "Stanislav \v{Z}ivn\'y and David A. Cohen and Peter G. Jeavons",
year = "2008",
month = "November",
note = "arXiv:0811.1885",
url = "http://arxiv.org/abs/0811.1885",
}
@techreport{RR-08-10,
title = "PROCEEDINGS OF THE OXFORD UNIVERSITY COMPUTING LABORATORY STUDENT CONFERENCE 2008",
author = "Programme Co-Chairs: Shamal Faily and Stanislav \v{Z}ivn\'y Conference Co-Chairs: Christo Fogelberg and Andras Salamon and Max Schafer",
year = "2008",
institution = "OUCL",
month = "October",
number = "RR-08-10",
pages = "33",
}
@techreport{RR-08-10,
title = "PROCEEDINGS OF THE OXFORD UNIVERSITY COMPUTING LABORATORY STUDENT CONFERENCE 2008",
author = "Programme Co-Chairs: Shamal Faily and Stanislav \v{Z}ivn\'y Conference Co-Chairs: Christo Fogelberg and Andras Salamon and Max Schafer",
year = "2008",
institution = "OUCL",
month = "October",
number = "RR-08-10",
pages = "33",
url = "http://www.cs.ox.ac.uk/files/1328/RR-08-10.pdf",
}
@article{cjz08:tcs,
title = "The expressive power of valued constraints: {H}ierarchies and collapses",
author = "David A. Cohen and Peter G. Jeavons and Stanislav \v{Z}ivn\'y",
year = "2008",
journal = "Theoretical Computer Science",
number = "1",
pages = "137--153",
url = "http://zivny.cz/publications/cjz08tcs-preprint.pdf",
volume = "409",
doi = "10.1016/j.tcs.2008.08.036",
}
@inproceedings{zj08:cp,
title = "{C}lasses of {S}ubmodular {C}onstraints {E}xpressible by {G}raph {C}uts",
author = "Stanislav \v{Z}ivn\'y and Peter G. Jeavons",
year = "2008",
booktitle = "{P}roceedings of the 14th {I}nternational {C}onference on {P}rinciples and {P}ractice of {C}onstraint {P}rogramming ({C}{P}'08)",
pages = "112--127",
publisher = "Springer",
series = "Lecture Notes in Computer Science",
url = "http://zivny.cz/publications/zj08cp-preprint.pdf",
volume = "5202",
doi = "10.1007/978-3-540-85958-1_8",
}
@misc{zj07:cp-dp,
title = "Expressibility of valued constraints",
author = "Stanislav \v{Z}ivn\'y and Peter Jeavons",
year = "2007",
booktitle = "{P}roc. of the {D}octoral {P}rogramme of {C}{P}'07",
month = "September",
pages = "193--198",
}
@techreport{cjz07:tr-hierarchies,
title = "The expressive power of valued constraints: {H}ierarchies and collapses",
author = "Cohen, D.A. and Jeavons, P.G. and \v{Z}ivn\'y, S.",
year = "2007",
address = "Oxford, UK",
institution = "Computing Laboratory, University of Oxford",
month = "April",
number = "CS-RR-07-03",
url = "http://www.cs.ox.ac.uk/files/668/RR-07-03.pdf",
}
@inproceedings{cjz07:cp,
title = "The Expressive Power of Valued Constraints: Hierarchies and Collapses",
author = "David A. Cohen and Peter G. Jeavons and Stanislav \v{Z}ivn\'y",
year = "2007",
booktitle = "{P}roceedings of the 13th {I}nternational {C}onference on {P}rinciples and {P}ractice of {C}onstraint {P}rogramming ({C}{P}'07)",
pages = "798--805",
publisher = "Springer",
series = "Lecture Notes in Computer Science",
url = "http://zivny.cz/publications/cjz07cp-preprint.pdf",
volume = "4741",
doi = "10.1007/978-3-540-74970-7_57",
}
@mastersthesis{z05:msc-amsterdam,
title = "Properties of oracle classes that collapse or separate complexity classes",
author = "Stanislav \v{Z}ivn\'y",
year = "2005",
address = "The Netherlands",
month = "July",
school = "Vrije Universiteit in Amsterdam",
url = "http://eccc.hpi-web.de/eccc-local/ECCC-Theses/zivny.html",
}
@mastersthesis{z05:msc-prague,
title = "Relation between accepting languages and complexity of questions on oracle",
author = "Stanislav \v{Z}ivn\'y",
year = "2005",
address = "Czech republic",
month = "April",
school = "Charles University in Prague",
}
@techreport{tz12:arxiv-dichotomy,
title = "The complexity of finite-valued {C}{S}{P}s",
author = "Johan Thapper and Stanislav \v{Z}ivn\'y",
month = "October",
note = "arXiv:1210.2977",
url = "http://arxiv.org/abs/1210.1079",
}