Zobrazeno 1 - 10
of 75
pro vyhledávání: '"Amnon Ta-Shma"'
Publikováno v:
Proceedings of the 55th Annual ACM Symposium on Theory of Computing.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::a44d9f0c3937da8d0a4f7c6b09b34e1e
https://doi.org/10.1145/3564246.3585181
https://doi.org/10.1145/3564246.3585181
Autor:
Nir Aviv, Amnon Ta-Shma
Publikováno v:
ACM Transactions on Computation Theory. 11:1-14
Many algorithms are proven to work under the assumption that they have access to a source of random, uniformly distributed bits. However, in practice, sources of randomness are often imperfect, giving n random bits that have only k < n min-entropy. T
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::392da1dc37d4139de63512638a60abaf
https://doi.org/10.1145/3317691
https://doi.org/10.1145/3317691
Publikováno v:
STOC
In this work we ask the following basic question: assume the vertices of an expander graph are labelled by 0,1. What “test” functions f : { 0,1}t → {0,1} cannot distinguish t independent samples from those obtained by a random walk? The expande
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::8a93c041755b23b4843d022b531b01fe
https://doi.org/10.1145/3406325.3451049
https://doi.org/10.1145/3406325.3451049
The problem of constructing hitting-set generators for polynomials of low degree is fundamental in complexity theory and has numerous well-known applications. We study the following question, which is a relaxation of this problem: Is it easier to con
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::ebd250091fc067b91812aeb9698aa64a
Publikováno v:
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms
We strengthen the notion of "double samplers", first introduced by Dinur and Kaufman [Proc. 58th FOCS, 2017], which are samplers with additional combinatorial properties, and whose existence we prove using high dimensional expanders. The ABNNR code c
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::ddefbcc9758c3de518ce5d3f43a13e5d
https://doi.org/10.1137/1.9781611975482.129
https://doi.org/10.1137/1.9781611975482.129
Publikováno v:
computational complexity. 26:393-420
We show that approximating the second eigenvalue of stochastic operators is BPL-complete, thus giving a natural problem complete for this class. We also show that approximating any eigenvalue of a stochastic and Hermitian operator with constant accur
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::2d39c7d33ba4e53a90cc7fcc3b3e1566
https://doi.org/10.1007/s00037-016-0150-y
https://doi.org/10.1007/s00037-016-0150-y
Autor:
Dean Doron, Amnon Ta-Shma
Publikováno v:
Information Processing Letters. 115:750-753
Revisiting the problem of de-randomizing approximate counting.We study approximation problems in the space-bounded model motivated by quantum algorithms for linear algebraic problems.Deterministic logspace approximation schemes under de-randomization
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::7fc11a88110f8633f16088763607a60f
https://doi.org/10.1016/j.ipl.2015.03.005
https://doi.org/10.1016/j.ipl.2015.03.005
Autor:
Amnon Ta-Shma
Publikováno v:
STOC
The question of finding an epsilon-biased set with close to optimal support size, or, equivalently, finding an explicit binary code with distance 1-ϵ/2 and rate close to the Gilbert-Varshamov bound, attracted a lot of attention in recent decades. In
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::274200e4da217186a7072515dc8830b4
https://doi.org/10.1145/3055399.3055408
https://doi.org/10.1145/3055399.3055408
Autor:
Amnon Ta-Shma, Uri Zwick
Publikováno v:
Scopus-Elsevier
We obtain several improved solutions for the deterministic rendezvous problem in general undirected graphs. Our solutions answer several problems left open by Dessmark et al. We also introduce an interesting variant of the rendezvous problem, which w
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::893f64a70ff2bd6695940903a3e797c3
https://doi.org/10.1145/2601068
https://doi.org/10.1145/2601068
Publikováno v:
STOC
The breakthrough result of Chattopadhyay and Zuckerman (2016) gives a reduction from the construction of explicit two-source extractors to the construction of explicit non-malleable extractors. However, even assuming the existence of optimal explicit
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::92f0d479d4a6d8919891b794c8aae26a
https://doi.org/10.1137/17m1133245
https://doi.org/10.1137/17m1133245