Campus Event Calendar: Gunjan Kumar (07/20/2023 in E1 4/024)

Campus Event Calendar

Campus Event Calendar:
- All Upcoming:
  - only for D1
  - only for D2
  - only for INET
  - only for D4
  - only for D5
  - only for D6
  - only for RG1
  - Mailing Lists
  - by Speaker
  - by Type
  - by Category
  - by Title
  - Calendar
  - RSS Feed
- History of Events:

Event Entry

What and Who

Approximate Model Counting: Is SAT Oracle More Powerful than NP Oracle?

Gunjan Kumar

National University of Singapore

AG1 Mittagsseminar (own work)

AG 1

AG Audience

English

Note: We use this to send email in the morning.

Date, Time and Location

Thursday, 20 July 2023

13:00

30 Minutes

E1 4

024

Saarbrücken

Abstract

Given a Boolean formula $\phi$ over $n$ variables, the problem of model counting is to compute the number of solutions of $\phi$. Model counting is a fundamental problem in computer science with wide-ranging applications in domains such as quantified information leakage, probabilistic reasoning, network reliability, neural network verification, and more. Owing to the #P-hardness of the problems, Stockmeyer initiated the study of the complexity of approximate counting and showed that $\log n$ calls to an NP oracle are necessary and sufficient to achieve tight guarantees.

It is well known that an NP oracle does not fully capture the behavior of SAT solvers, as SAT solvers are also designed to provide satisfying assignments when a formula is satisfiable, without additional overhead. Accordingly, the notion of SAT oracle has been proposed to capture the behavior of SAT solver wherein given a Boolean formula, an SAT oracle returns a satisfying assignment if the formula is satisfiable or returns unsatisfiable otherwise.

The primary contribution of this work is to study the relative power of the NP oracle and SAT oracle in the context of approximate model counting. We develop a new methodology to achieve the main result: a SAT oracle is no more powerful than an NP oracle in the context of approximate model counting.

(To appear in ICALP 2023 (https://arxiv.org/abs/2306.10281). Joint work with Diptarka Chakraborty, Sourav Chakraborty, and Kuldeep S. Meel).

Contact

Roohani Sharma

+49 681 9325 1116

--email hidden

Virtual Meeting Details

System used:

Zoom

Meeting URL:

https://zoom.us/j/5272788807

Meeting ID:

527 278 8807

Passcode:

passcode not visible

Code Visible for:

logged in users only

Tags, Category, Keywords and additional notes

Note:

If you wish to attend the talk online but do not have the zoom password, contact Roohani Sharma at rsharma@mpi-inf.mpg.de.

Roohani Sharma, 06/22/2023 12:46
Roohani Sharma, 06/21/2023 09:23 -- Created document.

Imprint / Impressum | Data Protection / Datenschutzhinweis