Zobrazeno 1 - 10
of 102
pro vyhledávání: '"Joe Neeman"'
Publikováno v:
Probability Theory and Related Fields.
The analysis of large simple graphs with extreme values of the densities of edges and triangles has been extended to the statistical structure of typical graphs of fixed intermediate densities, by the use of large deviations of Erdoes-Renyi graphs. W
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::86a35790289b3631501e47f4bf0562ac
https://doi.org/10.1007/s00440-023-01187-8
https://doi.org/10.1007/s00440-023-01187-8
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_________::50431a44694c7cdbebfa8b1ba56cc4c4
https://doi.org/10.1137/1.9781611977554.ch48
https://doi.org/10.1137/1.9781611977554.ch48
Publikováno v:
Journal of Statistical Physics. 181:305-328
We analyze ensembles of random networks with fixed numbers of edges, triangles, and nodes. In the limit as the number of nodes goes to infinity, this model is known to exhibit sharp phase transitions as the density of edges and triangles is varied. I
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::96d41587695d0d36ab26dd743fd17cec
https://doi.org/10.1007/s10955-020-02582-4
https://doi.org/10.1007/s10955-020-02582-4
Publikováno v:
Theory of Computing. 15:1-47
Questions of noise stability play an important role in hardness of approximation in computer science as well as in the theory of voting. In many applications, the goal is to find an optimizer of noise stability among all possible partitions of Rn for
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::3cdee2b68ce4cdcbaa1ba7565254fcc5
https://doi.org/10.4086/toc.2019.v015a006
https://doi.org/10.4086/toc.2019.v015a006
Publikováno v:
STOC
A natural problem in high-dimensional inference is to decide if a classifier f:ℝn → {−1,1} depends on a small number of linear directions of its input data. Call a function g: ℝn → {−1,1}, a linear k-junta if it is completely determined b
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::280afcd6306ede5c0dc797fb57503b68
https://doi.org/10.1145/3406325.3451115
https://doi.org/10.1145/3406325.3451115
We prove moderate deviations bounds for the lower tail of the number of odd cycles in a $\calG(n, m)$ random graph. We show that the probability of decreasing triangle density by $t^3$, is $\exp(-\Theta(n^2 t^2))$ whenever $n^{-3/4} \ll t^3 \ll 1$, w
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::6b935b0b6fe39545cea90b8e0da370cf
Autor:
Joe Neeman, Grigoris Paouris
Publikováno v:
Lecture Notes in Mathematics ISBN: 9783030467616
We prove Ehrhard’s inequality using interpolation along the Ornstein–Uhlenbeck semi-group. We also provide an improved Jensen inequality for Gaussian variables that might be of independent interest.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::073a3f0a2d9942729d6599c9779db10a
https://doi.org/10.1007/978-3-030-46762-3_12
https://doi.org/10.1007/978-3-030-46762-3_12
Publikováno v:
arXiv
FOCS
FOCS
The problem of tolerant junta testing is a natural and challenging problem which asks if the property of a function having some specified correlation with a $k$-Junta is testable. In this paper we give an affirmative answer to this question: We show
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::16bc7f4aa95499fe49bd71cf30d47656
http://arxiv.org/abs/1904.04216
http://arxiv.org/abs/1904.04216
Publikováno v:
Israel Journal of Mathematics. 213:33-53
The Standard Simplex Conjecture and the Plurality is Stablest Conjecture are two conjectures stating that certain partitions are optimal with respect to Gaussian and discrete noise stability respectively. These two conjectures are natural generalizat
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::22381f713339b05941d8f7366a17a234
https://doi.org/10.1007/s11856-016-1320-y
https://doi.org/10.1007/s11856-016-1320-y
Publikováno v:
Theory of Computing. 12:1-50
The Majority is Stablest Theorem has numerous applications in hardness of approximation and social choice theory. We give a new proof of the Majority is Stablest Theorem by induction on the dimension of the discrete cube. Unlike the previous proof, i
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::383f9850f90d51c3db06a4ea216d82cb
https://doi.org/10.4086/toc.2016.v012a004
https://doi.org/10.4086/toc.2016.v012a004