Flipping out with many flips: hardness of testing k-monotonicity
From MaRDI portal
Publication:5243170
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
Cites work
- scientific article; zbMATH DE number 3130282 (Why is no real title available?)
- scientific article; zbMATH DE number 1418269 (Why is no real title available?)
- scientific article; zbMATH DE number 5686753 (Why is no real title available?)
- scientific article; zbMATH DE number 6395191 (Why is no real title available?)
- A Szemerédi-type regularity lemma in abelian groups, with applications
- A \(o(n)\) monotonicity tester for Boolean functions over the hypercube
- A characterization of locally testable affine-invariant properties via decomposition theorems
- A polynomial lower bound for testing monotonicity
- A removal lemma for systems of linear equations over finite fields
- A unified framework for testing linear-invariant properties
- Algebraic property testing: the role of invariance
- Alternation, sparsity and sensitivity: combinatorial bounds and exponential gaps
- An \(\widetilde O(n)\) queries adaptive tester for unateness
- Approximating the distance to monotonicity in high dimensions
- Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness
- Boolean function complexity. Advances and frontiers.
- Boolean function monotonicity testing requires (almost) \(n^{1/2}\) non-adaptive queries
- Every locally characterized affine-invariant property is testable
- Fast approximate PCPs for multidimensional bin-packing problems
- Flipping out with many flips: hardness of testing \(k\)-monotonicity
- Green's conjecture and testing linear invariant properties
- Improved bounds for testing forbidden order patterns
- Information theory in property testing and monotonicity testing in higher dimension
- Learning circuits with few negations
- Monotonicity testing and shortest-path routing on the cube
- Monotonicity testing over general poset domains
- Negation-Limited Formulas.
- On Monotonicity Testing and Boolean Isoperimetric-type Theorems
- On the strength of comparisons in property testing
- Optimal bounds for monotonicity and Lipschitz testing over hypercubes and hypergrids
- Optimal unateness testers for real-valued functions: Adaptivity helps
- 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
- Sensitivity conjecture and log-rank conjecture for functions with small alternating numbers
- Spot-checkers
- Testing \(k\)-monotonicity
- Testing for forbidden order patterns in an array
- Testing linear-invariant non-linear properties
- Testing low complexity affine-invariant properties
- Testing monotonicity
- Testing monotonicity over graph products
- Testing probability distributions underlying aggregated data
- Testing problems with sublearning sample complexity
- Testing surface area
- Testing surface area with arbitrary accuracy
- Testing unateness nearly optimally
- The power of negations in cryptography
- Tolerant property testing and distance approximation
- Transitive-closure spanners
- \(L_p\)-testing
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)
