Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Shahar Samocha:

TR20-161 | 5th November 2020
Gil Cohen, Dean Doron, Shahar Samocha

Seed Protecting Extractors

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

TR20-014 | 16th February 2020
Gil Cohen, Shahar Samocha

Palette-Alternating Tree Codes

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

TR19-147 | 31st October 2019
Gil Cohen, Shahar Samocha

Capacity-Approaching Deterministic Interactive Coding Schemes Against Adversarial Errors

Revisions: 2 , Comments: 1

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

ISSN 1433-8092 | Imprint