Monotonicity testing and shortest-path routing on the cube

DOI10.1007/S00493-012-2765-1zbMATH Open1265.68079OpenAlexW2400386569MaRDI QIDQ452855FDOQ452855

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

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

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)

Cites Work

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

Cited In (18)

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