Sravanthi Chede

dblp:293/8211 · DBLP profile ↗
← Back
3ranked-venue papers
3as first author
3since 2021 · last 2026
—ORCID · unresolved

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 3 · 3 first-author · 3 since 2021Artificial intelligence and machine learning · 1 · 1 first-author · 1 since 2021
YearPublicationVenuePosition
2026 On Proof Systems for #QBF (Short Paper)
abstract
For a quantified Boolean formula (QBF), the problem of computing the number of winning strategies is known as the #QBF problem. This problem is considered harder than the analogous #SAT problem. Recently, important proof systems for QBFs and #SAT have been studied. By extending the ideas from both fields, we show that it is possible to design proof systems for #QBF. Such proof systems are important not only for advancing the theory of #QBF but also for certifying and designing better #QBF solvers, an area that is still in its early stages. In this paper, we explore #QBF proof systems to count the number of Skolem functions. In addition to a naive system, we study #QBF systems based on the ∀-expansion rule of QBFs. We observe that these systems have inherent structural weaknesses that lead to lower bounds. As an alternative, we propose a #QBF proof system that we call Q-MICE, which consists of sound inference rules for computing and certifying the #QBF solution, similar to the line-based #SAT proof system MICE. To demonstrate the strength of Q-MICE, we present various upper bounds, such as the quantified version of the propositional XOR-PAIRS formula, which are known to be hard for MICE. Consequently, we also separate Q-MICE from ∀-expansion based #QBF proof systems.
Sravanthi Chede, Leroy Chew, Vaibhav Krishan, Anil Shukla
SAT1
2024 Circuits, Proofs and Propositional Model Counting
Sravanthi Chede, Leroy Chew, Anil Shukla
FSTTCS1
2023 Extending Merge Resolution to a Family of QBF-Proof Systems
Sravanthi Chede, Anil Shukla
STACS1