Submodular functions are noise stable
From MaRDI portal
Recommendations
- Learning submodular functions
- Learning Pseudo-Boolean k-DNF and Submodular Functions
- Optimal bounds on approximation of submodular and XOS functions by juntas
- Algorithms for maximizing monotone submodular function minus modular function under noise
- Submodular functions: learnability, structure, and optimization
Cites work
- Agnostically Learning Halfspaces
- An analysis of approximations for maximizing submodular set functions—I
- Efficient noise-tolerant learning from statistical queries
- Hardness amplification within NP
- scientific article; zbMATH DE number 3169075 (Why is no real title available?)
- scientific article; zbMATH DE number 5485445 (Why is no real title available?)
- scientific article; zbMATH DE number 3635849 (Why is no real title available?)
- Information Inequalities for Joint Distributions, With Interpretations and Applications
- Learning intersections and thresholds of halfspaces
- Learning submodular functions
- Matroids and the greedy algorithm
- Maximizing Non-monotone Submodular Functions
- Noise sensitivity of Boolean functions and applications to percolation
- Some optimal inapproximability results
- Submodular maximization by simulated annealing
- Symmetry and Approximability of Submodular Maximization Problems
- Theory of Cryptography
- Toward efficient agnostic learning
- Truthful randomized mechanisms for combinatorial auctions
- What can we learn privately?
Cited in
(13)- Tight bounds on \(\ell_1\) approximation and learning of self-bounding functions
- Efficient algorithms for privately releasing marginals via convex relaxations
- Optimal bounds on approximation of submodular and XOS functions by juntas
- scientific article; zbMATH DE number 6537946 (Why is no real title available?)
- Submodular functions: learnability, structure, and optimization
- Tight bounds on \(\ell_1\) approximation and learning of self-bounding functions
- Is submodularity testable?
- Differential privacy on finite computers
- Approximate modularity revisited
- Approximating the Noise Sensitivity of a Monotone Boolean Function
- Approximate F₂-Sketching of Valuation Functions
- Testing distributional assumptions of learning algorithms
- Cut sparsification and succinct representation of submodular hypergraphs
This page was built for publication: Submodular functions are noise stable
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5743502)
