An Approximate Skolem Function Counter

Learn about an innovative approach to counting Skolem functions in quantified Boolean formulas (QBF) through this 30-minute talk by Brendan Juba from Washington University in St. Louis. Explore the challenges and practical applications of this quantitative problem in program verification and specification evaluation. Discover a novel algorithm that utilizes exact model counting for #SAT queries to approximate the number of Skolem functions with PAC guarantees. Gain insights into the complexity-theoretic aspects of the problem and understand how this tool scales to handle formulas with thousands of variables. Delve into the joint research conducted with Kuldeep Meel and Arijit Shaw, addressing the synthesis challenges in quantified Boolean formulas.

An Approximate Skolem Function Counter