All reports by Author Navid Talebanfard:

__
TR20-011
| 9th February 2020
__

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

__
TR19-181
| 9th December 2019
__

Michal Koucky, Vojtech Rodl, Navid Talebanfard#### A Separator Theorem for Hypergraphs and a CSP-SAT Algorithm

Revisions: 1

__
TR18-170
| 4th October 2018
__

Nicola Galesi, Navid Talebanfard, Jacobo Toran#### Cops-Robber games and the resolution of Tseitin formulas

__
TR17-191
| 15th December 2017
__

Alexander Smal, Navid Talebanfard#### Prediction from Partial Information and Hindsight, an Alternative Proof

Revisions: 2

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

Michal Koucky, Vojtech Rodl, Navid Talebanfard

We show that for every $r \ge 2$ there exists $\epsilon_r > 0$ such that any $r$-uniform hypergraph on $m$ edges with bounded vertex degree has a set of at most $(\frac{1}{2} - \epsilon_r)m$ edges the removal of which breaks the hypergraph into connected components with at most $m/2$ edges. ... more >>>

Nicola Galesi, Navid Talebanfard, Jacobo Toran

We characterize several complexity measures for the resolution of Tseitin formulas in terms of a two person cop-robber game. Our game is a slight variation of the one Seymour and Thomas used in order to characterize the tree-width parameter. For any undirected graph, by counting the number of cops needed ... more >>>

Alexander Smal, Navid Talebanfard

Let $X$ be a random variable distributed over $n$-bit strings with $H(X) \ge n - k$, where $k \ll n$. Using subadditivity we know that a random coordinate looks random. Meir and Wigderson [TR17-149] showed a random coordinate looks random to an adversary who is allowed to query around $n/k$ ... more >>>