Parameterized property testing of functions

DOI10.4230/LIPICS.ITCS.2017.12MaRDI QIDQ4638061zbMATH OpenOpenAlexFDO

Authors Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin M. Varma

Publication date 3 May 2018

Full work available at URL https://doi.org/10.4230/LIPIcs.ITCS.2017.12

zbMATH Keywords

monotonicityconvexityparameterizationproperty testingsublinear algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Recommendations

• Parameterized property testing of functions
• Parameterized testability
• Parameterized testability
• Testing polymorphic properties
• Testing in functional programming
• Towards property oriented testing
• Foundational property-based testing

Cites work

• scientific article; zbMATH DE number 1583788 (Why is no real title available?)
• scientific article; zbMATH DE number 6538684 (Why is no real title available?)
• scientific article; zbMATH DE number 1418269 (Why is no real title available?)
• scientific article; zbMATH DE number 6395191 (Why is no real title available?)
• A polynomial lower bound for testing monotonicity
• An o(n) monotonicity tester for Boolean functions over the hypercube
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Boolean function monotonicity testing requires (almost) \(n^{1/2}\) non-adaptive queries
• Erasure-resilient property testing
• Fast approximate PCPs for multidimensional bin-packing problems
• Improving and extending the testing of distributions for shape-restricted properties
• Information theory in property testing and monotonicity testing in higher dimension
• Monotonicity testing and shortest-path routing on the cube
• Monotonicity testing over general poset domains
• On Monotonicity Testing and Boolean Isoperimetric-type Theorems
• On Proximity-Oblivious Testing
• On Testing Convexity and Submodularity
• On disjoint chains of subsets
• On sample-based testers
• On the strength of comparisons in property testing
• Optimal bounds for monotonicity and Lipschitz testing over hypercubes and hypergrids
• Parameterized testability
• Property Testing on Product Distributions: Optimal Testers for Bounded Derivative Properties
• Property testing and its connection to learning and approximation
• Property testing lower bounds via communication complexity
• Robust Characterizations of Polynomials with Applications to Program Testing
• Spot-checkers
• Testing and reconstruction of Lipschitz functions with applications to data privacy
• Testing convexity of figures under the uniform distribution
• Testing monotonicity
• Testing monotonicity over graph products
• The power and limitations of uniform samples in testing properties of figures
• Transitive-closure spanners
• \(L_p\)-testing

Cited in

(12)

• Adaptive Boolean Monotonicity Testing in Total Influence Time
• scientific article; zbMATH DE number 7559054 (Why is no real title available?)
• Testing piecewise functions
• Sublinear-time computation in the presence of online erasures
• Information theory in property testing and monotonicity testing in higher dimension
• A large lower bound on the query complexity of a simple Boolean function
• Directed isoperimetric theorems for Boolean functions on the hypergrid and an \(\widetilde{O}(n\sqrt{d})\) monotonicity tester
• Almost Optimal Distribution-Free Sample-Based Testing of k-Modality
• Properties Incompleteness Evaluation by Functional Verification
• Parameterized property testing of functions
• Adaptive lower bound for testing monotonicity on the line
• The power and limitations of uniform samples in testing properties of figures

This page was built for publication: Parameterized property testing of functions

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