Open Problem: Meeting Times for Learning Random Automata
[edit]
Proceedings of the 2017 Conference on Learning Theory, PMLR 65:811, 2017.
Abstract
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 nontrivial 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


