Zobrazeno 1 - 10
of 27
pro vyhledávání: '"DORON, DEAN"'
Autor:
Doron, Dean, Ribeiro, João
(abstract shortened due to space constraints) Existing constructions of seeded extractors with short seed length and large output length run in time $\Omega(n \log(1/\varepsilon))$ and often slower, where $n$ is the input source length and $\varepsil
Externí odkaz:
http://arxiv.org/abs/2411.07473
The Gilbert--Varshamov (GV) bound is a classical existential result in coding theory. It implies that a random linear binary code of rate $\epsilon^2$ has relative distance at least $\frac{1}{2} - O(\epsilon)$ with high probability. However, it is a
Externí odkaz:
http://arxiv.org/abs/2405.08584
Autor:
Doron, Dean, Venkitesh, S.
We prove that Reed-Solomon (RS) codes with random evaluation points are list recoverable up to capacity with optimal output list size, for any input list size. Namely, given an input list size $\ell$, a designated rate $R$, and any $\varepsilon > 0$,
Externí odkaz:
http://arxiv.org/abs/2404.00206
We give a deterministic, nearly logarithmic-space algorithm for mild spectral sparsification of undirected graphs. Given a weighted, undirected graph $G$ on $n$ vertices described by a binary string of length $N$, an integer $k\leq \log n$, and an er
Externí odkaz:
http://arxiv.org/abs/2002.11237
Autor:
DORON, DEAN1 deand@bgu.ac.il, MOSHKOVITZ, DANA2 diz@utexas.edu, OH, JUSTIN2, ZUCKERMAN, DAVID2
Publikováno v:
Journal of the ACM. Nov2022, Vol. 69 Issue 6, p1-55. 55p.
Autor:
Doron, Dean, Tell, Roei
Existing proofs that deduce BPL = 𝐋 from circuit lower bounds convert randomized algorithms into deterministic algorithms with large constant overhead in space. We study space-bounded derandomization with minimal footprint, and ask what is the min
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::ba2b37c90c4e9d4fd3202834356578d6
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Autor:
Doron, Dean, Wootters, Mary
An error correcting code 𝒞 : Σ^k → Σⁿ is efficiently list-recoverable from input list size 𝓁 if for any sets ℒ₁, …, ℒ_n ⊆ Σ of size at most 𝓁, one can efficiently recover the list ℒ = {x ∈ Σ^k : ∀ j ∈ [n], 𝒞(x)_j
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::0793e267c4aa3407388707e092cfef81
Autor:
Blanc, Guy, Doron, Dean
We construct a family of binary codes of relative distance 1/2-ε and rate ε² ⋅ 2^(-log^α (1/ε)) for α ≈ 1/2 that are decodable, probabilistically, in near-linear time. This improves upon the rate of the state-of-the-art near-linear time dec
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::c09e155be8ccc89cbd2945151db76099
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.