Earlier versions of the work were featured on HN [3][4], but this is much more sophisticated. (plus a few more zero-comment submissions)
The basic idea (bicyclic semigroup and binary search) is the same as the submission. I think earliest attribution is to Bar-On and Vishkin[5] from 1985. Another implementation of this idea is in pareas[6], an experimental GPU-accelerated compiler.
I believe this work is publishable and would love to work with a student to resubmit it. Especially if you're a student or prof in Sydney, please reach out.
[1]: https://arxiv.org/abs/2205.11659
[2]: https://github.com/raphlinus/raphlinus.github.io/issues/66
[3]: https://news.ycombinator.com/item?id=24385095
[4]: https://news.ycombinator.com/item?id=27164009
You can solve the same problem with Range Min Query Tree. The query for balanced or unbalanced parentheses is O(log N). A two or three level RMQTree can represent billions of parentheses already (a two-level tree of 65536 branch factor = 4B parentheses). The query is O(65536 + 65536) or effectively O(1). For a four-level tree of 256 branch factor, the query is O(256 + 256 + 256 + 256) or O(1). It becomes a problem of memory access on the number of levels vs the number of entries to process per level. A total = 0 and min > 0 mean the parentheses are balanced.
The parentheses can be broken up into multiple segments, and be processed in parallel. Multiple RMQTrees can be used, one per segment, and the trees can be processed in parallel. Need to have a final pass to sum up the 'total' and 'min' from all the RMQTrees. Parallel processing probably doesn't gain much.
I've heard that phrase couple of times, and cannot stop noting that then every real-world algorithm is "effectively O(1)", because in real world we have bounded inputs and RAM. E.g. every integer is O(2^64) = O(1).
If we need to say that something is really fast, let's just say that. E.g if a CPU needs to iterate something 65536 + 65536 times, we can just say that it would take about 0.1ms on 1GHz CPU, no need to involve asymptotic.
E.g. Scala boasts that their Vector implementation is "effectively constant", while in doing up to 5 non-consecutive RAM accesses, that screws up the CPU cache. But if we can bound something to "no more than 5 operations", then I can say that any array in 32-bit arch is "no more than 2^32 operations", which is equal to O(1).