Thanks @brinda.eu for the nice sketch of our work with Ondřej Sladký! 👇

1/9 Just out: k-mer indexes are the backbone of fast search in genomic data, but many degrade under small k, subsampling, or high diversity. With Ondřej Sladký and @pavelvesely.bsky.social we asked: can we build one that works efficiently for any k-mer set?

🧮 Just out in Bioinformatics Advances: “FroM Superstring to Indexing: A space-efficient index for unconstrained k-mer sets using the Masked Burrows-Wheeler Transform (MBWT)”  Full article available: https://doi.org/10.1093/bioadv/vbaf290  Authors include: @pavelvesely.bsky.social, @brinda.eu

WHAT

Optimized k-mer search across millions of bacterial genomes on laptops https://www.biorxiv.org/content/10.1101/2025.11.23.690050v1

Ubohost Tohle jedno slovo nejlépe vystihuje počin jednoho z nově zvolených ústavních činitelů téhle země Začít mandát tím, že sundáte ukrajinskou vlajku z budovy pěkně ilustruje to, o co mu jde. Nikoliv o zlepšení téhle země, ale jen o rozdmýchávání vášní Co s tím? Já si koupil drona

During the next two months, I will have two long talks about streaming algorithms / data sketching for high-school students. Did you give a similar talk? What was your experience?

Tomorrow at ESA: my former postdoc Nick Matsakis will present our streaming algorithm for diameter in high-dimensional spaces. Very simple: just 4 lines of pseudocode, and yet, achieving optimal approximation. Joint work with Magnús M. Halldórsson. arxiv.org/abs/2505.16720

Pythagorean Triple Square Day, as one man affectionately calls 9/16/25, is a day like no other this century.

Zstandard's --long range mode works wonders for assemblies, but needs uninterrupted single line sequences. *AllTheBacteria 661k, multiline fasta* gzip (pigz): 751GB zstandard --long: 641GB (30% original size) *Single line fasta* gzip (pigz): 700GB zstandard --long: 232GB (10% original size)

🌎👩‍🔬 For 15+ years biology has accumulated petabytes (million gigabytes) of🧬DNA sequencing data🧬 from the far reaches of our planet.🦠🍄🌵 Logan now democratizes efficient access to the world’s most comprehensive genetics dataset. Free and open. doi.org/10.1101/2024...

At scale, the way that we store (and process) data matters! Many may think that the way we keep data, the file formats we adopt, and the way that we compress data are unimportant details, but they are, in fact, critical considerations to allow science to move forward at scale!

Springer publishes a P ≠ NP "proof" and Eric Allender has words to say. blog.computationalco...

A monumental collaborative effort with many incredible people ☺️ Proud to be part of this!

Slides from my talk (with @kamilsjaron.bsky.social) on an history of k-mers in bioinformatics: rayan.chikhi.name/pdf/2025-kme...

Nicely written blog post by David Eppstein on the Boyer–Moore (deterministic) streaming algorithm to find a majority element in a stream, and its extensions, first to the turnstile model, and then to frequency estimation (Misra–Gries). 11011110.github.io/blog/2025/05... via @theory.report

We finally concluded the meeting. Thanks to all attendees for their scientific contributions and for traveling (near or far) to the meeting! Thanks to the local organizers for the infrastructure and catering, and thanks to the co-organizers @yaronorenstein.bsky.social @camillemrcht.bsky.social!

@pavelvesely.bsky.social (CSI) on the mother of spss: masked superstrings that help you representing k-mer sets in a very compact way. He actually takes a lot from @brinda.eu since he squeezed 3 papers in a 12 min talk 😳

🚀 Just 2 days to go! Excitement is building for #RECOMBseq 2025 in Seoul 🎉 Join leading researchers as we dive into cutting-edge computational genomics, from single-cell to long-read sequencing. 🗓 April 24-25 📍 Seoul 📄 Program: recomb-seq.github.io/program/ #RECOMB2025 #Genomics #Bioinformatics

A decade ago, we had thousands of bacterial genomes. Now, we have millions. How to scale computational methods? Our paper in @naturemethods.bsky.social answers this: use evolutionary history to guide compression and search. rdcu.be/eg4OA w/ @baym.lol, @zaminiqbal.bsky.social et al. 🧵1/

So glad this is finally out. The method has been instrumental in allowing us to compress the AllTheBacteria data - ~2 million bacterial genomes shrink from 3Terabytes (gzipped) to 100Gb using phylogenetic compression. Great work by @brinda.eu

European Sympsium on Algorithms 2025 will be held in Warsaw in September, as part of ALGO 2025. Do you have great work on design and analysis of algorithms? Submit it by April 23! algo-conference.org/2025/esa/

STOC in Prague! With FOCS deadline over, there's no excuse to postpone the registration. acm-stoc.org/stoc2025/

Taking a break from the submission season? Swing by the Workshop on Algorithms for Large Data (Online), WALDO 2025 🗓️ April 14—16: waldo-workshop.github.io/2025.html Registration is free! (but necessary by April 7)

Aleksander {\L}ukasiewicz, Jakub T\v{e}tek, Pavel Vesel\'y SplineSketch: Even More Accurate Quantiles with Error Guarantees https://arxiv.org/abs/2504.01206

The upcoming trade war with the penguins, Is a good excuse to mention the following fantastic book... en.m.wikipedia.org/wiki/War_wit...

The talks regarding Ukraine and Russia will fail. We have been there multiple times and this pattern will not suddenly change. Even the chances of a mere ceasefire are - even when not zero - rather modest. Though if it would occur it would fall apart, eventually, and probably soon. It is inevitable.

🚨 Late-Breaking Posters! 🚨 Missed the deadline? We’ve got you covered! Submit your poster abstracts for RECOMB-seq and showcase your work in sequence analysis & computational genomics. 🗓️ Late poster deadline: April 5, 23:59 AoE Don't miss this last chance! 🚀 #RECOMBseq

Open question for CS community: What to teach from modern parallel algorithms to 2nd CS undergrads? We teach sorting networks (bitonic sort) and boolean circuits (summation, multiplication), which is fine but does not feel very modern. What else to show about parallelism in, say, 2 lectures?

I'm going to slowly repost my math notes from the other site🐦 here🦋; it's the only thing I posted over there that I think may have some long-term value & worth not deleting. These started out as notes for myself, but people seem to appreciate them. 😅 I'll keep track of all of them in this thread.

An announcement: the Workshop on Algorithms for Large Data (Online) 2025 will take place 🗓️ April 14—16. waldo-workshop.github.io/2025.html Goal: "to generate new collaborations through an emphasis on big data algorithms, broadly defined" Register (free) by ⏰ April 7 to access the virtual platform

#STOC2025 (June 23-27, Prague) Theory Fest is looking for workshop proposals. The deadline is March 9th. Apply here: stoc2025theoryfest.netlify.app

New paper: Simulating Time With Square-Root Space people.csail.mit.edu/rrw/time-vs-... It's still hard for me to believe it myself, but I seem to have shown that TIME[t] is contained in SPACE[sqrt{t log t}]. To appear in STOC. Comments are very welcome!

So many were freaking out regarding Trump's statements in reference to Ukraine and it is true that many of those statements were rubbish and even factually outright wrong.

In the late 2000s, computer scientist Stephen Cook (left) bet $100 that it was impossible to use the same piece of memory for storage and calculations simultaneously. In 2020, his own son (right) proved him wrong — and collected the cash. https://buff.ly/4i6G7Tz

A bit of poetry one day before the deadline: It's going to be tight ... but we have one more night! 🌃

🚨 Keynotes at RECOMB-seq 2025! 🚨 🌟 Alicia Oshlack – computational transcriptomics @aliciao.bsky.social 🌟 Rayan Chikhi – sequencing data structures @rayanchikhi.bsky.social 🗓️ Dates: April 24–25, 2025 📍 Seoul, South Korea recomb-seq.github.io/speakers/

Excited to co-organise another summer school on learning theory! This time in beautiful Odense, Denmark. Please share and apply here: event.sdu.dk/algoml2025

Looking for a PhD position or a post-doc position in theoretical computer science? Consider applying to one of our calls, closing January 10! barc.ku.dk/career/

Very interesting (short) paper by Graham Cormode (@grahamrc.bsky.social), "Applications of Sketching and Pathways to Impact", using sketching algos as case study to see how to go from theory to—impactful—practice, and what to keep in mind in the process. (Small) sample below doi.org/10.1145/3584...

Indeed, I was most productive when I had to the most time to think