Random Generation of Combinatorial Structures from a Uniform Distribution
By M. Jerrum, Leslie G. Valiant, Vijay V. Vazirani. 1986
Subfields: Probabilistic & Bayesian Methods, Algorithms & Complexity
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Probabilistic & Bayesian Methods
- Roger Baker Grosse
- Ruslan Salakhutdinov
- Yuri Burda
- Yuhuai Wu
- Yoshua Bengio
- Stanislav Minsker
- Andriy Mnih
- Peter L. Bartlett
In Algorithms & Complexity
- Stanislav Minsker
- Rocco A. Servedio
- Kannan Ramchandran
- Peter L. Bartlett
- Philip M. Long
- Dong Yin
- Yudong Chen
- Nate Strawn
Citations in the corpus
- On the Quantitative Analysis of Decoder-Based Generative Models (2016, methodology): “While posterior sampling is just as hard as log-likelihood estimation [14], in the case of log-likelihood estimation for simulated data, one has available a single exact posterior sample: the parameters and/or latent variables which generated the data.”
- Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates (2018, methodology): “This idea is studied in Alon et al. (1999), Jerrum et al. (1986), Lerasle and Oliveira (2011), Minsker et al. (2015), Nemirovskii et al. (1983), and has been applied to bandit and least square regression problems (Bubeck et al., 2013, Kogler and Traxler, 2016, Lugosi and Mendelson, 2016) as well as…”
- Distributed Statistical Estimation and Rates of Convergence in Normal Approximation (2017, methodology): “This estimator has been introduced by Nemirovski and Yudin (1983) in the context of stochastic optimization, and later appeared in (Jerrum et al., 1986) and (Alon et al.”
- Hashing-Based Approximate Probabilistic Inference in Hybrid Domains (2015, background): “…time using a ΣP2 -oracle, a number of more recent results show how random polynomial-time realizations are possible using an NP-oracle (e.g., a SAT solver) (Jerrum et al., 1986; Karp et al., 1989; Bellare et al., 2000; Gomes et al., 2006; Ermon et al., 2013b, 2014; Chakraborty et al., 2013a,b).”
- Efficient and Robust Median-of-Means Algorithms for Location and Regression (2016, unknown): “An early use is [11] (Lemma 6.1).”
- Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning (2018, methodology): “The coordinatewise median aggregation subroutine that we consider is related to the median-of-means estimator [52, 31], which has been applied to various robust inference problems [51, 47, 50].”