Talk archive
2022
Wed 13 Apr 2022
Anuj Dawar — Definable Inapproximability: New Challenges for Duplicator
Wed 16 Mar 2022
Victor Lagerkvist — The (Coarse) Fine-Grained Structure of NP-Hard SAT and CSP Problems
Wed 16 Feb 2022
Dor Minzer — An invariance principle for the multi-slice, with applications
Wed 19 Jan 2022
Dmitriy Zhuk — Heptachotomy of QCSPs
2021
Wed 8 Dec 2021
Lorenzo Ciardo — CLAP: A New Algorithm for Promise CSPs
Wed 10 Nov 2021
Chi-Ning Chou — Approximability of all finite CSPs with linear sketches
Wed 20 Oct 2021
Albert Atserias — Promise Constraint Satisfaction and Width
Wed 30 Jun 2021
Sivakanth Gopi — CSPs with global modular constraints: algorithms and hardness via polynomial representations
Wed 16 Jun 2021
Andrei Bulatov — Complexity classification of counting graph homomorphisms modulo a prime number
Wed 2 Jun 2021
Kevin Berg — Symmetric promise constraint satisfaction problems: Beyond the Boolean case
Wed 19 May 2021
Michael Pinsker — Smooth approximations
Wed 5 May 2021
Per Austrin — Optimal inapproximability with universal factor graphs
Wed 21 Apr 2021
Jacob Focke — Counting homomorphisms to $K_4$-minor-free graphs, modulo 2
Wed 14 Apr 2021
Sai Sandeep — Conditional dichotomy of Boolean ordered promise CSPs
Wed 31 Mar 2021
Alexandr Kazda — Minion homomorphisms give reductions for promise valued CSP
Wed 10 Mar 2021
Marcin Wrochna — Topology and adjunction in promise constraint satisfaction
Wed 24 Feb 2021
Simon Knäuer — Network satisfaction for symmetric relation algebras with a flexible atom
Wed 10 Feb 2021
Akbar Rafiey — On the complexity of CSP-based Ideal Membership Problems
2020
Wed 2 Dec 2020
Alex Brandts — The complexity of promise SAT on non-Boolean domains
Wed 18 Nov 2020
Pravesh Kothari — Strongly Refuting all Semirandom Boolean CSPs
Wed 4 Nov 2020
Sai Sandeep — \(d\)-to-1 hardness of coloring 3-colorable graphs with \(O(1)\) colors
Wed 28 Oct 2020
Silvia Butti — The Complexity of the Distributed Constraint Satisfaction Problem
Wed 21 Oct 2020
Barnaby Martin — QCSP monsters and the future of the Chen Conjecture
Wed 7 Oct 2020
William DeMeo — Complexity of the Homomorphism Problem for Boolean Models
Wed 30 Sep 2020
Aditya Potukuchi — Inapproximability of coloring problems in hypergraphs
Wed 23 Sep 2020
Neng Huang — On the Mysteries of MAX NAE-SAT
Wed 9 Sep 2020
Caterina Viola — The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains
Wed 2 Sep 2020
Dmitriy Zhuk — No-rainbow problem and the complexity of the Surjective Constraint Satisfaction Problem
Wed 19 Aug 2020
Joshua Brakensiek — The power of the combined basic LP and affine relaxation for promise CSPs
Wed 22 Jul 2020
Libor Barto — Baby PCP theorem and reductions between Promise CSPs
past talks
·
what is this seminar about?
·
home