Lower bounds on same-set inner product in correlated spaces
Let Ρ be a probability distribution over a finite alphabet Ωℓ with all ℓ marginals equal. Let X(1), . . . , X(ℓ), X(j) = (X(j)1 , . . . , X(j)n ) be random vectors such that for every coordinate i ϵ [n] the tuples (X(i)1 , . . . , X(ℓ)i ) are i.i.d. according to Ρ. The question we address is: does t...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
2022
|
| Online Access: | https://hdl.handle.net/1721.1/145808 |
| _version_ | 1826207376273833984 |
|---|---|
| author | Hazła, J Holenstein, T Mossel, E |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Hazła, J Holenstein, T Mossel, E |
| author_sort | Hazła, J |
| collection | MIT |
| description | Let Ρ be a probability distribution over a finite alphabet Ωℓ with all ℓ marginals equal. Let X(1), . . . , X(ℓ), X(j) = (X(j)1 , . . . , X(j)n ) be random vectors such that for every coordinate i ϵ [n] the tuples (X(i)1 , . . . , X(ℓ)i ) are i.i.d. according to Ρ. The question we address is: does there exist a function cΡ() independent of n such that for every f :Ωn → [0, 1] with E[f(X(1))] = μ > 0: E Φ Yj=1 f(X(j)) # ≥ cΡ(μ) > 0 ? We settle the question for ℓ = 2 and when ℓ > 2 and P has bounded correlation ρ(P) < 1. |
| first_indexed | 2024-09-23T13:48:40Z |
| format | Article |
| id | mit-1721.1/145808 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T13:48:40Z |
| publishDate | 2022 |
| record_format | dspace |
| spelling | mit-1721.1/1458082022-10-13T03:20:19Z Lower bounds on same-set inner product in correlated spaces Hazła, J Holenstein, T Mossel, E Massachusetts Institute of Technology. Department of Mathematics Let Ρ be a probability distribution over a finite alphabet Ωℓ with all ℓ marginals equal. Let X(1), . . . , X(ℓ), X(j) = (X(j)1 , . . . , X(j)n ) be random vectors such that for every coordinate i ϵ [n] the tuples (X(i)1 , . . . , X(ℓ)i ) are i.i.d. according to Ρ. The question we address is: does there exist a function cΡ() independent of n such that for every f :Ωn → [0, 1] with E[f(X(1))] = μ > 0: E Φ Yj=1 f(X(j)) # ≥ cΡ(μ) > 0 ? We settle the question for ℓ = 2 and when ℓ > 2 and P has bounded correlation ρ(P) < 1. 2022-10-12T18:30:07Z 2022-10-12T18:30:07Z 2016-09-01 2022-10-12T18:05:34Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/145808 Lower Bounds on Same-Set Inner Product in Correlated Spaces. 19th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2016 and the 20th International Workshop on Randomization and Computation, RANDOM 2016, September 7, 2016 - September 9, 2016. 2016. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. en 10.4230/LIPIcs.APPROX-RANDOM.2016.34 Leibniz International Proceedings in Informatics, LIPIcs Creative Commons Attribution 4.0 International license https://creativecommons.org/licenses/by/4.0/ application/pdf DROPS |
| spellingShingle | Hazła, J Holenstein, T Mossel, E Lower bounds on same-set inner product in correlated spaces |
| title | Lower bounds on same-set inner product in correlated spaces |
| title_full | Lower bounds on same-set inner product in correlated spaces |
| title_fullStr | Lower bounds on same-set inner product in correlated spaces |
| title_full_unstemmed | Lower bounds on same-set inner product in correlated spaces |
| title_short | Lower bounds on same-set inner product in correlated spaces |
| title_sort | lower bounds on same set inner product in correlated spaces |
| url | https://hdl.handle.net/1721.1/145808 |
| work_keys_str_mv | AT hazłaj lowerboundsonsamesetinnerproductincorrelatedspaces AT holensteint lowerboundsonsamesetinnerproductincorrelatedspaces AT mossele lowerboundsonsamesetinnerproductincorrelatedspaces |