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