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
7731994
Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
AA Razborov
Mat. Zametki 41 (4), 598-607, 1987
7191987
Îď the distributional complexity
ĀĀ Razborov
Theoretical Computer Science 106, 385-390, 1992
636*1992
Lower bounds on the monotone complexity of some Boolean function
A Razborov
Soviet Math. Dokl. 31, 354-357, 1985
5621985
Flag algebras
AA Razborov
The Journal of Symbolic Logic 72 (4), 1239-1282, 2007
3932007
Majority gates vs. general weighted threshold gates
M Goldmann, J Hĺstad, A Razborov
Computational Complexity 2, 277-300, 1992
2781992
On the minimal density of triangles in graphs
AA Razborov
Combinatorics, Probability and Computing 17 (4), 603-618, 2008
2722008
Quantum communication complexity of symmetric predicates
AA Razborov
Izvestiya: Mathematics 67 (1), 145, 2003
2242003
On systems of equations in a free group
AA Razborov
Mathematics of the USSR-Izvestiya 25 (1), 115, 1985
2231985
On lower bounds for read-k-times branching programs
A Borodin, A Razborov, R Smolensky
Computational Complexity 3 (1), 1-18, 1993
2091993
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
2022000
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
2021985
Lower bounds for the polynomial calculus
AA Razborov
computational complexity 7 (4), 291-324, 1998
1871998
On 3-hypergraphs with forbidden 4-vertex configurations
AA Razborov
SIAM Journal on Discrete Mathematics 24 (3), 946-963, 2010
1722010
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
1672013
Why are there so many loop formulas?
V Lifschitz, A Razborov
ACM Transactions on Computational Logic (TOCL) 7 (2), 261-268, 2006
1642006
Lower bounds for polynomial calculus: Non-binomial case
M Alekhnovich, AA Razborov
Proceedings 42nd IEEE Symposium on Foundations of Computer Science, 190-199, 2001
1632001
Lower bounds for deterministic and nondeterministic branching programs
AA Razborov
International Symposium on Fundamentals of Computation Theory, 47-60, 1991
1631991
Applications of matrix methods to the theory of lower bounds in computational complexity
AA Razborov
Combinatorica 10, 81-93, 1990
1611990
Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
AA Razborov
Izvestiya: mathematics 59 (1), 205, 1995
1571995
The system can't perform the operation now. Try again later.
Articles 1–20