Video URL

https://simons.berkeley.edu/talks/pseudo-boolean-solving-and-optimization

Approximate Counting and Sampling

(2021). Approximate Counting and Sampling. The Simons Institute for the Theory of Computing. https://simons.berkeley.edu/talks/pseudo-boolean-solving-and-optimization

Approximate Counting and Sampling. The Simons Institute for the Theory of Computing, Feb. 05, 2021, https://simons.berkeley.edu/talks/pseudo-boolean-solving-and-optimization 

          @misc{ scivideos_16968,
            doi = {},
            url = {https://simons.berkeley.edu/talks/pseudo-boolean-solving-and-optimization},
            author = {},
            keywords = {},
            language = {en},
            title = {Approximate Counting and Sampling},
            publisher = {The Simons Institute for the Theory of Computing},
            year = {2021},
            month = {feb},
            note = {16968 see, \url{https://scivideos.org/Simons-Institute/16968}}
          }
Kuldeep Meel (National University of Singapore)
Source Repository Simons Institute
Subject

Abstract

Pre-recorded videos not available for Friday session.   The availability of efficient SAT solvers presents opportunity for designing techniques for problems "beyond SAT". We will discuss two such problems that have witnessed increase in interest over the past decade: counting and sampling. Given a formula, the problem of counting is to compute the total number of solutions while sampling seeks to sample solutions uniformly at random. Counting and sampling are fundamental problems with applications such as probabilistic reasoning, information leakage, verification, and the like. In this talk, we will discuss approach that combines the classical ideas of universal hashing with CDCL solvers to design scalable approximate counters and samplers.