Standa Živný Professor of Computer Science Tutorial Fellow at Jesus College University of Oxford Email: standa • zivny @ cs • ox • ac • uk Phone: +44 (0)1865 610724

RESEARCH

I am interested in algorithms and computational complexity, particularly in convex relaxations, discrete and combinatorial optimisation, graph homomorphisms, and submodularity. Most of my work lies at the intersection of the above, namely it is on constraint satisfaction problems (CSP) in its many forms (approximation, counting, decision, optimisation, promise).

From the available courses in Oxford's Department of Computer Science, the relevant courses are Computational Complexity, Advanced Computational Complexity, Probability and Computing, and Combinatorial Optimisation. (I will lecture the last one in MT 2022.)

Get in touch if you are interested in doing an undergraduate project, a master dissertation, or a PhD in algorithms, discrete mathematics, or computational complexity. I'm happy to supervise highly motivated students with a strong background in theoretical computer science and/or (any branch of) mathematics.

I currently serve, among many other roles, as the Director of Teaching.

All my publications are available online. My short CV is available here.

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

Conferences Programme Committees

• TCS: 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

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

Organiser

• 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
• Dagstuhl Seminar 18231 The Constraint Satisfaction Problem: Complexity and Approximability, 2018 (with M. Grohe, V. Guruswami, and D. Marx)

Other

• Informatics Europe, Board Member, since 2020
• London Mathematical Society (LMS) Computer Science Committee, since 2019
• EurAI PhD Dissertation Award, Panel Member, 2019
• EPSRC Peer Review College, Member, since 2018
• ACP Doctoral Research Award, Panel Member, 2018
• Royal Society International Exchanges Committee, Panel Member, 2015-2020

SUPERVISION AND MENTORING

PhD Students

• Tamio-Vesa Nakajima, since 2021
• Thomas Orton, since 2019 (with V. Kanade and R. Santhanam)
• Alexandre Brandts-Longtin, since 2018
• Jacob Focke, PhD 2020 (with L. Goldberg), On the complexity of counting homomorphisms under surjectivity constraints
  (→ postdoc at CISPA/MPI, Germany)
• Peter Fulla, PhD 2018, On the valued constraint satisfaction problem
  (→ faculty at Chuo University, Japan)
• Andrius Vaicenavičius, 2014-2017 (with P. Jeavons and C. McDiarmid)
  (→ transferred to pursue a PhD in applied AI)

Postdocs

• Jakub Opršal, since 2021
• Lorenzo Ciardo, since 2020
• Caterina Viola, since 2020
• Shuai Shao, 2020-2021 (→ University of Edinburgh, UK)
• Michael Kompatscher, 2020-2021 (→ Charles University, Czechia)
• Balázs Mezei, 2020-2021 (→ finance)
• Marcin Wrochna, 2018-2020 (→ University of Warsaw, Poland)
• Miguel Romero, 2017-2019 (→ Adolfo Ibañez University, Chile)
• Clément Carbonnel, 2017-2018 (→ CNRS, France)

BSc and MSc Students

• Costin Oncescu, fourth-year project, since 2021 (with J.F. Henriques), Characterising the optimisation geometry of modern deep neural networks
• Jáchym Solecký, MMathComSci 2021 (distinction), Minimum cut estimation using local queries
• Costin Oncescu, BA 2021 (distinction), Additive approximation of generalisations of submodular functions
• Eden Pelleg, MSc 2020 (distinction), Additive sparsification of graphs
• Yunus Ayidin, BA (distinction), 2020, Computational complexity of puzzles and games
• David Klambauer, MSc 2019 (distinction), On sparsifiability of two-variable CSPs
• Silvia Butti, MSc 2018 (dissertation), On sparsifiability of valued CSPs
• Gregor Matl, MSc 2018 (dissertation), On surjective and lower-bounded general-valued CSPs
• Ragnar Groot Koerkamp, MSc 2017 (dissertation), On rainbow-free colourings of uniform hypergraphs
• Andrius Vaicenavičius, MMath 2014, (Gibbs dissertation prize) (with P. Jeavons), A study of weighted clones

Research Internships

• Piotr Mitosek, internship funded by the RS, 2020 (with M. Wrochna)
• Joanna Ochremiak, internship funded by the EU, 2015
• Andrius Vaicenavičius, internship funded by the EPSRC, 2013 (with P. Jeavons)

College Lecturers

• Atılım Güneş Baydin, since 2021
• Matthias Lanzinger, since 2021
• Cristina Matache, 2020–2021
• Swaraj Dash, 2019-2021
• Matthew Katzman, 2019-2021
• Reino Niskanen, 2019-2020

TEACHING

Lectures

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

Classes

• Probability and Computing
• Computational Complexity
• Automata and Formal Languages
• Advanced Data Structures and Algorithms
• Theory of Data and Knowledge Bases
• Randomised Algorithms
• Data Structures and Algorithms
• Functional Programming
• Introduction to Programming

Tutorials

• Models of Computation
• Design and Analysis of Algorithms
• Algorithms and Data Structures
• Advanced Data Structures and Algorithms
• Linear Algebra
• Logic and Proof
• Discrete Mathematics
• Continuous Mathematics
• Functional programming
• Imperative Programming 1
• Imperative Programming 2
• Introduction to Formal Proof
• Object Oriented Programming
• Digital Systems
• Concurrency

Trivia

My official first name is Stanislav but I go by Standa /'stʌn.da/, which is 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 various reasons I try to minimise travel but you can always visit me (virtually) in Oxford.