Natural proofs AA Razborov, S Rudich Proceedings of the twenty-sixth annual ACM symposium on Theory of computing …, 1994 | 751 | 1994 |
Lower bounds on the size of bounded depth circuits over a complete basis with logical addition AA Razborov Mathematical Notes of the Academy of Sciences of the USSR 41 (4), 333-338, 1987 | 672 | 1987 |
On the distributional complexity of disjointness AA Razborov Theor. Comput. Sci. 106 (2), 385-390, 1992 | 624 | 1992 |
Lower bounds on the monotone complexity of some Boolean function A Razborov Soviet Math. Dokl. 31, 354-357, 1985 | 551 | 1985 |
Flag algebras AA Razborov The Journal of Symbolic Logic 72 (4), 1239-1282, 2007 | 374 | 2007 |
Majority gates vs. general weighted threshold gates M Goldmann, J Håstad, A Razborov Computational Complexity 2, 277-300, 1992 | 277 | 1992 |
On the minimal density of triangles in graphs AA Razborov Combinatorics, Probability and Computing 17 (4), 603-618, 2008 | 262 | 2008 |
Quantum communication complexity of symmetric predicates AA Razborov Izvestiya: Mathematics 67 (1), 145, 2003 | 223 | 2003 |
On systems of equations in a free group AA Razborov Mathematics of the USSR-Izvestiya 25 (1), 115, 1985 | 219 | 1985 |
On lower bounds for read-k-times branching programs A Borodin, A Razborov, R Smolensky Computational Complexity 3 (1), 1-18, 1993 | 208 | 1993 |
Lower bounds on monotone complexity of the logical permanent AA Razborov Mathematical Notes of the Academy of Sciences of the USSR 37, 485-493, 1985 | 202 | 1985 |
Space complexity in propositional calculus M Alekhnovich, E Ben-Sasson, A Wigderson Proceedings of the thirty-second annual ACM symposium on Theory of computing …, 2000 | 196 | 2000 |
Lower bounds for the polynomial calculus AA Razborov computational complexity 7 (4), 291-324, 1998 | 179 | 1998 |
On 3-hypergraphs with forbidden 4-vertex configurations AA Razborov SIAM Journal on Discrete Mathematics 24 (3), 946-963, 2010 | 164 | 2010 |
Why are there so many loop formulas? V Lifschitz, A Razborov ACM Transactions on Computational Logic (TOCL) 7 (2), 261-268, 2006 | 162 | 2006 |
On the number of pentagons in triangle-free graphs H Hatami, J Hladký, D Králʼ, S Norine, A Razborov Journal of Combinatorial Theory, Series A 120 (3), 722-732, 2013 | 160 | 2013 |
Lower bounds for deterministic and nondeterministic branching programs AA Razborov International Symposium on Fundamentals of Computation Theory, 47-60, 1991 | 159 | 1991 |
Lower bounds for polynomial calculus: Non-binomial case M Alekhnovich, AA Razborov Proceedings 42nd IEEE Symposium on Foundations of Computer Science, 190-199, 2001 | 156 | 2001 |
Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic AA Razborov Izvestiya: mathematics 59 (1), 205, 1995 | 153 | 1995 |
Applications of matrix methods to the theory of lower bounds in computational complexity AA Razborov Combinatorica 10, 81-93, 1990 | 153 | 1990 |