Approximate F_2-Sketching of Valuation Functions

DOI10.4230/LIPIcs.APPROX-RANDOM.2019.69OpenAlexW3023533112MaRDI QIDQ5875529

Samson Zhou, Grigory Yaroslavtsev

Publication date: 3 February 2023

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

zbMATH Keywords

approximation algorithmssublinear algorithmslinear sketches

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Is submodularity testable?
• The communication complexity of the Hamming distance problem
• On the parity complexity measures of Boolean functions
• The space complexity of approximating the frequency moments
• On the power of circuits with gates of low \(L_{1}\) norms.
• Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas
• Testing Coverage Functions
• Privately Releasing Conjunctions and the Statistical Query Barrier
• Computational Advertising: Techniques for Targeting Relevant Ads
• Single Pass Spectral Sparsification in Dynamic Streams
• Tight Bounds on Communication Complexity of Symmetric XOR Functions in One-Way and SMP Models
• Sparse and Lopsided Set Disjointness via Information Theory
• Extensions of Lipschitz mappings into a Hilbert space
• Streaming Algorithms for Submodular Function Maximization
• SAMPLING IN DYNAMIC DATA STREAMS AND APPLICATIONS
• Composition Theorems in Communication Complexity
• Polynomial Threshold Functions, $AC^0 $ Functions, and Spectral Norms
• Communication Complexity of Simultaneous Messages
• Incidence Geometries and the Pass Complexity of Semi-Streaming Set Cover
• Semi-Streaming Algorithms for Annotated Graph Streams
• Structure of Protocols for XOR Functions
• Communication Complexity
• Semi-Streaming Set Cover
• Recent advances on the log-rank conjecture in communication complexity
• Analysis of Boolean Functions
• Turnstile streaming algorithms might as well be linear sketches
• Tight bounds for single-pass streaming complexity of the set cover problem
• Learning submodular functions
• Learning Pseudo-Boolean k-DNF and Submodular Functions

This page was built for publication: Approximate F_2-Sketching of Valuation Functions