scientific article; zbMATH DE number 7378652

DOI10.4230/LIPIcs.APPROX-RANDOM.2018.40zbMath1496.68378arXiv1705.04205MaRDI QIDQ5009536

Karl Wimmer, Elena Grigorescu, Akash Kumar

Publication date: 4 August 2021

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

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

zbMATH Keywords

Boolean functionslower boundsproperty testing\(k\)-monotonicity

Mathematics Subject Classification ID

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

Related Items (1)

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

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
• An $o(n)$ Monotonicity Tester for Boolean Functions over the Hypercube
• Approximating the distance to monotonicity in high dimensions
• Property testing and its connection to learning and approximation
• On the Inversion Complexity of a System of Functions
• 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
• 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: