Junqiang Peng

activity

20212026

most citedFurther Improvements for SAT in Terms of Formula Length

1 citations · 1 across the 6 of their papers we have counts for

collaborators

Showing 2026 · cs.DSShow all

3 papers · 2 filters

cs.DS2026

Solving Restricted Versions of #SAT Faster than $2^{m}$ : Algorithms and Lower Bounds

Sanjay Jain, Junqiang Peng, Frank Stephan +1

Under the Strong Exponential Time Hypothesis (SETH), for any constant $ε > 0$ , the #SAT problem (counting the number of satisfying assignments of a CNF formula) cannot be…

cs.DS2026

New Algorithms for Parity-SAT and Its Bounded-Occurrence Versions

Sanjay Jain, Junqiang Peng, Frank Stephan +2

Parity-SAT is the problem of determining whether a given CNF formula has an odd number of satisfying assignments. As a canonical $\oplus$ P-complete problem, it represents a fundame…

cs.DS2026

Faster Parameterized Vertex Multicut

Huairui Chu, Yuxi Liu, Daniel Lokshtanov +3

In the {\sc Vertex Multicut} problem the input consists of a graph $G$ , integer $k$ , and a set $T = {(s_{1}, t_{1}), \dots, (s_{p}, t_{p})}$ of pairs of vertices of $G$ . The ta…

Solving Restricted Versions of #SAT Faster than 2m: Algorithms and Lower Bounds

New Algorithms for Parity-SAT and Its Bounded-Occurrence Versions

Faster Parameterized Vertex Multicut

Solving Restricted Versions of #SAT Faster than $2^{m}$ : Algorithms and Lower Bounds