Flipping out with many flips: hardness of testing k-monotonicity
From MaRDI portal
Publication:5243170
DOI10.1137/18M1217978zbMATH Open1493.68396OpenAlexW2987535108MaRDI QIDQ5243170FDOQ5243170
Authors: Elena Grigorescu, A. 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
Recommendations
- Flipping out with many flips: hardness of testing \(k\)-monotonicity
- Testing \(k\)-monotonicity
- Testing \(k\)-monotonicity. The rise and fall of Boolean functions
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Optimal bounds for monotonicity and Lipschitz testing over hypercubes and hypergrids
Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Property testing and its connection to learning and approximation
- Self-testing/correcting with applications to numerical problems
- Spot-checkers
- Fast approximate PCPs for multidimensional bin-packing problems
- Testing monotonicity over graph products
- Monotonicity testing over general poset domains
- Robust Characterizations of Polynomials with Applications to Program Testing
- Title not available (Why is that?)
- \(L_p\)-testing
- Title not available (Why is that?)
- Optimal bounds for monotonicity and Lipschitz testing over hypercubes and hypergrids
- Testing monotonicity
- Boolean function complexity. Advances and frontiers.
- A removal lemma for systems of linear equations over finite fields
- A Szemerédi-type regularity lemma in abelian groups, with applications
- Algebraic property testing: the role of invariance
- A unified framework for testing linear-invariant properties
- On the strength of comparisons in property testing
- Monotonicity testing and shortest-path routing on the cube
- Property testing lower bounds via communication complexity
- Information theory in property testing and monotonicity testing in higher dimension
- Every locally characterized affine-invariant property is testable
- Approximating the distance to monotonicity in high dimensions
- Title not available (Why is that?)
- Transitive-closure spanners
- Tolerant property testing and distance approximation
- Testing for forbidden order patterns in an array
- Optimal unateness testers for real-valued functions: Adaptivity helps
- The power of negations in cryptography
- Learning circuits with few negations
- Testing problems with sublearning sample complexity
- Testing probability distributions underlying aggregated data
- Testing surface area
- Testing \(k\)-monotonicity
- Testing linear-invariant non-linear properties
- Green's conjecture and testing linear invariant properties
- A characterization of locally testable affine-invariant properties via decomposition theorems
- Testing low complexity affine-invariant properties
- Improved bounds for testing forbidden order patterns
- On Monotonicity Testing and Boolean Isoperimetric-type Theorems
- Boolean function monotonicity testing requires (almost) \(n^{1/2}\) non-adaptive queries
- Alternation, sparsity and sensitivity: combinatorial bounds and exponential gaps
- Sensitivity conjecture and log-rank conjecture for functions with small alternating numbers
- Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness
- A polynomial lower bound for testing monotonicity
- A \(o(n)\) monotonicity tester for Boolean functions over the hypercube
- An \(\widetilde O(n)\) queries adaptive tester for unateness
- Testing unateness nearly optimally
- Title not available (Why is that?)
- Testing surface area with arbitrary accuracy
- Negation-Limited Formulas.
- Flipping out with many flips: hardness of testing \(k\)-monotonicity
Cited In (3)
This page was built for publication: Flipping out with many flips: hardness of testing \(k\)-monotonicity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5243170)
