On Sketching Quadratic Forms

DOI10.1145/2840728.2840753zbMath1334.68091arXiv1511.06099OpenAlexW2176494464MaRDI QIDQ2800579

Robert Krauthgamer, Bo Qin, Jiecao Chen, David P. Woodruff, Qin Zhang, Alexandr Andoni

Publication date: 15 April 2016

Published in: Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

sketchingquadratic formslower boundgraph sparsification

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Quadratic and bilinear forms, inner products (15A63)

Related Items (12)

Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving ⋮ Sparsification of Binary CSPs ⋮ Unnamed Item ⋮ The algebraic structure of the densification and the sparsification tasks for CSPs ⋮ Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions ⋮ Faster cut sparsification of weighted graphs ⋮ Unnamed Item ⋮ Sparsification of Binary CSPs ⋮ A note on distance-preserving graph sparsification ⋮ A General Framework for Graph Sparsification ⋮ Tight Bounds for the Subspace Sketch Problem with Applications ⋮ Sparsification of Two-Variable Valued Constraint Satisfaction Problems

This page was built for publication: On Sketching Quadratic Forms