2026-07-27T17:10:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6657 2024-03-06T10:38:36Z ddc:004 open_access

Lower Bounds on Same-Set Inner Product in Correlated Spaces Hazla, Jan Holenstein, Thomas Mossel, Elchanan same set hitting product spaces correlation lower bounds Let P be a probability distribution over a finite alphabet Omega^L with all L marginals equal. Let X^(1), ..., X^(L), where X^(j) = (X_1^(j), ..., X_n^(j)) be random vectors such that for every coordinate i in [n] the tuples (X_i^(1), ..., X_i^(L)) are i.i.d. according to P. The question we address is: does there exist a function c_P independent of n such that for every f: Omega^n -> [0, 1] with E[f(X^(1))] = m > 0 we have E[f(X^(1)) * ... * f(X^(n))] > c_P(m) > 0? We settle the question for L=2 and when L>2 and P has bounded correlation smaller than 1. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jan Hazla and Thomas Holenstein and Elchanan Mossel 2016 Is Part Of LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2016.34 urn:nbn:de:0030-drops-66571 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.34 eng https://creativecommons.org/licenses/by/3.0/legalcode