Trying to tame the NP-complete beast — writing a paper about my algorithm for solving the Hamiltonian cycle #graphs #hamiltoncycle #npcomplete #graphalgorithms #computerscience #heuristics #optimization #research #computationalcomplexity #hacking #latex

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.

Dr. Alexandra Kolla will be presenting "Quantum Max Cuts and Local Hamiltonians" in the Codes & Expansions (CodEx) seminar tomorrow Mar 4, 2025 at 10am PST = 19:00 CET. Sign up on the website: https://www.math.colostate.edu/~king/codex/

I got stuck in a bathroom stall today at #CGTC. Best pun: I had a PeeSPACE-hard problem.

This is a joke, but not a lie.

If you see a door handle like these photos, you push like so to release the lock.

Harm Derksen will be talking about "Invariant Theory and [Computational] Complexity" in tomorrow's online CodEx Seminar: https://www.math.colostate.edu/~king/codex/

Tue Jan 28, 2025 10am Pacific
Sign up on the website for the zoom link

Heard of AIM SQuaREs? (if you haven't, you should: https://aimath.org/programs/squares/)

Now we have Simons-Jane Circles (https://simons.berkeley.edu/participate/circles-call-proposals), at what I'd call the intersection of #Math and
#CS (#TheoryCS).

Both fund small collaborations (~3-6) for 3-4 weeklong visits over 2-3 yrs.

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.

#Tensors Everywhere in #Complexity

Me! At the colloquium.

With connections to geometric complexity theory, graph isomorphism, group isomorphism, #quantum entanglement, and post-quantum-secure cryptosystems.

Online Fri Oct 25 2024 at IU Bloomington CS: https://events.iu.edu/siceiub/event/1663944-tensors-everywhere-in-complexity

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!

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

I just finished listening to the latest If Books Could Kill episode, this one about Michael Lewis' book on Sam Bankman-Fried: https://twitter.com/IfBooksPod/status/1786021820941963597

Saying that chess is too simple is a huge red flag for those aware that it's EXPTIME-hard. (https://www.sciencedirect.com/science/article/pii/0097316581900169) If you can solve Chess scenarios effortlessly, then you can solve all sorts of extremely heavy computational problems that elude us. #CombinatorialGames #ComputationalComplexity

@rottenindenmark

It's well known you can find a solution to the linear Diophantine equation

$$a_1{x}_1+a_2{x}_2+\dots +a_n{x}_n=c$$

in polynomial time using the Extended Euclidean Algorithm. But I haven't been able to find a clear answer for the complexity of finding a non-negative integer solution, that is, $x_i\ge 0$.

The unbounded knapsack problem is NP-complete, and this is the case where the weights and costs are equal, but I'm not sure that the NP-hardness reduction applies given that additional constraint.

I have also found a statement that the "multidimensional knapsack problem" is NP-hard even with a single row, which seems to match this, but I lack a copy of Papadimitriou and Steiglitz to verify that statement, and can't figure out the reduction.

If this problem is NP-hard, then I'm also interested in showing that a related problem is also NP-hard: if we have one non-negative solution, can we find a second one? I'm trying to answer a question about the special case $c=\sum _{i=1}^n{a}_i$.

This year's #Turing Award winner is of course Avi Wigderson. I found this highly accessible talk by him on his work on randomness and pseudorandomness, which form the basis of much of cryptography and other parts of computers science. https://www.youtube.com/watch?v=Jz1UoAWD80Q #mathematics #computationalcomplexity #computerscience #random #pseudorandom

Two of my papers recently got submitted (kyleburke.info/?main=research) so I now have some #CombinatorialGames I implemented that I can share.

The first of these is Paint Can: http://kyleburke.info/DB/combGames/paintCan.html. This game has stacks of bricks: blue, red, green, and gray. A player can either take a green brick or a brick of their color (Red or Blue). (Neither player can choose gray bricks.) When they remove a brick, that also removes all bricks above that one. Any pile that has non-green bricks also has a paint can on top of it. When any brick is removed, the can spills and all the remaining bricks in that stack become green.

#PaintCanGame is novel because each component has very low stakes (all options are to nimbers or zero) but the game is still complicated (NP-hard) to play optimally.

P vs. NP: The Biggest #Puzzle in #ComputerScience

"Are there limits to what #Computers can do? How complex is too complex for #Computation? The question of how hard a problem is to solve lies at the heart of an important field of computer science called #ComputationalComplexity."

https://www.youtube.com/watch?v=pQsdygaYcE4

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