Playing with Grammars: What Have We Known So Far!
Talkat Computational Complexity of Low-Polynomial Time Problems (Simons Institute workshop, 2015) · on Tuesday, 2015-12-08·
summary
Simple randomized stack algorithm gives an O(D) approximation for Dyck edit distance by deleting mismatches (analysis maps to a gambler’s‑ruin walk); refining by block decomposition and parallelizing local random deletions brings the guarantee down to an O(log D) approximation and yields near-linear time implementations that match optimal edits on real XML/RNA tests. For general CFGs the approach switches to algebraic methods: reductions to min‑plus and Valiant‑style closure produce N^ω (1±ε) for CFG/stochastic CFG parsing. Exact insertion‑only edit is APSP‑hard (no subcubic exact algorithm).
AI-written summary · about
chapters (30)
- 0:00Start
- 1:09How Clean is the XML Web ?
- 2:22How Good is Edit Distance as a Measure for Repair ?
- 4:29CFG Recognition
- 6:12Applications
- 9:41Dyck Language Edit Distance
- 10:18Connection to String Edit Distance
- 11:10Computational Challenges
- 11:43Contributions (Saha. FOCS 2014)
- 16:13Analysis of Random Deletion
- 18:53Refinement
- 20:53Sequential Random Deletion
- 22:10The Factor "Z" in Approximation
- 23:36Parallel Random Deletion Example
- 24:53Performance
- 25:08General Language Edit Distance Saha, FOCS'15
- 27:06Stochastic CFG Parsing
- 27:42Connection to APSP and Other Graph Problems
- 28:18O(n) Dynamic Programming Algorithm [Aho & Peterson 1972]
- 30:33An Alternate View
- 32:51Computing Transitive Closure Fast - Cannot compute transitive closure by repeated aquaring
- 33:17Non-associativity → Lack of flexibility in combining partial results
- 34:05Valiant's Transitive Closure Computation 1978
- 34:39Quality of Solution after Valiant's Algorithm
- 35:08A Randomized Algorithm
- 37:29Connection to Graph Problems
- 38:07Recent Progress
- 39:00Implications
- 40:02Many Future Directions
- 40:48Structures to Beat DP
related talks
19mAn Incremental Algorithm for Algebraic Program Analysis
17mA Better Approximation for Interleaved Dyck Reachability
12mAutomatic Grammar Repair
15mFaster Reachability Analysis for LR(1) Parsers
51mRegular Expressions in C++, Present and Future
15mDetecting and explaining (in-)equivalence of context-free grammars
23mAn Abstract Interpretation for SPMD Divergence on Reducible Control Flow Graphs
22mStatic Analysis for Checking the Disambiguation Robustness of Regular Expressions