Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1]
Hardness of Identity Testing for Restricted Boltzmann Machines and Potts models
Authors: Antonio Blanca, Zongchen Chen, Daniel Štefankovič, Eric Vigoda
JMLR 2021 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the identity testing problem for restricted Boltzmann machines (RBMs), and more generally, for undirected graphical models. In this problem, given sample access to the Gibbs distribution corresponding to an unknown or hidden model M and given an explicit model M, the goal is to distinguish if either M = M or if the models are (statistically) far apart. We establish the computational hardness of identity testing for RBMs (i.e., mixed Ising models on bipartite graphs), even when there are no latent variables or an external field. Specifically, we show that unless RP = NP, there is no polynomial-time identity testing algorithm for RBMs when βd = ω(log n)... To prove our results, we introduce a novel methodology to reduce the corresponding approximate counting problem to testing utilizing the phase transition exhibited by these models. |
| Researcher Affiliation | Academia | Antonio Blanca EMAIL Pennsylvania State University University Park, PA, USA; Zongchen Chen EMAIL Georgia Institute of Technology Atlanta, GA, USA; Daniel Štefankovič EMAIL University of Rochester Rochester, NY, USA; Eric Vigoda EMAIL Georgia Institute of Technology Atlanta, GA, USA |
| Pseudocode | No | The paper describes algorithms conceptually (e.g., polynomial-time identity testing algorithm, exact sampling algorithm) and outlines proof strategies, but does not present any structured pseudocode blocks or algorithms with numbered steps formatted like code. |
| Open Source Code | No | The paper does not contain any explicit statements about releasing code for the described methodology, nor does it provide links to source code repositories. |
| Open Datasets | No | The paper is theoretical, focusing on computational hardness and proofs for models like Restricted Boltzmann Machines and Potts models. It does not utilize or refer to any experimental datasets, and therefore provides no information about public availability or access. |
| Dataset Splits | No | As the paper is theoretical and does not involve experimental evaluation with datasets, there is no mention of dataset splits (training, validation, test) required for reproducibility. |
| Hardware Specification | No | The paper focuses on theoretical computational complexity results and does not report on experiments run on specific hardware. Therefore, no hardware specifications are provided. |
| Software Dependencies | No | The paper is theoretical and discusses mathematical models and complexity. It does not describe any implementation details or experiments that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper presents theoretical results and proofs concerning computational hardness. It does not include any experimental section, and thus no details about experimental setup, hyperparameters, or training configurations are provided. |