All reports by Author Shahar Samocha:

__
TR20-161
| 5th November 2020
__

Gil Cohen, Dean Doron, Shahar Samocha#### Seed Protecting Extractors

__
TR20-014
| 16th February 2020
__

Gil Cohen, Shahar Samocha#### Palette-Alternating Tree Codes

__
TR19-147
| 31st October 2019
__

Gil Cohen, Shahar Samocha#### Capacity-Approaching Deterministic Interactive Coding Schemes Against Adversarial Errors

Revisions: 2
,
Comments: 1

Gil Cohen, Dean Doron, Shahar Samocha

We introduce a new type of seeded extractors we dub seed protecting extractors. Informally, a seeded extractor is seed protecting against a class of functions $C$, mappings seeds to seeds, if the seed $Y$ remains close to uniform even after observing the output $\mathrm{Ext}(X,A(Y))$ for every choice of $A \in ... more >>>

Gil Cohen, Shahar Samocha

A tree code is an edge-coloring of the complete infinite binary tree such that every two nodes of equal depth have a fraction--bounded away from $0$--of mismatched colors between the corresponding paths to their least common ancestor. Tree codes were introduced in a seminal work by Schulman (STOC 1993) and ... more >>>

Gil Cohen, Shahar Samocha

We devise a deterministic interactive coding scheme with rate $1-O(\sqrt{\varepsilon\log(1/\varepsilon)})$ against $\varepsilon$-fraction of adversarial errors. The rate we obtain is tight by a result of Kol and Raz (STOC 2013). Prior to this work, deterministic coding schemes for any constant fraction $\varepsilon>0$ of adversarial errors could obtain rate no larger ... more >>>