Monotonicity testing and shortest-path routing on the cube
From MaRDI portal
Publication:452855
DOI10.1007/s00493-012-2765-1zbMath1265.68079OpenAlexW2400386569MaRDI QIDQ452855
Arie Matsliah, Sourav Chakraborty, David García-Soriano, Jop Briët
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
Combinatorics in computer science (68R05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (15)
Parameterized property testing of functions ⋮ On Monotonicity Testing and Boolean Isoperimetric-type Theorems ⋮ Approximating the distance to monotonicity of Boolean functions ⋮ Improved algorithm for permutation testing ⋮ Unnamed Item ⋮ Erasure-Resilient Property Testing ⋮ Is submodularity testable? ⋮ Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces ⋮ Almost Optimal Distribution-Free Sample-Based Testing of k-Modality ⋮ An $o(n)$ Monotonicity Tester for Boolean Functions over the Hypercube ⋮ Unnamed Item ⋮ A Polynomial Lower Bound for Testing Monotonicity ⋮ Flipping Out with Many Flips: Hardness of Testing $k$-Monotonicity ⋮ Unnamed Item ⋮ Exponentially improved algorithms and lower bounds for testing signed majorities
Cites Work
- 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
- Spot-checkers
- On the strength of comparisons in property testing
- Testing monotonicity over graph products
- Monotonicity testing over general poset domains
- Transitive-Closure Spanners
- On the capacity of information networks
- Testing monotonicity
- On disjoint chains of subsets
- Unnamed Item
- Unnamed Item
This page was built for publication: Monotonicity testing and shortest-path routing on the cube
