random coloring
[04-15-24]
For my stochastic processes final project I'm reading a paper about understanding the solution geometry of random coloring instances. The paper is: Dimitris Achlioptas, and Amin Coja-Oghlan. "Algorithmic barriers from phase transitions." 2008 49th Annual IEEE Symposium on Foundations of Computer Science. IEEE, 2008. I think it's quite neat. In this post I will organize some thoughts that I had after reading the proof sketches.
Formal complexity measure
[12-13-23]
Saw a cool complexity theory idea today. Quickly jotting it down so I don't forget it.
Exchanging triangles / squares for larger cycles and listing cycles
[12-26-23]
Proof from Appendix of Aboud FOCS22. "Hardness of approximation in P via short-cycle removal"
FPT part 1
[11-24-23]
Sometimes problems are hard. But sometimes they're less hard if you parameterize them correctly.
SAT notes: Demaine Fun with Hardness
[09-23-23]
We talked about a lot of special cases of SAT that are NP-hard in Erik Demaine's Fun with Hardness class. I have had a hard time keeping track of them all so I've created this little condensed reference for all the various versions.
