Standa Živný Professor of Computer Science University of Oxford Email: standa • zivny @ cs • ox • ac • uk Phone: +44 (0)1865 610724 A faculty member at Oxford since 2013, a full professor since 2021.

RESEARCH

My research is in the broad areas of theoretical computer science and discrete mathematics. I am particularly interested in algorithms, computational complexity, and homomorphism problems. Most of my work lies at the intersection of the above, namely it is on (the mathematics of) constraint satisfaction problems (CSP) in its many forms.

All my publications are available online. Here are some examples of problems I have worked on:

• What is the power of linear programming for combinatorial problems [KTŽ15,TŽ17,CRŽ22]?
• Which problems, just like linear equations, cannot be solved by any polynomial-size convex relaxation [TŽ18]?
• Which problems, just like graph cuts, admit a sparsifier [BŽ20,PŽ24]?
• Which generalisations of submodularity admit efficient optimisation [KTŽ15,WŽ16]?
• Which discrete optimisation problems are solvable exactly efficiently [KŽ13,TŽ16]?
• Which counting homomorphism problems can be solved approximately [BŽ20,FGŽ21]?
• Which promise problems can be solved by combining linear programming and linear Diophantine equations [BGWŽ20,CŽ23a]?
• When can max-cut, and beyond, be solved with arbitrarily good approximation [RWŽ23,MWŽ23]?
• Given a 7-colourable graph, can one find a 35-colouring efficiently [KOWŽ23] and why relaxations cannot solve this problem [CŽ23b,CŽ23c]?

Get in touch if you are interested in doing an undergraduate project, a master dissertation, or a PhD with me. I cannot take on interns (except for, occasionally, Oxford undergraduates) and thus generally do not respond to such requests. I'm happy to supervise highly motivated students with a strong background in theoretical computer science and/or (any branch of) mathematics in any area of in algorithms, discrete mathematics, or computational complexity.

GRANTS

• ERC Consolidator Grant New Approaches to Approximability of Satisfiable Problems (NAASP), 2022-2027, €2.0M
• ERC Starting Grant Power of Algorithms in Discrete Optimisation (PowAlgDO), 2017-2022, €1.4M
• Royal Society University Research Fellowship (URF), 2013-2021, £880K

SERVICE

I currently serve as the Deputy Head of Department (Teaching). Previously, I served for almost three years as the Director of Teaching.

Conferences Programme Committees

• TCS: CSL'25, STOC'24, WG'24, ITCS'22, MFCS'20, STACS'20, ISAAC'19, ESA'19, MFCS'18, ICALP'18
• AI:   CP'21 (SPC), IJCAI'21 (SPC), AAA'21, IJCAI-PRICAI'20, AAAI'20, IJCAI'19, IJCAI-ECAI'18, AAAI'18, AAAI'17, CP'17, CP'16, IJCAI'15, CP'14, CP'13, DPCP'13, IJCAI'13, AAAI'12, CP'12, DPCP'12 (co-chair), SOFSEM'12, AAAI'11, CP'11, DPCP'11, IJCAI'11, AAAI'10, CP'10, DPCP'10 (co-chair), DPCP'09

Journal Editorial

• SIAM Journal on Discrete Mathematics (SIDMA), Editor-in-Chief, since 2022; Associate Editor, 2017-2022
• Philosophical Transactions of the Royal Society A (PTA), Editorial Board Member, since 2019
• Constraints, Editorial Board Member, 2019-2023

Organiser

• Dagstuhl Seminar 25211 The Constraint Satisfaction Problem: Complexity and Approximability, 2025 (with M. Bodirsky, V. Guruswami, and D. Marx)
• American Institute of Mathematics (AIM) SQuARE: Relaxations for Promise CSPs, 2023-2025
• Dagstuhl Seminar 22201 The Constraint Satisfaction Problem: Complexity and Approximability, 2022 (with M. Grohe, V. Guruswami, and D. Marx)
• Early Career Researchers Workshop, European Computer Science Summit, 2021 (with E. Di Nitto)
• Dagstuhl Seminar 18231 The Constraint Satisfaction Problem: Complexity and Approximability, 2018 (with M. Grohe, V. Guruswami, and D. Marx)
• Doctoral Programme of CP 2012, 2012 (with M. Lombardi)
• Doctoral Programme of CP 2010, 2010 (with P. Nightingale)
• Oxford University Computer Science Student Conference, 2008 (with S. Faily)

Other

• EATCS Distinguished Dissertation Award, Committee Member, 2024.
• London Mathematical Society (LMS) Computer Science Committee, Chair, since 2023 (member 2019-2023)
• Czech Summer School on Discrete Mathematics, Scientific Board, Member, since 2021
• EPSRC Peer Review College, Member, since 2018
• Informatics Europe, Board Member, 2021-2022
• EurAI PhD Dissertation Award, Panel Member, 2019
• ACP Doctoral Research Award, Panel Member, 2018
• Royal Society International Exchanges Committee, Panel Member, 2015-2020

SUPERVISION AND MENTORING

Postdocs

• Alberto Larrauri, since 2023
• Silvia Butti, since 2023
• Lorenzo Ciardo, since 2020
• Caterina Viola, 2020-2022 (→ faculty at University of Catania, Italy)
• Jakub Opršal, 2021-2022 (→ faculty at University of Birmingham)
• Shuai Shao, 2020-2021 (→ faculty at USTC, China)
• Michael Kompatscher, 2020-2021 (→ faculty at Charles University, Czechia)
• Balázs Mezei, 2020-2021 (→ finance)
• Marcin Wrochna, 2018-2020 (→ faculty at University of Warsaw, Poland)
• Miguel Romero, 2017-2019 (→ faculty at PUC, Chile)
• Clément Carbonnel, 2017-2018 (→ CNRS, France)

PhD Students

• Tamio-Vesa Nakajima, since 2021
• Thomas Orton, PhD 2023 (with V. Kanade and R. Santhanam) (→ finance)
• Alex Brandts, PhD 2022 (→ finance)
• Jacob Focke, PhD 2020 (with L. Goldberg) (→ postdoc at CISPA/MPI, Germany)
• Peter Fulla, PhD 2018 (→ faculty at Chuo University, Japan)
• Andrius Vaicenavičius, 2014-2017 (with P. Jeavons and C. McDiarmid) (→ transferred to pursue a PhD in AI)

BSc and MSc Students

• Leon Balan-Tribus
• Ruxandra-Laura Nanu
• Hong Zhang, MSc 2023 (distinction)
• Serban-Ion Cercelescu, BA 2023 (distinction)
• Yichen Huang, BA 2023 (distinction) (→ PhD at Harvard)
• Jannik Kudla, MSc 2022 (distinction)
• Costin Oncescu, MCompSci 2022 (distinction) (with J.F. Henriques) (→ PhD at Harvard)
• Jáchym Solecký, MMathCompSci 2021 (distinction)
• Costin Oncescu, BA 2021 (distinction)
• Eden Pelleg, MSc 2020 (distinction)
• Yunus Ayidin, BA (distinction), 2020 (→ PhD at UC Riverside)
• David Klambauer, MSc 2019 (distinction)
• Silvia Butti, MSc 2018 (distinction) (→ PhD at UPF)
• Gregor Matl, MSc 2018 (distinction)
• Ragnar Groot Koerkamp, MSc 2017 (distinction) (→ PhD at ETH)
• Andrius Vaicenavičius, MMath 2014 (Gibbs dissertation prize) (with P. Jeavons) (→ PhD at Oxford)

Research Interns

• Piotr Mitosek, internship funded by the RS, 2020 (with M. Wrochna) (→ PhD at University of Birmingham)
• Joanna Ochremiak, internship funded by the EU, 2015 (→ PhD at University of Warsaw)
• Andrius Vaicenavičius, internship funded by the EPSRC, 2013 (with P. Jeavons) (→ PhD at Oxford)

College Lecturers

• Zev Shirazi, 2023-2024
• Ross Gales, 2023-2024
• Atılım Güneş Baydin, 2021-2024
• Matthias Lanzinger, 2021-2023
• Cristina Matache, 2020–2021
• Swaraj Dash, 2019-2021
• Matthew Katzman, 2019-2021
• Reino Niskanen, 2019-2020

TEACHING

Lectures

• Algorithms for Constraint Satisfaction Problems
• Combinatorial Optimisation
• Complexity of Valued Constraint Satisfaction Problems
• Mathematics for Computer Scientists
• Probability and Computing

Classes and tutorials

• Advanced Data Structures and Algorithms
• Algorithms and Data Structures
• Automata and Formal Languages
• Computational Complexity
• Concurrency
• Continuous Mathematics
• Data Structures and Algorithms
• Design and Analysis of Algorithms
• Digital Systems
• Discrete Mathematics
• Functional programming
• Introduction to Formal Proof
• Introduction to Programming
• Imperative Programming
• Linear Algebra
• Logic and Proof
• Models of Computation
• Object Oriented Programming
• Probability and Computing
• Randomised Algorithms
• Theory of Data and Knowledge Bases

Trivia

My first name is Stanislav but I go by Standa /'stʌn.da/, a commonly used Czech variant/diminutive of Stanislav.

My last name Živný /'ʒiv.ni:/ has two diacritics called the caron and acute accent respectively; this can be achieved in LaTeX by \v{Z}ivn\'{y}.

For several special reasons I try to minimise travel but you can always visit me (virtually) in Oxford.