Although I didn't know it by that name, I have seen the bicyclic semigroup in competitive programming many times before (usually any problem involving intervals/brackets and segment trees).
For example in this problem https://codeforces.com/contest/1285/problem/E, one solution is to parse and count the number of top-level parentheses after small modifications. For example the original string might be "(()())()". Then "(()())" is 1, "(())()" is 2, "()()()" is 3.
This is solved with the following monoid to make incremental reparsing fast:
Monoid cached trees are extremely popular in competitive programming, but never by that name. It's always referred to as a "segment tree" without using any mathematical terminology more advanced than "associativity".
Due to its popularity, all kinds of crazy monoid states have already been explored (though you need to squint a bit to see them due to the terminology mismatch): https://codeforces.com/blog/entry/15890. I've never seen stack used though. You almost always want to compress the state as much as possible and the problems I've seen only needed stack depth (aka the bicyclic semigroup), not contents. Requiring O(N) to merge also highly limits its use cases.
Anyway, not sure how relevant this is to you since the use of monoids in data structures and for parallelism is slightly different (binary merges all the way down versus stopping at some chunk size).
> Automatically generating monoids such as the stack monoid from their corresponding simple sequential programs seems like an extremely promising area for research.
I was interested in this problem a while back and the papers I remembered being useful were:
The motivating example is whether you can generate a mergesort (where the monoid is combine two sorted lists) given an implementation of an insertion sort (where the sequential program is inserting one element by one into a sorted list).
I remember being disappointed by the answer after reading these papers but in the citation graph there are a bunch of relatively recent program synthesis papers. Maybe there's something better now.
There were a few interesting ideas by others in the original comment thread. Mostly on how to compress the sdp so you can get away with just one large QR code without flashing (for example by presharing a dictionary or stripping the sdp down to the bare minimum: https://webrtchacks.com/the-minimum-viable-sdp/).
I lost interest in this approach because it was way more practical to give up on serverless in exchange for only scanning in one direction instead of both ways (e.g., scan a QR code once on mobile to both open the webpage and join a websocket channel, then use it to upgrade to a webrtc connection). It's a neat trick for use cases like AR.js where this is natural to do: https://github.com/jeromeetienne/AR.js
It's pretty hard to fully protect in the first place because someone desperate enough can always inpaint (aka content-aware fill) over the watermark. Project Naptha has a pretty nice web demo showing how well that works for erasing text from images: https://projectnaptha.com/
Off-topic: Can you fill out your profile? I am not active on HN but I sometimes go by the initials fta elsewhere
I didn't expect to see Hopcroft/Kannan in that list. I used it in a course taught by Kannan and back then it was called "Computer Science Theory for the Information Age". Apparently the book is now called "Foundations of Data Science". I always thought the old naming was terrible but compared to the new title it actually describes the content a lot better since the book is mainly about CS theory and mathematical foundations for them. It was one of my favorite courses but I would not classify it as ML book.
Flashing qr codes was just a quick hack and actually doesn't work super well. I think if I had more time I would try compressing and stripping down the message more so it would fit in a single qr code instead (like in https://webrtchacks.com/the-minimum-viable-sdp/).
I have previously written about how to predict the next Math.random in Java (and hence Firefox also): http://franklinta.com/2014/08/31/predicting-the-next-math-ra...
The TL;DR; is that it is easy since you only have to brute force around 2^22 possibilities (which runs in < 1 second).
Someone then asked whether it is also possible in Chrome and Node: https://github.com/fta2012/ReplicatedRandom/issues/2. After examining the MWC1616 code I saw the same “two concatenated sub-generators” problem explained in this post. The implication of it is that you can brute force the top and bottom 16 bits independently. So it is also easy since that’s just doing 2^16 possibilities twice! Code: https://gist.github.com/fta2012/57f2c48702ac1e6fe99b
For example in this problem https://codeforces.com/contest/1285/problem/E, one solution is to parse and count the number of top-level parentheses after small modifications. For example the original string might be "(()())()". Then "(()())" is 1, "(())()" is 2, "()()()" is 3.
This is solved with the following monoid to make incremental reparsing fast:
Reference solution: https://codeforces.com/contest/1285/submission/92169958
Monoid cached trees are extremely popular in competitive programming, but never by that name. It's always referred to as a "segment tree" without using any mathematical terminology more advanced than "associativity".
Due to its popularity, all kinds of crazy monoid states have already been explored (though you need to squint a bit to see them due to the terminology mismatch): https://codeforces.com/blog/entry/15890. I've never seen stack used though. You almost always want to compress the state as much as possible and the problems I've seen only needed stack depth (aka the bicyclic semigroup), not contents. Requiring O(N) to merge also highly limits its use cases.
Anyway, not sure how relevant this is to you since the use of monoids in data structures and for parallelism is slightly different (binary merges all the way down versus stopping at some chunk size).