On the Statistical Query Complexity of Learning Semiautomata: a Random Walk Approach Link to the paper: arxiv.org/abs/2510.04115

I wrote a blog post about it. Link: medium.com/@kimon.fount...

New paper: Learning to Add, Multiply, and Execute Algorithmic Instructions Exactly with Neural Networks

Update, 14 empirical papers added!

The SIAM Conference on Optimization 2026 will be in Edinburgh! I don’t really work on optimization anymore (at least not directly), but it’s cool to see a major optimization conference taking place where I did my PhD.

Currently NeurIPS has 21390 submissions. The final number last year was 15671. Observation made by my student George Giapitzakis.

Got a pin this morning Einstein problem: en.wikipedia.org/wiki/Einstei...

Our new work on scaling laws that includes compute, model size, and number of samples. The analysis involves an extremely fine-grained analysis of online sgd built up over the last 8 years of understanding sgd on simple toy models (tensors, single index models, multi index model)

Hey, I definitely predicted this correctly.

ChatGPT gives me the ability to expand my search capabilities on topics that I can only roughly describe, or even illustrate with a figure, when I don’t know the exact keywords to use in a Google search.

Positional Attention is accepted at ICML 2025! Thanks to all co-authors for the hard work (64 pages). If you’d like to read the paper, check the quoted post.

NeurIPS 2026 in the Cyclades. Just saying.

I enjoyed reading the paper "A Generalized Neural Tangent Kernel for Surrogate Gradient Learning" (Spotlight, NeurIPS 2024). They extend the NTK framework to activation functions that have finitely many jumps.

✍️ Code Shaping, an AI-powered software, allows users to edit their code through sketches like diagrams and graphs 📈 🏆 This game-changing platform won the Best Paper Award at #CHI2025. 🔗Read more: uwaterloo.ca/computer-sci... #UWaterloo #AI

With my first Bluesky post, I am very pleased to share that my last PhD paper "Deterministic complexity analysis of Hermitian eigenproblems" has been accepted in ICALP 2025. A preprint is available on Arxiv: arxiv.org/abs/2410.21550 A bit more info on linkedin: www.linkedin.com/posts/aleksa...

Update "Memory Augmented Large Language Models are Computationally Universal", Dale Schuurmans link: arxiv.org/abs/2301.04589

Excited to be part of Greeksin.ai

Shenghao's Ph.D Thesis "Perspectives of Graph Diffusion: Computation, Local Partitioning, Statistical Recovery, and Applications" is now available. Link: dspacemainprd01.lib.uwaterloo.ca/server/api/c... Relevant papers: 1) Local Graph Clustering with Noisy Labels (ICLR 2024)

I am still surprised by how difficult it is to train a 2-layer MLP to simply learn to copy or permute the input exactly. If k is the input length, the result below provides a (seemingly tight) upper bound of O(k²) training trials.

New additions 1. Graph neural networks extrapolate out-of-distribution for shortest paths. arxiv.org/abs/2503.19173 2. Round and Round We Go! What makes Rotary Positional Encodings useful?. ICLR 2025. openreview.net/forum?id=Gtv...

Our second kid arrived!

GLOW is returning on 𝗠𝗮𝗿𝗰𝗵 𝟮𝟲𝘁𝗵, 𝟱𝗽𝗺 𝗖𝗘𝗧 with a special guest: @petar-v.bsky.social 🌟 He will lecture on LLMs as GNNs – a topic which received quite some attention at our last session. Specifically, we will learn how Graph ML tools can help understand LLM generalisation

1 out of 12 papers in my batch at ICML has a score above 3 (weak acceptance). Each paper has at least 3 reviews.

Computational Capability and Efficiency of Neural Networks: A Repository of Papers I compiled a list of theoretical papers related to the computational capabilities of Transformers, recurrent networks, feedforward networks, and graph neural networks. Link: github.com/opallab/neur...

Every time I try to use chatGPT or Gemini to write some text for me, I always get vague results. This is not useful. It can't be creative. I don't know why people talk about it as if it actually produces knowledge. Even if I initially think it's helpful, I end up rewriting the entire text because,

Given the recent trend in RL and the Turing Award to RL, you might also be interested in reading "Intelligent Machinery" by A. M. Turing from 1948, where he planted the seeds for RL and discussed the ability of computers to learn from their environment. Link: weightagnostic.github.io/papers/turin...

Can neural networks learn to copy or permute an input exactly with high probability? We study this basic and fundamental question in "Exact Learning of Permutations for Nonzero Binary Inputs with Logarithmic Training Size and Quadratic Ensemble Complexity" Link: arxiv.org/abs/2502.16763

GLOW is back this Wednesday, Feb 19th, 5pm CET 🌟 Instead of talks, we’re hosting a casual discussion on where graph learning is headed and where early-career researchers can make the most impact. Join our open conversation with junior and senior graph researchers! sites.google.com/view/graph-l...

Cool paper: Theoretical limitations of multi-layer Transformer, spotted by Shenghao Yang. link: arxiv.org/abs/2412.02975

Registration is now open for the 2nd RSS/Turing Workshop on Gradient Flows for Sampling, Inference, and Learning at rss.org.uk/training-eve.... Date: Monday 24 March 2025, 10.00AM - 5.00PM Location: The Alan Turing Institute

Positional Attention: Expressivity and Learnability of Algorithmic Computation (v2) We study the effect of using only fixed positional encodings in the Transformer architecture for computational tasks. These positional encodings remain the same across layers.

I am wondering what percentage of reviewers, who are also authors at the same conference, received positive feedback for their paper and then changed their opinion about a (multiple) paper(s) they reviewed during the rebuttal.

🚀 🇬🇷 A year in the making! I’ve just completed a set of 21 lectures in Machine Learning, in Greek, designed for high school students. The course introduces key ML concepts, coding in Python & PyTorch, and real-world AI applications. 👉 WebPage: tinyurl.com/ye2awe8m 🎥 YouTube: tinyurl.com/2wwjru6z

I miss those summer European conferences! I used to attend them as a PhD student, it was always fun!

. Shenghao Yang passed his PhD defence today. Shenghao is the second PhD student to graduate from our group. I am very happy for Shenghao and the work that he has done!

Some of my thoughts on OpenAI's o3 and the ARC-AGI benchmark aiguide.substack.com/p/did-openai...

It seems that Finland's Publication Forum (known as JUFO) decided that the review process in journals like MDPI is too fast and unreliable. As a result, they downgraded these journals to the lowest classification: zero. deevybee.blogspot.com/2024/12/finl....

My book is (at last) out, just in time for Christmas! A blog post to celebrate and present it: francisbach.com/my-book-is-o...

ICML 2025 has some exciting changes. Here are two of my favorites. 1. Only 1 round of back-and-forth between authors & reviewers. The review process should not be an endless back and forth. It shouldn't be possible to get your paper accepted by exhausting reviewers.

On this day, 6 years ago, we started a road trip from Berkeley to Waterloo. It lasted 8 days, and we passed through California, Nevada, Arizona, Utah, Colorado, Nebraska, Iowa, Illinois, Indiana, and Michigan.

The first major breakthrough in AI occurred in the field of images, driven by the availability of large amounts of labeled image data. Then, it extended to text, thanks to the abundance of "labeled" internet data. It's hard to imagine a larger generic dataset.

A nice lecture series on graph theory www.youtube.com/@DiestelGrap...

Robert Wang is presenting his work at #NeurIPS2024 "Analysis of Corrected Graph Convolutions". Date/time: Fri 13 Dec 11 a.m. PST — 2 p.m. PST. link: openreview.net/pdf?id=MSsQD...

Aseem's thesis, "Statistical Foundations for Learning on Graphs", is available on UWSpace. link: uwspace.uwaterloo.ca/items/291d10...

Link: arxiv.org/abs/2412.024...

Dear #ICLR authors: As the discussion period comes to an end, please consider writing a 𝐜𝐨𝐧𝐜𝐢𝐬𝐞, accurate, and clear summary of the rebuttal and discussion period for the reviewers/AC/SAC to ground the next phase of the decision making.

LVLM-COUNT: Enhancing the Counting Ability of Large Vision-Language Models By splitting the image into sub-images using a novel object-aware division technique, we can enhance the performance of LVLMs such as GPT-4o and Gemini Pro 1.5. Link: arxiv.org/abs/2412.00686

*AI for Mathematics and Theoretical Computer Science*, a workshop hosted jointly by the Simons Institute for the Theory of Computing and the Simons Laufer Mathematical Sciences Institute, will be held in Berkeley at April 7-11, 2025. simons.berkeley.edu/workshops/si...