On the Statistical Query Complexity of Learning Semiautomata: a Random Walk Approach Link to the paper: arxiv.org/abs/2510.04115
Kimon Fountoulakis
@kfountou.bsky.social
Associate Professor at CS UWaterloo Machine Learning Lab: opallab.ca
New paper: Learning to Add, Multiply, and Execute Algorithmic Instructions Exactly with Neural Networks
Update, 14 empirical papers added!
Kimon Fountoulakis@kfountou.bsky.social · last yr.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...
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.
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)
Eshaan Nichani@eshaannichani.bsky.social · last yr.Excited to announce a new paper with Yunwei Ren, Denny Wu, @jasondeanlee.bsky.social! We prove a neural scaling law in the SGD learning of extensive width two-layer neural networks. arxiv.org/abs/2504.19983 🧵below (1/10)
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.
Positional Attention: Expressivity and Learnability of Algorithmic Computation
There is a growing interest in the ability of neural networks to execute algorithmic tasks (e.g., arithmetic, summary statistics, and sorting). The goal of this work is to better understand the role o...
arxiv.org
Kimon Fountoulakis@kfountou.bsky.social · 2y agoPositional 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 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
New AI model turns sketches into code | Cheriton School of Computer Science | University of Waterloo
Co-developed by alum Ryan Yen, Code Shaping can transform coding beyond the keyboard.
uwaterloo.ca
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...
Deterministic complexity analysis of Hermitian eigenproblems
In this work we revisit the arithmetic and bit complexity of Hermitian eigenproblems. We first provide an analysis for the divide-and-conquer tridiagonal eigensolver of Gu and Eisenstat [GE95] in the ...
arxiv.org
Update "Memory Augmented Large Language Models are Computationally Universal", Dale Schuurmans link: arxiv.org/abs/2301.04589
Memory Augmented Large Language Models are Computationally Universal
We show that transformer-based large language models are computationally universal when augmented with an external memory. Any deterministic language model that conditions on strings of bounded length...
arxiv.org
Kimon Fountoulakis@kfountou.bsky.social · last yr.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...
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)
Kimon Fountoulakis@kfountou.bsky.social · 2y ago. 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!
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.
Kimon Fountoulakis@kfountou.bsky.social · last yr.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
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...
Graph neural networks extrapolate out-of-distribution for shortest paths
Neural networks (NNs), despite their success and wide adoption, still struggle to extrapolate out-of-distribution (OOD), i.e., to inputs that are not well-represented by their training dataset. Addres...
arxiv.org
Kimon Fountoulakis@kfountou.bsky.social · last yr.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...
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...