High Dimensional Expanders Imply Agreement Expanders

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمر

ملخص

We show that high dimensional expanders imply derandomized direct product tests, with a number of subsets that is linear in the size of the universe. Direct product tests belong to a family of tests called agreement tests that are important components in PCP constructions and include, for example, low degree tests such as line vs. line and plane vs. plane. For a generic hypergraph, we introduce the notion of agreement expansion, which captures the usefulness of the hypergraph for an agreement test. We show that explicit bounded degree agreement expanders exist, based on Ramanujan complexes.
اللغة الأصليةالإنجليزيّة
عنوان منشور المضيف2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)
ناشرIEEE Computer Society
الصفحات974-985
عدد الصفحات12
رقم المعيار الدولي للكتب (الإلكتروني)9781538634646
رقم المعيار الدولي للكتب (المطبوع)1538634643
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 13 نوفمبر 2017
الحدث58th IEEE Annual Symposium on Foundations of Computer Science (FOCS) - United States, CA, Berkeley, Berkeley, الولايات المتّحدة
المدة: ١٥ أكتوبر ٢٠١٧١٧ أكتوبر ٢٠١٧

سلسلة المنشورات

الاسمAnnual IEEE Symposium on Foundations of Computer Science

!!Conference

!!Conference58th IEEE Annual Symposium on Foundations of Computer Science (FOCS)
الدولة/الإقليمالولايات المتّحدة
المدينةBerkeley
المدة١٥/١٠/١٧١٧/١٠/١٧

All Science Journal Classification (ASJC) codes

  • !!General Computer Science

قم بذكر هذا