Diffusion Posterior Sampling is Computationally Intractable
Authors: Shivam Gupta, Ajil Jalal, Aditya Parulekar, Eric Price, Zhiyang Xun
ICML 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper we show that posterior sampling is computationally intractable: under the most basic assumption in cryptography that one-way functions exist there are instances for which every algorithm takes superpolynomial time, even though unconditional sampling is provably fast. We also show that the exponential-time rejection sampling algorithm is essentially optimal under the stronger plausible assumption that there are one-way functions that take exponential time to invert. |
| Researcher Affiliation | Academia | 1Department of Computer Science, University of Texas at Austin 2Department of Electrical Engineering and Computer Science, University of California, Berkeley. |
| Pseudocode | Yes | Algorithm 1 Rejection Sampling Algorithm |
| Open Source Code | No | The paper does not provide any statement or link regarding the release of open-source code for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not use any datasets for training. Therefore, it does not provide access information for a public dataset. |
| Dataset Splits | No | The paper is theoretical and does not conduct experiments with dataset splits. It does not provide any information about training/test/validation splits. |
| Hardware Specification | No | The paper is theoretical and does not report on experiments requiring hardware. Therefore, no hardware specifications are provided. |
| Software Dependencies | No | The paper is theoretical and does not report on experiments that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with hyperparameters or training settings. |