Vi studerar problemet med att få fram effektiva, deterministiska, svart-box polynomiska identitetstestningsalgoritmer (PIT) för algebraiska grenningsprogram (ABPs) som är läskunniga och omedvetna. Denna klass har en effektiv, deterministisk, vit-box polynom identitetstestande algoritm (på grund av Raz och Shpilka [RS05], men innan detta arbete fanns det ingen känd sådan svart-box algoritm. Huvudresultatet av detta arbete ger de första kvasi-polynom storlek slaguppsättningar för storlek S kretsar från denna klass, när ordningen av variablerna är känd. Eftersom vår träffuppsättning är av storlek exp(lg 2 S), är detta (i terminologin av boolesk pseudorandomness) analogt med en frölängd av lg 2 S, som är frölängden av pseudorandom generatorer av Nisan [Nis92] och Impagliazzo-Nisan-Wigderson [INW94] för read-once omedvetna boolean grenningsprogram. Således kan vårt arbete ses som en algebraisk analog av dessa grundläggande resultat i boolesk pseudorandomness. Våra resultat är starkare för grenning program med begränsad bredd, där vi ger en träff uppsättning av storlek exp(LG 2 S/ lg lg S), vilket motsvarar en frölängd på lg 2 S/ lg lg S. Detta är i skarp kontrast till de kända resultaten för read-once olivious boolean grenning program av avgränsad bredd, där ingen pseudorandom generator (eller slå uppsättning) med utsädeslängd o(LG 2 S) är känd. Medan vårt arbete på något sätt är en algebraisk analog till befintliga booleska resultat, verkar de två regimerna ha icke-triviala skillnader. I uppföljningsarbetet ([FS13]) stärkte vi ett resultat av Mulmuley [Mul12a], och visade att avrandomisering av ett särskilt fall av Noether Normalization Lemma är reducible till blackbox PIT av read-once glömska ABPs. Med hjälp av resultaten av det nuvarande arbetet ger detta en derandomisering av Noether Normalization i det fallet, vilket Mulmuley förmodade skulle vara svårt på grund av sina relationer till problem i algebraisk geometri. Vi visar också att flera andra kretsklasser kan vara svart-box reduceras till read-once glömska ABPs, inklusive set-multilinear ABPs (en generalisering av djup-3 set-multilinear formler), non-commutative ABPs (generaliserande icke-kommutativa formler), och (semi-)diagonal djup-4 kretsar (som infördes av saxena [Sax08]). För set-multilinear ABPs och non-commutative ABPs, ger vi kvasi-polynomial-time black-box PIT algoritmer, där det senare fallet innebär utvärderingar över algebra av (D + 1) × (D + 1) matriser, där D är djupet av ABP. För (semi-)diagonala djup-4 kretsar, får vi en svart-box PIT algoritm (över någon egenskap) vars körtid är kvasi-polynomial i körtiden för Saxenas white-box algoritm, som matchar det samtidiga arbetet av Agrawal, Saha, och Saxena [ASS12]. Slutligen, genom att kombinera våra resultat med rekonstruktionsalgoritmen för Klivans och Shpilka [KS06], får vi deterministiska rekonstruktionsalgoritmer för ovanstående kretsklasser. - Vad är det för fel på dig?
Forbes och Shpilka REF var de första att överväga svart-box version av detta problem, och de fick en träff uppsättning av storlek (nwd ) O (log n), för n-variat, grad-d, och bredd-w ROABPs, om den ordning i vilken variablerna läses är känd i förväg.
Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs
{'venue': '54rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013,', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}