Embed and Project: Discrete Sampling with Universal Hashing

By Stefano Ermon, Carla P. Gomes, Ashish Sabharwal, Bart Selman. 2013

76 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Algorithms & Complexity

Citations in the corpus

A* Sampling (2014, methodology): “The problem of drawing samples from a discrete distribution can be converted into a discrete optimization problem [1, 2, 3, 4].”
Logic meets Probability: Towards Explainable AI Systems for Uncertain Worlds (2017, background): “A variety of exact and approximate solver techniques have since been developed that are known to be very competitive, especially in the presence of hard constraints, deterministic reasoning and logical dependencies [Chavira and Darwiche, 2008; Ermon et al., 2013].”
Stochastic Beams and Where to Find Them: The Gumbel-Top-k Trick for Sampling Sequences Without Replacement (2019, methodology): “The idea of sampling by solving optimization problems has been used for various purposes (Papandreou & Yuille, 2011; Hazan & Jaakkola, 2012; Tarlow et al., 2012; Ermon et al., 2013; Maddison et al., 2014; Chen & Ghahramani, 2016; Balog et al., 2017), but to our knowledge this idea has not been used ”
Weighted Model Counting With Function Symbols (2017, background): “The last decade has seen signiﬁcant progress in exact and approximate WMC technology [Chavira and Darwiche, 2008, Gogate and Domingos, 2011, Ermon et al., 2013], which enable deterministic reasoning and exploit context-speciﬁc independencies.”
Open-Universe Weighted Model Counting (2017, methodology): “Exact solvers are based on knowledge compilation (Chavira and Darwiche 2008) or exhaustive DPLL search (Sang, Beame, and Kautz 2005); approximate ones use local search (Wei and Selman 2005) or sampling (Ermon et al. 2013; Chakraborty et al. 2014).”
Learning and Inference via Maximum Inner Product Search (2016, background): “Problems with large output spaces arise naturally in many fields including NLP and computer vision (Bengio et al., 2006; Andreas et al., 2015; Devlin et al., 2014), and pose numerous challenges to inference and learning algorithms (Ermon et al., 2013a).”