scientific article

zbMath1232.68093MaRDI QIDQ3549649

Alexandr Andoni, Ronitt Rubinfeld, Kevin Matulef, Ning Xie, Noga Alon, Tali Kaufman

Publication date: 5 January 2009

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

testing\(k\)-wise independencestatistical distancealmost \(k\)-wise independence

Mathematics Subject Classification ID

Nonparametric hypothesis testing (62G10) Analysis of algorithms and problem complexity (68Q25) Hypothesis testing in multivariate analysis (62H15) Measures of association (correlation, canonical correlation, etc.) (62H20) Characterization and structure theory for multivariate probability distributions; copulas (62H05) Random graphs (graph-theoretic aspects) (05C80) Randomized algorithms (68W20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (19)

Tensor clustering with planted structures: statistical optimality and computational limits ⋮ If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser ⋮ Optimal detection of sparse principal components in high dimension ⋮ Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation ⋮ The Hsu-Robbins-Erdös theorem for the maximum partial sums of quadruplewise independent random variables ⋮ Statistical and computational limits for sparse matrix detection ⋮ Testing shape restrictions of discrete distributions ⋮ Small Sample Spaces Cannot Fool Low Degree Polynomials ⋮ A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem ⋮ Sample-Based High-Dimensional Convexity Testing. ⋮ Bounded Independence Plus Noise Fools Products ⋮ Invariance in Property Testing ⋮ Testing Monotone Continuous Distributions on High-Dimensional Real Cubes ⋮ On the hardness of designing public signals ⋮ Improving and extending the testing of distributions for shape-restricted properties ⋮ Robust characterizations of k -wise independence over product spaces and related testing results ⋮ Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learning ⋮ Digital almost nets ⋮ Computational barriers in minimax submatrix detection

This page was built for publication: