Seminar series
Date
Tue, 21 Jan 2025
Time
14:00 -
15:00
Location
L4
Speaker
Standa Živný
Organisation
University of Oxford
I'll discuss how a certain notion of symmetry captures the computational complexity of approximating homomorphism problems between relational structures, also known as constraint satisfaction problems. I'll present recent results on inapproximability of conflict-free and linearly-ordered hypergraph colourings and solvability of systems of equations.