On the Hardness of Probabilistic Inference Relaxations
Authors: Supratik Chakraborty, Kuldeep S. Meel, Moshe Y. Vardi7785-7792
AAAI 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we show that contrary to common belief, several relaxations used for model counting and its applications (including probablistic inference) do not really lead to computational efficiency in a complexity theoretic sense. Our arguments proceed by showing the corresponding relaxed notions of counting to be computationally hard. We argue that approximate counting with multiplicative tolerance and probabilistic guarantees of correctness is the only class of relaxations that provably simplifies the problem, given access to an NP-oracle. Finally, we show that for applications that compare probability estimates with a threshold, a new notion of relaxation with gaps between low and high thresholds can be used. This new relaxation allows efficient decision making in practice, given access to an NP-oracle, while also bounding the approximation error. |
| Researcher Affiliation | Academia | Supratik Chakraborty Dept of Computer Science & Engineering Indian Institute of Technology, Bombay Kuldeep S. Meel School of Computing National University of Singapore Moshe Y. Vardi Department of Computer Science Rice University |
| Pseudocode | No | The paper does not contain any pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not mention releasing any source code for the methodology described. |
| Open Datasets | No | The paper is theoretical and does not use or refer to any datasets. |
| Dataset Splits | No | The paper is theoretical and does not involve dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not mention any hardware specifications for running experiments. |
| Software Dependencies | No | The paper is theoretical and discusses concepts like 'SAT solvers' and '2QBF solver' as types of oracles, but it does not specify any concrete software dependencies with version numbers for experimental reproducibility. |
| Experiment Setup | No | The paper is theoretical and does not describe any experimental setup details such as hyperparameters or training settings. |