Today Jose Correa from the University of Chile will deliver an (online) survey talk at Bangalore Theory Seminar on "Prophet inequalities".
Last week, Christian Coester (Oxford) gave a tutorial on mirror descent (and applications in online algorithms)
Link: www.csa.iisc.ac.in/theorysemina...
How did I miss this?! A recent (2025) survey by Rocco Servedio on PAC learning and its variants, and recent results in these learning models:
arxiv.org/abs/2511.08791
(Anything by Rocco is worth reading!)
Two cartoon characters, a computer scientist and a physicist, arguing whether the universe is discrete or continuous
From the latest SMBC comics @smbccomics.bsky.social, a 5-page collaboration between @zachweinersmith.bsky.social and Terry Tao on #maths: www.smbc-comics.com/comic/sphere...
THE UNIVERSE IS CHUNKY
A seemingly simple 🧩: let G be an arbitrary undirected (simple) graph on n vertices. Does G always have a cut with at least half its edges?
![Draw U1,...,Un independently and uniformly in [0,1], and compute the argmax of log(ai-log log(1/Ui). Call that Z.
Then Z is distributed proportionally to the weights a1,..,an](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:ac6qioenkpl3jmmnib3tpbhb/bafkreieentf6mvng3y5ge2rirgbjjd2p5zi4eucfpjj6bcam47pipufmpm)
Draw U1,...,Un independently and uniformly in [0,1], and compute the argmax of log(ai-log log(1/Ui). Call that Z. Then Z is distributed proportionally to the weights a1,..,an
Random fact of the day: imagine you have weights a₁,...,aₙ≥0 and want to sample according to these weights. What's an efficient way to do so?
You may say Huffman coding, etc. Yes, but... there's a way that's more fun: the Gumbel trick!
The 2nd Quantum Cambridge–Oxford–Warwick (QCOW) Workshop will take place at Warwick on April 23–24. Theme: Quantum Learning Theory. The programme will feature tutorials and accessible in-depth talks on recent advances by leading experts. Speakers/updates:
qcow.cs.ox.ac.uk/
This new preprint by Hugo Aaronson, Tom Gur, and Jiawei Li on quantum pseudodeterministic* algorithms, a line of research hitherto unexplored, seems quite interesting! cc/ @tomgur.bsky.social @jiaweili.bsky.social
arxiv.org/abs/2602.17647
*must consistently output a canonical solution w.h.p.
We want to evaluate $$ \sum_{\color{red}k=0}^\infty (\color{red}k+1) \color{blue}p^{\color{red}k}\,. $$ Introduce the function $f$, for $|\color{blue}x|<1$: $$ f(\color{blue}x) = \sum_{\color{red}k=0}^\infty \color{blue}x^{\color{red}k}\,. $$ That's a nice geometric series, and we easily get $f(\color{blue}x) = \frac{1}{1-\color{blue}x}$. So we can differentiate that: $$ f'(\color{blue}x) = \frac{1}{(1-\color{blue}x)^2} $$ But $f$ was defined as a power series, and we can also differentiate *that* termwise: $$ f'(\color{blue}x) = \sum_{\color{red}k=1}^\infty \color{red}k \color{blue}x^{\color{red}{k-1}} = \sum_{\color{red}k=0}^\infty {(\color{red}k+1)} \color{blue}x^{\color{red}{k}}\,. $$ Well, $f'(\color{blue}x)= f'(\color{blue}x)$ (!), so we can use both expressions, and evaluate them at $\color{blue}p$: $$ \boxed{\sum_{\color{red}k=0}^\infty {(\color{red}k+1)} \color{blue}p^{\color{red}{k}} = \frac{1}{(1-\color{blue}p)^2}} $$
Let's say you want, e.g., to compute the expectation of a Geometric r.v. That'll involve, at some point, evaluating a series of the form "Σ (k+1) p^k" which looks like what Lovecraft may have done to a geometric series. How to do it?
One trick I enjoy: differentiate the same function, in two ways!
A bit, typically encoded as 0 or 1, is a binary value encoding a unit of information. A qubit is the quantum analogue, encoding a unit of quantum information.
Introducing the hobit, encoding a unit of fantastic information!
3rd "Mathematics of Data" Summer School is being held in Singapore in June. Applications for attendance (with accommodation for most & no registration fee for all) are open throughout February and possibly longer: ims.nus.edu.sg/events/ma_da...
New short note up! In which I attempt to explain something which took me a good ten years to understand: a lower bound method for symmetric properties of distributions, or "how to use univariate polynomials to build your hard instances"
Comments welcome!
📝 eccc.weizmann.ac.il/report/2026/...
Screenshot of the YouTube playlist for the course.
On the topic of online resources, worth spreading the word again about Ryan O'Donnell's "CS Theory Toolkit" course: "Covers a large number of the math/CS topics that you need to know for reading and doing research in Computer Science Theory"
youtube.com/playlist?lis... @booleananalysis.bsky.social
An exciting graduate summer school at NUS on "Mathematical Aspects of Data Science" on June 22—July 1, organized by Daniel Bartl, Shahar Mendelson, Jonathan Scarlett , and Roman Vershynin.
Free registration, (some) free accommodation. Apply by ⏰ Feb 27.
Details: ims.nus.edu.sg/events/ma_da...
Quantum Toolbox (15): Relating Relative Entropy and Fidelity (1/6):
Quantum Toolbox (13): Matrix Geometric Mean (1/7)
The cover of the first issue of the magazine, "Polynomial Times" (2025-26) Featured articles: - Watermarks and Pseudorandom Codes - Edge Coloring in Nearly Linear Time - The Compressed Oracle Method and Its Generalization - Optimal List Decoding
This new magazine by the @simonsinstitute.bsky.social looks really cool! And great name, too. It was the best of times. Also the worst-case of times.
View online: simons.berkeley.edu/media/28058/...
It was a pleasure to work with the team at Futurum to develop these resources on #privacy — I hope you find them interesting (and enjoy the activity sheet puzzle 🧩!)
futurumcareers.com/make-some-no... @futurumcareers.bsky.social
Quantum Toolbox (12): Bretagnolle-Huber Inequality (1/6)
Congratulations!! 🎉
Quantum Toolbox (11): Generalized Operator Schwarz Inequality (1/6)
![A short proof: here is the LaTeX code.
**Proof.** We have, for any $\color{blue}{\lambda} \in\mathbb{R}$,
\begin{align*}
\mathbb{E}[(X-\color{blue}{\lambda})^2]
&= \mathbb{E}[(X-\color{red}{\mathbb{E}[X]} + \color{red}{\mathbb{E}[X]} - \color{blue} {\lambda})^2] \\
&=\mathbb{E}[(X-\color{red}{\mathbb{E}[X]})^2 + 2(X-\color{red}{\mathbb{E}[X]})(\color{red}{\mathbb{E}[X]} - \color{blue} {\lambda}) + (\color{red}{\mathbb{E}[X]} - \color{blue} {\lambda})^2]\\
&=\underbrace{\mathbb{E}[(X-\color{red}{\mathbb{E}[X]})^2]}_{=\textrm{Var}[X]} + 2\underbrace{\mathbb{E}[X-\color{red}{\mathbb{E}[X]}]}_{=0}(\color{red}{\mathbb{E}[X]} - \color{blue} {\lambda})] + (\color{red}{\mathbb{E}[X]} - \color{blue} {\lambda})^2
\end{align*}
and that's all. (The first step is a trick known as *"hiding zero:"* writing $0=a-a$. 🤷)](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:ac6qioenkpl3jmmnib3tpbhb/bafkreieevv3petzx4kqxx3o6i4oqtugsjh52n7i2ellidxmetefboag6fi)
A short proof: here is the LaTeX code. **Proof.** We have, for any $\color{blue}{\lambda} \in\mathbb{R}$, \begin{align*} \mathbb{E}[(X-\color{blue}{\lambda})^2] &= \mathbb{E}[(X-\color{red}{\mathbb{E}[X]} + \color{red}{\mathbb{E}[X]} - \color{blue} {\lambda})^2] \\ &=\mathbb{E}[(X-\color{red}{\mathbb{E}[X]})^2 + 2(X-\color{red}{\mathbb{E}[X]})(\color{red}{\mathbb{E}[X]} - \color{blue} {\lambda}) + (\color{red}{\mathbb{E}[X]} - \color{blue} {\lambda})^2]\\ &=\underbrace{\mathbb{E}[(X-\color{red}{\mathbb{E}[X]})^2]}_{=\textrm{Var}[X]} + 2\underbrace{\mathbb{E}[X-\color{red}{\mathbb{E}[X]}]}_{=0}(\color{red}{\mathbb{E}[X]} - \color{blue} {\lambda})] + (\color{red}{\mathbb{E}[X]} - \color{blue} {\lambda})^2 \end{align*} and that's all. (The first step is a trick known as *"hiding zero:"* writing $0=a-a$. 🤷)
Here's a classic (but fun to show) fact: if X is any random variable (with a finite variance) and λ is a real, then
𝔼[(X-λ)²] = Var[X]+(𝔼[X]-λ)²
(In particular, this shows that 𝔼[X] is the quantity minimizing 𝔼[(X-λ)²] over all λ, and that Var[X] is the resulting value.)
Quantum Toolbox (10): Uhlmann's Theorem (1/6)
Oh, and guess what — not only is this pre #FOCS2025 satellite event free, there is some financial support (covering accommodation, on the #USyd campus) for students available!
Register to the event, apply for travel support! (The latter by Sep 19)
sites.google.com/view/celebra...
Quantum Toolbox (9): Sample Complexity Lower Bounds via Mutual Information (1/6)
🍾💐 Celebrating a successful thesis defence by Josep Lumbreras Zarapico!! 🍉🧀🍪 Advised by @marcotomamichel.bsky.social, Josep defended his thesis "Bandits Roaming Hilbert Space". He will next join Mile Gu’s group as a research fellow. Congrats and all the best, Dr Josep!
Quantum Toolbox (8): Hadamard's Three-Lines Theorem (1/6)
New podcast episode of "Probably Approximately Correct Learners," featuring guest Clément Canonne @ccanonne.github.io!
Check it out on Youtube, Spotify, Apple Podcasts, or wherever you get your podcasts. Subscribe so you don't miss out! (links in the next post) 1/2
Quantum Toolbox (7): Continuity of the von Neumann Entropy (1/6)
We are happy to share our work in classical distribution testing "Testing (Conditional) Mutual Information" (arxiv.org/abs/2506.03894), which was recently accepted at COLT 2025. (1/6)
Quantum Toolbox (6): Hoeffding's Inequality (1/7)