All reports by Author Dominik Scheder:

__
TR21-069
| 12th May 2021
__

Dominik Scheder#### PPSZ is better than you think

Revisions: 1

__
TR20-011
| 9th February 2020
__

Dominik Scheder, Navid Talebanfard#### Super Strong ETH is true for strong PPSZ

__
TR18-179
| 31st October 2018
__

Dominik Scheder#### PPSZ on CSP Instances with Multiple Solutions

__
TR18-113
| 30th May 2018
__

Dominik Scheder#### PPSZ for $k \geq 5$: More Is Better

__
TR13-189
| 21st December 2013
__

Periklis Papakonstantinou, Dominik Scheder, Hao Song#### Overlays and Limited Memory Communication Mode(l)s

Dominik Scheder

PPSZ, for long time the fastest known algorithm for k-SAT, works by going through the variables of the input formula in random order; each variable is then set randomly to 0 or 1, unless the correct value can be inferred by an efficiently implementable rule (like small-width resolution; or being ... more >>>

Dominik Scheder, Navid Talebanfard

We construct $k$-CNFs with $m$ variables on which the strong version of PPSZ $k$-SAT algorithm, which uses bounded width resolution, has success probability at most $2^{-(1 - (1 + \epsilon)2/k)m}$ for every $\epsilon > 0$. Previously such a bound was known only for the weak PPSZ algorithm which exhaustively searches ... more >>>

Dominik Scheder

We study the success probability of the PPSZ algorithm on $(d,k)$-CSP formulas. We greatly simplify the analysis of Hertli, Hurbain, Millius, Moser, Szedlak, and myself for the notoriously difficult case that the input formula has more than one satisfying assignment.

more >>>Dominik Scheder

We show that for $k \geq 5$, the PPSZ algorithm for $k$-SAT runs exponentially faster if there is an exponential number of satisfying assignments. More precisely, we show that for every $k\geq 5$, there is a strictly increasing function $f: [0,1] \rightarrow \mathbb{R}$ with $f(0) = 0$ that has the ... more >>>

Periklis Papakonstantinou, Dominik Scheder, Hao Song

We give new characterizations and lower bounds relating classes in the communication complexity polynomial hierarchy and circuit complexity to limited memory communication models.

We introduce the notion of rectangle overlay complexity of a function $f: \{0,1\}^n\times \{0,1\}^n\to\{0,1\}$. This is a natural combinatorial complexity measure in terms of combinatorial rectangles in ... more >>>