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
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 13 נוב׳ 2017
אירוע58th IEEE Annual Symposium on Foundations of Computer Science (FOCS) - United States, CA, Berkeley, Berkeley, ארצות הברית
משך הזמן: 15 אוק׳ 201717 אוק׳ 2017

סדרות פרסומים

שםAnnual IEEE Symposium on Foundations of Computer Science

כנס

כנס58th IEEE Annual Symposium on Foundations of Computer Science (FOCS)
מדינה/אזורארצות הברית
עירBerkeley
תקופה15/10/1717/10/17

ASJC Scopus subject areas

  • ???subjectarea.asjc.1700.1700???

פורמט ציטוט ביבליוגרפי