A #SAT Algorithm for Small Constant-Depth Circuits with PTF gates.

Swapnam  Balaji; Vaibhav Krishan; Deepanshu  Kush; Nutan Limaye; Srikanth Srinivasan

doi:10.1007/s00453-021-00915-7

A #SAT Algorithm for Small Constant-Depth Circuits with PTF gates.

Swapnam Balaji, Vaibhav Krishan, Deepanshu Kush, Nutan Limaye, Srikanth Srinivasan

Research output: Journal Article or Conference Article in Journal › Journal article › Research › peer-review

Abstract

We show that there is a randomized algorithm that, when given a small constant-depth Boolean circuit C made up of gates that compute constant-degree Polynomial Threshold functions or PTFs (i.e., Boolean functions that compute signs of constant-degree polynomials), counts the number of satisfying assignments to C in significantly better than brute-force time.

Original language	English
Journal	Algorithmica
Volume	84
ISSN	0178-4617
DOIs	https://doi.org/10.1007/s00453-021-00915-7
Publication status	Published - 2022

Keywords

Circuit Satisfiability
Memoization
PTF circuits

Access to Document

10.1007/s00453-021-00915-7

A #SAT Algorithm for Small Constant-Depth CircuitsOther version, 809 KB

Cite this

@article{c2eea90b45674d1d82a4884e17ac5537,

title = "A #SAT Algorithm for Small Constant-Depth Circuits with PTF gates.",

abstract = "We show that there is a randomized algorithm that, when given a small constant-depth Boolean circuit C made up of gates that compute constant-degree Polynomial Threshold functions or PTFs (i.e., Boolean functions that compute signs of constant-degree polynomials), counts the number of satisfying assignments to C in significantly better than brute-force time.",

keywords = "Circuit Satisfiability, Memoization, PTF circuits, Circuit Satisfiability, Memoization, PTF circuits",

author = "Swapnam Balaji and Vaibhav Krishan and Deepanshu Kush and Nutan Limaye and Srikanth Srinivasan",

year = "2022",

doi = "10.1007/s00453-021-00915-7",

language = "English",

volume = "84",

journal = "Algorithmica",

issn = "0178-4617",

publisher = "Springer New York LLC",

}

TY - JOUR

T1 - A #SAT Algorithm for Small Constant-Depth Circuits with PTF gates.

AU - Balaji, Swapnam

AU - Krishan, Vaibhav

AU - Kush, Deepanshu

AU - Limaye, Nutan

AU - Srinivasan, Srikanth

PY - 2022

Y1 - 2022

N2 - We show that there is a randomized algorithm that, when given a small constant-depth Boolean circuit C made up of gates that compute constant-degree Polynomial Threshold functions or PTFs (i.e., Boolean functions that compute signs of constant-degree polynomials), counts the number of satisfying assignments to C in significantly better than brute-force time.

AB - We show that there is a randomized algorithm that, when given a small constant-depth Boolean circuit C made up of gates that compute constant-degree Polynomial Threshold functions or PTFs (i.e., Boolean functions that compute signs of constant-degree polynomials), counts the number of satisfying assignments to C in significantly better than brute-force time.

KW - Circuit Satisfiability

KW - Memoization

KW - PTF circuits

KW - Circuit Satisfiability

KW - Memoization

KW - PTF circuits

U2 - 10.1007/s00453-021-00915-7

DO - 10.1007/s00453-021-00915-7

M3 - Journal article

SN - 0178-4617

VL - 84

JO - Algorithmica

JF - Algorithmica

ER -

A #SAT Algorithm for Small Constant-Depth Circuits with PTF gates.

Abstract

Keywords

Access to Document

Fingerprint

Cite this