Postdoc position in Cambridge with Julia Wolf:
Julia is a phenomenal researcher and a wonderful collaborator. She is advertising a 2-year postdoc in additive combinatorics and model theory.
Closing date: 16 March. Details: jobs.ac.uk/job/DQP803/postdoctoral-research-associate-fixed-term
Today the winter Olympics open. Russia and Belarus are allowed to participate under neutral flag.
Picture by Gatis Šļūka
Dear Gautam, your notes and videos are really great! Indeed I learned a lot from them, and with Pavel Hubáček, we teach DP based on your notes + a couple of other sources: iuuk.mff.cuni.cz/~vesely/vyuk...
Thanks a lot for sharing them!
I am looking for a postdoc to develop high-performance algorithms in computational genomics. Email or DM me if interested. For more information, see hlilab.github.io/vacancies. RTs appreciated!
The #dblp computer science bibliography faces a strong demand. But its net budget is shrinking. This is why we humbly ask for your kind support in the form of a donation to Schloss #Dagstuhl LZI.
Learn more or donate here:
www.dagstuhl.de/en/dblp/donate
Thank you very much!
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
Thanks for your interest! Unfortunately, we don't have such an online class, and it'll actually be in Czech.
I've already given such a talk last year, starting with some motivation and then talking about cardinality estimation (hiding many details). About 50 students attending, some interacting at the beginning. Slides in Czech (hopefully easy to translate nowadays):
docs.google.com/presentation...
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?
Btw, Nick's profile: @nickmatsakis.bsky.social
The algorithm gives more than just an estimate for the diameter: Using the stored points, one can sqrt(2)+epsilon-approximate Furthest Neighbor queries or 1.22-approximate the Minimum Enclosing Ball. The approx. ratio for diameter is optimal but it's still open for MEB. Lots of nice open problems!
Specifically, for sqrt(2)+epsilon-approximation of diameter, the AS'10 algorithm stores O(1/epsilon^3 log(1/epsilon)) input points, and we managed to shave off one factor of 1/epsilon. Still, we can only prove a lower bound of 1/epsilon, and closing the gap is a nice open problem!
The AS'10 algorithm covers points by blurred balls, and this approach overall works. Adding a few ideas, we have circumvented the issue in AS'10, slightly simplified the algorithm and its analysis, and improved the space bounds.
We in fact simplify a nice paper by Agarwal and Sharathkumar from SODA'10 and Algorithmica '15. Yet, despite that it's published in a decent journal, there appears to be a subtle flaw in the argument, and fixing it probably requires using more space...
link.springer.com/article/10.1...
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...
Yes! Even a full hard drive with family photos is apparently a useful computational resource.
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
Thanks a lot for organizing the workshop! I really enjoyed it!
