The Fourth Moment Method

DOI10.1137/S0097539792240005MaRDI QIDQ4376165zbMATH OpenOpenAlexWikidataFDO

Authors Bonnie Berger

Publication date 10 February 1998

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

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

zbMATH Keywords

Gayle--Berlekamp switching gamemaximum acyclic subgraphremoving randomnessset discrepancy

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Recommendations

• Solving some discrepancy problems in NC
• Bounding probability of small deviation: a fourth moment approach
• scientific article; zbMATH DE number 1528185
• The fourth moment in Luby's distribution
• Simulating (log ^c n )-wise independence in NC

Cited in

(14)

• Distinguishability of quantum states under restricted families of measurements with an application to quantum data hiding
• Improved algorithms via approximations of probability distributions
• An ODE method to prove the geometric convergence of adaptive stochastic algorithms
• Quasi-random multilinear polynomials
• Some applications of hypercontractive inequalities in quantum information theory
• Low rank matrix recovery from rank one measurements
• Distinguishing multi-partite states by local measurements
• CROSS-MOMENTS COMPUTATION FOR STOCHASTIC CONTEXT-FREE GRAMMARS
• Cross-moments computation for stochastic context-free grammars
• Extremal results on feedback arc sets in digraphs
• Deterministic parallel algorithms for bilinear objective functions
• The fourth moment in Luby's distribution
• Upper bounds on the minimum size of feedback arc set of directed multigraphs with bounded degree
• Improved parallel derandomization via finite automata with applications

This page was built for publication: The Fourth Moment Method

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