Alexander Razborov

Alexander Razborov's AcademicInfluence.com Rankings

Alexander Razborov

Mathematics

#1508

World Rank

#2458

Historical Rank

Complexity Theory

#11

World Rank

#11

Historical Rank

Measure Theory

#1914

World Rank

#2332

Historical Rank

mathematics Degrees

Download Badge

Mathematics

Why Is Alexander Razborov Influential?

(Suggest an Edit or Addition)

According to Wikipedia, Aleksandr Aleksandrovich Razborov , sometimes known as Sasha Razborov, is a Soviet and Russian mathematician and computational theorist. He is Andrew McLeish Distinguished Service Professor at the University of Chicago.

(See a Problem?)

Alexander Razborov's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

Communication Complexity (2011) (975)
Natural proofs (1994) (585)
On the Distributional Complexity of Disjointness (1992) (520)
Lower bounds on the size of bounded depth circuits over a complete basis with logical addition (1987) (502)
Majority gates vs. general weighted threshold gates (1992) (238)
Quantum communication complexity of symmetric predicates (2002) (199)
Lower bounds for the polynomial calculus (1998) (190)
ON SYSTEMS OF EQUATIONS IN A FREE GROUP (1985) (160)
Space complexity in propositional calculus (2000) (158)
Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic (1995) (150)
Lower bounds for polynomial calculus: non-binomial case (2001) (149)
On 3-Hypergraphs with Forbidden 4-Vertex Configurations (2010) (141)
Complexity of Propositional Proofs (2010) (139)
Applications of matrix methods to the theory of lower bounds in computational complexity (1990) (132)
On the number of pentagons in triangle-free graphs (2011) (131)
Resolution is not automatizable unless W[P] is tractable (2001) (128)
Why are there so many loop formulas? (2006) (125)
Lower Bounds for Deterministic and Nondeterministic Branching Programs (1991) (118)
Pseudorandom generators in propositional proof complexity (2000) (115)
On provably disjoint NP-pairs (1994) (115)
Bounded Arithmetic and Lower Bounds in Boolean Complexity (1995) (115)
Lower bounds on monotone complexity of the logical permanent (1985) (97)
On the method of approximations (1989) (96)
Resolution lower bounds for perfect matching principles (2002) (91)
On the Minimal Density of Triangles in Graphs (2008) (86)
Satisfiability, Branch-Width and Tseitin tautologies (2002) (81)
The Sign-Rank of AC0 (2010) (80)
Pseudorandom generators hard for $k$-DNF resolution and polynomial calculus resolution (2015) (80)
On lower bounds for read-k-times branching programs (2005) (77)
The Sign-Rank of AC^O (2008) (73)
Exponential Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions over Finite Fields (2000) (67)
Proof complexity in algebraic systems and bounded depth Frege systems with modular counting (1997) (64)
The Set of Minimal Braids is co-NP-Complete (1991) (61)
Non-Three-Colourable Common Graphs Exist (2011) (60)
Proof Complexity of Pigeonhole Principles (2001) (57)
On Small Depth Threshold Circuits (1992) (56)
Resolution lower bounds for the weak functional pigeonhole principle (2003) (52)
Almost Euclidean subspaces of e N 1 via expander codes (2008) (50)
Diameter of polyhedra: limits of abstraction (2009) (50)
The Sign-rank of Ac (2008) (49)
A Simple Proof of Bazzi’s Theorem (2009) (47)
n^Omega(log n) Lower Bounds on the Size of Depth-3 Threshold Circuits with AND Gates at the Bottom (1993) (46)
Read-once branching programs, rectangular proofs of the pigeonhole principle and the transversal calculus (1997) (43)
Lower Bounds for Propositional Proofs and Independence Results in Bounded Arithmetic (1996) (42)
Asymptotic Structure of Graphs with the Minimum Number of Triangles (2012) (41)
On submodular complexity measures (1992) (38)
Flag Algebras: An Interim Report (2013) (38)
Exponential complexity lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields (1998) (37)
On the Caccetta–Häggkvist Conjecture with Forbidden Subgraphs (2011) (37)
On P versus NP $ \cap $ co-NP for decision trees and read-once branching programs (1997) (37)
Improved lower bounds on the rigidity of Hadamard matrices (1998) (37)
On the Width of Semi-Algebraic Proofs and Algorithms (2017) (36)
Improved Resolution Lower Bounds for the Weak Pigeonhole Principle (2001) (36)
The gap between the chromatic number of a graph and the rank of its adjacency matrix is superlinear (1992) (35)
Guest Column: Proof Complexity and Beyond (2016) (34)
Andrei Nikolaevich Kolmogorov (1903–1987) (1990) (34)
Neither Reading Few Bits Twice Nor Reading Illegally Helps Much (1998) (34)
Constructing Small Sets that are Uniform in Arithmetic Progressions (1993) (33)
Almost Euclidean subspaces of ℓ1N VIA expander codes (2007) (33)
Notions of computability at higher types I (2016) (31)
On the Density of Transitive Tournaments (2015) (30)
An upper bound on the threshold quantum decoherence rate (2003) (30)
A product theorem in free groups (2014) (29)
Parameterized Bounded-Depth Frege Is not Optimal (2011) (25)
Real Advantage (2013) (24)
On the AC0 Complexity of Subgraph Isomorphism (2014) (24)
On the Fon-Der-Flaass interpretation of extremal examples for Turán’s (3, 4)-problem (2010) (22)
Clique is hard on average for regular resolution (2018) (21)
An \Omega(n^1/3 ) Lower Bound for Bilinear Group Based Private Information Retrieval (2006) (19)
A New Kind of Tradeoffs in Propositional Proof Complexity (2016) (19)
On the Distributional Complexity of Disjontness (1990) (19)
Periodic groups and Lie algebras (1987) (17)
Lower bounds of the complexity of symmetric boolean functions of contact-rectifier circuits (1990) (16)
What is... a flag algebra (2013) (15)
On the Shrinkage Exponent for Read-Once Formulae (1995) (13)
An Ω ( n 1 / 3 ) Lower Bound for Bilinear Group Based Private Information Retrieval (2006) (13)
Analytic and pseudo-analytic structures (2016) (11)
Polynomial to exponential transition in Ramsey theory (2019) (10)
Almost Euclidean subspaces of $\ell_1^N$ via expander codes. (2007) (9)
On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution (2009) (9)
Propositional proof complexity (2003) (9)
On Space and Depth in Resolution (2018) (8)
Proof Complexity and Beyond (2018) (7)
The future of computational complexity theory: part I (1996) (7)
Semantic limits of dense combinatorial objects (2019) (7)
On CDCL-Based Proof Systems with the Ordered Decision Strategy (2019) (6)
On Turán’s (3,4)-problem with forbidden subgraphs (2014) (6)
On the Parameterization of solutions for equations in Free Groups (1993) (6)
Новые нижние оценки устойчивости матриц Адамара@@@Improved lower bounds on the rigidity of Hadamard matrices (1998) (6)
An Omega(n1/3) Lower Bound for Bilinear Group Based Private Information Retrieval (2007) (6)
An Ω(n) Lower Bound for Bilinear Group Based Private Information Retrieval (2008) (5)
Space characterizations of complexity measures and size-space trade-offs in propositional proof systems (2023) (5)
Read-Once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and the Transversal Calculus (2002) (5)
A two-dimensional tree ideal (2016) (5)
Lower Bounds for Propositional Proofs and Independence Results in Bounded Arithmetic (Abstract) (1995) (4)
One Property of Cross-Intersecting Families (1999) (4)
Upper and lower bounds for nilpotency classes of Lie algebras with Engel conditions (1989) (4)
On Small Size Approximation Models (2013) (3)
On Turan's (3,4)-problem with forbidden configurations (2012) (3)
An Ultimate Trade-Off in Propositional Proof Complexity (2015) (3)
Guessing More Secrets via List Decoding (2005) (3)
Natural quasirandomness properties (2020) (3)
Biregularity in Sidorenko's Conjecture (2021) (3)
More about sparse halves in triangle-free graphs (2021) (3)
COMMUNICATIONS OF THE MOSCOW MATHEMATICAL SOCIETY: Lower estimates of the dimension of schemes of bounded depth in the basis \{\&,\vee,\oplus\} (1986) (3)
Review: Michael Alekhnovich, Sam Buss, Shlomo Moran, Toniann Pitassi, Minimum Propositional Proof Length Is NP-Hard to Linearly Approximate (2002) (2)
Improved Convergence Guarantees for Shallow Neural Networks (2022) (1)
Quantum Computing (1)
Logic Colloquium 2000 : proceedings of the Annual European Summer Meeting of the Association for Symbolic Logic, held in Paris, France, July 23-31, 2000 (2016) (1)
Семантические пределы плотных комбинаторных объектов (2020) (1)
Sergei Ivanovich Adian (on his eightieth birthday) (2011) (1)
Computer Science - Theory and Applications, Third International Computer Science Symposium in Russia, CSR 2008, Moscow, Russia, June 7-12, 2008, Proceedings (2008) (1)
Еще раз о разреженных вершинных полуграфах в графах без треугольников (2021) (1)
Logic Colloquium 2000 (hardcover) : Lecture Notes in Logic, 19 (2005) (1)
Some Results in Circuit Complexity (2014) (1)
Сергей Иванович Адян (к восьмидесятилетию со дня рождения)@@@Sergei Ivanovich Adian (on his eightieth birthday) (2011) (0)
Sergei Ivanovich Adian (2021) (0)
Surveys in Modern Mathematics: Foundations of computational complexity theory (2005) (0)
Feasible proofs and computations: partnership and fusion (2004) (0)
Timed Modal Specifications........ 8 (0)
The Ackermann Award 2009 (2009) (0)
Model theory and geometry (2016) (0)
Themes Complexity Theory ’ 94 In the months of August and September , 1994 (0)
La Sorbonne, Paris, France, July 23–31, 2000 (2001) (0)
Sergei Ivanovich Adian (on his 75th birthday) (2006) (0)
Hilbert's wide program (2016) (0)
Computational complexity: counting, evasiveness, and isolation (2010) (0)
Improved Lower Bounds on the Rigidity ofHadamard Matri esBoris (1998) (0)
On Space and Depth in Resolution (2017) (0)
C O ] 2 M ay 2 01 1 NON-THREE-COLORABLE COMMON GRAPHS EXIST (2013) (0)
Nine Papers from the International Congress of Mathematicians 1986 (1990) (0)
On the AC 0 Complexity of Subgraph Isomorphism Yuan Li (2014) (0)
2000 European Summer Meeting of the Association for Symbolic Logic Logic Colloquium 2000 (2001) (0)
Maurice Boffa (1939–2001) (2016) (0)
On The Method of À pproximations À (0)
Psychology looks hopefully to logic (2016) (0)
0 A pr 2 00 2 Quantum Communication Complexity of Symmetric Predicates (2003) (0)
Quasirandom Structures (2017) (0)
Eulogy: Michael (Misha) Alekhnovich 1978-2006 (2007) (0)
Alekhnovich Michael, Buss Sam, Moran Shlomo, and Pitassi Toniann. Minimum propositional proof length is NP-hard to linearly approximate. The journal of symbolic logic , vol. 66 (2001), pp. 171–191. (2002) (0)
Akademiai Kiad6 -Springer-Verlag APPLICATIONS OF MATRIX METHODS ÒÎ ÒÍÅ THEORY OF LOWER BOUNDS IN COMPUTATIONAL COMPLEXITY À. À. RAZBOROV (1988) (0)
A NORMAL FORM THEOREMFOR SECOND-ORDER CLASSICAL LOGICWITH AN AXIOM OF CHOICE (2017) (0)
Special Issue In Memory of Misha Alekhnovich. Foreword (2011) (0)
Proof complexity and feasible arithmetics, DIMACS workshop, April 21–24, 1996 , edited by Beame Paul W. and Buss Samuel R., Series in discrete mathematics and theoretical computer science, vol. 39, American Mathematical Society, Providence 1998, xii + 320 pp. (1999) (0)
2010 north american annual meeting of the association for symbolic logic (2011) (0)
Diameter of Polyhedra : Limits of Abstraction Friedrich Eisenbrand (2010) (0)
The Ackermann Award 2005 (2005) (0)
The P \mathop = \limits^? NP-Problem: A View from the 1990s (2006) (0)
On Turán’s (3,4)-problem with forbidden subgraphs (2014) (0)
Testing Properties of Boolean Functions : Lower Bounds on Testing Fourier Degree (2011) (0)
An extremal problem motivated by triangle-free strongly regular graphs (2020) (0)
K. Jon Barwise (1942-2000) (2016) (0)
Proceedings of the 3rd international conference on Computer science: theory and applications (2008) (0)
Сергей Иванович Адян (к 75-летию со дня рождения)@@@Sergei Ivanovich Adian (on his 75th birthday) (2006) (0)
Международная школа-конференция “Теория рекурсий и теория сложности” (WRTCT'97)@@@International School-Conference “Recursion Theory and Theory of Complexity” (WRTCT'97) (1997) (0)
Сергей Иванович Адян (некролог) (2021) (0)
Вопросы алгебры и математической логики. Научное наследие С. И. Адяна (2021) (0)
Чувствительность булевых функций (2020) (0)
Questions in algebra and mathematical logic. Scientific heritage of S. I. Adian (2021) (0)

This paper list is powered by the following services:

Other Resources About Alexander Razborov

What Schools Are Affiliated With Alexander Razborov?

Alexander Razborov is affiliated with the following schools:

Alexander Razborov's Academic­Influence.com Rankings

Why Is Alexander Razborov Influential?

Alexander Razborov's Published Works

Published Works

Other Resources About Alexander Razborov

What Schools Are Affiliated With Alexander Razborov?

Alexander Razborov's AcademicInfluence.com Rankings