Exponential lower bounds for AC0-frege imply superpolynomial frege lower bounds

Yuval Filmus, Toniann Pitassi, Rahul Santhanam

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנסביקורת עמיתים

תקציר

We give a general transformation which turns polynomial-size Frege proofs to subexponential-size AC0-Frege proofs. This indicates that proving exponential lower bounds for AC0-Frege is hard, since it is a longstanding open problem to prove super-polynomial lower bounds for Frege. Our construction is optimal for tree-like proofs. As a consequence of our main result, we are able to shed some light on the question of weak automatizability for bounded-depth Frege systems. First, we present a simpler proof of the results of Bonet et al. [5] showing that under cryptographic assumptions, bounded-depth Frege proofs are not weakly automatizable. Secondly, we show that because our proof is more general, under the right cryptographic assumptions, it could resolve the weak automatizability question for lower depth Frege systems.

שפה מקוריתאנגלית
כותר פרסום המארחAutomata, Languages and Programming - 38th International Colloquium, ICALP 2011, Proceedings
עמודים618-629
מספר עמודים12
מהדורהPART 1
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2011
פורסם באופן חיצוניכן
אירוע38th International Colloquium on Automata, Languages and Programming, ICALP 2011 - Zurich, שוויץ
משך הזמן: 4 יולי 20118 יולי 2011

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

שםLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
מספרPART 1
כרך6755 LNCS

כנס

כנס38th International Colloquium on Automata, Languages and Programming, ICALP 2011
מדינה/אזורשוויץ
עירZurich
תקופה4/07/118/07/11

ASJC Scopus subject areas

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

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Exponential lower bounds for AC0-frege imply superpolynomial frege lower bounds'. יחד הם יוצרים טביעת אצבע ייחודית.

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