A PRG for lipschitz functions of polynomials with applications to sparsest cut

DOI10.1145/2488608.2488610zbMath1293.65007arXiv1211.1109OpenAlexW1980830593MaRDI QIDQ5495770

Raghu Meka, Daniel M. Kane

Publication date: 7 August 2014

Published in: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

pseudorandom generatorssparsest cutpolynomial threshold function

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Random number generation in numerical analysis (65C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Vertical perimeter versus horizontal perimeter ⋮ PCPs via the low-degree long code and hardness for constrained hypergraph coloring ⋮ Unnamed Item ⋮ Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes ⋮ Comparison of Metric Spectral Gaps ⋮ The Andoni–Krauthgamer–Razenshteyn Characterization of Sketchable Norms Fails for Sketchable Metrics ⋮ The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ ₁