Talk archive
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
upcoming talks
·
past talks
·
what is this seminar about?
·
home