Wednesday / CS Seminar
April 22 / 12:00 PM
Hybrid / Mudd 3514
Speaker
Lev Reyzin, University of Illinois Chicago
Talk Title
On the Hardness of Learning Regular Expressions
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. We show that PAC learning is hard even under the uniform distribution on the hypercube, and also prove hardness of distribution-free learning with membership queries. Furthermore, if regular expressions are extended with complement or intersection, we establish hardness of learning with membership queries even under the uniform distribution. We emphasize that these results do not follow from existing hardness results for learning DFAs or NFAs, since the descriptive complexity of regular languages can differ exponentially between DFAs, NFAs, and regular expressions.
This work is joint with Idan Attias, Nati Srebro, and Gal Vardi"
Biography
Lev Reyzin is a Professor of Mathematics, Statistics, and Computer Science at the University of Illinois Chicago and Co-Director of the IDEAL Institute. He works on the theory of machine learning, data science, and artificial intelligence. Prior to UIC, Reyzin was a Simons Postdoctoral Fellow at Georgia Tech and an NSF Computing Innovation Fellow at Yahoo! Research. Reyzin received his Ph.D. on an NSF doctoral fellowship from Yale under Dana Angluin and his bachelor’s degree from Princeton. He is currently the Chair of the Steering Committee for the ALT conference and the Editor-in-Chief of Mathematics of Data, Learning, and Intelligence. He has also served as a General Chair for FOCS 2024, the Program Chair for ISAIM 2020, and a Program Chair for ALT 2017. His work has earned awards at ICML, COLT, and AISTATS and has received extensive funding.
Research Areas/Interests: theory of machine learning, data science, and artificial intelligence
---
Zoom Link
Panopto Link
Cost: free
Wynante R Charles
(847) 467-8174
Email