Testing local properties of arrays

DOI10.4230/LIPICS.ITCS.2019.11MaRDI QIDQ5090383zbMATH OpenFDO

Authors Omri Ben-Eliezer

Publication date 18 July 2022

Full work available at URL https://arxiv.org/abs/1811.07448

zbMATH Keywords

hypergridlocal propertiesmonotonicity testingpattern matchingproperty testing

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Testing of matrix properties
• Testing for forbidden order patterns in an array
• Approximate testing of visual properties
• L_p-testing
• Deleting and Testing Forbidden Patterns in Multi-Dimensional Arrays

Cites work

• L_p-testing
• Adaptive lower bound for testing monotonicity on the line
• Deleting and Testing Forbidden Patterns in Multi-Dimensional Arrays
• Discrete Convex Analysis
• Earthmover Resilience and Testing in Ordered Structures
• Every property of hyperfinite graphs is testable
• Fast-Match: fast affine template matching
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• scientific article; zbMATH DE number 6395191 (Why is no real title available?)
• Introduction to Property Testing
• Is submodularity testable?
• On discrete Hessian matrix and convex extensibility
• On Proximity-Oblivious Testing
• On Testing Convexity and Submodularity
• On the strength of comparisons in property testing
• Optimal bounds for monotonicity and Lipschitz testing over hypercubes and hypergrids
• Parameterized property testing of functions
• Property testing and its connection to learning and approximation
• Property testing lower bounds via communication complexity
• Property Testing on Product Distributions
• Regular languages are testable with a constant number of queries
• Robust Characterizations of Polynomials with Applications to Program Testing
• Sample-based high-dimensional convexity testing
• Spot-checkers
• Testing and reconstruction of Lipschitz functions with applications to data privacy
• Testing convexity of figures under the uniform distribution
• Testing Lipschitz functions on hypergrid domains
• Testing submodularity and other properties of valuation functions
• Tolerant testers of image properties

Cited in

(5)

• Almost Optimal Distribution-Free Sample-Based Testing of k-Modality
• scientific article; zbMATH DE number 7758320 (Why is no real title available?)
• Testing local properties of arrays
• Property testing with online adversaries
• Property testing with online adversaries

This page was built for publication: Testing local properties of arrays

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