data structures, algorithms, and algorithmic complexity are so interesting

Follow

@shoofle arguably my whole line of billiards research is a proof of concept for ideas that were originally motivated by computational complexity and its imo underexplored links to entropy and communication complexity and type theory

it's... arguably rather a long diversion, for a proof of concept, but maybe someday it will circle back xD

@fae ooooooo... the thing i always think about with algorithmic complexity is like. how much of a sense building a physics engine gave me for what efficiency means

@shoofle fun fact: take any (possibly infinite, etc) surface. consider the group of closed paths on it. pick any set of generators for the group.

the growth rate of the number of distinct possible paths by taking the product of n generators depends (up to constant factor) only on the surface, not on the generators u chose.

(in particular, it will be either polynomial or exponential, depending on whether the surface is hyperbolic)

Sign in to participate in the conversation
Awoo Space

Awoo.space is a Mastodon instance where members can rely on a team of moderators to help resolve conflict, and limits federation with other instances using a specific access list to minimize abuse.

While mature content is allowed here, we strongly believe in being able to choose to engage with content on your own terms, so please make sure to put mature and potentially sensitive content behind the CW feature with enough description that people know what it's about.

Before signing up, please read our community guidelines. While it's a very broad swath of topics it covers, please do your best! We believe that as long as you're putting forth genuine effort to limit harm you might cause – even if you haven't read the document – you'll be okay!