Monotonicity testing over general poset domains

DOI10.1145/509907.509977MaRDI QIDQ3579209zbMATH OpenOpenAlexFDO

Authors Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld, Alex Samorodnitsky

Publication date 5 August 2010

Published in Proceedings of the thiry-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/509907.509977

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Boolean functions (06E30)

Cited in

(46)

• Property testing of massively parametrized problems -- a survey
• An algebraic characterization of testable Boolean CSPs
• Adaptive Boolean Monotonicity Testing in Total Influence Time
• Adaptivity is exponentially powerful for testing monotonicity of halfspaces
• Sparse hypergraphs with applications to coding theory
• Almost optimal distribution-free junta testing
• Erasure-Resilient Property Testing
• Testing Lipschitz functions on hypergrid domains
• Testing convexity properties of tree colorings
• Testing juntas
• Is submodularity testable?
• Testing \(k\)-monotonicity
• An \(o(n)\) monotonicity tester for Boolean functions over the hypercube
• Tolerant property testing and distance approximation
• Constant-query testability of assignments to constraint satisfaction problems
• Transitive-closure spanners: a survey
• Lower Bounds for Testing Computability by Small Width OBDDs
• Monotonicity testing and shortest-path routing on the cube
• Local property reconstruction and monotonicity
• Fast approximate PCPs for multidimensional bin-packing problems
• Exponentially improved algorithms and lower bounds for testing signed majorities
• Property testing lower bounds via communication complexity
• A characterization of constant-sample testable properties
• Information theory in property testing and monotonicity testing in higher dimension
• Flipping out with many flips: hardness of testing \(k\)-monotonicity
• Approximating the distance to monotonicity of Boolean functions
• scientific article; zbMATH DE number 7053293 (Why is no real title available?)
• On Monotonicity Testing and Boolean Isoperimetric-type Theorems
• Isoperimetric inequalities for real-valued functions with applications to monotonicity testing
• Testing Euclidean Spanners
• A large lower bound on the query complexity of a simple Boolean function
• Testing list H-homomorphisms
• Estimating the longest increasing sequence in polylogarithmic time
• On the strength of comparisons in property testing
• Parameterized property testing of functions
• Directed isoperimetric theorems for Boolean functions on the hypergrid and an \(\widetilde{O}(n\sqrt{d})\) monotonicity tester
• On regularity lemma and barriers in streaming and dynamic matching
• Almost Optimal Distribution-Free Sample-Based Testing of k-Modality
• Distribution-free connectivity testing for sparse graphs
• Testing monotonicity over graph products
• Flipping out with many flips: hardness of testing \(k\)-monotonicity
• Adaptive lower bound for testing monotonicity on the line
• Testing of matrix-poset properties
• The power and limitations of uniform samples in testing properties of figures
• A polynomial lower bound for testing monotonicity
• Colorings with only rainbow arithmetic progressions

This page was built for publication: Monotonicity testing over general poset domains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3579209)