Idan Attias: On the Hardness of Learning Regular Expressions
Keywords
Summary
181 words
Critical Evaluation
Value of the Information & Strength of the Argument
The talk provides valuable insights into a relatively understudied problem, clearly explaining why learning regular expressions is fundamentally different from learning automata. The argumentation is rigorous, building on established cryptographic assumptions and providing proof sketches. The speaker effectively communicates the technical nuances, such as the exponential blow-up in both directions between regular expressions and DFAs, and why this matters for hardness reductions. The presentation is well-structured, with clear motivation and a logical flow from background to results to proof ideas.
Scientific Rigor, Source Quality, Title Accuracy
The talk is scientifically rigorous, referencing a specific paper (arXiv:2510.04834) and discussing relevant prior work (e.g., Gold, Angluin, Valiant, Kearns, and others). The speaker correctly notes the need for cryptographic assumptions rather than NP-hardness for improper learning, citing a 2008 paper. The title accurately reflects the content. The presentation is a seminar talk, so it does not provide full proofs but gives sufficient detail to convey the main ideas. The speaker also mentions a survey on star height, indicating awareness of related literature.
178 words
Title / Content Match
The title accurately reflects the content, which focuses on the computational hardness of learning regular expressions.
Quality & Reliability
8/10
The talk presents rigorous theoretical results from a peer-reviewed paper, with clear technical explanations and references to established cryptographic assumptions. The speaker is a postdoctoral researcher, and the work received an award. However, the presentation is an informal seminar, and the results are based on unproven cryptographic assumptions.
Key Moments
Markers derived by PSI from the transcript: the creator did not define chapters.
- Introduction and speaker introduction
- Motivation: learning regular expressions for spam filtering
- PAC learning model and membership queries
- Representation size differences between regular expressions and DFAs
- Examples of exponential blow-up in both directions
- Main hardness results overview
- Proof strategy: reduction from DNF learning
- Hardness under uniform distribution using local pseudorandom generators
- Hardness for extended regular expressions with intersection/complement
- Discussion of open questions and related work
Cited Sources
- On the Hardness of Learning Regular Expressions — The paper presenting the main results discussed in the talk.
Concurring Sources
- On the Hardness of Learning Regular Expressions — The paper itself, which the talk is based on.
Contribution & Novelties
The talk presents novel hardness results for learning regular expressions, a topic that has received less attention than DFA learning. The key contribution is showing that, unlike DFAs, regular expressions are hard to learn even with membership queries, and also hard under the uniform distribution. This highlights the importance of representation size in computational learning theory. The talk also provides a clear explanation of why existing hardness results for DFAs do not directly apply to regular expressions.
Pour aller plus loin :
- PAC learning — Foundational model for the discussed learning framework.
- L* algorithm — Algorithm for learning DFAs with membership queries, contrasting with the hardness results.
- Cryptographic hardness — Assumptions underlying the hardness results.
115 words
Radar Profile
The radar profile shows high scores in quality of information, technical level, and reliability, with a slightly lower score for quantity of information due to the seminar format. This indicates a technically dense and reliable presentation, though not exhaustive in covering all aspects of the topic.
💬 No comments were provided for analysis.