Follow
Alexander Razborov
Alexander Razborov
Verified email at math.uchicago.edu
Title
Cited by
Cited by
Year
Natural proofs
AA Razborov, S Rudich
Proceedings of the twenty-sixth annual ACM symposium on Theory of computing …, 1994
7471994
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
6711987
On the distributional complexity of disjointness
AA Razborov
Theor. Comput. Sci. 106 (2), 385-390, 1992
6241992
Lower bounds on the monotone complexity of some Boolean function
A Razborov
Soviet Math. Dokl. 31, 354-357, 1985
5491985
Flag algebras
AA Razborov
The Journal of Symbolic Logic 72 (4), 1239-1282, 2007
3722007
Majority gates vs. general weighted threshold gates
M Goldmann, J Hĺstad, A Razborov
Computational Complexity 2, 277-300, 1992
2771992
On the minimal density of triangles in graphs
AA Razborov
Combinatorics, Probability and Computing 17 (4), 603-618, 2008
2602008
Quantum communication complexity of symmetric predicates
AA Razborov
Izvestiya: Mathematics 67 (1), 145, 2003
2232003
On systems of equations in a free group
AA Razborov
Mathematics of the USSR-Izvestiya 25 (1), 115, 1985
2191985
On lower bounds for read-k-times branching programs
A Borodin, A Razborov, R Smolensky
Computational Complexity 3 (1), 1-18, 1993
2081993
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
2011985
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
1962000
Lower bounds for the polynomial calculus
AA Razborov
computational complexity 7 (4), 291-324, 1998
1791998
On 3-hypergraphs with forbidden 4-vertex configurations
AA Razborov
SIAM Journal on Discrete Mathematics 24 (3), 946-963, 2010
1642010
Why are there so many loop formulas?
V Lifschitz, A Razborov
ACM Transactions on Computational Logic (TOCL) 7 (2), 261-268, 2006
1622006
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
1602013
Lower bounds for deterministic and nondeterministic branching programs
AA Razborov
International Symposium on Fundamentals of Computation Theory, 47-60, 1991
1591991
Lower bounds for polynomial calculus: Non-binomial case
M Alekhnovich, AA Razborov
Proceedings 42nd IEEE Symposium on Foundations of Computer Science, 190-199, 2001
1562001
Applications of matrix methods to the theory of lower bounds in computational complexity
AA Razborov
Combinatorica 10, 81-93, 1990
1531990
Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
AA Razborov
Izvestiya: mathematics 59 (1), 205, 1995
1521995
The system can't perform the operation now. Try again later.
Articles 1–20