Almost Optimal Pseudorandom Generators for Spherical Caps

DOI10.1145/2746539.2746611MaRDI QIDQ2941513zbMATH OpenOpenAlexFDO

Authors Pravesh Kothari, Raghu Meka

Publication date 21 August 2015

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

Full work available at URL https://doi.org/10.1145/2746539.2746611

zbMATH Keywords

classical moment problemhalfspacesorthogonal designspseudorandom generators

Mathematics Subject Classification ID

Random number generation in numerical analysis (65C10) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 1256644
• On Optimal GFSR Pseudorandom Number Generators
• Randomized geometric algorithms and pseudorandom generators
• Pseudorandom generators for space-bounded computation
• scientific article; zbMATH DE number 1834654
• Pseudodistributions that beat all pseudorandom generators (extended abstract)
• Near-optimal pseudorandom generators for constant-depth read-once formulas
• An efficient algorithm to generate random sphere packs in arbitrary domains
• An asymptotically perfect pseudorandom generator

Cites work

• Approximate distance oracles
• Approximate distance oracles with constant query time
• Automata, Languages and Programming
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Fast C-K-R partitions of sparse graphs
• Near-Linear Time Construction of Sparse Neighborhood Covers
• On approximate distance labels and routing schemes with affine stretch
• On sparse spanners of weighted graphs
• Ramsey partitions and proximity data structures
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• Shortest-path queries in static networks

Cited in

(5)

• Explicit correlation amplifiers for finding outlier correlations in deterministic subquadratic time
• Pseudorandomness via the discrete Fourier transform
• Fooling Polytopes
• Simple and efficient pseudorandom generators from gaussian processes
• Positive spectrahedra: invariance principles and pseudorandom generators

Describes a project that uses

Uses Software

• Graphs

This page was built for publication: Almost Optimal Pseudorandom Generators for Spherical Caps

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2941513)