Recovery from Non-Decomposable Distance Oracles
summary
Study of locating an unknown length-n sequence from distance queries for non-decomposable metrics focuses on DTW and gives concrete bounds and constructions: exact recovery needs ~n / log n queries information-theoretically, equivalence-class recovery needs Theta(n), a general adaptive coordinate descent framework uses O(n^2) steps, and specialized DTW algorithms achieve optimal non-adaptive recovery with n+2 queries over a four-symbol alphabet by designing monotonic queries that force input uniqueness and an isomorphic DTW matching.
AI-written summary · about
chapters (15)
- 0:00Intro
- 0:14Recovery from Distance Queries
- 2:05Non-Decomposable Distances
- 4:10Main Contributions
- 5:16Existence of Indistinguishable Sequences
- 6:25Three Levels of Recovery Guarantees
- 7:41Lower Bounds for Recovery (Exact Recover)
- 8:32Lower Bounds for Recovery (Equivalence Class)
- 9:21Lower Bounds for Recovery (Proof Sketch)
- 10:55General Framework for Recovery, Adaptively
- 12:28Adaptive Recovery Strategies
- 13:26Equivalence Class Recovery from DTW Oracle
- 15:17Exact Recovery from DTW Oracle, Non-adaptively
- 16:34Exact Recovery from DTW Oracle (Proof Sketch)
- 21:07Application and Open Problems
related talks
26mLow-bandwidth recovery of linear functions of Reed-Solomon-encoded data
34mLocally Recoverable Code Constructions and Some Extensions
25mErasure-Resilient Sublinear-Time Graph Algorithms
29mDirect Access for Conjunctive Queries with Aggregation
17mPractical Design Considerations for Wide Locally Recoverable Codes (LRCs)
57mQuery Optimization and Evaluation 1: Output Size Bounds and Information Theory
36mOptimizing Relational Programs II
43mResizable Sketches