Lance Fortnow, Rahul Santhanam, Ryan Williams, 2009 24th Annual IEEE Conference on Computational Complexity, 2009, 19
Lijie Chen, “Nondeterministic Quasi-Polynomial Time is Average-Case Hard for \(\textsf{ACC}\) Circuits”, SIAM J. Comput., 2024, FOCS19-332
R. Paturi, P. Pudlák, “Circuit lower bounds and linear codes”, J Math Sci, 134, no. 5, 2006, 2425
Jan Krajíček, “Substitutions into propositional tautologies”, Information Processing Letters, 101, no. 4, 2007, 163
Ryan Williams, 2014 IEEE 29th Conference on Computational Complexity (CCC), 2014, 248
Zhiyuan Fan, Jiatu Li, Tianqi Yang, Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, 2022, 962
M. Alekhnovich, A.A. Razborov, Proceedings 42nd IEEE Symposium on Foundations of Computer Science, 2001, 190
Eric Allender, 77, 2009, 117
Jan Krajíček, “Tautologies from Pseudo-Random Generators”, Bull. symb. log., 7, no. 2, 2001, 197
Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, Detlef Ronneburger, “Power from Random Strings”, SIAM J. Comput., 35, no. 6, 2006, 1467