From Batch to Stream: Automatic Generation of Online Algorithms

We propose a new technique that converts batch processing programs (i.e., offline algorithms) to their online streaming version that takes one element at a time.
As a cool example, given the standard variance computation for a list of elements (left), our method can automatically generate Welford’s algorithm for online variance computation (right):

https://pbs.twimg.com/media/GMBpnclXcAEh9B9?format=jpg&name=4096x4096

Paper: https://arxiv.org/abs/2404.04743
Code: https://github.com/utopia-group/opera

Merklizing the key/value store for fun and profit


https://docs.canvas.xyz/blog/2023-05-04-merklizing-the-key-value-store.html

Distributed Snapshots: Chandy-Lamport protocol

https://blog.fponzi.me/2024-05-30-distributed-snapshots.html

Control structures
Xavier Leroy
English translation, 2023-2024

https://xavierleroy.org/CdF/2023-2024/index.html

What Goes Around Comes Around... And Around...
M. Stonebraker, A. Pavlo

It took three years to finish, but our follow-up to the 2006 "What Goes Around Comes Around" is finally out! Stonebraker and I examine the last 20 years in databases and discuss why relational databases + SQL will continue to remain on top.

https://db.cs.cmu.edu/papers/2024/whatgoesaround-sigmodrec2024.pdf

https://hal.science/hal-04535159/ Lesbre, Lemerre, [2024] "Compiling with abstract interpretation"

Anyway, I'll allow myself to advertise Valera's course on constructive mathematics. It is available online at https://www.youtube.com/watch?v=EHYiB19EYFs&list=PLRtkLMXefuh8EiRRuc7Uz-k6NKIIWHJf8

However, probably some knowledge of Russian is required.

Новая версия
Polynomial Functors: A Mathematical Theory of Interaction
https://arxiv.org/abs/2312.00990
Что там, не смотрел, но скорее всего, что исправления мелких багов.

Concurrent Data Structures Made Easy
C. Le, K. Gopinathan, K. Wen Lee, S. Gilbert, I. Sergey.

https://ilyasergey.net/assets/pdf/papers/obatcher-oopsla24.pdf
https://github.com/verse-lab/obatcher_ds/tree/paper-artefact

https://x.com/ilyasergey/status/1829026676623454661

Soundly Handling Linearity
W. Tang, D. Hillerström, S. Lindley, and J. G. Morris

https://blog.sigplan.org/2024/08/12/soundly-handling-linearity/

https://dl.acm.org/doi/10.1145/3632896

Swift: Error Handling Rationale

https://github.com/swiftlang/swift/blob/9315673c003875158852579bd1f33480cdec5461/docs/ErrorHandlingRationale.md#fundamentals

https://stringdiagram.com/wp-content/uploads/2024/08/graphicaltheoryofmonadsv2.0.pdf

The graphical theory of monads
R. Hinze, D. Marsden

Warning: requires some background, not a monad tutorial.

Capabilities for Control — ICFP 2024
M. Odersky

https://www.youtube.com/live/F70QZaMoYJQ?feature=shared&t=2090

34:50

What is Entropy?
John C. Baez, 2024

https://arxiv.org/pdf/2409.09232

The authors show that, with the right algorithmic enhancements, first-order methods(*) can be competitive with state-of-the-art Linear Programming solvers, even for problems requiring high-accuracy solutions. This opens up new possibilities and computational trade-offs when solving LP problems, especially for large-scale instances.

* In numerical analysis, methods that have at most linear local error are called first order methods.

Blog: https://research.google/blog/scaling-up-linear-programming-with-pdlp/

Paper (go read the blog for intro): https://www.openread.academy/en/paper/reading?corpusId=235376806