All reports by Author Vojtech Rodl:

__
TR19-181
| 9th December 2019
__

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

Revisions: 1

__
TR19-058
| 16th April 2019
__

Pavel Pudlak, Vojtech Rodl#### Extractors for small zero-fixing sources

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

Pavel Pudlak, Vojtech Rodl

A random variable $X$ is an $(n,k)$-zero-fixing source if for some subset $V\subseteq[n]$, $X$ is the uniform distribution on the strings $\{0,1\}^n$ that are zero on every coordinate outside of $V$. An $\epsilon$-extractor for $(n,k)$-zero-fixing sources is a mapping $F:\{0,1\}^n\to\{0,1\}^m$, for some $m$, such that $F(X)$ is $\epsilon$-close in statistical ... more >>>