Open Problem: Meeting Times for Learning Random Automata
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 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.
Cite
Text
Fish and Reyzin. "Open Problem: Meeting Times for Learning Random Automata." Proceedings of the 2017 Conference on Learning Theory, 2017.Markdown
[Fish and Reyzin. "Open Problem: Meeting Times for Learning Random Automata." Proceedings of the 2017 Conference on Learning Theory, 2017.](https://mlanthology.org/colt/2017/fish2017colt-open/)BibTeX
@inproceedings{fish2017colt-open,
title = {{Open Problem: Meeting Times for Learning Random Automata}},
author = {Fish, Benjamin and Reyzin, Lev},
booktitle = {Proceedings of the 2017 Conference on Learning Theory},
year = {2017},
pages = {8-11},
volume = {65},
url = {https://mlanthology.org/colt/2017/fish2017colt-open/}
}