On Monday, November 17, at 3:30pm ET, I get to give the next VCGT talk on the computational complexity of the game #BattleSheep: https://sites.google.com/view/virtual-cgt/seminar

Abstract: Battle Sheep is a board game published by Blue Orange Games where players take turns moving stacks of sheep tokens around a hexagonal board, always leaving at least one sheep behind. In this talk we'll learn the basics of the game, play once, and finally show that determining the winnability of the game is PSPACE-complete. This talk assumes no prior knowledge of computational complexity.

#CombinatorialGames #ComputationalComplexity #PSPACE

The second day of #Integers2025 was excellent! I heard some great talks, especially one from Carrie Finch-Smith. Me and the other three gamesters I know about here also took some time and I think we found a game to be #PSPACE complete, so we're definitely going to be writing that up!

Tonight we got to see a tree that owns itself. Cool stuff!

The organizers have been totally awesome. Great conference so far!

#NumberTheory #CombinatorialGames

🤩#call4reading

✍️Towards a #quantum-inspired proof for #IP = #PSPACE #by Ayal Green, Guy Kindler, and Yupan Liu

🔗10.26421/QIC21.5-6-2 (#arXiv:1912.11611)

#Quantumwalks #Singularcontinuousmeasure

I finally wrote a #CombinatorialGames piece I've wanted to write for a long time. It's about how Col's computational complexity went confusedly unsolved for over 35 years and how I got scooped at the end of that but still got a cool result. https://combinatorialgametheory.blogspot.com/2024/08/the-curious-case-of-cols-computational.html

#ComputationalComplexity #PSPACE

I'm going to be talking about Algorithmic CGT in India in a few weeks. I really want to start with the fundamentals of #PSPACE, so I want to present the Boolean Formula Game (https://en.wikipedia.org/wiki/Formula_game). Whenever I talk about a game, I like to play it with the audience.

So... I coded a working version: http://kyleburke.info/DB/combGames/booleanFormula.html

It's not particularly fun, mostly because it's often very easy to win as the True player. (I didn't implement any deep strategies to generate more interesting formulas. Advice is welcome!)

Nevertheless, I'm very excited to use this next week and in future talks. #CombinatorialGames #ComputationalComplexity #WebGames

In our effort to put courses online, we continue lectures on Algorithmic Lower Bound Course. Now you can watch

Lesson 4-11: Algorithmic Lower Bounds by Mohammad Hajiaghayi - NP-Completeness and Beyond

(FEEL FREE TO SUBSCRIBE TO YOUTUBE @hajiaghayi FOR FUTURE LESSONS Premiering on WEDNESDAYS)

https://youtu.be/VZyffnAb1r0 (Lesson 4: 3-Partition Problem & Proving NP-Hardness)

https://youtu.be/4fCD9_1eQw0 (Lesson 5: Puzzle Problem NP-Hardness & 3-Partition)

https://youtu.be/FIyEj72-UJQ (Lesson 6: 3-SAT Problem & Proving NP-Hardness)

https://youtu.be/tbSJzaKx2pA (Lesson 7: Puzzle Problem NP-Hardness via 3-SAT)

https://youtu.be/voRVebBsh94 (Lesson 8: Fine-grained Subcubic Complexity: Part 1)

https://youtu.be/gRURSM6QARo (Lesson 9: Fine-grained Subcubic Complexity: Part 2)

https://youtu.be/qPw82bTAXkc (Lesson 10: Fine-grained Subquadratic Complexity 1)

https://youtu.be/C6j4avVkI7U (Lesson 11: Fine-grained Subquadratic Complexity 2)

#AlorithmicComplexity,

#3SAT,

#3Partition,

#subquadratic,

#subcubic,

#Finegrained,

#HardnessExploration,

#NP,

#PSPACE,

#NPComplete,

#LogSpace,

#ExponentialComplexity,

#ParallelComputation,

#PvsNP,

#NPSPACE,

#NonDeterministicSpace, hashtag

#SavitchTheorem,

#ComplexityClasses,

#Reductions,

#ImportantProblems,

#CommunicationComplexity, hashtag

#GeometricProblems,

#AlgorithmDesign,

#ComputationalComplexity,

#TheoreticalComputerScience,

#AlgorithmicLowerBounds

For comprehensive handwritten lecture notes on this course, visit the instructor's website:

http://www.cs.umd.edu/~hajiagha/
The course textbook "Computational Intractability: A Guide to Algorithmic Lower Bounds" by Demaine, Gasarch, and Hajiaghayi is available for free at:

https://hardness.mit.edu/