Optimal unateness testers for real-valued functions: adaptivity helps

DOI10.4086/TOC.2020.V016A003MaRDI QIDQ5140837zbMATH OpenOpenAlexFDO

Authors Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, C. Seshadhri

Publication date 17 December 2020

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

hypercubehypergridproperty testingunate and monotone functions

Mathematics Subject Classification ID

Computational methods for problems pertaining to real functions (26-08) Randomized algorithms (68W20)

Recommendations

• Optimal unateness testers for real-valued functions: Adaptivity helps
• An O(n) queries adaptive tester for unateness
• Testing unateness nearly optimally
• Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness
• A polynomial lower bound for testing monotonicity

Cites work

• An o(n) monotonicity tester for Boolean functions over the hypercube
• Boolean function monotonicity testing requires (almost) \(n^{1/2}\) non-adaptive queries
• Breaking the -soundness bound of the linearity test over GF(2)
• Distribution-Free Property-Testing
• Erasure-Resilient Property Testing
• Fast approximate PCPs for multidimensional bin-packing problems
• scientific article; zbMATH DE number 6538684 (Why is no real title available?)
• Information theory in property testing and monotonicity testing in higher dimension
• Introduction to Property Testing
• Is submodularity testable?
• Linearity testing in characteristic two
• Monotonicity testing and shortest-path routing on the cube
• Non‐Abelian homomorphism testing, and distributions close to their self‐convolutions
• On disjoint chains of subsets
• On Monotonicity Testing and Boolean Isoperimetric-type Theorems
• 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
• Robust Characterizations of Polynomials with Applications to Program Testing
• Self-testing/correcting with applications to numerical problems
• Spot-checkers
• Testing and reconstruction of Lipschitz functions with applications to data privacy
• Testing Lipschitz functions on hypergrid domains
• Testing monotonicity
• Testing monotonicity over graph products
• Testing the Lipschitz property over product distributions with applications to data privacy
• Transitive-closure spanners
• Transitive-closure spanners: a survey

Cited in

(6)

• A Nearly-Quadratic Gap between Adaptive and Non-adaptive Property Testers
• An O(n) queries adaptive tester for unateness
• Optimal unateness testers for real-valued functions: Adaptivity helps
• Testing unateness nearly optimally
• Approximating the distance to monotonicity of Boolean functions
• Isoperimetric inequalities for real-valued functions with applications to monotonicity testing

This page was built for publication: Optimal unateness testers for real-valued functions: adaptivity helps

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