Testing submodularity and other properties of valuation functions

DOI10.4230/LIPICS.ITCS.2017.33MaRDI QIDQ4638085zbMATH OpenFDO

Authors Eric Blais, Abhinav Bommireddi

Publication date 3 May 2018

Full work available at URL https://arxiv.org/abs/1611.07879

zbMATH Keywords

property testingself-bounding functionstesting by implicit learning

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Recommendations

• Is submodularity testable?
• On Testing Convexity and Submodularity
• scientific article; zbMATH DE number 2019621
• Testing coverage functions
• Optimal bounds on approximation of submodular and XOS functions by juntas

Cites work

• L_p-testing
• Analysis of Boolean Functions
• Combinatorial auctions with decreasing marginal utilities
• Efficient sample extractors for juntas with applications
• Efficiently Testing Sparse GF(2) Polynomials
• Is submodularity testable?
• Learning Decision Trees Using the Fourier Spectrum
• Learning submodular functions
• Maximizing Non-monotone Submodular Functions
• On maximizing welfare when utility functions are subadditive
• On the hardness of approximating minimum vertex cover
• On the measure of intersecting families, uniqueness and stability
• Optimal bounds on approximation of submodular and XOS functions by juntas
• Partially symmetric functions are efficiently isomorphism testable
• Property testing and its connection to learning and approximation
• Recognizing coverage functions
• Robust Characterizations of Polynomials with Applications to Program Testing
• Self-testing/correcting with applications to numerical problems
• Sketching valuation functions
• Testing Basic Boolean Formulae
• Testing by implicit learning: a brief survey
• Testing Fourier dimensionality and sparsity
• Testing Halfspaces
• Testing juntas
• Testing juntas nearly optimally
• Testing linear-invariant function isomorphism

Cited in

(11)

• Tight bounds on \(\ell_1\) approximation and learning of self-bounding functions
• Testing coverage functions
• Recognizing coverage functions
• On Testing Convexity and Submodularity
• scientific article; zbMATH DE number 2019621 (Why is no real title available?)
• Is submodularity testable?
• Faster and simpler sketches of valuation functions
• Testing local properties of arrays
• On the Nisan-Ronen conjecture for submodular valuations
• Sketching valuation functions
• Approximate F₂-Sketching of Valuation Functions

This page was built for publication: Testing submodularity and other properties of valuation functions

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