scientific article; zbMATH DE number 7286913

DOI10.4086/toc.2020.v016a003zbMath1462.68235arXiv1703.05199OpenAlexW3085987675MaRDI QIDQ5140837

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

Publication date: 17 December 2020

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

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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

hypercubeproperty testinghypergridunate and monotone functions

Mathematics Subject Classification ID

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

Related Items (1)

Approximating the distance to monotonicity of Boolean functions

Cites Work

• Unnamed Item
• Testing Lipschitz functions on hypergrid domains
• Monotonicity testing and shortest-path routing on the cube
• Is submodularity testable?
• Property testing lower bounds via communication complexity
• Information theory in property testing and monotonicity testing in higher dimension
• Self-testing/correcting with applications to numerical problems
• Spot-checkers
• Fast approximate PCPs for multidimensional bin-packing problems
• On the strength of comparisons in property testing
• An $o(n)$ Monotonicity Tester for Boolean Functions over the Hypercube
• Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy
• Boolean Function Monotonicity Testing Requires (Almost) n 1/2 Non-adaptive Queries
• On Proximity-Oblivious Testing
• Breaking the $\epsilon$-Soundness Bound of the Linearity Test over GF(2)
• Linearity testing in characteristic two
• Property testing and its connection to learning and approximation
• Distribution-Free Property-Testing
• Testing monotonicity over graph products
• On Testing Convexity and Submodularity
• On Monotonicity Testing and Boolean Isoperimetric-type Theorems
• Erasure-Resilient Property Testing
• Robust Characterizations of Polynomials with Applications to Program Testing
• Testing the Lipschitz Property over Product Distributions with Applications to Data Privacy
• Transitive-Closure Spanners
• Transitive-Closure Spanners: A Survey
• Parameterized Property Testing of Functions
• Introduction to Property Testing
• Non‐Abelian homomorphism testing, and distributions close to their self‐convolutions
• Optimal bounds for monotonicity and lipschitz testing over hypercubes and hypergrids
• Testing monotonicity
• On disjoint chains of subsets

This page was built for publication: