Research map / Learning theory and algorithms / Sample complexity
Computational and Statistical Tradeoffs in Inferring Combinatorial Structures of Ising Model
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use pairwise correlation query functions x_j x_k with a max-minus-min test statistic (quadratic testing statistic) instead of computationally unrestricted statistics for testing empty graph against structures | Ising model structure testing (clique, perfect matching, nearest neighbor graph) · Testing empty graph vs. s-structure, polynomial-time oracle model | detection boundary on edge strength theta (sufficient condition for vanishing te | No clear effect |
| Restrict computational budget to polynomial (T = d^eta) and use a shared-vertex overlap-based lower bound | Clique detection under polynomial-time oracle model · s-clique detection, s = O(d^alpha), alpha in (0,1/2) | minimax testing risk lower bound (lim inf risk = 1) | No clear effect |
| Add a dense-edge information-theoretic query/test (squared average of spins over subsets of size s) rather than pairwise correlation | Clique detection and s/4-nearest neighbor graph detection · Unlimited computation, dense-edge structures | detection boundary on theta (information upper bound) | Helped |
| Information-theoretic lower bound for perfect matching matches the polynomial-time boundary | Perfect matching detection · Testing empty graph vs. perfect matching of size s | signal strength theta threshold | No clear effect |
Closest papers by meaning
- Inference and Sampling of $K_33$-free Ising Models (ICML 2019 · similarity 0.88)
- The Edge Density Barrier: Computational-Statistical Tradeoffs in Combinatorial Inference (ICML 2018 · similarity 0.88)
- Interaction Screening: Efficient and Sample-Optimal Learning of Ising Models (NeurIPS 2016 · similarity 0.87)
- Sample-Efficient L0-L2 Constrained Structure Learning of Sparse Ising Models (AAAI 2021 · similarity 0.87)
- Distribution Learning Meets Graph Structure Sampling (NeurIPS 2025 · similarity 0.84)
- A Machine Learning Approach to Duality in Statistical Physics (ICML 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.