Taught a bonus lecture for a course on Algorithms for NP-hard Problems today. Material won't be on the exam, so technically, this lecture was "just for fun".
Quite some pressure to make coming to class on Friday morning 8:45am worth it for a gang of 20-year-olds.
Students were a hoot. They were listening actively and participating. Great to meet them. Had a blast 
Afterwards, some of them thanked me for the "really great lecture" 
Ab-so-lute-ly exhausted now.
Given a decision problem Π, I need a name for the polytope constructed by taking the convex hull of the characteristic vectors (or binary inputs of fixed length) corresponding to "yes" instances. If nobody has a better suggestion I might use "the characteristic polytope of Π". OTOH, for $reasons I'd much rather use something more standard / widespread.
Apparently I missed that Zhuk posted a *simplified* proof of the CSP Dichotomy Conjecture back in January: https://arxiv.org/abs/2404.01080
I'd really love to understand all of this!
Second: complexity classes! P, PP, BPP, ZPP, are all actual #ComputationalComplexity classes. (I swear! It's true!)
Q2: Without looking it up, do you know how they relate to each other?
3/4
Very nice and clear article by @benbenbrubaker on @QuantaMagazine, describing the meaning and implications of the latest advances regarding random #quantum circuit sampling:
https://www.quantamagazine.org/new-algorithm-closes-quantum-supremacy-window-20230109/
Heck, I felt I understood something! #TheoreticalComputerScience #TCS #ComputationalComplexity
Speaking of hashtags, I'm curious how the TCS community feels about making "complexity" searchable, given how overloaded that term is. #complexity is at least partially taken, #computationalcomplexity is super long. #TCScomplexity? More broadly speaking, any interest in making #TCS a thing?
Thoughts @rrwilliams @tomgur @boazbaraktcs @joshuagrochow @ccanonne?
