scientific article; zbMATH DE number 5485485
From MaRDI portal
Publication:3549649
Random graphs (graph-theoretic aspects) (05C80) Nonparametric hypothesis testing (62G10) Characterization and structure theory for multivariate probability distributions; copulas (62H05) Hypothesis testing in multivariate analysis (62H15) Measures of association (correlation, canonical correlation, etc.) (62H20) Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Randomized algorithms (68W20)
Cited in
(28)- Testing shape restrictions of discrete distributions
- Digital almost nets
- Tensor clustering with planted structures: statistical optimality and computational limits
- Statistical and computational limits for sparse matrix detection
- On the hardness of designing public signals
- Improving and extending the testing of distributions for shape-restricted properties
- Computational barriers in minimax submatrix detection
- The Hsu-Robbins-Erdös theorem for the maximum partial sums of quadruplewise independent random variables
- Robust characterizations of k-wise independence over product spaces and related testing results
- Small Sample Spaces Cannot Fool Low Degree Polynomials
- Optimal detection of sparse principal components in high dimension
- If the current clique algorithms are optimal, so is Valiant's parser
- A nearly tight sum-of-squares lower bound for the planted clique problem
- Bounded independence plus noise fools products
- Invariance in property testing
- Testing monotone continuous distributions on high-dimensional real cubes
- Sample-based high-dimensional convexity testing
- Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learning
- Hardness self-amplification: simplified, optimized, and unified
- Testing distributional assumptions of learning algorithms
- Cryptography from planted graphs: security with logarithmic-size messages
- On the hardness and approximation of the densest k-subgraph problem in parameterized metric graphs
- Pseudorandomness, symmetry, smoothing: I
- Is the space complexity of planted clique recovery the same as that of detection?
- Fixed-strength spherical designs
- On the satisfiability of random 3-SAT formulas with \(k\)-wise independent clauses
- Fooling near-maximal decision trees
- Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3549649)
