En av de framträdande aktuella utmaningarna i komplexitetsteori är försöket att bevisa lägre gränser för T C 0, klass av konstant djup, polynom storlek kretsar med majoritet grindar. På grundval av resultaten av Williams (2013), ett tilltalande tillvägagångssätt för att bevisa sådana lägre gränser är att konstruera en icke-trivial derandomization algoritm för T C 0. I detta arbete tar vi ett första steg mot det senare målet, genom att bevisa de första positiva resultaten när det gäller derandomisering av T C 0 kretsar av djup d > 2. Vårt första huvudresultat är en kvantifierad derandomiseringsalgoritm för TC 0-kretsar med ett superlinjärt antal trådar. Specifikt konstruerar vi en algoritm som får som ingång en T C 0 krets C över n ingångsbitar med djup d och n 1+exp(-d ) ledningar, körs i nästan polynom-tid, och skiljer mellan fallet att C avvisar högst 2 n 1−1/5d ingångar och fallet som C accepterar högst 2 n 1−1/5d ingångar. I själva verket fungerar vår algoritm även när kretsen C är en linjär tröskelkrets, snarare än bara en TC 0-krets (dvs. C är en krets med linjära tröskelportar, som är starkare än majoritetsportar). Vårt andra huvudsakliga resultat är att även en blygsam förbättring av vår kvantifierade derandomization algoritm skulle ge en icke-trivial algoritm för standard derandomization av alla T C 0, och skulle följaktligen innebära att N EXP T C 0. Specifikt, om det finns en kvantifierad derandomiseringsalgoritm som får som ingång en T C 0 krets med djup d och n 1 + O (1/d ) ledningar (snarare än n 1 + exp (-d ) ledningar), körs i tid som mest 2 n exp (-d ), och skiljer mellan fallet att C avvisar högst 2 n 1‐1/5d ingångar och fallet att C accepterar högst 2 n 1‐1/5d ingångar, då det finns en algoritm med körtid 2 n 1‐1. (1) för standard derandomization av T C 0.
Tell REF konstruerad en kvantifierad derandomiseringsalgoritm för TC-kretsar med djup d och n
Quantified derandomization of linear threshold circuits
{'venue': 'STOC 2018', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}