# On the Statistical Query Complexity of Learning Semiautomata: a Random Walk Approach

arXiv: https://arxiv.org/abs/2510.04115 · HTML: https://mlsanity.com/paper/2510.04115/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 65 references that are in the map.
- First posted on arXiv 5 Oct 2025.

## Builds on (most cited first, 12 of 12)

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Transformers Learn Shortcuts to Automata](https://mlsanity.com/paper/2210.10749/) (2022)
- [Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures](https://mlsanity.com/paper/1611.03473/) (2016)
- [Extracting Automata from Recurrent Neural Networks Using Queries and Counterexamples](https://mlsanity.com/paper/1711.09576/) (2017)
- [Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descent](https://mlsanity.com/paper/2006.12011/) (2020)
- [Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals](https://mlsanity.com/paper/2006.16200/) (2020)
- [Learning Compositional Functions with Transformers from Easy-to-Hard Data](https://mlsanity.com/paper/2505.23683/) (2025)
- [A survey on policy search algorithms for learning robot controllers in a handful of trials](https://mlsanity.com/paper/1807.02303/) (2018)
- [On the Power of Differentiable Learning versus PAC and SQ Learning](https://mlsanity.com/paper/2108.04190/) (2021)
- [Near-Optimal Statistical Query Lower Bounds for Agnostically Learning Intersections of Halfspaces with Gaussian Marginals](https://mlsanity.com/paper/2202.05096/) (2022)
- [L^*LM: Learning Automata from Examples using Natural Language Oracles](https://mlsanity.com/paper/2402.07051/) (2024)
- [Learning Deterministic Finite Automata from Confidence Oracles](https://mlsanity.com/paper/2311.10963/) (2023)

## Built on by (most cited first, 4 of 4)

- [Learning to Reason with Curriculum I: Provable Benefits of Autocurriculum](https://mlsanity.com/paper/2603.18325/) (2026)
- [LLM Priors for ERM over Programs](https://mlsanity.com/paper/2510.14331/) (2025)
- [Learning to Reason with Curriculum II: Compositional Generalization](https://mlsanity.com/paper/2606.27721/) (2026)
- [What Pretraining and Midtraining Make Learnable from Rewards?](https://mlsanity.com/paper/2609.38446/) (2026)

## Abstract (arXiv)

Semiautomata form a rich class of sequence-processing algorithms with applications in natural language processing, robotics, computational biology, and data mining. We establish the first Statistical Query hardness result for semiautomata under the uniform distribution over input words and initial states. We show that Statistical Query hardness can be established when both the alphabet size and input length are polynomial in the number of states. Unlike the case of deterministic finite automata, where hardness typically arises through the hardness of the language they recognize (e.g., parity), our result is derived solely from the internal state-transition structure of semiautomata. Our analysis reduces the task of distinguishing the final states of two semiautomata to studying the behavior of a random walk on the group SN × SN. By applying tools from Fourier analysis and the representation theory of the symmetric group, we obtain tight spectral gap bounds, demonstrating that after a polynomial number of steps in the number of states, distinct semiautomata become nearly uncorrelated, yielding the desired hardness result.