Post

My WABI submission: anti-lexicographic SUS-anchors. For sigma=4, this selection scheme (a k=1 sampling scheme) has density within 1% of the lower bound! The idea: find the smallest* substring that does not have a 2nd occurrence, and sample its start pos. curiouscoding.nl/posts/sus-an...

22/5/26, 7:07 pm2 reposts4 likes

Ragnar {Groot Koerkamp}

@curiouscoding.nl

22 May

*: small w.r.t. the anti-lexicographic order, which minimizes the first character and maximizes the remaining ones. So AZZZZ is a small string in this order. You might recognise this from my thesis or Pisa DSB talk. But it's such a simple yet strong result, it deserves more attention :)

Ragnar {Groot Koerkamp}

@curiouscoding.nl

22 May

All are invited to help with a proof of the density [which would be great for an extended version]. I have ideas, but need someone to discuss them with, and it gets a bit more messy than I hoped.

Ragnar {Groot Koerkamp}

@curiouscoding.nl

2 June

arxiv.org/abs/2606.01190

arxiv.orgThe anti-lexicographic SUS-anchor: a near-optimal k=1 sampling schemeIn recent years, there has been a renewed interest in the search for low density minimizer schemes. These schemes take a window of $w$ consecutive $k$-mers, and sample one of them: the smallest under ...

Camille Marchet ⚡

@camillemrcht.bsky.social

22 May

Ragnar {Groot Koerkamp}

@curiouscoding.nl

22 May

OMG OMG the name actually works better than I realized. It could be abbreviated Anti-SUS or so, indicating they're the smallest string that's not hidden anymore