The quadratic problem nobody fixed

(iev.ee)

51 points | by lalitmaganti 4 days ago

2 comments

  • adzm 10 minutes ago

    Is there any reason that RE#'s two-pass approach couldn't be adopted by other regex engines?

    Ah, there is a post with more detail about RE# and discussion here recently that I must have missed: https://news.ycombinator.com/item?id=47206647

    • ChadNauseam 1 hour ago

      You can make it lowercase and replace the em-dashes with hyphens, but we can still tell. That said, interesting article. I look forward to reading the PLDI when it comes out. Eliminating an O(n^2) in a primitive as important as regex is extremely valuable, so this is impressive work and clearly wasn't easy

      • halperter 48 minutes ago

        I'm of the opinion that their post is still human-written. They describe in their first blog post that it's human written (which could be a lie, but oh well) and their other blog posts seem to have the same informal lowercase hyphenated writing style. Sentance length varies throughout the posts. Sure, you could prompt this writing style, but I lean towards thinking that the piece is human written.

        • dooglius 43 minutes ago

          The fact that terms like Aho-Corasick, PLDI, Go, etc. are properly capitalized, including if they begin sentences, but otherwise sentences are uncapitalized, makes me think it's an explicit LLM instruction "don't capitalize the start of sentences" rather than writing style.

          • tux3 11 minutes ago

            Oh no, this is just what that writing style looks like. Names and acronyms are usually capitalized normally.

            I keep being surprised by the magnitude of the disconnect between this place and the other circles of hell. I'd have thought the Venn diagram would have a lot more overlap.

            • jlarocco 33 minutes ago

              What's with this silly "all lower case" style lately?

              Jack Dorsey's layoff message last month did the same thing.

              Is it some kind of "Prove you're not an AI by purposely writing like an idiot" or something?

              • gfody 8 minutes ago

                not anti-capitalist, just a subtle preference away from capitalism

          • mkehrt 34 minutes ago

            This reads nothing like any AI text I've read before.