Skip to main content

Constrained sampling and counting: Universal hashing meets SAT solving

Author(s): Meel, KS; Vardi, MY; Chakraborty, S; Fremont, DJ; Seshia, SA; et al

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1xj55
Full metadata record
DC FieldValueLanguage
dc.contributor.authorMeel, KS-
dc.contributor.authorVardi, MY-
dc.contributor.authorChakraborty, S-
dc.contributor.authorFremont, DJ-
dc.contributor.authorSeshia, SA-
dc.contributor.authorFried, D-
dc.contributor.authorIvrii, A-
dc.contributor.authorMalik, Sharad-
dc.date.accessioned2020-04-01T13:22:53Z-
dc.date.available2020-04-01T13:22:53Z-
dc.date.issued2016-3-29en_US
dc.identifier.citationMeel, KS, Vardi, MY, Chakraborty, S, Fremont, DJ, Seshia, SA, Fried, D, Ivrii, A, Malik, S. (2016). Constrained sampling and counting: Universal hashing meets SAT solving. WS-16-01 - WS-16-15 (344 - 351en_US
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr1xj55-
dc.description.abstractConstrained sampling and counting are two fundamental problems in artificial intelligence with a diverse range of applications, spanning probabilistic reasoning and planning to constrained-random verification. While the theory of these problems was thoroughly investigated in the 1980s, prior work either did not scale to industrial size instances or gave up correctness guarantees to achieve scalability. Recently, we proposed a novel approach that combines universal hashing and SAT solving and scales to formulas with hundreds of thousands of variables without giving up correctness guarantees. This paper provides an overview of the key ingredients of the approach and discusses challenges that need to be overcome to handle larger real-world instances.en_US
dc.format.extent344 - 351en_US
dc.language.isoen_USen_US
dc.relation.ispartofAAAI Workshop - Technical Reporten_US
dc.relation.ispartofseries30th AAAI Conference on Artificial Intelligence, AAAI 2016; Phoenix; United States; 12 February 2016 through 13 February 2016;-
dc.rightsAuthor's manuscripten_US
dc.titleConstrained sampling and counting: Universal hashing meets SAT solvingen_US
dc.typeConference Articleen_US
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/conference-proceedingen_US

Files in This Item:
File Description SizeFormat 
Constrained sampling and counting Universal hashing meets SAT solving.pdf349.89 kBAdobe PDFView/Download


Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.