Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
A. A. Razborov

This publication is cited in the following articles:

1. Josh Alman, Jingxun Liang, Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025, 1383  
2. Lijie Chen, Ron D. Rothblum, Roei Tell, Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025, 977  
3. Yizhi Huang, Rahul Ilango, Hanlin Ren, “NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach”, SIAM J. Comput., 54:4 (2025), 819  
4. Yuyu Wang, Lecture Notes in Computer Science, 16004, Advances in Cryptology – CRYPTO 2025, 2025, 38  
5. I. S. Sergeev, “Nizhnie otsenki additivnoi slozhnosti lineinykh operatorov i bilineinykh algoritmov umnozheniya matrits i mnogochlenov nad $GF(2)$”, Matem. zametki, 118:4 (2025), 607–624    
6. Lijie Chen, “Nondeterministic Quasi-Polynomial Time is Average-Case Hard for \(\textsf{ACC}\) Circuits”, SIAM J. Comput., 2024, FOCS19-332  
7. Yilei Chen, Jiatu Li, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024, 620  
8. Shivam Nadimpalli, Natalie Parham, Francisca Vasconcelos, Henry Yuen, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024, 1498  
9. Yuyu Wang, Chuanjie Su, Jiaxin Pan, Lecture Notes in Computer Science, 14921, Advances in Cryptology – CRYPTO 2024, 2024, 251  
10. Ján Pich, “Localizability of the approximation method”, comput. complex., 33:2 (2024)  
11. Libor Caha, Xavier Coiteux-Roy, Robert Koenig, “Single-qubit gate teleportation provides a quantum advantage”, Quantum, 8 (2024), 1548  
12. Pooya Hatami, William M. Hoza, Avishay Tal, Roei Tell, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023, 895  
13. Ronen Shaltiel, “Is it possible to improve Yao's XOR lemma using reductions that exploit the efficiency of their oracle?”, comput. complex., 32:1 (2023)  
14. Yeyuan Chen, Yizhi Huang, Jiatu Li, Hanlin Ren, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023, 1058  
15. Rahul Ilango, 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), 2023, 733  
16. Yuyu Wang, Jiaxin Pan, Yu Chen, “Fine-Grained Secure Attribute-Based Encryption”, J Cryptol, 36:4 (2023)  
17. Uma Girish, Makrand Sinha, Avishay Tal, Kewen Wu, 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), 2023, 721  
18. Emmanuel Abbe, Colin Sandon, 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), 2023, 177  
19. Mika Göös, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov, 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), 2023, 1048  
20. Yizhi Huang, Rahul Ilango, Hanlin Ren, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023, 1067  
21. Lijie Chen, Ce Jin, Rahul Santhanam, R. Ryan Williams, 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), 2022, 646  
22. Mark Braverman, Sumegha Garg, Or Zamir, 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), 2022, 1068  
23. Yuyu Wang, Jiaxin Pan, Lecture Notes in Computer Science, 13276, Advances in Cryptology – EUROCRYPT 2022, 2022, 305  
24. Lijie Chen, Hanlin Ren, “Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization”, SIAM J. Comput., 51:3 (2022), STOC20-115  
25. Jiatu Li, Tianqi Yang, Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, 2022, 1180  
26. Benjamin Lovitz, Vincent Steffan, “New techniques for bounding stabilizer rank”, Quantum, 6 (2022), 692  
27. Shir Peleg, Amir Shpilka, Ben Lee Volk, “Lower Bounds on Stabilizer Rank”, Quantum, 6 (2022), 652  
28. Yuyu Wang, Jiaxin Pan, Yu Chen, Lecture Notes in Computer Science, 12828, Advances in Cryptology – CRYPTO 2021, 2021, 179  
29. Xuangui Huang, Emanuele Viola, Lecture Notes in Computer Science, 12730, Computer Science – Theory and Applications, 2021, 186  
30. Itai Dinur, Lecture Notes in Computer Science, 12696, Advances in Cryptology – EUROCRYPT 2021, 2021, 374  
31. Janio Carlos Nascimento Silva, Uéverton S. Souza, Luiz Satoru Ochi, Lecture Notes in Computer Science, 13153, Algorithmic Aspects in Information and Management, 2021, 380  
32. R. Ryan Williams, “From Circuit Complexity to Faster All-Pairs Shortest Paths”, SIAM Rev., 63:3 (2021), 559  
33. Pyung Kim, Eunji Jo, Younho Lee, “An Efficient Search Algorithm for Large Encrypted Data by Homomorphic Encryption”, Electronics, 10:4 (2021), 484  
34. Mark Bun, Robin Kothari, Justin Thaler, “Quantum algorithms and approximating polynomials for composed functions with shared inputs”, Quantum, 5 (2021), 543  
35. Timothy M. Chan, R. Ryan Williams, “Deterministic APSP, Orthogonal Vectors, and More”, ACM Trans. Algorithms, 17:1 (2021), 1  
36. Daniel Grier, Luke Schaeffer, Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020, 875  
37. Dmitry Sokolov, Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020, 78  
38. Olaf Beyersdorff, Ilario Bonacina, Leroy Chew, Jan Pich, “Frege Systems for Quantified Boolean Logic”, J. ACM, 67:2 (2020), 1  
39. Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan, Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science, 2020, 209  
40. Lijie Chen, Hanlin Ren, Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020, 1327  
41. Oded Goldreich, Guy N. Rothblum, Lecture Notes in Computer Science, 12050, Computational Complexity and Property Testing, 2020, 326  
42. Prerona Chatterjee, Mrinal Kumar, C Ramya, Ramprasad Saptharishi, Anamay Tengse, 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), 2020, 870  
43. Charlotte Bonte, Ilia Iliashenko, Proceedings of the 2020 ACM SIGSAC Conference on Cloud Computing Security Workshop, 2020, 105  
44. Nikhil Balaji, Andreas Krebs, Nutan Limaye, “Skew circuits of small width”, Theoretical Computer Science, 821 (2020), 111  
45. Lijie Chen, Xin Lyu, R. Ryan Williams, 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), 2020, 1  
46. Russell Impagliazzo, Sasank Mouli, Toniann Pitassi, Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science, 2020, 591  
47. Srikanth Srinivasan, Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020, 1349  
48. Roei Tell, “Improved Bounds for Quantified Derandomization of Constant-Depth Circuits and Polynomials”, comput. complex., 28:2 (2019), 259  
49. Prahladh Harsha, Srikanth Srinivasan, “On polynomial approximations to AC”, Random Struct Algorithms, 54:2 (2019), 289  
50. Adi Akavia, Craig Gentry, Shai Halevi, Max Leibovich, “Setup-Free Secure Search on Encrypted Data: Faster and Post-Processing Free”, Proceedings on Privacy Enhancing Technologies, 2019:3 (2019), 87  
51. Lijie Chen, Roei Tell, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019, 34  
52. Lijie Chen, 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), 2019, 1281  
53. Mrinal Kumar, Ramprasad Saptharishi, “The Computational Power of Depth Five Arithmetic Circuits”, SIAM J. Comput., 48:1 (2019), 144  
54. Marvin Künnemann, Daniel Moeller, Ramamohan Paturi, Stefan Schneider, “Subquadratic Algorithms for Succinct Stable Matching”, Algorithmica, 81:7 (2019), 2991  
55. G. V. Bokov, “Ot bulevykh skhem k dokazatelstvu teorem”, Intellektualnye sistemy. Teoriya i prilozheniya, 22:1 (2018), 123–130  
56. Joan Boyar, Magnus Gausdal Find, “Multiplicative complexity of vector valued Boolean functions”, Theoretical Computer Science, 720 (2018), 36  
57. Tim Roughgarden, Sergei Vassilvitskii, Joshua R. Wang, “Shuffles and Circuits (On Lower Bounds for Modern Parallel Computation)”, J. ACM, 65:6 (2018), 1  
58. Fu Li, Iddo Tzameret, Zhengyu Wang, “Characterizing Propositional Proofs as Noncommutative Formulas”, SIAM J. Comput., 47:4 (2018), 1424  
59. Akinori Kawachi, “Circuit lower bounds from learning-theoretic approaches”, Theoretical Computer Science, 733 (2018), 83  
60. Matteo Campanelli, Rosario Gennaro, Lecture Notes in Computer Science, 11240, Theory of Cryptography, 2018, 66  
61. Dan Boneh, Yuval Ishai, Alain Passelègue, Amit Sahai, David J. Wu, Lecture Notes in Computer Science, 11240, Theory of Cryptography, 2018, 699  
62. Alman J. Williams R., “Probabilistic Rank and Matrix Rigidity”, Stoc'17: Proceedings of the 49Th Annual Acm Sigact Symposium on Theory of Computing, Annual Acm Symposium on Theory of Computing, ed. Hatami H. McKenzie P. King V., Assoc Computing Machinery, 2017, 641–652    
63. Valentine Kabanets, Daniel M. Kane, Zhenjian Lu, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017, 615  
64. Gil Cohen, Amir Shpilka, Avishay Tal, “On the degree of univariate polynomials over the integers”, Combinatorica, 37:3 (2017), 419  
65. Michael A. Forbes, Amir Shpilka, Ben Lee Volk, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017, 653  
66. Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, Madars Virza, “Scalable Zero Knowledge Via Cycles of Elliptic Curves”, Algorithmica, 79:4 (2017), 1102  
67. Johan Håstad, Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan, “An Average-Case Depth Hierarchy Theorem for Boolean Circuits”, J. ACM, 64:5 (2017), 1  
68. Olaf Beyersdorff, Ilario Bonacina, Chew Leroy, Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016, 249  
69. Zachary Remscrim, 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), 2016, 197  
70. Daniel Moeller, Ramamohan Paturi, Stefan Schneider, Lecture Notes in Computer Science, 9691, Computer Science – Theory and Applications, 2016, 294  
71. Josh Alman, Timothy M. Chan, Ryan Williams, 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), 2016, 467  
72. Akshay Degwekar, Vinod Vaikuntanathan, Prashant Nalini Vasudevan, Lecture Notes in Computer Science, 9816, Advances in Cryptology – CRYPTO 2016, 2016, 533  
73. Emmanuel Abbe, Amir Shpilka, Avi Wigderson, Proceedings of the forty-seventh annual ACM symposium on Theory of Computing, 2015, 297  
74. Brendan Juba, Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015, 93  
75. Emmanuel Abbe, Amir Shpilka, Avi Wigderson, “Reed–Muller Codes for Random Erasures and Errors”, IEEE Trans. Inform. Theory, 61:10 (2015), 5229  
76. Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan, 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, 2015, 1030  
77. Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan, “Complexity Theory Column 89”, SIGACT News, 46:4 (2015), 50  
78. Joan Boyar, Magnus Gausdal Find, Lecture Notes in Computer Science, 9210, Fundamentals of Computation Theory, 2015, 106  
79. Joshua A. Grochow, “Unifying Known Lower Bounds via Geometric Complexity Theory”, comput. complex., 24:2 (2015), 393  
80. Chia-Jung Lee, Satyanarayana V. Lokam, Shi-Chun Tsai, Ming-Chuan Yang, 2015 IEEE International Symposium on Information Theory (ISIT), 2015, 501  
81. Josh Alman, Ryan Williams, 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, 2015, 136  
82. Ruiwen Chen, Valentine Kabanets, Antonina Kolokolova, Ronen Shaltiel, David Zuckerman, “Mining Circuit Lower Bound Proofs for Meta-Algorithms”, comput. complex., 24:2 (2015), 333  
83. Hervé Fournier, Nutan Limaye, Meena Mahajan, Srikanth Srinivasan, Lecture Notes in Computer Science, 9235, Mathematical Foundations of Computer Science 2015, 2015, 324  
84. Nikhil Balaji, Andreas Krebs, Nutan Limaye, Lecture Notes in Computer Science, 9198, Computing and Combinatorics, 2015, 199  
85. Andrew Drucker, Fabian Kuhn, Rotem Oshman, Proceedings of the 2014 ACM symposium on Principles of distributed computing, 2014, 367  
86. Akinori KAWACHI, “Proving Circuit Lower Bounds in High Uniform Classes”, IIS, 20:1 (2014), 1  
87. Ryan Williams, 2014 IEEE 29th Conference on Computational Complexity (CCC), 2014, 248  
88. Ruiwen Chen, Valentine Kabanets, Antonina Kolokolova, Ronen Shaltiel, David Zuckerman, 2014 IEEE 29th Conference on Computational Complexity (CCC), 2014, 262  
89. Ryan Williams, Proceedings of the forty-sixth annual ACM symposium on Theory of computing, 2014, 664  
90. Kei UCHIZAWA, “Lower Bounds for Threshold Circuits of Bounded Energy”, IIS, 20:1 (2014), 27  
91. Kristoffer Arnsfelt Hansen, Balagopal Komarath, Jayalal Sarma, Sven Skyum, Navid Talebanfard, Lecture Notes in Computer Science, 8635, Mathematical Foundations of Computer Science 2014, 2014, 336  
92. Albert Atserias, Anuj Dawar, “Degree lower bounds of tower-type for approximating formulas with parity quantifiers”, ACM Trans. Comput. Logic, 15:1 (2014), 1  
93. Ruiwen Chen, Valentine Kabanets, Jeff Kinne, “Lower Bounds Against Weakly-Uniform Threshold Circuits”, Algorithmica, 70:1 (2014), 47  
94. Arkadev Chattopadhyay, Ricard Gavaldà, Kristoffer Arnsfelt Hansen, Denis Thérien, “Learning Read-Constant Polynomials of Constant Degree Modulo Composites”, Theory Comput Syst, 55:2 (2014), 404  
95. Benjamin Rossman, Proceedings of the forty-sixth annual ACM symposium on Theory of computing, 2014, 203  
96. Ryan Williams, “Nonuniform ACC Circuit Lower Bounds”, J. ACM, 61:1 (2014), 1  
97. Alexander A. Razborov, The Mathematics of Paul Erdős I, 2013, 425  
98. Andrej Bogdanov, Akinori Kawachi, Hidetoki Tanaka, “Hard Functions for Low-Degree Polynomials over Prime Fields”, ACM Trans. Comput. Theory, 5:2 (2013), 1  
99. Shachar Lovett, Partha Mukhopadhyay, Amir Shpilka, “Pseudorandom generators for CC0[p] and the Fourier spectrum of low-degree polynomials over finite fields”, comput. complex., 22:4 (2013), 679  
100. Arkadev Chattopadhyay, Jacobo Torán, Fabian Wagner, “Graph Isomorphism is Not AC0-Reducible to Group Isomorphism”, ACM Trans. Comput. Theory, 5:4 (2013), 1  
101. A. P. Davydow, S. I. Nikolenko, “Circuit complexity of linear functions: gate elimination and feeble security”, J. Math. Sci. (N. Y.), 188:1 (2013), 35–46      
102. Ruiwen Chen, Valentine Kabanets, Lecture Notes in Computer Science, 7434, Computing and Combinatorics, 2012, 408  
103. V. V. Podolskii, “Exponential lower bound for bounded depth circuits with few threshold gates”, Inform. Process. Lett., 112:7 (2012), 267–271        
104. Guy N. Rothblum, Lecture Notes in Computer Science, 7417, Advances in Cryptology – CRYPTO 2012, 2012, 552  
105. Albert Atserias, Anuj Dawar, Lecture Notes in Computer Science, 7392, Automata, Languages, and Programming, 2012, 67  
106. Dmitry Gavinsky, Shachar Lovett, Srikanth Srinivasan, 2012 IEEE 27th Conference on Computational Complexity, 2012, 287  
107. Ido Ben-Eliezer, Rani Hod, Shachar Lovett, “Random low-degree polynomials are hard to approximate”, comput. complex., 21:1 (2012), 63  
108. Gil Cohen, Amir Shpilka, Avishay Tal, Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, 2012, 409  
109. Richard J. Lipton, Kenneth W. Regan, Atri Rudra, Lecture Notes in Computer Science, 6907, Mathematical Foundations of Computer Science 2011, 2011, 436  
110. Andrej Bogdanov, Akinori Kawachi, Hidetoki Tanaka, Lecture Notes in Computer Science, 6907, Mathematical Foundations of Computer Science 2011, 2011, 120  
111. Arkadev Chattopadhyay, Ricard Gavaldà, Kristoffer Arnsfelt Hansen, Denis Thérien, Lecture Notes in Computer Science, 6651, Computer Science – Theory and Applications, 2011, 29  
112. Fengming Wang, Lecture Notes in Computer Science, 6648, Theory and Applications of Models of Computation, 2011, 164  
113. Arkadev Chattopadhyay, Shachar Lovett, 2011 IEEE 26th Annual Conference on Computational Complexity, 2011, 300  
114. Sebastian Faust, Tal Rabin, Leonid Reyzin, Eran Tromer, Vinod Vaikuntanathan, Lecture Notes in Computer Science, 6110, Advances in Cryptology – EUROCRYPT 2010, 2010, 135  
115. Mark Braverman, “Polylogarithmic independence fools AC 0 circuits”, J. ACM, 57:5 (2010), 1  
116. Parikshit Gopalan, Subhash Khot, Rishi Saket, “Hardness of Reconstructing Multivariate Polynomials over Finite Fields”, SIAM J. Comput., 39:6 (2010), 2598  
117. Shachar Lovett, Partha Mukhopadhyay, Amir Shpilka, 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, 2010, 695  
118. Omer Barkol, Yuval Ishai, Enav Weinreb, “On d-Multiplicative Secret Sharing”, J Cryptol, 23:4 (2010), 580  
119. Mark Braverman, 2009 24th Annual IEEE Conference on Computational Complexity, 2009, 3  
120. Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai, “Zero-Knowledge Proofs from Secure Multiparty Computation”, SIAM J. Comput., 39:3 (2009), 1121  
121. Parikshit Gopalan, Shachar Lovett, Amir Shpilka, 2009 24th Annual IEEE Conference on Computational Complexity, 2009, 173  
122. Rahul Santhanam, “Circuit Lower Bounds for Merlin–Arthur Classes”, SIAM J. Comput., 39:3 (2009), 1038  
123. Benjamin Rossman, Lecture Notes in Computer Science, 5514, Logic, Language, Information and Computation, 2009, 350  
124. Arkadev Chattopadhyay, Avi Wigderson, 2009 50th Annual IEEE Symposium on Foundations of Computer Science, 2009, 43  
125. Ido Ben-Eliezer, Rani Hod, Shachar Lovett, Lecture Notes in Computer Science, 5687, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2009, 366  
126. Kristoffer Arnsfelt Hansen, Lecture Notes in Computer Science, 5675, Computer Science - Theory and Applications, 2009, 117  
127. Kristoffer Arnsfelt Hansen, Michal Koucký, 2009 24th Annual IEEE Conference on Computational Complexity, 2009, 27  
128. Vladimir V. Podolskii, Lecture Notes in Computer Science, 5010, Computer Science – Theory and Applications, 2008, 261  
129. Yael Tauman Kalai, Ran Raz, Lecture Notes in Computer Science, 5126, Automata, Languages and Programming, 2008, 536  
130. Parikshit Gopalan, “Query-Efficient Algorithms for Polynomial Interpolation over Composites”, SIAM J. Comput., 38:3 (2008), 1033  
131. Pavel Pudlák, Lecture Notes in Computer Science, 5010, Computer Science – Theory and Applications, 2008, 13  
132. Omer Barkol, Yuval Ishai, Enav Weinreb, Proceedings of the fortieth annual ACM symposium on Theory of computing, 2008, 661  
133. Kristoffer Arnsfelt Hansen, 2008 23rd Annual IEEE Conference on Computational Complexity, 2008, 92  
134. Ran Raz, Amir Yehudayoff, 2008 23rd Annual IEEE Conference on Computational Complexity, 2008, 128  
135. Rahul Santhanam, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, 2007, 275  
136. Debajyoti Bera, Frederic Green, Steven Homer, “Small depth quantum circuits”, SIGACT News, 38:2 (2007), 35  
137. Parikshit Gopalan, Subhash Khot, Rishi Saket, 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), 2007, 349  
138. Amitabha Roy, Howard Straubing, “Definability of Languages by Generalized First-Order Formulas over $(\mathbb{N},+)$”, SIAM J. Comput., 37:2 (2007), 502  
139. Alexander Healy, Emanuele Viola, Lecture Notes in Computer Science, 3884, STACS 2006, 2006, 672  
140. J. Buresh-Oppenheim, R. Santhanam, 21st Annual IEEE Conference on Computational Complexity (CCC'06), 2006, 73  
141. Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton, “Symmetric polynomials over Zm and simultaneous communication protocols”, Journal of Computer and System Sciences, 72:2 (2006), 252  
142. Amitabha Roy, Howard Straubing, Lecture Notes in Computer Science, 3884, STACS 2006, 2006, 489  
143. Lane A. Hemaspaandra, “SIGACT news complexity theory column 53”, SIGACT News, 37:4 (2006), 47  
144. Arkadev Chattopadhyay, Kristoffer Arnsfelt Hansen, Lecture Notes in Computer Science, 3580, Automata, Languages and Programming, 2005, 994  
145. Stephen Fenner, Frederic Green, Steven Homer, Yong Zhang, Lecture Notes in Computer Science, 3623, Fundamentals of Computation Theory, 2005, 44  
146. Omer Barkol, Yuval Ishai, Lecture Notes in Computer Science, 3621, Advances in Cryptology – CRYPTO 2005, 2005, 395  
147. Farid Ablayev, Aida Gainutdinova, Marek Karpinski, Cristopher Moore, Christopher Pollett, “On the computational power of probabilistic and quantum branching program”, Information and Computation, 203:2 (2005), 145  
148. Jin-Yi Cai, Osamu Watanabe, Lecture Notes in Computer Science, 3341, Algorithms and Computation, 2004, 209  
149. A. D. Korshunov, “Monotone Boolean functions”, Russian Math. Surveys, 58:5 (2003), 929–1001                
150. Peter Høyer, Robert Špalek, Lecture Notes in Computer Science, 2607, STACS 2003, 2003, 234  
151. Ran Raz, Amir Shpilka, “Lower Bounds for Matrix Product in Bounded Depth Circuits with Arbitrary Gates”, SIAM J. Comput., 32:2 (2003), 488  
152. V. Beiu, 2, Proceedings of the International Joint Conference on Neural Networks, 2003., 2003, 989  
153. Adam R. Klivans, Lecture Notes in Computer Science, 2129, Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques, 2001, 249  
154. Cristopher Moore, Denis Thérien, François Lemieux, Joshua Berman, Arthur Drisko, “Circuits and Expressions with Nonassociative Gates”, Journal of Computer and System Sciences, 60:2 (2000), 368  
155. Y. Ishai, E. Kushilevitz, Proceedings 41st Annual Symposium on Foundations of Computer Science, 2000, 294  
156. Carsten Damm, Ki Hang Kim, Fred Roush, Lecture Notes in Computer Science, 1627, Computing and Combinatorics, 1999, 123  
157. Howard Straubing, Lecture Notes in Computer Science, 1373, STACS 98, 1998, 332  
158. D. Grigoriev, A.A. Razborov, Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280), 1998, 269  
159. Uwe Schöning, Randall Pruim, Gems of Theoretical Computer Science, 1998, 101  
160. Alexis Maciel, Denis Thérien, “Threshold Circuits of Small Majority-Depth”, Information and Computation, 146:1 (1998), 55  
161. Cristopher Moore, “Predicting nonlinear cellular automata quickly by decomposing them into linear ones”, Physica D: Nonlinear Phenomena, 111:1-4 (1998), 27  
162. Mikael Goldmann, Johan Håstad, “Monotone Circuits for Connectivity Have Depth (log n)2-o(1)”, SIAM J. Comput., 27:5 (1998), 1283  
163. R. Paturi, P. Pudlak, F. Zane, Proceedings 38th Annual Symposium on Foundations of Computer Science, 1997, 566  
164. Alexander A Razborov, Steven Rudich, “Natural Proofs”, Journal of Computer and System Sciences, 55:1 (1997), 24  
165. Domenico Zambella, “Algebraic Methods and Bounded Formulas”, Notre Dame J. Formal Logic, 38:1 (1997)  
166. M. Agrawal, E. Allender, S. Datta, Proceedings of Computational Complexity. Twelfth Annual IEEE Conference, 1997, 134  
167. R. Beigel, A. Maciel, Proceedings of Computational Complexity. Twelfth Annual IEEE Conference, 1997, 149  
168. Pierre Péladeau, Howard Straubing, Denis Therien, “Finite semigroup varieties defined by programs”, Theoretical Computer Science, 180:1-2 (1997), 325  
169. Shi-Chun Tsai, “Lower Bounds on Representing Boolean Functions as Polynomials in $Z_m $”, SIAM J. Discrete Math., 9:1 (1996), 55  
170. Jordan Gergov, Christoph Meinel, “Mod-2-OBDDs—A data structure that generalizes EXOR-sum-of-products and ordered binary decision diagrams”, Form Method Syst Des, 8:3 (1996), 273  
171. Hervé Caussinus, “A note on a theorem of Barrington, Straubing and Thérien”, Information Processing Letters, 58:1 (1996), 31  
172. Jehoshua Bruck, “Reflections on ?Representations of sets of Boolean functions by commutative rings? by Roman Smolensky”, Comput Complexity, 6:3 (1996), 209  
173. Richard Beigel, Alexis Maciel, “Upper and lower bounds for some depth-3 circuit classes”, Comput Complexity, 6:3 (1996), 235  
174. Iain A. Stewart, Collegium Logicum, 2, Collegium Logicum, 1996, 101  
175. E. N. Mayoraz, “On the Power of Democratic Networks”, SIAM J. Discrete Math., 9:2 (1996), 258  
176. Eric Allender, Lecture Notes in Computer Science, 1090, Computing and Combinatorics, 1996, 127  
177. Izv. Math., 59:1 (1995), 205–227          
178. G. Tardos, D.A.M. Barrington, Proceedings Third Israel Symposium on the Theory of Computing and Systems, 1995, 52  
179. J. H�stad, S. Jukna, P. Pudl�k, “Top-down lower bounds for depth-three circuits”, Comput Complexity, 5:2 (1995), 99  
180. Meera Sitharam, “Evaluating spectral norms for constant depth circuits with symmetric gates”, Comput Complexity, 5:2 (1995), 167  
181. A. Gal, Proceedings of Structure in Complexity Theory. Tenth Annual IEEE Conference, 1995, 82  
182. Alexander A. Razborov, Feasible Mathematics II, 1995, 344  
183. J. Kobler, Proceedings of Structure in Complexity Theory. Tenth Annual IEEE Conference, 1995, 246  
184. Mikael Goldmann, “A note on the power of majority gates and modular gates”, Information Processing Letters, 53:6 (1995), 321  
185. V.P. Roychowdhury, A. Orlitsky, Kai-Yeung Siu, “Lower bounds on threshold and related circuits via communication complexity”, IEEE Trans. Inform. Theory, 40:2 (1994), 467  
186. Eric Allender, Vivek Gore, “A Uniform Circuit Lower Bound for the Permanent”, SIAM J. Comput., 23:5 (1994), 1026  
187. J. Aspnes, R. Beigel, M. Furst, S. Rudich, “The expressive power of voting polynomials”, Combinatorica, 14:2 (1994), 135  
188. Lance Fortnow, Lecture Notes in Computer Science, 880, Foundation of Software Technology and Theoretical Computer Science, 1994, 256  
189. Noam Nisan, Mario Szegedy, “On the degree of boolean functions as real polynomials”, Comput Complexity, 4:4 (1994), 301  
190. Richard Beigel, Jun Tarui, “On ACC”, Comput Complexity, 4:4 (1994), 350  
191. David A. Mix Barrington, Richard Beigel, Steven Rudich, “Representing Boolean functions as polynomials modulo composite numbers”, Comput Complexity, 4:4 (1994), 367  
192. P. Pudlák, Lecture Notes in Computer Science, 710, Fundamentals of Computation Theory, 1993, 106  
193. M. Karchmer, A. Wigderson, [1993] Proceedings of the Eigth Annual Structure in Complexity Theory Conference, 1993, 102  
194. Mario Szegedy, “Functions with bounded symmetric communication complexity, programs over commutative monoids, and ACC”, Journal of Computer and System Sciences, 47:3 (1993), 405  
195. Rafi Heiman, Ilan Newman, Avi Wigderson, “On read-once threshold formulae and their randomized decision tree complexity”, Theoretical Computer Science, 107:1 (1993), 63  
196. S.-C. Tsai, [1993] Proceedings of the Eigth Annual Structure in Complexity Theory Conference, 1993, 96  
197. R. Smolensky, Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science, 1993, 130  
198. R. Beigel, [1993] Proceedings of the Eigth Annual Structure in Complexity Theory Conference, 1993, 82  
199. Carl Sturtivant, Gudmund Skovbjerg Frandsen, “The computational efficacy of finite-field arithmetic”, Theoretical Computer Science, 112:2 (1993), 291  
200. J. Hastad, S. Jukna, P. Pudlak, Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science, 1993, 124  
201. Jehoshua Bruck, Roman Smolensky, “Polynomial Threshold Functions, $AC^0 $ Functions, and Spectral Norms”, SIAM J. Comput., 21:1 (1992), 33  
202. Joan Boyar, Gudmund Frandsen, Carl Sturtivant, “An arithmetic model of computation equivalent to threshold circuits”, Theoretical Computer Science, 93:2 (1992), 303  
203. D.A.M. Barrington, [1992] Proceedings of the Seventh Annual Structure in Complexity Theory Conference, 1992, 86  
204. David A. Mix Barrington, Kevin Compton, Howard Straubing, Denis Thérien, “Regular languages in NC1”, Journal of Computer and System Sciences, 44:3 (1992), 478  
205. Richard Beigel, Jun Tarui, Seinosuke Toda, Lecture Notes in Computer Science, 650, Algorithms and Computation, 1992, 420  
206. Mikael Goldmann, Johan Håstad, “A simple lower bound for monotone clique using a communication game”, Information Processing Letters, 41:4 (1992), 221  
207. Carsten Damm, Matthias Krause, Christoph Meinel, Stephan Waack, Lecture Notes in Computer Science, 577, STACS 92, 1992, 279  
208. I. E. Shparlinski, “On some problems in the theory of finite fields”, Russian Math. Surveys, 46:1 (1991), 199–240          
209. R. Beigel, N. Reingold, D. Spielman, [1991] Proceedings of the Sixth Annual Structure in Complexity Theory Conference, 1991, 286  
210. R. Beigel, J. Tarui, [1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science, 1991, 783  
211. Jeff Kahn, Roy Meshulam, “On modp transversals”, Combinatorica, 11:1 (1991), 17  
212. Eddy Mayoraz, Lecture Notes in Computer Science, 540, Artificial Neural Networks, 1991, 78  
213. Jun Tarui, Lecture Notes in Computer Science, 480, STACS 91, 1991, 238  
214. David A. Mix Barrington, James Corbett, “A note on some languages in uniform ACC0”, Theoretical Computer Science, 78:2 (1991), 357  
215. R. Smolensky, Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science, 1990, 628  
216. Eric Allender, Ulrich Hertrampf, Lecture Notes in Computer Science, 452, Mathematical Foundations of Computer Science 1990, 1990, 158  
217. Ravi B. BOPPANA, Michael SIPSER, Algorithms and Complexity, 1990, 757  
218. David A. Mix Barrington, Neil Immerman, Howard Straubing, “On uniformity within NC1”, Journal of Computer and System Sciences, 41:3 (1990), 274  
219. J. Bruck, R. Smolensky, Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science, 1990, 632  
220. Jin-yi Cai, “Lower bounds for constant-depth circuits in the presence of help bits”, Information Processing Letters, 36:2 (1990), 79  
221. R. Heiman, I. Newman, A. Wigderson, Proceedings Fifth Annual Structure in Complexity Theory Conference, 1990, 78  
222. Jehoshua Bruck, “Harmonic Analysis of Polynomial Threshold Functions”, SIAM J. Discrete Math., 3:2 (1990), 168  
223. David A. Mix Barrington, James Corbett, “On the relative complexity of some languages in NC1”, Information Processing Letters, 32:5 (1989), 251  
224. J.-Y. Cai, 30th Annual Symposium on Foundations of Computer Science, 1989, 532