الحد الأعلى لمجموعة غير واضحة ضمن توزيع المنتجات

Question

بالنسبة لمشكلة غير واضحة في نموذج تعقيد الاتصال 2، يتم إعطاء أليس إدخال $ x $ ويعمل بوب المدخلات $ y $ ، $ x $ و $ y $ هي < Span Class="حاوية الرياضيات"> $ n $ length bitstrings (عينات من بعض التوزيع)، والتي يتم تفسيرها على أنها فرعية من $ [n] $ ، IE، $ x_i= 1 $ يعني $ i $ $ -bit من $ X $ في المجموعة الفرعية. الهدف هو أليس وبوب للإجابة على ما إذا كانت المجموعات الفرعية الممثلة $ x $ و $ y $ $ \ Omega (n) $ bits ضرورية في أسوأ الحالات للبروتوكولات العشوائية.

جئت عبر مشروع الكتاب المدرسي تعقيد الاتصالات بواسطة anup rao و amir yehudayoff ، حيث التمرين 6.8 يذكر أن محطمة 2 أحزاب يمكن حلها مع المتوقع عدد من $ O (n ^ {2 / 3} \ Log ^ 2 n) $ بت إذا تم أخذ عينات مدخلات أليس وبوب بشكل مستقل.

النظر في البروتوكول التالي. إذا كان هناك تنسيق $ J \ in [n] $ مثل هذا $ h (x_j) $ و $ h (y_j) $ كلاهما على الأقل $ \ Epsilon $ ، ثم أليس وبوب التواصل $ x_j، y_j $ . أنها شرطية على القيم التي يرونها وتكرر هذه الخطوة حتى لا يمكن العثور على أي تنسيق مثل. في هذه المرحلة، استخدم أليس وبوب نظرية الترميز Shannon لتشفير $ x $ ، $ y $ . إظهار كيفية تعيين $ \ Epsilon $ يمكن أن يحدها الاتصالات المتوقعة بواسطة $ n ^ {2/3} \ Log ^ 2 N $ . تلميح: استخدم حقيقة أن $ h (x_j) \ ge \ epsilon $ يعني أن $ pr [x_j= 1] \ GE \ Omega (\ Epsilon / (\ Log (1 / ε))) $ .

أفترض أن الفكرة هي أولا توصيل جميع المؤشرات حيث $ x $ و $ y $ لديك انتروبا كبيرا ثم استخدم حقيقة أن المؤشرات المتبقية يجب أن يكون لديك انتروبيا صغيرا. ومع ذلك، فإن تفاصيل البروتوكول وحيث استقلال $ X $ و $ Y $ قادم ، ليست واضحة بالنسبة لي.

Answer 1

خلال المرحلة الأولى من الخوارزمية، يقوم اللاعبون بتكبير التنسيق العالي الانتروبيا. يتبادلون $ o (1) $ bits، وتوقف عند كل خطوة مع احتمال $ \ أوميغا (\ epsilon ^ 2 / \ سجل ^ 2 (1 / \ epsilon)) $ (هنا نستخدم الاستقلال). وبالتالي، تستخدم هذه المرحلة على الأكثر $ o (\ log ^ 2 (1 / \ epsilon) / \ epsilon ^ 2) $ bits في التوقع. تستخدم المرحلة الثانية $ O (n \ epsilon) $ بت. في المجموع، استخدمنا هذه البتات في التوقعات: $$ o (\ log ^ 2 (1 / \ epsilon) / \ epsilon ^ 2 + \ epsilon n). $ اختر $ \ Epsilon= 1 / n ^ {1/3} $ للحصول على ملزمة المعلنة.

بدون استقلال، ليس لدينا أي سيطرة على احتمال وقف التوقف في كل خطوة من المرحلة الأولى. على سبيل المثال، يمكن أن يكون ذلك $ x $ يتم أخذ عينات منها بشكل موحد عشوائيا، و $ y $ هو نفي $ x $ . في هذه الحالة، لن تتوقف المرحلة الأولى أبدا، وبالتالي فإن البروتوكول سيؤدي دائما إلى استخدام $ 2n $ bits.

جانبا، يمكن تحسين الحد الأعلى إلى تحسين $ O (\ sqrt {n} \ log n) $ ، مما يطابق تقريبا الحد الأدنى السفلي $ \ Omega (\ sqrt {n}) $ (ربما تم إغلاق الفجوة في الأدب). انظر محاضرة ملاحظات براهلظ هارشة < / a>.