Sampling and Approximately Counting CNF Formula Solutions in the Local Lemma Regime

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=9NvZIZlX1B8


Duration: 15:14
281 views
9

Weiming Feng (UC Berkeley)
https://simons.berkeley.edu/talks/weiming-feng-uc-berkeley-2023-09-08
Meet the Fellows Welcome Event Fall 2023

In this talk, I will describe recent progress on sampling and approximately counting CNF formula solutions. Given a CNF formula in which each clause has k variables and each variable belongs to at most d clauses, if a local lemma-type condition k = Ω(log d) is satisfied, we can provide efficient algorithms for generating almost uniform random solutions and for approximately counting the number of solutions. Our sampling algorithm uses the MCMC method on a projected space. The randomized approximate counting algorithm can be derived from the standard reduction. Additionally, we introduce a new technique that derandomizes certain MCMC algorithms and obtains deterministic approximate counting algorithms.



Other Videos By Simons Institute for the Theory of Computing


2023-09-19A Blackbox Reduction for Adaptive Adversaries using Differential Privacy
2023-09-19Recent Progress on Sublinear Time Algorithms for Maximum Matching: Upper Bounds
2023-09-18Parallelism in Dynamic Graph Algorithms
2023-09-18Optimizing Dynamic-Graph Data Structures on Multicores with the Locality-First Strategy
2023-09-18Recent Advances in Diversity Maximization in the Offline and Composable Coreset Models
2023-09-18Approximating Edit Distance in the Fully Dynamic Model
2023-09-18Lightning Talks
2023-09-12Dynamic Graph Algorithms: What We Know and What We Don’t | Richard M. Karp Distinguished Lecture
2023-09-08Probabilistic and Logical Circuits for Tractable Causal Reasoning
2023-09-08Probabilistic Reasoning and Learning for Trustworthy AI
2023-09-08Sampling and Approximately Counting CNF Formula Solutions in the Local Lemma Regime
2023-09-08Massively Parallel Join Algorithms
2023-09-08Relational Programming
2023-09-08Title: Research Interests and Latest Works
2023-09-08What can the demand analyst learn from machine learning?
2023-09-08From Robustness to Privacy and Back
2023-09-08Decoding the Maze: New Frontiers in Achieving Nash Equilibrium in AI Architectures
2023-09-08Risk Convergence and Algorithmic Regularization of Discrete-Stepsize (Stochastic) Gradient Descent
2023-09-08Quantum Cryptography in Algorithmica
2023-09-08Noncommutative constraint satisfaction problems
2023-09-08Faster inverse maintenance for faster conic programming


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Meet the Fellows Welcome Event Fall 2023
Weiming Feng