Gal Vardi

Congratulations to Gal Vardi, Zuckerman Faculty Scholar at Weizmann Institute of Science’s Department of Computer Science and Applied Mathematics, on the publication of his study, “On the Hardness of Learning Regular Expression”  in the October 6 issue of arXiv. Dr. Vardi’s study established that RegEx patterns are much harder for computers to learn than previously believed, and highlights significant theoretical limitations for automated pattern recognition systems.

Abstract:
Despite the theoretical significance and wide practical use of regular expressions, the computational complexity of learning them has been largely unexplored. We study the computational hardness of improperly learning regular expressions in the PAC model and with membership queries…and show that PAC learning is hard even under the uniform distribution on the hypercube, and also provehardness of distribution-free learning with membership queries.