تعقيد الاتصالات لتوزيع المنتجات

Question

بشكل عام بالنسبة للمشكلة غير المشتركة (الطرفين) لمشكلة غير واضحة للمدخلات من الطول N، نحن نعلم أن الأطراف بحاجة إلى توصيل $ \ أوميغا (ن) $ وبعد من المستغرب، لقد اكتشفت اليوم (إذا فهمت بشكل صحيح) أن هذا غير صحيح لتوزيع المنتجات، أي عندما يتم اختيار مدخلات أليس وبوب بشكل مستقل عن التوزيعات التعسفية! في هذا ورقة ، على سبيل المثال، أنها توفر ملزمة أعلى مع تعقيد الاتصالات $ \ mathcal {o} (\ sqrt {n} \ log (1 / \ epsilon)) $ ، حيث $ \ epsilon $ هو بعض مصطلح الخطأ غير مناسب للسؤال هنا. الآن أنا فضولي حول ما إذا كانت الثغرات موجودة لمشاكل تعقيد الاتصالات المعروفة الأخرى.

سؤال: ما هي المشاكل الأخرى المعروفة تظهر فجوة بين تعقيدات الاتصالات عندما يعتبر المرء توزيعات المدخلات التعسفية وتوزيع المنتجات. هل هناك نتائج مماثلة للمنتجات الداخلية أو التقاطعات؟

Answer 1

set disfietness هو أسهل لتوزيع المنتجات نظرا لأن التوزيع الثابت لمجموعة غير واضحة بعيدة جدا عن كونه توزيع المنتج. ماذا نطلب من التوزيع الثابت $ (x، y) $ للمنتج الداخلي؟ نريد كل من $ x، $ $ بشكل منفصل ليكون عشوائيا تماما، ونحن نريد $ x \ cdot y $ أن تكون في الغالب صفر، قل $ x \ cdot y $ يحتوي على معظم $ 1 $ . لا يمكن تحقيق ذلك من خلال توزيع المنتجات. بينما يمكنك الحصول على $ x \ cdot y $ الخاصية، وهذا يعني أن كل من المدخلات سيكون متحيزا للغاية. على العكس، إذا كانت المدخلات $ x، $ $ هي عشوائية تماما، ثم $ x \ cdot y $ الإرادة لديك العديد من $ 1 $ s.

وظيفة المنتج الداخلي لا تعاني من نفس المشكلة. في الواقع، يبدو أن أصعب التوزيع هو التوزيع الموحد. يمكنك إثبات وجود خطط خطي باستخدام طريقة التناقض - وهذا هو المعيار، ويستخدم ملزمة على التناقض المعروف باسم Lindsey's Lemma .

ظهر Sherstov مثالا مثاليا للفجوة في ورقته تعقيد الاتصالات تحت توزيعات المنتج وغير المنتج . وظيفته هي وظيفة عشوائية، تم اختيارها بحيث لا يوجد عدد كبير أحادي اللون $ 1 $ -Rectangles. النتيجة النهائية هي وظيفة تعقيد الاتصالات العشوائية هي $ \ Omega (n) $ ، ولكن بالنسبة لأي توزيع منتجات، تعقيد الاتصالات العشوائية $ O (1) $ .