Flipping Out with Many Flips: Hardness of Testing $k$-Monotonicity

DOI10.1137/18M1217978zbMath1493.68396OpenAlexW2987535108MaRDI QIDQ5243170

Elena Grigorescu, Akash Kumar, Karl Wimmer

Publication date: 15 November 2019

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/18m1217978

zbMATH Keywords

hypercubelower boundsproperty testingone-sided

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Monotonicity testing and shortest-path routing on the cube
• Boolean function complexity. Advances and frontiers.
• 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
• A removal lemma for systems of linear equations over finite fields
• Fast approximate PCPs for multidimensional bin-packing problems
• On the strength of comparisons in property testing
• Tolerant property testing and distance approximation
• A Szemerédi-type regularity lemma in abelian groups, with applications
• Alternation, sparsity and sensitivity: combinatorial bounds and exponential gaps
• Approximating the distance to monotonicity in high dimensions
• Boolean Function Monotonicity Testing Requires (Almost) n 1/2 Non-adaptive Queries
• Property testing and its connection to learning and approximation
• Testing monotonicity over graph products
• Monotonicity testing over general poset domains
• On Monotonicity Testing and Boolean Isoperimetric-type Theorems
• Testing for Forbidden Order Patterns in an Array
• Improved Bounds for Testing Forbidden Order Patterns
• An ~O(n) Queries Adaptive Tester for Unateness
• Robust Characterizations of Polynomials with Applications to Program Testing
• Green’s Conjecture and Testing Linear Invariant Properties
• Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness
• A unified framework for testing linear‐invariant properties
• Optimal unateness testers for real-valued functions: Adaptivity helps
• Sensitivity Conjecture and Log-rank Conjecture for functions with small alternating numbers
• Testing Probability Distributions Underlying Aggregated Data
• Testing unateness nearly optimally
• A characterization of locally testable affine-invariant properties via decomposition theorems
• L _p -testing
• Testing surface area with arbitrary accuracy
• The Power of Negations in Cryptography
• Learning circuits with few negations
• Negation-Limited Formulas.
• A polynomial lower bound for testing monotonicity
• Testing Surface Area
• A o(n) monotonicity tester for boolean functions over the hypercube
• Optimal bounds for monotonicity and lipschitz testing over hypercubes and hypergrids
• Every locally characterized affine-invariant property is testable
• Testing Low Complexity Affine-Invariant Properties
• Testing problems with sublearning sample complexity
• Testing monotonicity

This page was built for publication: Flipping Out with Many Flips: Hardness of Testing $k$-Monotonicity