scientific article; zbMATH DE number 7250148

DOI10.4230/LIPIcs.CCC.2018.8zbMath1441.68051MaRDI QIDQ5121896

Swagato Sanyal, Sampath Kannan, Grigory Yaroslavtsev, Elchanan Mossel

Publication date: 22 September 2020

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

communication complexitystreaming algorithmslinear sketchXOR-functions

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Communication complexity, information complexity (68Q11)

Related Items

A Short List of Equalities Induces Large Sign-Rank, Approximate F_2-Sketching of Valuation Functions, Querying a Matrix Through Matrix-Vector Products., Optimality of linear sketching under modular updates

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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.
• On the structure of Boolean functions with small spectral norm
• Toward Optimal Bounds in the Congested Clique
• Improved Bounds for the Randomized Decision Tree Complexity of Recursive Majority
• Sparse and Lopsided Set Disjointness via Information Theory
• Near-Optimal Upper Bound on Fourier Dimension of Boolean Functions in Terms of Fourier Sparsity
• The Simultaneous Communication of Disjointness with Applications to Data Streams
• Lower Bounds on Frequency Estimation of Data Streams (Extended Abstract)
• Testing Reed–Muller Codes
• Learning juntas
• Two applications of information complexity
• Composition Theorems in Communication Complexity
• Learning Decision Trees Using the Fourier Spectrum
• Maximum Matchings in Dynamic Graph Streams and the Simultaneous Communication Model
• On Estimating Maximum Matching Size in Graph Streams
• Semi-Streaming Algorithms for Annotated Graph Streams
• Communication Complexity
• Robust Characterizations of Polynomials with Applications to Program Testing
• Recent advances on the log-rank conjecture in communication complexity
• Turnstile streaming algorithms might as well be linear sketches
• An Improved Lower Bound for the Randomized Decision Tree Complexity of Recursive Majority,
• MST in Log-Star Rounds of Congested Clique
• Rectangles Are Nonnegative Juntas
• Testing Fourier Dimensionality and Sparsity