Sample-based distance-approximation for subsequence-freeness

DOI10.1007/s00453-024-01233-4MaRDI QIDQ6586659zbMATH OpenFDO

Authors Omer Cohen Sidon, Dana Ron

Publication date 13 August 2024

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s00453-024-01233-4

zbMATH Keywords

distance-approximationproperty testingsample-basedsubsequence-freeness

Mathematics Subject Classification ID

Graph theory (05Cxx) Algorithms in computer science (68Wxx)

Cites work

• L_p-testing
• Approximating the distance to monotonicity in high dimensions
• Approximating the distance to monotonicity of Boolean functions
• Approximating the distance to properties in bounded-degree and general sparse graphs
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Domain Reduction for Monotonicity Testing: A o(d) Tester for Boolean Functions in d-Dimensions
• Downsampling for testing and learning in product distributions
• Erasure-Resilient Property Testing
• Erasures versus errors in local decoding and property testing
• Estimating the distance to a hereditary graph property
• Estimating the distance to a monotone function
• scientific article; zbMATH DE number 7559095 (Why is no real title available?)
• scientific article; zbMATH DE number 7650357 (Why is no real title available?)
• scientific article; zbMATH DE number 7788436 (Why is no real title available?)
• Improved monotonicity testers via hypercube embeddings
• Local reconstructors and tolerant testers for connectivity and diameter
• Optimal Distribution-Free Sample-Based Testing of Subsequence-Freeness with One-Sided Error
• Property testing and its connection to learning and approximation
• Robust Characterizations of Polynomials with Applications to Program Testing
• Robustly self-ordered graphs: constructions and applications to property testing
• Sample-based distance-approximation for subsequence-freeness
• Sampling lower bounds via information theory
• Testing \(k\)-monotonicity. The rise and fall of Boolean functions
• Testing versus Estimation of Graph Properties
• Tolerant junta testing and the connection to submodular optimization and function isomorphism
• Tolerant Linearity Testing and Locally Testable Codes
• Tolerant property testing and distance approximation
• Tolerant Testers of Image Properties
• Tolerant versus intolerant testing for Boolean properties
• VC dimension and distribution-free sample-based testing

Cited in

(1)

• Let's try to be more tolerant: on tolerant property testing and distance approximation (invited talk)

This page was built for publication: Sample-based distance-approximation for subsequence-freeness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6586659)