Open Problem: Meeting Times for Learning Random Automata


Benjamin Fish, Lev Reyzin ;
Proceedings of the 2017 Conference on Learning Theory, PMLR 65:8-11, 2017.


Learning automata is a foundational problem in computational learning theory. However, even efficiently learning random DFAs is hard. A natural restriction of this problem is to consider learning random DFAs under the uniform distribution. To date, this problem has no non-trivial lower bounds nor algorithms faster than brute force. In this note, we propose a method to find faster algorithms for this problem. We reduce the learning problem to a conjecture about meeting times of random walks over random DFAs, which may be of independent interest to prove.

Related Material