On the public citation graph
Statistical Algorithms and a Lower Bound for Detecting Planted Cliques
0 signed · 151 inferred · view as graph
Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.
Is this your work? Sign in with ORCID and put your name on the
claims that are yours.
Reference health. See whether every reference in this work resolves to a
known work and none has been retracted — and get a dated CiteStamped
badge you can embed.
What this work says
Outgoing claims: the papers this work cites, builds on, or argues with.
inferredcites →https://doi.org/10.1002/(sici)1098-2418(199810/12)13:3/4<457::aid-rsa14>3.3.co;2-kopenalex-snapshot
Finding a large hidden clique in a random graph
inferredcites →https://doi.org/10.1002/(sici)1098-2418(200003)16:2<195::aid-rsa5>3.0.co;2-aopenalex-snapshot
Finding and certifying a large hidden clique in a semirandom graph
inferredcites →https://doi.org/10.1002/rsa.3240030402openalex-snapshot
Large Cliques Elude the Metropolis Process
inferredcites →https://doi.org/10.1006/jcss.1998.1569openalex-snapshot
Learning with Restricted Focus of Attention
inferredcites →https://doi.org/10.1006/jcss.1999.1666openalex-snapshot
Computational Sample Complexity and Attribute-Efficient Learning
inferredcites →https://doi.org/10.1007/3-540-44581-1_15openalex-snapshot
Rademacher and Gaussian Complexities: Risk Bounds and Structural Results
inferredcites →https://doi.org/10.1007/3-540-45583-3_7openalex-snapshot
On Learning Correlated Boolean Functions Using Statistical Queries (Extended Abstract)
inferredcites →https://doi.org/10.1007/978-3-319-21852-6_3openalex-snapshot
On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
inferredcites →https://doi.org/10.1007/978-3-642-03685-9_31openalex-snapshot
Random Tensors and Planted Cliques
inferredcites →https://doi.org/10.1007/978-3-642-03685-9_50openalex-snapshot
Small Clique Detection and Approximate Nash Equilibria
inferredcites →https://doi.org/10.1007/978-3-642-04414-4_18openalex-snapshot
Characterizing Statistical Query Learning: Simplified Notions and Proofs
inferredcites →https://doi.org/10.1007/bf00940812openalex-snapshot
Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm
inferredcites →https://doi.org/10.1007/pl00013833openalex-snapshot
A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions
inferredcites →https://doi.org/10.1007/s10107-007-0095-7openalex-snapshot
A simple polynomial-time rescaling algorithm for solving linear programs
inferredcites →https://doi.org/10.1007/s10107-011-0459-xopenalex-snapshot
Nuclear norm minimization for the planted clique and biclique problems
inferredcites →https://doi.org/10.1007/s10208-014-9215-yopenalex-snapshot
Finding Hidden Cliques of Size $$\sqrt{N/e}$$ N / e in Nearly Linear Time
inferredcites →https://doi.org/10.1016/0166-218x(94)00103-kopenalex-snapshot
Expected complexity of graph partitioning problems
inferredcites →https://doi.org/10.1016/j.jcss.2004.10.003openalex-snapshot
New lower bounds for statistical query learning
inferredcites →https://doi.org/10.1016/j.jcss.2011.12.024openalex-snapshot
A complete characterization of statistical query learning with applications to evolvability
inferredcites →https://doi.org/10.1017/s0963548309990514openalex-snapshot
Graph Partitioning via Adaptive Spectral Techniques
inferredcites →https://doi.org/10.1017/s096354831300045xopenalex-snapshot
Finding Hidden Cliques in Linear Time with High Probability
inferredcites →https://doi.org/10.1023/a:1008374125234openalex-snapshot
Hiding Cliques for Cryptographic Security
inferredcites →https://doi.org/10.1063/1.1699114openalex-snapshot
Equation of State Calculations by Fast Computing Machines
inferredcites →https://doi.org/10.1080/01621459.1987.10478458openalex-snapshot
The Calculation of Posterior Distributions by Data Augmentation
inferredcites →https://doi.org/10.1080/01621459.1990.10476213openalex-snapshot
Sampling-Based Approaches to Calculating Marginal Densities
inferredcites →https://doi.org/10.1080/14786440009463897openalex-snapshot
X. On the criterion that a given system of deviations from the probable in the case of a correlated system of variables is such that it can be reasonably supposed to have arisen from random sampling
inferredcites →https://doi.org/10.1090/dimacs/026/25openalex-snapshot
Local search strategies for satisfiability testing
inferredcites →https://doi.org/10.1093/biomet/57.1.97openalex-snapshot
Monte Carlo sampling methods using Markov chains and their applications
inferredcites →https://doi.org/10.1109/focs.2004.59openalex-snapshot
Ruling Out PTAS for Graph Min-Bisection, Densest Subgraph and Bipartite Clique
inferredcites →https://doi.org/10.1109/sfcs.1977.24openalex-snapshot
Probabilistic computations: Toward a unified measure of complexity
inferredcites →https://doi.org/10.1109/sfcs.1996.548492openalex-snapshot
A polynomial-time algorithm for learning noisy linear threshold functions
inferredcites →https://doi.org/10.1109/sfcs.2001.959929openalex-snapshot
Spectral partitioning of random graphs
inferredcites →https://doi.org/10.1111/j.2517-6161.1977.tb01600.xopenalex-snapshot
Maximum Likelihood from Incomplete Data Via the EM Algorithm
inferredcites →https://doi.org/10.1137/090766991openalex-snapshot
How Hard Is It to Approximate the Best Nash Equilibrium?
inferredcites →https://doi.org/10.1137/1.9781611973099.34openalex-snapshot
Polynomial integrality gaps for strong SDP relaxations of Densest k -subgraph
inferredcites →https://doi.org/10.1137/1.9781611974782.82openalex-snapshot
Statistical Query Algorithms for Stochastic Convex Optimization
inferredcites →https://doi.org/10.1137/1116025openalex-snapshot
On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
inferredcites →https://doi.org/10.1137/s009753970240118xopenalex-snapshot
The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set
inferredcites →https://doi.org/10.1145/1250790.1250863openalex-snapshot
Testing k-wise and almost k-wise independence
inferredcites →https://doi.org/10.1145/1374376.1374465openalex-snapshot
Evolvability from learning algorithms
inferredcites →https://doi.org/10.1145/1806689.1806715openalex-snapshot
Public-key cryptography from different assumptions
inferredcites →https://doi.org/10.1145/195058.195147openalex-snapshot
Weakly learning DNF and characterizing statistical query learning using Fourier analysis
inferredcites →https://doi.org/10.1145/258533.258536openalex-snapshot
Some optimal inapproximability results
inferredcites →https://doi.org/10.1145/2746539.2746600openalex-snapshot
Sum-of-squares Lower Bounds for Planted Clique
inferredcites →https://doi.org/10.1145/293347.293351openalex-snapshot
Efficient noise-tolerant learning from statistical queries
inferredcites →https://doi.org/10.1145/509907.509985openalex-snapshot
Relations between average case complexity and approximation complexity
inferredcites →https://doi.org/10.1214/14-aos1300openalex-snapshot
Computational barriers in minimax submatrix detection
inferredcites →https://doi.org/10.1214/16-aos1519openalex-snapshot
Sparse CCA: Adaptive estimation and computational barriers
inferredcites →https://doi.org/10.1287/moor.1090.0388openalex-snapshot
An Efficient Rescaled Perceptron Algorithm for Conic Systems
inferredcites →https://doi.org/10.2307/2287858openalex-snapshot
Proceedings of the Computer Science and Statistics: 12th Annual Symposium on the Interface.
inferredcites →https://doi.org/10.4230/lipics.fsttcs.2008.1752openalex-snapshot
A new approach to the planted clique problem
inferredcites →https://doi.org/10.46298/dmtcs.2802openalex-snapshot
Finding hidden cliques in linear time
inferredcites →https://doi.org/10.48550/arxiv.1001.2891openalex-snapshot
Detecting High Log-Densities -- an O(n^1/4) Approximation for Densest k-Subgraph
inferredcites →https://doi.org/10.48550/arxiv.1304.7047openalex-snapshot
Finding Hidden Cliques of Size \sqrt{N/e} in Nearly Linear Time
inferredcites →https://doi.org/10.48550/arxiv.1502.06590openalex-snapshot
Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems
inferredcites →https://doi.org/10.5555/2095116.2095150openalex-snapshot
Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph
inferredcites →https://doi.org/10.5555/314613.315014openalex-snapshot
Finding a large hidden clique in a random graph
inferredcites →https://doi.org/10.7551/mitpress/7503.003.0040openalex-snapshot
Map-Reduce for Machine Learning on Multicore
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1002/cpa.22121openalex-snapshot
Polynomial‐time universality and limitations of deep learning
inferred← citeshttps://doi.org/10.1002/rsa.21274openalex-snapshot
Almost‐Linear Planted Cliques Elude the Metropolis Process
inferred← citeshttps://doi.org/10.1007/978-3-030-61616-8_9openalex-snapshot
Obstacles to Depth Compression of Neural Networks
inferred← citeshttps://doi.org/10.1007/978-3-030-97127-4_1openalex-snapshot
Notes on Computational Hardness of Hypothesis Testing: Predictions Using the Low-Degree Likelihood Ratio
inferred← citeshttps://doi.org/10.1007/978-3-031-26303-3_21openalex-snapshot
Learning Heuristics for the Maximum Clique Enumeration Problem Using Low Dimensional Representations
inferred← citeshttps://doi.org/10.1007/978-3-031-78017-2_9openalex-snapshot
Low-Degree Security of the Planted Random Subgraph Problem
inferred← citeshttps://doi.org/10.1007/s00440-021-01089-7openalex-snapshot
The overlap gap property in principal submatrix recovery
inferred← citeshttps://doi.org/10.1007/s10208-022-09588-2openalex-snapshot
Adversarial Manifold Estimation
inferred← citeshttps://doi.org/10.1007/s10732-023-09512-zopenalex-snapshot
Learning fine-grained search space pruning and heuristics for combinatorial optimization
inferred← citeshttps://doi.org/10.1007/s41884-024-00135-2openalex-snapshot
Codivergences and information matrices
inferred← citeshttps://doi.org/10.1016/j.acha.2026.101880openalex-snapshot
Computational lower bounds for multi-frequency group synchronization
inferred← citeshttps://doi.org/10.1016/j.laa.2020.01.039openalex-snapshot
Exact recovery in the hypergraph stochastic block model: A spectral algorithm
inferred← citeshttps://doi.org/10.1038/s41467-025-68097-2openalex-snapshot
Quantum advantage for learning shallow neural networks with natural data distributions
inferred← citeshttps://doi.org/10.1038/s42254-023-00662-4openalex-snapshot
A survey on the complexity of learning quantum states
inferred← citeshttps://doi.org/10.1088/1742-5468/ad3a5bopenalex-snapshot
Computational complexity of deep learning: fundamental limitations and empirical phenomena
inferred← citeshttps://doi.org/10.1088/1742-5468/ae8435openalex-snapshot
An optimized Franz–Parisi criterion and its equivalence with SQ lower bounds *
inferred← citeshttps://doi.org/10.1093/imaiai/iaaa032openalex-snapshot
High-temperature structure detection in ferromagnets
inferred← citeshttps://doi.org/10.1093/imaiai/iaac019openalex-snapshot
Computationally efficient sparse clustering
inferred← citeshttps://doi.org/10.1103/xhn1-vnp9openalex-snapshot
Predicting Adaptively Chosen Observables in Quantum Systems
inferred← citeshttps://doi.org/10.1109/focs52979.2021.00047openalex-snapshot
On statistical inference when fixed points of belief propagation are unstable
inferred← citeshttps://doi.org/10.1109/focs54457.2022.00061openalex-snapshot
Algorithms and Barriers in the Symmetric Binary Perceptron Model
inferred← citeshttps://doi.org/10.1109/focs54457.2022.00112openalex-snapshot
Continuous LWE is as Hard as LWE & Applications to Learning Gaussian Mixtures
inferred← citeshttps://doi.org/10.1109/focs61266.2024.00063openalex-snapshot
Sum-of-Squares Lower Bounds for Non-Gaussian Component Analysis
inferred← citeshttps://doi.org/10.1109/focs61266.2024.00064openalex-snapshot
Semirandom Planted Clique and the Restricted Isometry Property
inferred← citeshttps://doi.org/10.1109/isit50566.2022.9834647openalex-snapshot
The Random Number Partitioning Problem: Overlap Gap Property and Algorithmic Barriers
inferred← citeshttps://doi.org/10.1109/isit54713.2023.10206786openalex-snapshot
Detecting a Planted Bipartite Graph
inferred← citeshttps://doi.org/10.1109/jproc.2018.2846588openalex-snapshot
A Selective Overview of Sparse Principal Component Analysis
inferred← citeshttps://doi.org/10.1109/jsait.2020.3037170openalex-snapshot
Robust Hypergraph Clustering via Convex Relaxation of Truncated MLE
inferred← citeshttps://doi.org/10.1109/tit.2020.3028440openalex-snapshot
Inference Under Information Constraints I: Lower Bounds From Chi-Square Contraction
inferred← citeshttps://doi.org/10.1109/tit.2023.3334024openalex-snapshot
Communication-Constrained Hypothesis Testing: Optimality, Robustness, and Reverse Data Processing Inequalities
inferred← citeshttps://doi.org/10.1109/tit.2024.3382228openalex-snapshot
Planted Bipartite Graph Detection
inferred← citeshttps://doi.org/10.1109/tpami.2025.3643798openalex-snapshot
Detection of Model-Based Planted Pseudo-Cliques in Random Dot Product Graphs by the Adjacency Spectral Embedding and the Graph Encoder Embedding
inferred← citeshttps://doi.org/10.1109/tsipn.2022.3211208openalex-snapshot
Inferring Hidden Structures in Random Graphs
inferred← citeshttps://doi.org/10.1111/rssb.12547openalex-snapshot
Exact Clustering in Tensor Block Model: Statistical Optimality and Computational Limit
inferred← citeshttps://doi.org/10.1137/1.9781611977073.49openalex-snapshot
Algorithmic Thresholds for Refuting Random Polynomial Systems
inferred← citeshttps://doi.org/10.1137/16m1078471openalex-snapshot
On the Complexity of Random Satisfiability Problems with Planted Solutions
inferred← citeshttps://doi.org/10.1137/24m1680489openalex-snapshot
Finding Planted Cliques Using Gradient Descent
inferred← citeshttps://doi.org/10.1137/25m1802456openalex-snapshot
Statistical and Computational Challenges in Ranking
inferred← citeshttps://doi.org/10.1145/3406325.3451135openalex-snapshot
Statistical query complexity of manifold estimation
inferred← citeshttps://doi.org/10.1145/3519935.3519970openalex-snapshot
Learning general halfspaces with general Massart noise under the Gaussian distribution
inferred← citeshttps://doi.org/10.1145/3564246.3585184openalex-snapshot
Algorithms Approaching the Threshold for Semi-random Planted Clique
inferred← citeshttps://doi.org/10.1145/3564246.3585226openalex-snapshot
Subsampling Suffices for Adaptive Data Analysis
inferred← citeshttps://doi.org/10.1145/3564246.3585232openalex-snapshot
Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials
inferred← citeshttps://doi.org/10.1145/3618260.3649751openalex-snapshot
Planted Clique Conjectures Are Equivalent
inferred← citeshttps://doi.org/10.1145/3698104openalex-snapshot
Subsampling Suffices for Adaptive Data Analysis
inferred← citeshttps://doi.org/10.1145/3717823.3718151openalex-snapshot
Sum-of-Squares Lower Bounds for Coloring Random Graphs
inferred← citeshttps://doi.org/10.1145/3717823.3718306openalex-snapshot
Using the Planted Clique Conjecture for Cryptography: Public-Key Encryption from Planted Clique and Noisy 𝑘-LIN over Expanders
inferred← citeshttps://doi.org/10.1145/3798129.3800739openalex-snapshot
A Unified Approach to Memory-Sample Tradeoffs for Detecting Planted Structures
inferred← citeshttps://doi.org/10.1145/3798129.3800883openalex-snapshot
Rigorous Implications of the Low-Degree Heuristic
inferred← citeshttps://doi.org/10.1214/21-aos2123openalex-snapshot
Tensor clustering with planted structures: Statistical optimality and computational limits
inferred← citeshttps://doi.org/10.1214/22-aos2179openalex-snapshot
Computational barriers to estimation from low-degree polynomials
inferred← citeshttps://doi.org/10.1214/23-aap1953openalex-snapshot
Algorithmic obstructions in the random number partitioning problem
inferred← citeshttps://doi.org/10.1214/23-aap2003openalex-snapshot
The landscape of the planted clique problem: Dense subgraphs and the overlap gap property
inferred← citeshttps://doi.org/10.1214/23-aos2331openalex-snapshot
Statistical-computational trade-offs in tensor PCA and related problems via communication complexity
inferred← citeshttps://doi.org/10.1214/24-aap2120openalex-snapshot
Sharp thresholds in inference of planted subgraphs
inferred← citeshttps://doi.org/10.1214/24-aos2412openalex-snapshot
Tensor factor model estimation by iterative projection
inferred← citeshttps://doi.org/10.1214/24-aos2437openalex-snapshot
Computational lower bounds for graphon estimation via low-degree polynomials
inferred← citeshttps://doi.org/10.1214/25-aos2490openalex-snapshot
Precise error rates for computationally efficient testing
inferred← citeshttps://doi.org/10.1360/ssm-2026-0032openalex-snapshot
Algorithmic inference: A modern machine learning framework that blends algorithmic thinking and inferential thinking
inferred← citeshttps://doi.org/10.1609/aaai.v33i01.33012314openalex-snapshot
Fine-Grained Search Space Classification for Hard Enumeration Variants of Subset Problems
inferred← citeshttps://doi.org/10.22331/q-2025-10-13-1883openalex-snapshot
On the average-case complexity of learning output distributions of quantum circuits
inferred← citeshttps://doi.org/10.30757/alea.v17-30openalex-snapshot
Finding a planted clique by adaptive probing
inferred← citeshttps://doi.org/10.3150/21-bej1433openalex-snapshot
Estimation of Wasserstein distances in the Spiked Transport Model
inferred← citeshttps://doi.org/10.3150/24-bej1798openalex-snapshot
Clustering a mixture of Gaussians with unknown covariance
inferred← citeshttps://doi.org/10.3929/ethz-b-000378784openalex-snapshot
Bilu-Linial Stability, Certified Algorithms and the Independent Set Problem
inferred← citeshttps://doi.org/10.4230/lipics.itcs.2021.10openalex-snapshot
The Strongish Planted Clique Hypothesis and Its Consequences
inferred← citeshttps://doi.org/10.4230/lipics.itcs.2021.34openalex-snapshot
Is the Space Complexity of Planted Clique Recovery the Same as That of Detection?
inferred← citeshttps://doi.org/10.48550/arxiv.1812.06369openalex-snapshot
Provable limitations of deep learning
inferred← citeshttps://doi.org/10.48550/arxiv.1911.11838openalex-snapshot
Robustly Clustering a Mixture of Gaussians
inferred← citeshttps://doi.org/10.48550/arxiv.2001.02992openalex-snapshot
Poly-time universality and limitations of deep learning
inferred← citeshttps://doi.org/10.48550/arxiv.2002.00329openalex-snapshot
The EM Algorithm gives Sample-Optimality for Learning Mixtures of Well-Separated Gaussians
inferred← citeshttps://doi.org/10.48550/arxiv.2002.08240openalex-snapshot
Quantum statistical query learning
inferred← citeshttps://doi.org/10.48550/arxiv.2002.12903openalex-snapshot
The estimation error of general first order methods
inferred← citeshttps://doi.org/10.48550/arxiv.2004.00557openalex-snapshot
Statistical Queries and Statistical Algorithms: Foundations and Applications
inferred← citeshttps://doi.org/10.48550/arxiv.2004.12002openalex-snapshot
Finding Planted Cliques in Sublinear Time
inferred← citeshttps://doi.org/10.48550/arxiv.2008.04101openalex-snapshot
Statistical Query Lower Bounds for Tensor PCA
inferred← citeshttps://doi.org/10.48550/arxiv.2008.12237openalex-snapshot
Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs
inferred← citeshttps://doi.org/10.48550/arxiv.2010.11925openalex-snapshot
The Polynomial Method is Universal for Distribution-Free Correlational SQ Learning
inferred← citeshttps://doi.org/10.48550/arxiv.2011.04253openalex-snapshot
Machinery for Proving Sum-of-Squares Lower Bounds on Certification Problems
inferred← citeshttps://doi.org/10.48550/arxiv.2102.04401openalex-snapshot
The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals
inferred← citeshttps://doi.org/10.48550/arxiv.2106.09689openalex-snapshot
Statistical Query Lower Bounds for List-Decodable Linear Regression
inferred← citeshttps://doi.org/10.48550/arxiv.2106.10744openalex-snapshot
On the Cryptographic Hardness of Learning Single Periodic Neurons
inferred← citeshttps://doi.org/10.48550/arxiv.2107.11886openalex-snapshot
Logspace Reducibility From Secret Leakage Planted Clique
inferred← citeshttps://doi.org/10.48550/arxiv.2111.05320openalex-snapshot
Robust Estimation for Random Graphs
inferred← citeshttps://doi.org/10.48550/arxiv.2111.10352openalex-snapshot
On the power of adaptivity in statistical adversaries
inferred← citeshttps://doi.org/10.52202/068431-1376openalex-snapshot
Reconstruction on Trees and Low-Degree Polynomials
Editorial review for independent work. ICSAC — the Institute for Complexity
Science and Advanced Computing — runs a structured editorial panel for researchers
publishing outside journals, and publishes on CiteStamp rails. Submission is free
and goes through ORCID: icsacinstitute.org/submit.