Explicit Dimension Reduction and Its Applications

DOI10.1137/110828812zbMath1253.68154OpenAlexW2131464080MaRDI QIDQ2884581

Zohar S. Karnin, Yuval Rabani, Amir Shpilka

Publication date: 30 May 2012

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/110828812

zbMATH Keywords

dimension reductionpseudorandom generatorlinear threshold functionsdigonsJohnson LindenstraussMAX-cut

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (7)

Binary vectors for fast distance and similarity estimation ⋮ Fooling Polytopes ⋮ A new central limit theorem and decomposition for Gaussian polynomials, with an application to deterministic approximate counting ⋮ Pseudorandomness via the Discrete Fourier Transform ⋮ Real-valued embeddings and sketches for fast distance and similarity estimation ⋮ Robustly Solvable Constraint Satisfaction Problems ⋮ Almost Optimal Explicit Johnson-Lindenstrauss Families

This page was built for publication: Explicit Dimension Reduction and Its Applications