Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Navid Talebanfard:

TR20-011 | 9th February 2020
Dominik Scheder, Navid Talebanfard

Super Strong ETH is true for strong PPSZ

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

TR19-181 | 9th December 2019
Michal Koucky, Vojtech Rodl, Navid Talebanfard

A Separator Theorem for Hypergraphs and a CSP-SAT Algorithm

Revisions: 1

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

TR18-170 | 4th October 2018
Nicola Galesi, Navid Talebanfard, Jacobo Toran

Cops-Robber games and the resolution of Tseitin formulas

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

TR17-191 | 15th December 2017
Alexander Smal, Navid Talebanfard

Prediction from Partial Information and Hindsight, an Alternative Proof

Revisions: 2

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

ISSN 1433-8092 | Imprint