Frank Stephan

activity

20242026

collaborators

7 papers

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.CC2026

Strictly Unfriendly $k$ -Partitions: Sharp Degree Thresholds and ETH-Based Lower Bounds

Sanjay Jain, Frank Stephan, Haoyun Tang

We present a complete complexity classification and fine-grained analysis for the Strictly Unfriendly $k$ -Partition problem ( $SU k P$ ), which asks whether the vertices…

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…

math.NT2025

Strong $n$ -conjectures over rings of integers

Rupert Hölzl, Sören Kleine, Frank Stephan

We study diophantine equations of the form $a_{1} + \dots + a_{n} = 0$ where the $a_{i}$ 's are assumed to be coprime and to satisfy certain subsum conditions. We are interested in the…

math.NT2024

Improved lower bounds for strong $n$ -conjectures

Rupert Hölzl, Sören Kleine, Frank Stephan

The well-known $ab c$ -conjecture concerns triples $(a, b, c)$ of non-zero integers that are coprime and satisfy $a + b + c = 0$ . The strong $n$ -conjecture is a generalisation to $n$ summa…

math.LO2024

Independence and Induction in Reverse Mathematics

David Belanger, Chi Tat Chong, Rupert Hölzl +1

We continue the project of the study of reverse mathematics principles inspired by cardinal invariants. In this article in particular we focus on principles encapsulating the exist…

math.LO2024

Randomness versus superspeedability

Rupert Hölzl, Philip Janicki, Wolfgang Merkle +1

Speedable numbers are real numbers which are algorithmically approximable from below and whose approximations can be accelerated nonuniformly. We begin this article by answering a…

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

Strictly Unfriendly k-Partitions: Sharp Degree Thresholds and ETH-Based Lower Bounds