@PREAMBLE{ "\newcommand{\noopsort}[1]{}"}
# zivny.bib
@MastersThesis{z05:msc-amsterdam,
author = "Stanislav {\noopsort{ZZ}\v{Z}}ivn\'y",
title = "{P}roperties of oracle classes that collapse or separate complexity classes",
school = "Vrije Universiteit in Amsterdam",
address = "The Netherlands",
month = "July",
year = "2005",
url = "http://eccc.hpi-web.de/eccc-local/ECCC-Theses/zivny.html"
}
@MastersThesis{z05:msc-prague,
author = "Stanislav {\noopsort{ZZ}\v{Z}}ivn\'y",
title = "{R}elation between accepting languages and complexity of questions on oracle",
school = "Charles University in Prague",
address = "Czech republic",
month = "April",
year = "2005"
}
@TechReport{cjz07:tr-hierarchies,
author = "Cohen, D.A. and Jeavons, P.G. and {\noopsort{ZZ}\v{Z}}ivn\'y, S.",
title = "{T}he expressive power of valued constraints: {H}ierarchies and collapses",
institution = "Computing Laboratory, University of Oxford",
year = "2007",
type = "Research Report",
number = "CS-RR-07-03",
address = "Oxford, UK",
month = "April",
url = "http://www.cs.ox.ac.uk/files/668/RR-07-03.pdf"
}
@InProceedings{cjz07:cp,
author = "David A. Cohen and Peter G. Jeavons and Stanislav {\noopsort{ZZ}\v{Z}}ivn{\'y}",
title = "{T}he {E}xpressive {P}ower of {V}alued {C}onstraints: {H}ierarchies and {C}ollapses",
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",
month = "September",
year = "2007",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
volume = "4741",
doi = "10.1007/978-3-540-74970-7_57"
}
@misc{zj07:cp-dp,
author = "Stanislav {\noopsort{ZZ}\v{Z}}ivn\'y and Peter Jeavons",
title = "{E}xpressibility of valued constraints",
booktitle = "{P}roc. of the {D}octoral {P}rogramme of {C}{P}'07",
pages = "193--198",
month = "September",
year = "2007"
}
@InProceedings{zj08:cp,
author = "Stanislav {\noopsort{ZZ}\v{Z}}ivn\'y and Peter G. Jeavons",
title = "{C}lasses of {S}ubmodular {C}onstraints {E}xpressible by {G}raph {C}uts",
booktitle = "{P}roceedings of the 14th {I}nternational {C}onference on {P}rinciples and {P}ractice of {C}onstraint {P}rogramming ({C}{P}'08)",
year = "2008",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "112--127",
volume = "5202",
doi = "10.1007/978-3-540-85958-1_8"
}
@Article{cjz08:tcs,
author = "David A. Cohen and Peter G. Jeavons and Stanislav {\noopsort{ZZ}\v{Z}}ivn{\'y}",
title = "{T}he expressive power of valued constraints: {H}ierarchies and collapses",
journal = "Theoretical Computer Science",
year = "2008",
pages = "137--153",
volume = "409",
number = "1",
doi = "10.1016/j.tcs.2008.08.036"
}
@article{zz09:ipl,
author = "Bruno Zanuttini and Stanislav {\v{Z}}ivn\'y",
title = "{A} note on some collapse results of valued constraints",
journal = "Information Processing Letters",
year = "2009",
pages = "534--538",
volume = "109",
number = "11",
doi = "10.1016/j.ipl.2009.01.018"
}
@TechReport{zj08:tr-sub,
author = "Stanislav {\noopsort{ZZ}\v{Z}}ivn\'y and Peter G. Jeavons",
title = "{W}hich submodular functions are expressible using binary submodular functions?",
institution = "Computing Laboratory, University of Oxford",
year = "2008",
type = "Research Report",
number = "CS-RR-08-08",
address = "Oxford, UK",
month = "June",
url = "http://www.cs.ox.ac.uk/files/628/RR-08-08.pdf"
}
@TechReport{zcj08:arxiv-sub,
author = "Stanislav {\noopsort{ZZ}\v{Z}}ivn\'y and David A. Cohen and Peter G. Jeavons",
title = "The {E}xpressive {P}ower of {B}inary {S}ubmodular {F}unctions",
note = "arXiv:0811.1885",
month = "November",
year = "2008",
url = "http://arxiv.org/abs/0811.1885"
}
@InProceedings{zj09:cp,
author = "Stanislav {\noopsort{ZZ}\v{Z}}ivn\'y and Peter G. Jeavons",
title = "The complexity of valued constraint models",
booktitle = "{P}roceedings of the 15th {I}nternational {C}onference on {P}rinciples and {P}ractice of {C}onstraint {P}rogramming ({C}{P}'09)",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
year = "2009",
volume = "5732",
pages = "833--841",
doi = "10.1007/978-3-642-04244-7_64"
}
@InProceedings{zcj09:mfcs,
author = "Stanislav {\noopsort{ZZ}\v{Z}}ivn\'y and David A. Cohen and Peter G. Jeavons",
title = "The {E}xpressive {P}ower of {B}inary {S}ubmodular {F}unctions",
booktitle = "Proceedings of the 34th International Symposium on Mathematical Foundations of Computer Science (MFCS'09)",
year = "2009",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "744--757",
volume = "5734",
doi = "10.1007/10.1007/978-3-642-03816-7_63"
}
@Article{zcj09:dam,
author = "Stanislav {\noopsort{ZZ}\v{Z}}ivn\'y and David A. Cohen and Peter G. Jeavons",
title = "The {E}xpressive {P}ower of {B}inary {S}ubmodular {F}unctions",
journal = "Discrete Applied Mathematics",
year = "2009",
doi = "10.1016/j.dam.2009.07.001",
volume = "157",
number = "15",
pages = "3347--3358"
}
@InProceedings{ckpsz09:cp,
author = "Christopher Jefferson and Serdar Kadioglu and Karen E. Petrie and Meinolf Sellmann and Stanislav {\noopsort{ZZ}\v{Z}}ivn\'y",
title = "Same-relation constraints",
booktitle = "{P}roceedings of the 15th {I}nternational {C}onference on {P}rinciples and {P}ractice of {C}onstraint {P}rogramming ({C}{P}'09)",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
year = "2009",
volume = "5732",
pages = "470--485",
doi = "10.1007/978-3-642-04244-7_38"
}
@article{z09:ipl,
author = "Stanislav {\noopsort{ZZ}\v{Z}}ivn\'y",
title = "{S}tructural properties of oracle classes",
journal = "Information Processing Letters",
year = "2009",
doi = "10.1016/j.ipl.2009.07.009",
pages = "1131--1135",
volume = "109",
number = "19"
}
@article{zj10:constraints,
author = "Stanislav {\noopsort{ZZ}\v{Z}}ivn\'y and Peter G. Jeavons",
title = "{C}lasses of {S}ubmodular {C}onstraints {E}xpressible by {G}raph {C}uts",
journal = "Constraints",
year = "2010",
doi = "10.1007/s10601-009-9078-z",
pages = "430-452",
volume = "15",
number = "3"
}
@PhDThesis{z09:phdthesis,
author = "Stanislav {\noopsort{ZZ}\v{Z}}ivn\'y",
title = "The Complexity and Expressive Power of Valued Constraints",
school = "University of Oxford",
year = "2009"
}
@inproceedings{cz10:cp,
author = "Martin C. Cooper and Stanislav {\noopsort{ZZ}\v{Z}}ivn\'y",
title = "A new hybrid tractable class of soft constraint problems",
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)",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "152--166",
volume = "6308",
doi = "10.1007/978-3-642-15396-9_15"
}
@article{cz10:arxiv-hybrid,
author = "Martin C. Cooper and Stanislav {\noopsort{ZZ}\v{Z}}ivn\'y",
title = "Hybrid tractability of soft constraint problems",
year = "2010",
month = "August",
url = "http://arxiv.org/abs/1008.4071"
}
@TechReport{kz10:arxive-finitecons,
author = "Vladimir Kolmogorov and Stanislav {\noopsort{ZZ}\v{Z}}ivn\'y",
title = "The complexity of conservative finite-valued {C}{S}{P}s",
note = "arXiv:1008.1555",
month = "August",
year = "2010",
url = "http://arxiv.org/abs/1008.1555"
}
@TechReport{kz10:arxiv-alg,
author = "Vladimir Kolmogorov and Stanislav {\noopsort{ZZ}\v{Z}}ivn\'y",
title = "Generalising tractable {V}{C}{S}{P}s defined by symmetric tournament pair multimorphisms",
note = "arXiv:1008.3104",
month = "August",
year = "2010",
url = "http://arxiv.org/abs/1008.3104"
}
@TechReport{ccjz10:tr-galois,
author = "Cohen, D.A. and Creed, P. and Jeavons, P.G. and {\noopsort{ZZ}\v{Z}}ivn\'y, S.",
title = "An algebraic theory of complexity for valued constraints: {E}stablishing a {G}alois connection",
institution = "Computing Laboratory, University of Oxford",
year = "2010",
type = "Research Report",
number = "CS-RR-10-16",
address = "Oxford, UK",
month = "November",
url = "http://www.cs.ox.ac.uk/files/3564/RR-10-16.pdf"
}
@article{cz11:ai,
author = "Martin C. Cooper and Stanislav {\noopsort{ZZ}\v{Z}}ivn\'y",
title = "Hybrid tractability of valued constraint problems",
year = "2011",
journal = "Artificial Intelligence",
doi = "10.1016/j.artint.2011.02.003",
pages = "1555-1569",
volume = "175",
number = "9-10"
}
@InProceedings{ccjz11:mfcs,
author = "Cohen, D.A. and Creed, P. and Jeavons, P.G. and {\noopsort{ZZ}\v{Z}}ivn\'y, S.",
title = "An algebraic theory of complexity for valued constraints: {E}stablishing a {G}alois connection",
year = "2011",
booktitle = "Proceedings of the 36th International Symposium on Mathematical Foundations of Computer Science (MFCS'11)",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "231--242",
volume = "6907",
doi = "10.1007/978-3-642-22993-0_23"
}
@InProceedings{cz11:cp-mwc,
author = "P\'aid\'i Creed and Stanislav {\noopsort{ZZ}\v{Z}}ivn\'y",
title = "On minimal weighted clones",
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)",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "210--224",
volume = "6876",
doi = "10.1007/978-3-642-23786-7_18"
}
@inproceedings{cz11:cp-triangles,
author = "Martin C. Cooper and Stanislav {\noopsort{ZZ}\v{Z}}ivn\'y",
title = "Tractable triangles",
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)",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "195--209",
volume = "6876",
doi = "10.1007/978-3-642-23786-7_17"
}
@inproceedings{cz11:cp-convex,
author = "Martin C. Cooper and Stanislav {\noopsort{ZZ}\v{Z}}ivn\'y",
title = "Hierarchically nested convex {V}{C}{S}{P}",
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)",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "187--194",
volume = "6876",
doi = "10.1007/978-3-642-23786-7_16"
}
@InProceedings{kz12:soda,
author = "Vladimir Kolmogorov and Stanislav {\noopsort{ZZ}\v{Z}}ivn\'y",
title = "The complexity of conservative valued {C}{S}{P}s",
year = "2012",
booktitle = "Proceedings of of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'12)",
publisher = "SIAM",
pages = "750--759",
url = "http://dl.acm.org/citation.cfm?id=2095177",
note = "full version available on arXiv:1110.2809."
}
@inproceedings{jz12:cup,
author = "Peter G. Jeavons and Stanislav \v{Z}ivn\'y",
title = "Tractable {V}alued {C}onstraints",
editor = "Lucas Bordeaux and Youssef Hamadi and Pushmeet Kohli and Robert Mateescu",
booktitle = "{T}ractability: {P}ractical {A}pproaches to {H}ard {P}roblems",
publisher = "Cambridge University Press",
year = "2012",
note = "to appear"
}
@inproceedings{z12:complexity,
title = "The complexity of valued constraint satisfaction problems",
author = "Stanislav \v{Z}ivn\'y",
series = "Cognitive Technologies",
year = "2012",
publisher = "Springer",
isbn = "978-3-642-33973-8",
doi = "10.1007/978-3-642-33974-5"
}
@article{cz12:jair,
author = "Martin C. Cooper and Stanislav {\noopsort{ZZ}\v{Z}}ivn\'y",
title = "Tractable triangles and cross-free convexity in discrete optimisation",
journal = "Journal of Artificial Intelligence Research",
volume = "44",
pages = "455--490",
year = "2012",
doi = "10.1613/jair.3598"
}
@inproceedings{jmnz12:cp-sat,
author = {Matti J\"arvisalo and Arie Matsliah and Jakob Nordstr\"om and Stanislav {\noopsort{ZZ}\v{Z}}ivn\'y},
title = "{R}elating {P}roof {C}omplexity {M}easures and {P}ractical {H}ardness of {S}{A}{T}",
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)",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "316--331",
volume = "7514",
doi = "10.1007/978-3-642-33558-7_25"
}
@inproceedings{cez12:cp-subproblems,
author = "Martin C. Cooper and Guillaume Escamoche and Stanislav {\noopsort{ZZ}\v{Z}}ivn\'y",
title = "{A} {C}haracterisation of the {C}omplexity of {F}orbidding {S}ubproblems in {B}inary {M}ax-{C}{S}{P}",
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)",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "265--273",
volume = "7514",
doi = "10.1007/978-3-642-33558-7_21"
}
@InProceedings{tz12:focs,
author = "Johan Thapper and Stanislav {\noopsort{ZZ}\v{Z}}ivn\'y",
title = "The power of linear programming for valued {C}{S}{P}s",
year = "2012",
booktitle = "Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'12)",
publisher = "IEEE",
pages = "669--678",
doi = "10.1109/FOCS.2012.25"
}
@InProceedings{tz13:stoc,
author = "Johan Thapper and Stanislav {\noopsort{ZZ}\v{Z}}ivn\'y",
title = "The complexity of finite-valued {C}{S}{P}s",
year = "2013",
booktitle = "Proceedings of the 45th ACM Symposium on the Theory of Computing (STOC'13)",
publisher = "ACM",
pages = "695--704",
doi = "10.1145/2488608.2488697"
}
@article{kz13:jacm,
author = "Vladimir Kolmogorov and Stanislav {\noopsort{ZZ}\v{Z}}ivn\'y",
title = "The complexity of conservative valued {C}{S}{P}s",
year = "2013",
journal = "Journal of the ACM",
volume = "60",
number = "2",
doi = "10.1145/2450142.2450146"
}
@TechReport{kz11:arxiv-cons,
author = "Vladimir Kolmogorov and Stanislav {\noopsort{ZZ}\v{Z}}ivn\'y",
title = "The complexity of conservative valued {C}{S}{P}s",
note = "arXiv:1110.2809",
month = "October",
year = "2011",
url = "http://arxiv.org/abs/1110.2809"
}
@TechReport{cccjz12:arxiv-algebraic,
author = "David A. Cohen and Martin C. Cooper and P\'aid\'i Creed and Peter Jeavons and Stanislav {\noopsort{ZZ}\v{Z}}ivn\'y",
title = "An algebraic theory of complexity for discrete optimisation",
note = "arXiv:1207.6692",
month = "July",
year = "2012",
url = "http://arxiv.org/abs/1207.6692"
}
@TechReport{tz12:arxiv-lp,
author = "Johan Thapper and Stanislav {\noopsort{ZZ}\v{Z}}ivn\'y",
title = "The power of linear programming for valued CSPs",
note = "arXiv:1204.1079v2",
month = "April",
year = "2012",
url = "http://arxiv.org/abs/1204.1079"
}
@TechReport{tz12:arxiv-dichotomy,
author = "Johan Thapper and Stanislav {\noopsort{ZZ}\v{Z}}ivn\'y",
title = "The complexity of finite-valued {C}{S}{P}s",
note = "arXiv:1210.2977",
month = "October",
year = "2012",
url = "http://arxiv.org/abs/1210.1079"
}