Alexander A. Razborov

From MaRDI portal
Person:1370854

Available identifiers

zbMath Open razborov.alexander-aWikidataQ93019 ScholiaQ93019MaRDI QIDQ1370854

List of research outcomes

PublicationDate of PublicationType
Propositional proof complexity2023-11-10Paper
Natural quasirandomness properties2023-10-17Paper
Space characterizations of complexity measures and size-space trade-offs in propositional proof systems2023-07-10Paper
On small depth threshold circuits2022-12-09Paper
Clique Is Hard on Average for Regular Resolution2022-12-08Paper
On CDCL-Based Proof Systems with the Ordered Decision Strategy2022-08-25Paper
An extremal problem motivated by triangle-free strongly regular graphs2022-04-27Paper
More about sparse halves in triangle-free graphs2022-03-28Paper
Biregularity in Sidorenko's Conjecture2021-08-14Paper
Questions in algebra and mathematical logic. Scientific heritage of S. I. Adian2021-06-04Paper
Sergei Ivanovich Adian2021-06-04Paper
Polynomial to exponential transition in Ramsey theory2021-05-14Paper
On CDCL-based proof systems with the ordered decision strategy2021-04-07Paper
Semantic limits of dense combinatorial objects2020-12-03Paper
Clique is hard on average for regular resolution2019-08-22Paper
On space and depth in resolution2018-11-07Paper
A New Kind of Tradeoffs in Propositional Proof Complexity2018-08-02Paper
On the Width of Semialgebraic Proofs and Algorithms2017-12-07Paper
Asymptotic Structure of Graphs with the Minimum Number of Triangles2017-10-10Paper
Why are there so many loop formulas?2017-07-12Paper
On the Density of Transitive Tournaments2017-06-30Paper
On the $AC^0$ Complexity of Subgraph Isomorphism2017-05-30Paper
Natural proofs2016-09-01Paper
Propositional proof complexity2015-12-07Paper
Die Komplexität der Kommunikation2015-10-29Paper
WHAT IS... a Flag Algebra?2015-10-14Paper
A Simple Proof of Bazzi’s Theorem2015-09-24Paper
Parameterized Bounded-Depth Frege Is not Optimal2015-09-24Paper
Real Advantage2015-09-24Paper
Communication Complexity2015-06-26Paper
On Turán's \((3,4)\)-problem with forbidden subgraphs2015-05-08Paper
Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution2015-02-09Paper
Space complexity in propositional calculus2014-09-26Paper
On the Fon-Der-Flaass interpretation of extremal examples for Turán's \((3,4)\)-problem2014-08-04Paper
A product theorem in free groups.2014-04-14Paper
On the Caccetta-Häggkvist Conjecture with Forbidden Subgraphs2013-10-21Paper
On the number of pentagons in triangle-free graphs2013-03-06Paper
Non-Three-Colourable Common Graphs Exist2012-09-12Paper
Satisfiability, branch-width and Tseitin tautologies2012-06-26Paper
Special issue in memory of Misha Alekhnovich. Foreword2012-06-26Paper
Parameterized Bounded-Depth Frege Is Not Optimal2011-07-06Paper
On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution2011-07-06Paper
Sergei Ivanovich Adian (on his eightieth birthday)2011-06-17Paper
On 3-Hypergraphs with Forbidden 4-Vertex Configurations2011-06-17Paper
https://portal.mardi4nfdi.de/entity/Q30027892011-05-24Paper
Diameter of Polyhedra: Limits of Abstraction2011-04-27Paper
The Sign-Rank of AC$^0$2010-11-04Paper
Almost Euclidean subspaces of \ell_1^N via expander codes2010-08-06Paper
Complexity of Propositional Proofs2010-06-22Paper
The Ackermann Award 20092009-11-12Paper
Resolution Is Not Automatizable Unless W[P Is Tractable]2009-08-20Paper
On the Minimal Density of Triangles in Graphs2008-09-29Paper
https://portal.mardi4nfdi.de/entity/Q35224792008-09-03Paper
Flag algebras2008-02-25Paper
https://portal.mardi4nfdi.de/entity/Q34339022007-04-23Paper
https://portal.mardi4nfdi.de/entity/Q57033792005-11-08Paper
https://portal.mardi4nfdi.de/entity/Q57026302005-11-02Paper
Guessing More Secrets via List Decoding2005-10-27Paper
Automata, Languages and Programming2005-08-24Paper
https://portal.mardi4nfdi.de/entity/Q46818892005-06-08Paper
Quantum communication complexity of symmetric predicates2005-05-17Paper
Pseudorandom Generators in Propositional Proof Complexity2005-02-21Paper
Resolution lower bounds for perfect matching principles2004-10-04Paper
https://portal.mardi4nfdi.de/entity/Q48188232004-09-24Paper
https://portal.mardi4nfdi.de/entity/Q47378992004-08-11Paper
Lower bounds for polynomial calculus in the case of nonbinomial ideals.2004-06-15Paper
Read-once branching programs, rectangular proofs of the pigeonhole principle and the transversal calculus2003-12-14Paper
Lower bounds for the polynomial calculus2003-12-07Paper
Resolution lower bounds for the weak functional pigeonhole principle.2003-08-17Paper
Space Complexity in Propositional Calculus2002-09-29Paper
https://portal.mardi4nfdi.de/entity/Q45270432001-03-01Paper
On P versus NP\(\cap\)co-NP for decision trees and read-once branching programs2000-11-20Paper
Exponential lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields.2000-08-08Paper
https://portal.mardi4nfdi.de/entity/Q46993081999-11-10Paper
Improved lower bounds on the rigidity of Hadamard matrices1999-03-15Paper
Neither reading few bits twice nor reading illegally helps much1998-08-20Paper
Proof complexity in algebraic systems and bounded depth Frege systems with modular counting1998-06-29Paper
Natural proofs1997-12-03Paper
On the shrinkage exponent for read-once formulae1997-09-29Paper
https://portal.mardi4nfdi.de/entity/Q27855681997-09-07Paper
https://portal.mardi4nfdi.de/entity/Q48505541996-06-06Paper
https://portal.mardi4nfdi.de/entity/Q48670931996-02-26Paper
Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic1996-02-25Paper
Constructing Small Sets that are Uniform in Arithmetic Progressions1994-11-20Paper
ON THE PARAMETERIZATION OF SOLUTIONS FOR EQUATIONS IN FREE GROUPS1994-08-14Paper
https://portal.mardi4nfdi.de/entity/Q31406401993-12-05Paper
On lower bounds for read-\(k\)-times branching programs1993-08-30Paper
Majority gates vs. general weighted threshold gates1993-08-08Paper
\(n^{{\Omega{}}(\log{} n)}\) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom1993-06-29Paper
https://portal.mardi4nfdi.de/entity/Q40367011993-05-18Paper
https://portal.mardi4nfdi.de/entity/Q40386961993-05-18Paper
On the distributional complexity of disjointness1993-04-22Paper
The gap between the chromatic number of a graph and the rank of its adjacency matrix is superlinear1993-01-17Paper
https://portal.mardi4nfdi.de/entity/Q40000011992-09-18Paper
Lower bounds of the complexity of symmetric Boolean functions of contact- rectifier circuits1992-06-25Paper
Applications of matrix methods to the theory of lower bounds in computational complexity1990-01-01Paper
https://portal.mardi4nfdi.de/entity/Q31973331990-01-01Paper
https://portal.mardi4nfdi.de/entity/Q52021461990-01-01Paper
https://portal.mardi4nfdi.de/entity/Q38267191989-01-01Paper
https://portal.mardi4nfdi.de/entity/Q38220971988-01-01Paper
Lower bounds on the size of bounded depth circuits over a complete basis with logical addition1987-01-01Paper
Periodic groups and Lie algebras1987-01-01Paper
https://portal.mardi4nfdi.de/entity/Q38221001987-01-01Paper
Lower estimates of the dimension of schemes of bounded depth in the basis $ \{\&,\vee,\oplus\}$1986-01-01Paper
https://portal.mardi4nfdi.de/entity/Q47245491986-01-01Paper
Lower bounds on monotone complexity of the logical permanent1985-01-01Paper
ON SYSTEMS OF EQUATIONS IN A FREE GROUP1985-01-01Paper
https://portal.mardi4nfdi.de/entity/Q37587291985-01-01Paper

Research outcomes over time


Doctoral students

No records found.


Known relations from the MaRDI Knowledge Graph

PropertyValue
MaRDI profile typeMaRDI person profile
instance ofhuman


This page was built for person: Alexander A. Razborov