Monotonicity testing and shortest-path routing on the cube

DOI10.1007/S00493-012-2765-1MaRDI QIDQ452855zbMATHOpenAlexFDO

Authors Jop Briët, Sourav Chakraborty, David García-Soriano, Arie Matsliah

Publication date 18 September 2012

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00493-012-2765-1

zbMATH Keywords

disk-\(k\)-monotone functionlower and upper bounds for complexitytesting function monotonicity

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Monotonicity testing and shortest-path routing on the cube
• scientific article; zbMATH DE number 1418269
• Adaptive lower bound for testing monotonicity on the line
• An optimal lower bound for monotonicity testing over hypergrids
• scientific article; zbMATH DE number 6395191

Cites work

• scientific article; zbMATH DE number 1418269 (Why is no real title available?)
• Counterexample to a conjecture of Szymanski on hypercube routing
• Information theory in property testing and monotonicity testing in higher dimension
• Monotonicity testing over general poset domains
• Network coding, does the model need tuning?
• On disjoint chains of subsets
• On the capacity of information networks
• On the strength of comparisons in property testing
• Property testing lower bounds via communication complexity
• Spot-checkers
• Testing monotonicity
• Testing monotonicity over graph products
• Transitive-closure spanners

Cited in

(18)

• Monotonicity testing and shortest-path routing on the cube
• Parameterized property testing of functions
• Erasure-Resilient Property Testing
• Exponentially improved algorithms and lower bounds for testing signed majorities
• Optimal unateness testers for real-valued functions: adaptivity helps
• Directed isoperimetric theorems for Boolean functions on the hypergrid and an \(\widetilde{O}(n\sqrt{d})\) monotonicity tester
• On Monotonicity Testing and Boolean Isoperimetric-type Theorems
• Adaptivity is exponentially powerful for testing monotonicity of halfspaces
• An \(o(n)\) monotonicity tester for Boolean functions over the hypercube
• Is submodularity testable?
• Flipping out with many flips: hardness of testing \(k\)-monotonicity
• Flipping out with many flips: hardness of testing \(k\)-monotonicity
• Isoperimetric inequalities for real-valued functions with applications to monotonicity testing
• A polynomial lower bound for testing monotonicity
• Approximating the distance to monotonicity of Boolean functions
• Improved algorithm for permutation testing
• Almost Optimal Distribution-Free Sample-Based Testing of k-Modality
• Testing \(k\)-monotonicity

This page was built for publication: Monotonicity testing and shortest-path routing on the cube

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