# zbMATH — the first resource for mathematics

## Razborov, Aleksandr Aleksandrovich

Compute Distance To:
 Author ID: razborov.alexander-a Published as: Razborov, A. A.; Razborov, Alexander A.; Razborov, Alexander; Razborov, A.; Razborov Alexander Homepage: http://people.cs.uchicago.edu/~razborov/ External Links: MGP · Wikidata · Math-Net.Ru · dblp Awards: Nevanlinna Prize (1990)
 Documents Indexed: 106 Publications since 1985, including 5 Books Biographic References: 2 Publications
all top 5

#### Co-Authors

 51 single-authored 7 Wigderson, Avi 5 Alekhnovich, Michael 3 Beklemishev, Lev D. 3 Ben-Sasson, Eli 3 Lauria, Massimo 3 Lysenok, Igor’ Geront’evich 3 Nordström, Jakob 3 Yao, Andrew Chi-Chih 3 Yukna, Stasys P. 2 Adyan, Sergeĭ Ivanovich 2 Alekhnovich, M. V. 2 Atabekyan, Varuzhan S. 2 Atserias, Albert 2 Beyersdorff, Olaf 2 Borodin, Allan B. 2 Bukhshtaber, Viktor Matveevich 2 Coregliano, Leonardo Nagami 2 Galesi, Nicola 2 Guba, Victor S. 2 Håstad, Johan Torkel 2 Hatami, Hamed 2 Hladký, Jan 2 Kashin, Boris Sergeevich 2 Král’, Daniel 2 Norine, Serguei 2 Novikov, Sergeĭ Petrovich 2 Pitassi, Toniann 2 Rudich, Steven 2 Savický, Petr 2 Semenov, Alexei Lvovich 2 Wegener, Ingo 1 Artemov, Sergei 1 Bashmakova, Izabella Grigor’evna 1 Belyi, Gennadii Vladimirovich 1 Bonacina, Ilario 1 Cori, René 1 de Rezende, Susanna F. 1 Diekert, Volker 1 Eisenbrand, Friedrich 1 Ershov, Yuriĭ Leonidovich 1 Gluskin, Efim D. 1 Godunov, Sergeĭ Konstantinovich 1 Goldmann, Mikael 1 Gonchar, Andreĭ Aleksandrovich 1 Goncharov, Sergeĭ Savost’yanovich 1 Grigor’ev, Dmitriĭ Yur’evich 1 Guruswami, Venkatesan 1 Hähnle, Nicolai 1 Hirsch, Edward A. 1 Impagliazzo, Russell 1 Kozlov, Valeriĭ Vasil’evich 1 Krajíček, Jan 1 Lee, James R. 1 Lifschitz, Vladimir 1 Makowsky, Johann-Andreas 1 Mal’tsev, Arkadiĭ Anatol’evich 1 Mubayi, Dhruv 1 Mull, Nathan 1 Olevskii, Alexander Moiseevich 1 Osipov, Yuriĭ Sergeevich 1 Pang, Shuo 1 Pentus, Mati 1 Peretyat’kin, Mikhail G. 1 Pikhurko, Oleg 1 Podol’skiĭ, Vladimir Vladimirovich 1 Pudlák, Pavel 1 Repin, N. N. 1 Rossman, Benjamin 1 Rothvoß, Thomas 1 Sadovnichiĭ, Viktor Antonovich 1 Semenov, Aleksei L. 1 Sgall, Jiří 1 Sherstov, Alexander A. 1 Shevrin, Lev Naumovich 1 Skorokhod, Anatoliĭ Volodymyrovych 1 Slissenko, Anatol 1 Smolensky, Roman 1 Szemerédi, Endre 1 Talambutsa, A. L. 1 Todorcevic, Stevo B. 1 Treshchev, Dmitriĭ Valer’evich 1 Vereshchagin, Nikolai K. 1 Viola, Emanuele 1 Wood, Carol 1 Yekhanin, Sergey
all top 5

#### Serials

 8 Computational Complexity 6 Russian Mathematical Surveys 5 Mathematical Notes 5 SIAM Journal on Computing 4 Theoretical Computer Science 4 Combinatorics, Probability and Computing 3 ACM Transactions on Computation Theory 2 Journal of Computer and System Sciences 2 Journal of Graph Theory 2 Mathematics of Operations Research 2 Combinatorica 2 Izvestiya: Mathematics 2 Journal of the ACM 2 Annals of Mathematics. Second Series 1 Discrete Applied Mathematics 1 Discrete Mathematics 1 Information Processing Letters 1 Matematicheskie Zametki 1 Uspekhi Matematicheskikh Nauk [N. S.] 1 Journal of Combinatorial Theory. Series A 1 The Journal of Symbolic Logic 1 Mathematics of the USSR. Izvestiya 1 Proceedings of the London Mathematical Society. Third Series 1 Soviet Mathematics. Doklady 1 Journal of Algorithms 1 SIAM Journal on Discrete Mathematics 1 International Journal of Algebra and Computation 1 Notices of the American Mathematical Society 1 Applicable Algebra in Engineering, Communication and Computing 1 Voprosy Kibernetiki (Moskva) 1 Sbornik: Mathematics 1 Doklady Mathematics 1 Theory of Computing Systems 1 ACM Transactions on Computational Logic 1 Internet Mathematics 1 Oberwolfach Reports 1 Lecture Notes in Computer Science 1 Lecture Notes in Logic 1 Proceedings of the Steklov Institute of Mathematics 1 Quantum Information & Computation 1 Theory of Computing 1 Translations. Series 2. American Mathematical Society
all top 5

#### Fields

 59 Computer science (68-XX) 38 Mathematical logic and foundations (03-XX) 25 Information and communication theory, circuits (94-XX) 23 Combinatorics (05-XX) 8 General and overarching topics; collections (00-XX) 8 Group theory and generalizations (20-XX) 6 History and biography (01-XX) 4 Operations research, mathematical programming (90-XX) 3 Order, lattices, ordered algebraic structures (06-XX) 3 Number theory (11-XX) 3 Nonassociative rings and algebras (17-XX) 2 Commutative algebra (13-XX) 2 Linear and multilinear algebra; matrix theory (15-XX) 2 Probability theory and stochastic processes (60-XX) 2 Quantum theory (81-XX) 1 Associative rings and algebras (16-XX) 1 Convex and discrete geometry (52-XX) 1 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 1 Mathematics education (97-XX)

#### Citations contained in zbMATH Open

77 Publications have been cited 1,309 times in 898 Documents Cited by Year
Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Zbl 0632.94030
Razborov, A. A.
1987
Flag algebras. Zbl 1146.03013
Razborov, Alexander A.
2007
On the minimal density of triangles in graphs. Zbl 1170.05036
Razborov, Alexander A.
2008
Lower bounds for the monotone complexity of some Boolean functions. Zbl 0621.94027
Razborov, A. A.
1985
On the distributional complexity of disjointness. Zbl 0787.68055
Razborov, A. A.
1992
Natural proofs. Zbl 0884.68055
Razborov, Alexander A.; Rudich, Steven
1997
On 3-hypergraphs with forbidden 4-vertex configurations. Zbl 1223.05204
Razborov, Alexander A.
2010
Majority gates vs. general weighted threshold gates. Zbl 0770.68054
Goldmann, Mikael; Håstad, Johan; Razborov, Alexander
1992
On the number of pentagons in triangle-free graphs. Zbl 1259.05087
Hatami, Hamed; Hladký, Jan; Král’, Daniel; Norine, Serguei; Razborov, Alexander
2013
On lower bounds for read-$$k$$-times branching programs. Zbl 0777.68043
Borodin, A.; Razborov, A.; Smolensky, R.
1993
Space complexity in propositional calculus. Zbl 1004.03047
Alekhnovich, Michael; Ben-Sasson, Eli; Razborov, Alexander A.; Wigderson, Avi
2002
On systems of equations in a free group. Zbl 0579.20019
Razborov, A. A.
1985
Resolution is not automatizable unless W[P] is tractable. Zbl 1169.03044
Alekhnovich, Michael; Razborov, Alexander A.
2008
Applications of matrix methods to the theory of lower bounds in computational complexity. Zbl 0717.68049
Razborov, A. A.
1990
Pseudorandom generators in propositional proof complexity. Zbl 1096.03070
Alekhnovich, Michael; Ben-Sasson, Eli; Razborov, Alexander A.; Wigderson, Avi
2004
Lower bounds on monotone complexity of the logical permanent. Zbl 0584.94026
Razborov, A. A.
1985
The sign-rank of AC$$^0$$. Zbl 1211.68213
Razborov, Alexander A.; Sherstov, Alexander A.
2010
On the quantum communication complexity of symmetric predicates. Zbl 1088.68052
Razborov, A. A.
2003
Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic. Zbl 0838.03045
Razborov, A. A.
1995
Lower bounds for the polynomial calculus. Zbl 1026.03043
Razborov, Alexander A.
1998
Proof complexity in algebraic systems and bounded depth Frege systems with modular counting. Zbl 0890.03030
Buss, S.; Impagliazzo, R.; Krajíček, J.; Pudlák, P.; Razborov, A. A.; Sgall, J.
1997
Asymptotic structure of graphs with the minimum number of triangles. Zbl 1371.05147
Pikhurko, Oleg; Razborov, Alexander
2017
Diameter of polyhedra: limits of abstraction. Zbl 1226.52004
Eisenbrand, Friedrich; Hähnle, Nicolai; Razborov, Alexander; Rothvoß, Thomas
2010
Why are there so many loop formulas? Zbl 1367.68036
2006
Non-three-colourable common graphs exist. Zbl 1248.05090
Hatami, Hamed; Hladký, Jan; Král’, Daniel; Norine, Serguei; Razborov, Alexander
2012
Satisfiability, branch-width and Tseitin tautologies. Zbl 1243.68182
Alekhnovich, Michael; Razborov, Alexander
2011
Improved lower bounds on the rigidity of Hadamard matrices. Zbl 0917.15013
Kashin, B. S.; Razborov, A. A.
1998
The gap between the chromatic number of a graph and the rank of its adjacency matrix is superlinear. Zbl 0776.05073
Razborov, A. A.
1992
Pseudorandom generators hard for $$k$$-DNF resolution and polynomial calculus resolution. Zbl 1376.03055
Razborov, Alexander A.
2015
Neither reading few bits twice nor reading illegally helps much. Zbl 0903.68074
Jukna, S.; Razborov, A.
1998
Bounded arithmetic and lower bounds in Boolean complexity. Zbl 0838.03044
Razborov, Alexander A.
1995
Exponential lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields. Zbl 1040.68045
Grigoriev, D.; Razborov, A.
2000
$$n^{{\Omega{}}(\log{} n)}$$ lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom. Zbl 0783.68046
Razborov, Alexander; Wigderson, Avi
1993
The set of minimal braids is Co-NP-complete. Zbl 0726.68047
Paterson, M. S.; Razborov, A. A.
1991
On submodular complexity measures. Zbl 0770.68073
Razborov, A. A.
1992
Constructing small sets that are uniform in arithmetic progressions. Zbl 0799.11022
Razborov, A.; Szemerédi, E.; Wigderson, A.
1993
On P versus NP$$\cap$$co-NP for decision trees and read-once branching programs. Zbl 0962.68075
Jukna, S.; Razborov, A.; Savický, P.; Wegener, I.
1999
Proof complexity of pigeonhole principles. Zbl 1073.03540
Razborov, Alexander A.
2002
On the distributional complexity of disjointness. Zbl 0765.68056
Razborov, A. A.
1990
On systems of equations in free groups. Zbl 0848.20018
Razborov, Alexander A.
1995
Lower bounds for polynomial calculus: nonbinomial case. Zbl 1079.03047
Alekhnovich, M. V.; Razborov, A. A.
2003
On the Caccetta-Häggkvist conjecture with forbidden subgraphs. Zbl 1273.05115
Razborov, Alexander A.
2013
Lower bounds for propositional proofs and independence results in bounded arithmetic. Zbl 1045.03524
Razborov, Alexander
1996
Resolution lower bounds for perfect matching principles. Zbl 1106.03049
Razborov, Alexander A.
2004
Natural proofs. Zbl 1345.68165
Razborov, Alexander A.; Rudich, Steven
1994
On the Fon-Der-Flaass interpretation of extremal examples for Turán’s $$(3,4)$$-problem. Zbl 1296.05099
Razborov, Alexander A.
2011
Lower bounds for polynomial calculus in the case of nonbinomial ideals. Zbl 1063.68589
Alekhnovich, M. V.; Razborov, A. A.
2001
A simple proof of Bazzi’s theorem. Zbl 1322.68108
Razborov, Alexander
2009
On the density of transitive tournaments. Zbl 1437.05086
Coregliano, Leonardo Nagami; Razborov, Alexander A.
2017
A new kind of tradeoffs in propositional proof complexity. Zbl 1394.03074
Razborov, Alexander
2016
An equivalence between second order bounded domain bounded arithmetic and first order bounded arithmetic. Zbl 0789.03046
Razborov, Alexander A.
1993
Rand-once branching programs, rectangular proofs of the pigeonhole principle and the transversal calculus. Zbl 0963.68048
Razborov, Alexander; Wigderson, Avi; Yao, Andrew
1999
Resolution lower bounds for the weak functional pigeonhole principle. Zbl 1050.03039
Razborov, Alexander A.
2003
Lower estimates of the size of schemes of bounded depth in the base $$\{$$ &,$$\vee,\oplus \}$$. Zbl 0615.94012
Razborov, A. A.
1986
Parameterized bounded-depth Frege is not optimal. Zbl 1322.68082
Beyersdorff, Olaf; Galesi, Nicola; Lauria, Massimo; Razborov, Alexander A.
2012
What is $$\ldots$$ a flag algebra? Zbl 1322.05077
Razborov, Alexander A.
2013
On the $$\mathrm{AC}^0$$ complexity of subgraph isomorphism. Zbl 1370.68135
Li, Yuan; Razborov, Alexander; Rossman, Benjamin
2017
On P versus $$\text{NP}\cap co-\text{NP}$$ for decision trees and read-once branching programs. Zbl 0941.68062
Jukna, S.; Razborov, A.; Savický, P.; Wegener, I.
1997
Lower bounds of the complexity of symmetric Boolean functions of contact- rectifier circuits. Zbl 0801.68091
Razborov, A. A.
1990
On the parameterization of solutions for equations in free groups. Zbl 0793.20028
Razborov, Alexander A.
1993
A product theorem in free groups. Zbl 1346.20061
Razborov, Alexander A.
2014
On Turán’s $$(3,4)$$-problem with forbidden subgraphs. Zbl 1310.05126
Razborov, A. A.
2014
Periodic groups and Lie algebras. Zbl 0627.17008
Adyan, S. I.; Razborov, A. A.
1987
Razborov, Alexander; Viola, Emanuele
2013
Space complexity in propositional calculus. Zbl 1296.03032
Alekhnovich, Michael; Ben-Sasson, Eli; Razborov, Alexander A.; Wigderson, Avi
2000
Lower estimates of the complexity of realization of symmetric Boolean functions by contact-value schemes. Zbl 0712.68053
Razborov, A. A.
1990
Communication complexity. Zbl 1314.68164
Razborov, Alexander A.
2011
Formulas of bounded depth in the basis (&,$$\oplus)$$ and some combinatorial problems. Zbl 0668.94017
Razborov, A. A.
1988
On the shrinkage exponent for read-once formulae. Zbl 0884.68092
Håstad, Johan; Razborov, Alexander; Yao, Andrew
1995
Read-once branching programs, rectangular proofs of the pigeonhole principle and the transversal calculus. Zbl 1027.03043
Razborov, Alexander; Wigderson, Avi; Yao, Andrew
2002
Almost Euclidean subspaces of $$l^N_1$$ via expander codes. Zbl 1192.68745
Guruswami, Venkatesan; Lee, James R.; Razborov Alexander
2008
Clique is hard on average for regular resolution. Zbl 1427.68102
Atserias, Albert; Bonacina, Ilario; de Rezende, Susanna F.; Lauria, Massimo; Nordström, Jakob; Razborov, Alexander
2018
On space and depth in resolution. Zbl 06974168
Razborov, Alexander
2018
On the width of semialgebraic proofs and algorithms. Zbl 1386.90128
Razborov, Alexander
2017
Parameterized bounded-depth Frege is not optimal. Zbl 1334.03056
Beyersdorff, Olaf; Galesi, Nicola; Lauria, Massimo; Razborov, Alexander
2011
An $$\Omega (n^{1/3})$$ lower bound for bilinear group based private information retrieval. Zbl 1213.68242
Razborov, Alexander; Yekhanin, Sergey
2007
A property of cross-intersecting families. Zbl 1109.05336
Razborov, Alexander A.; Vereshchagin, Nikolai K.
1999
Clique is hard on average for regular resolution. Zbl 1427.68102
Atserias, Albert; Bonacina, Ilario; de Rezende, Susanna F.; Lauria, Massimo; Nordström, Jakob; Razborov, Alexander
2018
On space and depth in resolution. Zbl 06974168
Razborov, Alexander
2018
Asymptotic structure of graphs with the minimum number of triangles. Zbl 1371.05147
Pikhurko, Oleg; Razborov, Alexander
2017
On the density of transitive tournaments. Zbl 1437.05086
Coregliano, Leonardo Nagami; Razborov, Alexander A.
2017
On the $$\mathrm{AC}^0$$ complexity of subgraph isomorphism. Zbl 1370.68135
Li, Yuan; Razborov, Alexander; Rossman, Benjamin
2017
On the width of semialgebraic proofs and algorithms. Zbl 1386.90128
Razborov, Alexander
2017
A new kind of tradeoffs in propositional proof complexity. Zbl 1394.03074
Razborov, Alexander
2016
Pseudorandom generators hard for $$k$$-DNF resolution and polynomial calculus resolution. Zbl 1376.03055
Razborov, Alexander A.
2015
A product theorem in free groups. Zbl 1346.20061
Razborov, Alexander A.
2014
On Turán’s $$(3,4)$$-problem with forbidden subgraphs. Zbl 1310.05126
Razborov, A. A.
2014
On the number of pentagons in triangle-free graphs. Zbl 1259.05087
Hatami, Hamed; Hladký, Jan; Král&rsquo;, Daniel; Norine, Serguei; Razborov, Alexander
2013
On the Caccetta-Häggkvist conjecture with forbidden subgraphs. Zbl 1273.05115
Razborov, Alexander A.
2013
What is $$\ldots$$ a flag algebra? Zbl 1322.05077
Razborov, Alexander A.
2013
Razborov, Alexander; Viola, Emanuele
2013
Non-three-colourable common graphs exist. Zbl 1248.05090
Hatami, Hamed; Hladký, Jan; Král&rsquo;, Daniel; Norine, Serguei; Razborov, Alexander
2012
Parameterized bounded-depth Frege is not optimal. Zbl 1322.68082
Beyersdorff, Olaf; Galesi, Nicola; Lauria, Massimo; Razborov, Alexander A.
2012
Satisfiability, branch-width and Tseitin tautologies. Zbl 1243.68182
Alekhnovich, Michael; Razborov, Alexander
2011
On the Fon-Der-Flaass interpretation of extremal examples for Turán’s $$(3,4)$$-problem. Zbl 1296.05099
Razborov, Alexander A.
2011
Communication complexity. Zbl 1314.68164
Razborov, Alexander A.
2011
Parameterized bounded-depth Frege is not optimal. Zbl 1334.03056
Beyersdorff, Olaf; Galesi, Nicola; Lauria, Massimo; Razborov, Alexander
2011
On 3-hypergraphs with forbidden 4-vertex configurations. Zbl 1223.05204
Razborov, Alexander A.
2010
The sign-rank of AC$$^0$$. Zbl 1211.68213
Razborov, Alexander A.; Sherstov, Alexander A.
2010
Diameter of polyhedra: limits of abstraction. Zbl 1226.52004
Eisenbrand, Friedrich; Hähnle, Nicolai; Razborov, Alexander; Rothvoß, Thomas
2010
A simple proof of Bazzi’s theorem. Zbl 1322.68108
Razborov, Alexander
2009
On the minimal density of triangles in graphs. Zbl 1170.05036
Razborov, Alexander A.
2008
Resolution is not automatizable unless W[P] is tractable. Zbl 1169.03044
Alekhnovich, Michael; Razborov, Alexander A.
2008
Almost Euclidean subspaces of $$l^N_1$$ via expander codes. Zbl 1192.68745
Guruswami, Venkatesan; Lee, James R.; Razborov Alexander
2008
Flag algebras. Zbl 1146.03013
Razborov, Alexander A.
2007
An $$\Omega (n^{1/3})$$ lower bound for bilinear group based private information retrieval. Zbl 1213.68242
Razborov, Alexander; Yekhanin, Sergey
2007
Why are there so many loop formulas? Zbl 1367.68036
2006
Pseudorandom generators in propositional proof complexity. Zbl 1096.03070
Alekhnovich, Michael; Ben-Sasson, Eli; Razborov, Alexander A.; Wigderson, Avi
2004
Resolution lower bounds for perfect matching principles. Zbl 1106.03049
Razborov, Alexander A.
2004
On the quantum communication complexity of symmetric predicates. Zbl 1088.68052
Razborov, A. A.
2003
Lower bounds for polynomial calculus: nonbinomial case. Zbl 1079.03047
Alekhnovich, M. V.; Razborov, A. A.
2003
Resolution lower bounds for the weak functional pigeonhole principle. Zbl 1050.03039
Razborov, Alexander A.
2003
Space complexity in propositional calculus. Zbl 1004.03047
Alekhnovich, Michael; Ben-Sasson, Eli; Razborov, Alexander A.; Wigderson, Avi
2002
Proof complexity of pigeonhole principles. Zbl 1073.03540
Razborov, Alexander A.
2002
Read-once branching programs, rectangular proofs of the pigeonhole principle and the transversal calculus. Zbl 1027.03043
Razborov, Alexander; Wigderson, Avi; Yao, Andrew
2002
Lower bounds for polynomial calculus in the case of nonbinomial ideals. Zbl 1063.68589
Alekhnovich, M. V.; Razborov, A. A.
2001
Exponential lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields. Zbl 1040.68045
Grigoriev, D.; Razborov, A.
2000
Space complexity in propositional calculus. Zbl 1296.03032
Alekhnovich, Michael; Ben-Sasson, Eli; Razborov, Alexander A.; Wigderson, Avi
2000
On P versus NP$$\cap$$co-NP for decision trees and read-once branching programs. Zbl 0962.68075
Jukna, S.; Razborov, A.; Savický, P.; Wegener, I.
1999
Rand-once branching programs, rectangular proofs of the pigeonhole principle and the transversal calculus. Zbl 0963.68048
Razborov, Alexander; Wigderson, Avi; Yao, Andrew
1999
A property of cross-intersecting families. Zbl 1109.05336
Razborov, Alexander A.; Vereshchagin, Nikolai K.
1999
Lower bounds for the polynomial calculus. Zbl 1026.03043
Razborov, Alexander A.
1998
Improved lower bounds on the rigidity of Hadamard matrices. Zbl 0917.15013
Kashin, B. S.; Razborov, A. A.
1998
Neither reading few bits twice nor reading illegally helps much. Zbl 0903.68074
Jukna, S.; Razborov, A.
1998
Natural proofs. Zbl 0884.68055
Razborov, Alexander A.; Rudich, Steven
1997
Proof complexity in algebraic systems and bounded depth Frege systems with modular counting. Zbl 0890.03030
Buss, S.; Impagliazzo, R.; Krajíček, J.; Pudlák, P.; Razborov, A. A.; Sgall, J.
1997
On P versus $$\text{NP}\cap co-\text{NP}$$ for decision trees and read-once branching programs. Zbl 0941.68062
Jukna, S.; Razborov, A.; Savický, P.; Wegener, I.
1997
Lower bounds for propositional proofs and independence results in bounded arithmetic. Zbl 1045.03524
Razborov, Alexander
1996
Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic. Zbl 0838.03045
Razborov, A. A.
1995
Bounded arithmetic and lower bounds in Boolean complexity. Zbl 0838.03044
Razborov, Alexander A.
1995
On systems of equations in free groups. Zbl 0848.20018
Razborov, Alexander A.
1995
On the shrinkage exponent for read-once formulae. Zbl 0884.68092
Håstad, Johan; Razborov, Alexander; Yao, Andrew
1995
Natural proofs. Zbl 1345.68165
Razborov, Alexander A.; Rudich, Steven
1994
On lower bounds for read-$$k$$-times branching programs. Zbl 0777.68043
Borodin, A.; Razborov, A.; Smolensky, R.
1993
$$n^{{\Omega{}}(\log{} n)}$$ lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom. Zbl 0783.68046
Razborov, Alexander; Wigderson, Avi
1993
Constructing small sets that are uniform in arithmetic progressions. Zbl 0799.11022
Razborov, A.; Szemerédi, E.; Wigderson, A.
1993
An equivalence between second order bounded domain bounded arithmetic and first order bounded arithmetic. Zbl 0789.03046
Razborov, Alexander A.
1993
On the parameterization of solutions for equations in free groups. Zbl 0793.20028
Razborov, Alexander A.
1993
On the distributional complexity of disjointness. Zbl 0787.68055
Razborov, A. A.
1992
Majority gates vs. general weighted threshold gates. Zbl 0770.68054
Goldmann, Mikael; Håstad, Johan; Razborov, Alexander
1992
The gap between the chromatic number of a graph and the rank of its adjacency matrix is superlinear. Zbl 0776.05073
Razborov, A. A.
1992
On submodular complexity measures. Zbl 0770.68073
Razborov, A. A.
1992
The set of minimal braids is Co-NP-complete. Zbl 0726.68047
Paterson, M. S.; Razborov, A. A.
1991
Applications of matrix methods to the theory of lower bounds in computational complexity. Zbl 0717.68049
Razborov, A. A.
1990
On the distributional complexity of disjointness. Zbl 0765.68056
Razborov, A. A.
1990
Lower bounds of the complexity of symmetric Boolean functions of contact- rectifier circuits. Zbl 0801.68091
Razborov, A. A.
1990
Lower estimates of the complexity of realization of symmetric Boolean functions by contact-value schemes. Zbl 0712.68053
Razborov, A. A.
1990
Formulas of bounded depth in the basis (&,$$\oplus)$$ and some combinatorial problems. Zbl 0668.94017
Razborov, A. A.
1988
Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Zbl 0632.94030
Razborov, A. A.
1987
Periodic groups and Lie algebras. Zbl 0627.17008
Adyan, S. I.; Razborov, A. A.
1987
Lower estimates of the size of schemes of bounded depth in the base $$\{$$ &,$$\vee,\oplus \}$$. Zbl 0615.94012
Razborov, A. A.
1986
Lower bounds for the monotone complexity of some Boolean functions. Zbl 0621.94027
Razborov, A. A.
1985
On systems of equations in a free group. Zbl 0579.20019
Razborov, A. A.
1985
Lower bounds on monotone complexity of the logical permanent. Zbl 0584.94026
Razborov, A. A.
1985
all top 5

#### Cited by 1,055 Authors

 24 Yukna, Stasys P. 23 Razborov, Aleksandr Aleksandrovich 20 Pikhurko, Oleg 19 Pudlák, Pavel 18 Král’, Daniel 14 Pitassi, Toniann 13 Lauria, Massimo 13 Myasnikov, Alexei G. 13 Sherstov, Alexander A. 13 Wigderson, Avi 12 Krajíček, Jan 11 Atserias, Albert 11 Lidický, Bernard 10 Galesi, Nicola 10 Nordström, Jakob 9 Alon, Noga M. 9 Impagliazzo, Russell 9 Kabanets, Valentine 9 Linial, Nathan 9 Sudakov, Benny 9 Thérien, Denis 9 Viola, Emanuele 8 Allender, Eric W. 8 Beyersdorff, Olaf 8 Bollig, Beate 8 Buss, Samuel R. 8 Göös, Mika 8 Itsykson, Dmitry M. 8 Kharlampovich, Olga G. 8 Wegener, Ingo 7 Ablaev, Farid M. 7 Ambainis, Andris 7 Braverman, Mark 7 Lovett, Shachar 7 Meir, Or 7 Pfender, Florian 7 Raz, Ran 7 Santhanam, Rahul 7 Volec, Jan 6 Chattopadhyay, Arkadev 6 Fox, Jacob 6 Gál, Anna 6 Hladký, Jan 6 Hromkovič, Juraj 6 Hrubeš, Pavel 6 Hu, Ping 6 Mix Barrington, David A. 6 Müller, Moritz 6 Podol’skiĭ, Vladimir Vladimirovich 6 Rodl, Vojtech 6 Schnitger, Georg 6 Servedio, Rocco A. 6 Szeider, Stefan 6 Thapen, Neil 5 Alekhnovich, Michael 5 Balogh, József 5 Beame, Paul W. 5 Diekert, Volker 5 Filmus, Yuval 5 Gao, Wei 5 Grzesik, Andrzej 5 Hatami, Hamed 5 Hirsch, Edward A. 5 Huang, Hao 5 Jain, Rahul 5 Li, Zhongshan 5 Liu, Hong 5 Mahajan, Meena 5 Mubayi, Dhruv 5 Norin, Sergey 5 Pokutta, Sebastian 5 Santos, Francisco 5 Shraibman, Adi 5 Williams, Richard Ryan 4 Andreev, Alexander E. 4 Beigel, Richard 4 Beimel, Amos 4 Braun, Gábor 4 Conlon, David 4 Cook, Stephen Arthur 4 Falgas-Ravry, Victor 4 Fiorini, Samuel 4 Furedi, Zoltan 4 Gao, Yubin 4 Gerbner, Dániel 4 Goldmann, Mikael 4 Grigor’ev, Dmitriĭ Yur’evich 4 Hansen, Kristoffer Arnsfelt 4 Jing, Guangming 4 Kamath, Pritish 4 Kayal, Neeraj 4 Kolokolova, Antonina 4 Krause, Matthias 4 Kulikov, Alexander S. 4 Maciel, Alexis 4 Meka, Raghu 4 Naves, Humberto 4 Saks, Michael E. 4 Sauerhoff, Martin 4 Savický, Petr ...and 955 more Authors
all top 5

#### Cited in 133 Serials

 85 Theoretical Computer Science 60 Computational Complexity 59 Journal of Computer and System Sciences 45 Information Processing Letters 38 SIAM Journal on Computing 28 Information and Computation 26 Journal of Combinatorial Theory. Series B 25 Theory of Computing Systems 22 Combinatorica 21 Annals of Pure and Applied Logic 21 Combinatorics, Probability and Computing 18 Discrete Mathematics 17 European Journal of Combinatorics 17 Algorithmica 13 Discrete Applied Mathematics 11 Journal of Graph Theory 9 SIAM Journal on Discrete Mathematics 9 International Journal of Algebra and Computation 8 Discrete & Computational Geometry 7 Israel Journal of Mathematics 7 Advances in Mathematics 7 Journal of Algebra 7 Journal of Cryptology 7 Archive for Mathematical Logic 7 Mathematical Programming. Series A. Series B 7 Journal of Mathematical Sciences (New York) 6 Artificial Intelligence 6 Transactions of the American Mathematical Society 6 Linear Algebra and its Applications 6 The Electronic Journal of Combinatorics 6 Journal of the ACM 6 RAIRO. Theoretical Informatics and Applications 6 ACM Transactions on Computational Logic 6 Logical Methods in Computer Science 5 Mathematical Notes 5 Journal of Combinatorial Theory. Series A 5 Graphs and Combinatorics 5 Mathematical Logic Quarterly (MLQ) 4 Journal of Statistical Physics 4 Journal of Pure and Applied Algebra 4 The Journal of Symbolic Logic 4 Annals of Mathematics. Second Series 4 Theory of Computing 3 Russian Mathematical Surveys 3 Proceedings of the American Mathematical Society 3 Journal of Symbolic Computation 3 Random Structures & Algorithms 3 Geometric and Functional Analysis. GAFA 3 Bulletin of the American Mathematical Society. New Series 3 Distributed Computing 3 The Bulletin of Symbolic Logic 3 Lobachevskii Journal of Mathematics 3 Theory and Practice of Logic Programming 3 Algebraic Combinatorics 2 Mathematical Proceedings of the Cambridge Philosophical Society 2 Czechoslovak Mathematical Journal 2 Inventiones Mathematicae 2 Journal of Functional Analysis 2 Mathematics of Operations Research 2 Mathematical Systems Theory 2 Memoirs of the American Mathematical Society 2 Notre Dame Journal of Formal Logic 2 Operations Research Letters 2 Journal of Automated Reasoning 2 International Journal of Approximate Reasoning 2 Neural Computation 2 MSCS. Mathematical Structures in Computer Science 2 Designs, Codes and Cryptography 2 SIAM Review 2 Journal of Applied Non-Classical Logics 2 Top 2 Journal of Combinatorial Optimization 2 Journal of Mathematical Cryptology 2 Diskretnyĭ Analiz i Issledovanie Operatsiĭ 2 Bulletin of Mathematical Sciences 2 Journal of Siberian Federal University. Mathematics & Physics 2 Matematicheskie Voprosy Kriptografii 1 Communications in Algebra 1 Journal of Mathematical Physics 1 Linear and Multilinear Algebra 1 Algebra and Logic 1 The Annals of Statistics 1 Applied Mathematics and Computation 1 Duke Mathematical Journal 1 Illinois Journal of Mathematics 1 Journal of Applied Probability 1 Journal of Economic Theory 1 Studia Logica 1 Synthese 1 Physica D 1 Probability Theory and Related Fields 1 Journal of the American Mathematical Society 1 Computational Mathematics and Modeling 1 JETAI. Journal of Experimental & Theoretical Artificial Intelligence 1 Differential Geometry and its Applications 1 Games and Economic Behavior 1 SIAM Journal on Mathematical Analysis 1 RAIRO. Informatique Théorique et Applications 1 Annales de la Faculté des Sciences de Toulouse. Mathématiques. Série VI 1 Experimental Mathematics ...and 33 more Serials
all top 5

#### Cited in 38 Fields

 564 Computer science (68-XX) 234 Combinatorics (05-XX) 159 Mathematical logic and foundations (03-XX) 128 Information and communication theory, circuits (94-XX) 53 Group theory and generalizations (20-XX) 48 Operations research, mathematical programming (90-XX) 27 Convex and discrete geometry (52-XX) 23 Number theory (11-XX) 22 Quantum theory (81-XX) 19 Linear and multilinear algebra; matrix theory (15-XX) 18 Order, lattices, ordered algebraic structures (06-XX) 18 Probability theory and stochastic processes (60-XX) 12 Algebraic geometry (14-XX) 12 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 8 Commutative algebra (13-XX) 6 Manifolds and cell complexes (57-XX) 5 Field theory and polynomials (12-XX) 5 Statistical mechanics, structure of matter (82-XX) 4 Statistics (62-XX) 4 Numerical analysis (65-XX) 3 History and biography (01-XX) 3 Topological groups, Lie groups (22-XX) 3 Dynamical systems and ergodic theory (37-XX) 3 Geometry (51-XX) 3 Algebraic topology (55-XX) 2 General algebraic systems (08-XX) 2 Real functions (26-XX) 2 Harmonic analysis on Euclidean spaces (42-XX) 2 Abstract harmonic analysis (43-XX) 2 Functional analysis (46-XX) 2 Differential geometry (53-XX) 2 Global analysis, analysis on manifolds (58-XX) 2 Biology and other natural sciences (92-XX) 1 General and overarching topics; collections (00-XX) 1 Associative rings and algebras (16-XX) 1 Nonassociative rings and algebras (17-XX) 1 Measure and integration (28-XX) 1 Approximations and expansions (41-XX)

#### Wikidata Timeline

The data are displayed as stored in Wikidata under a Creative Commons CC0 License. Updates and corrections should be made in Wikidata.