Zobrazeno 1 - 10
of 78
pro vyhledávání: '"Emanuele Viola"'
Autor:
Harm Derksen, Emanuele Viola
Publikováno v:
Discrete Analysis (2023)
Quasirandom groups enjoy interleaved mixing, Discrete Analysis 2023:14, 4 pp. In 1985 Babai and Sós asked whether there is a constant $c>0$ such that every group of order $n>1$ has a product-free subset of size at least $cn$, where this means a set
Externí odkaz:
https://doaj.org/article/fa999f52d4a045a39920531fcc53a607
Autor:
Xuangui Huang, Emanuele Viola
Publikováno v:
ACM Transactions on Computation Theory. 14:1-26
We prove that the OR function on {-1,1\} n can be pointwise approximated with error ε by a polynomial of degree O ( k ) and weight 2 O ( n log (1/ε)/k) , for any k ≥ √ n log (1/ε). This result is tight for any k ≤ (1-Ω (1)) n . Previous res
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::efd2029d2cf2afcc3eb19732b96a1940
https://doi.org/10.1145/3492338
https://doi.org/10.1145/3492338
Publikováno v:
Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) ISBN: 9781611977554
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::5ab4b6b0d67732b4aebd7dffec138255
https://doi.org/10.1137/1.9781611977554.ch108
https://doi.org/10.1137/1.9781611977554.ch108
Autor:
Harm Derksen, Emanuele Viola
Publikováno v:
2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS).
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::a1f5fe3558c7902c7022a1ef789aeb04
https://doi.org/10.1109/focs54457.2022.00045
https://doi.org/10.1109/focs54457.2022.00045
Autor:
Emanuele Viola
Publikováno v:
ACM Transactions on Computation Theory. 13:1-8
We prove that for every distribution D on n bits with Shannon entropy ≥ n − a , at most O (2 d a log d +1 g )/γ 5 of the bits D i can be predicted with advantage γ by an AC 0 circuit of size g and depth D that is a function of all of the bits o
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::c8000813f22fc86f7e0389a5b077c2f5
https://doi.org/10.1145/3442362
https://doi.org/10.1145/3442362
Autor:
Emanuele Viola
Publikováno v:
SIAM Journal on Computing. 49:119-137
We show that for every small AC$^{0}$ circuit $C:\{0,1\}^{\ell}\to\{0,1\}^{m}$ there exists a multiset $S$ of $2^{m-m^{\Omega(1)}}$ restrictions that preserve the output distribution of $C$ and, mo...
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::70023dc612087567cd7c78ad252c2720
https://doi.org/10.1137/18m1198405
https://doi.org/10.1137/18m1198405
Autor:
Emanuele Viola, Chin Ho Lee
Publikováno v:
Theory of Computing. 16:1-50
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::55730f271bcbfb2714493aaba98fbac3
https://doi.org/10.4086/toc.2020.v016a007
https://doi.org/10.4086/toc.2020.v016a007
Autor:
Emanuele Viola
Publikováno v:
ACM SIGACT News. 50:52-74
Finite groups provide an amazing wealth of problems of interest to complexity theory. And complexity theory also provides a useful viewpoint of group-theoretic notions, such as what it means for a group to be \far from abelian." The general problem t
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::a9a38c4a135291afcb6e71184d3d297a
https://doi.org/10.1145/3364626.3364637
https://doi.org/10.1145/3364626.3364637
Publikováno v:
ACM Transactions on Computation Theory. 11:1-27
For a test T ⊆ {0, 1} n , define k * ( T ) to be the maximum k such that there exists a k -wise uniform distribution over {0, 1} n whose support is a subset of T . For H t = { x ∈ {0, 1} n : | ∑ i x i − n /2| ≤ t }, we prove k * ( H t ) =
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::5bd935521f152624abb28cb1f9b9e28c
https://doi.org/10.1145/3337783
https://doi.org/10.1145/3337783
Autor:
Emanuele Viola
Publikováno v:
ACM Transactions on Computation Theory. 11:1-11
Research in the 1980s and 1990s showed how to construct a pseudorandom generator from a function that is hard to compute on more than 99% of the inputs. A more recent line of works showed, however, that if the generator has small error, then the proo
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::597363f34aa812162f1a58fbe7514ad9
https://doi.org/10.1145/3322815
https://doi.org/10.1145/3322815