The Edge Density Barrier: Computational-Statistical Tradeoffs in Combinatorial Inference
Authors: Hao Lu, Yuan Cao, Zhuoran Yang, Junwei Lu, Han Liu, Zhaoran Wang
ICML 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the hypothesis testing problem of inferring the existence of combinatorial structures in undirected graphical models. Although there exist extensive studies on the information-theoretic limits of this problem, it remains largely unexplored whether such limits can be attained by efficient algorithms. In this paper, we quantify the minimum computational complexity required to attain the information-theoretic limits based on an oracle computational model. We prove that, for testing common combinatorial structures, such as clique and nearest neighbor graph against an empty graph, or large clique against small clique, the information-theoretic limits are provably unachievable by tractable algorithms in general. |
| Researcher Affiliation | Academia | 1Department of Operations Research and Financial Engineering, Princeton University, Princeton, NJ, USA 2Department of Biostatistics, Harvard University, Boston, MA, USA 3Department of Electrical Engineering and Computer Science, Northwestern University, Evanston, IL, USA 4Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, IL, USA. |
| Pseudocode | No | The paper describes tests using mathematical formulations but does not provide pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any statement or link indicating the availability of open-source code for the methodology described. |
| Open Datasets | No | The paper describes a theoretical model involving 'n independent realizations x1, . . . , xn of X' but does not use or provide access to any specific publicly available dataset for training or evaluation. |
| Dataset Splits | No | The paper does not mention any training, validation, or test dataset splits, as it is a theoretical paper and does not conduct experiments on empirical data. |
| Hardware Specification | No | The paper is theoretical and does not mention any hardware specifications used for running experiments. |
| Software Dependencies | No | The paper is theoretical and does not mention any specific software dependencies with version numbers. |
| Experiment Setup | No | The paper does not describe any experimental setup details such as hyperparameters or system-level training settings, as it does not involve empirical experiments. |