Tight Bounds for Equivalence Testing with Non-Adaptive Conditional Samples

arXiv:2610.11145 · cs.DS, cs.IT, math.IT, stat.ML · Submitted 2026-10-08 · Read on arXiv

cs.DS, cs.IT, math.IT, stat.ML

Submitted: 2026-10-08

Updated: 2026-10-08

Terminology

• Sample Complexity — 9× in this paper · explained in 15 episodes
• Adaptivity — 8× in this paper · explained in 1 episode
• Combinatorial Optimization — 4× in this paper · explained in 2 episodes
• Query Complexity — 2× in this paper · explained in 2 episodes
• Accuracy — 1× in this paper · explained in 1 episode
• Core — 1× in this paper · explained in 2 episodes

Related papers

• Cascaded Learned Bloom Filter for Optimizing Model-Filter Size Balance and Fast Rejection
• Edge-Private Matching Kernels Through Local Decoding
• Local Node Differential Privacy
• Cheaper by the Batch: Shared Traversal for Genotype Graph Editing
• Scalable Algorithms for Approximate DNF Model Counting
• On the Approximation Relationship between Optimizing Ratio of Submodular (RS) and Difference of Submodular (DS) Functions