| Publication | Date of Publication | Type |
|---|
| Exponential complexity lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields | 2025-10-29 | Paper |
| Space characterizations of complexity measures and size-space trade-offs in propositional proof systems | 2024-06-24 | Paper |
Propositional proof complexity
European Congress of Mathematics | 2023-11-10 | Paper |
Natural quasirandomness properties
Random Structures & Algorithms | 2023-10-17 | Paper |
Space characterizations of complexity measures and size-space trade-offs in propositional proof systems
Journal of Computer and System Sciences | 2023-07-10 | Paper |
On small depth threshold circuits
Algorithm Theory — SWAT '92 | 2022-12-09 | Paper |
Clique Is Hard on Average for Regular Resolution
Journal of the ACM | 2022-12-08 | Paper |
On CDCL-Based Proof Systems with the Ordered Decision Strategy
SIAM Journal on Computing | 2022-08-25 | Paper |
An extremal problem motivated by triangle-free strongly regular graphs
Journal of Combinatorial Theory. Series B | 2022-04-27 | Paper |
More about sparse halves in triangle-free graphs
Sbornik: Mathematics | 2022-03-28 | Paper |
| Biregularity in Sidorenko's Conjecture | 2021-08-14 | Paper |
Questions in algebra and mathematical logic. Scientific heritage of S. I. Adian
Russian Mathematical Surveys | 2021-06-04 | Paper |
Sergei Ivanovich Adian
Russian Mathematical Surveys | 2021-06-04 | Paper |
Polynomial to exponential transition in Ramsey theory
Proceedings of the London Mathematical Society | 2021-05-14 | Paper |
On CDCL-based proof systems with the ordered decision strategy
(available as arXiv preprint) | 2021-04-07 | Paper |
Semantic limits of dense combinatorial objects
Russian Mathematical Surveys | 2020-12-03 | Paper |
Clique is hard on average for regular resolution
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing | 2019-08-22 | Paper |
On space and depth in resolution
Computational Complexity | 2018-11-07 | Paper |
A new kind of tradeoffs in propositional proof complexity
Journal of the ACM | 2018-08-02 | Paper |
On the width of semialgebraic proofs and algorithms
Mathematics of Operations Research | 2017-12-07 | Paper |
Asymptotic structure of graphs with the minimum number of triangles
Combinatorics, Probability and Computing | 2017-10-10 | Paper |
Why are there so many loop formulas?
ACM Transactions on Computational Logic | 2017-07-12 | Paper |
On the density of transitive tournaments
Journal of Graph Theory | 2017-06-30 | Paper |
On the \(\mathrm{AC}^0\) complexity of subgraph isomorphism
SIAM Journal on Computing | 2017-05-30 | Paper |
Natural proofs
Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 | 2016-09-01 | Paper |
Propositional proof complexity
Journal of the ACM | 2015-12-07 | Paper |
Die Komplexität der Kommunikation
Eine Einladung in die Mathematik | 2015-10-29 | Paper |
WHAT IS... a Flag Algebra?
Notices of the American Mathematical Society | 2015-10-14 | Paper |
A simple proof of Bazzi's theorem
ACM Transactions on Computation Theory | 2015-09-24 | Paper |
Parameterized bounded-depth Frege is not optimal
ACM Transactions on Computation Theory | 2015-09-24 | Paper |
Real advantage
ACM Transactions on Computation Theory | 2015-09-24 | Paper |
Communication complexity
An Invitation to Mathematics | 2015-06-26 | Paper |
On Turán's \((3,4)\)-problem with forbidden subgraphs
Mathematical Notes | 2015-05-08 | Paper |
Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
Annals of Mathematics. Second Series | 2015-02-09 | Paper |
Space complexity in propositional calculus
Proceedings of the thirty-second annual ACM symposium on Theory of computing | 2014-09-26 | Paper |
On the Fon-Der-Flaass interpretation of extremal examples for Turán's \((3,4)\)-problem
Proceedings of the Steklov Institute of Mathematics | 2014-08-04 | Paper |
A product theorem in free groups.
Annals of Mathematics. Second Series | 2014-04-14 | Paper |
On the Caccetta-Häggkvist conjecture with forbidden subgraphs
Journal of Graph Theory | 2013-10-21 | Paper |
On the number of pentagons in triangle-free graphs
Journal of Combinatorial Theory. Series A | 2013-03-06 | Paper |
Non-three-colourable common graphs exist
Combinatorics, Probability and Computing | 2012-09-12 | Paper |
Satisfiability, branch-width and Tseitin tautologies
Computational Complexity | 2012-06-26 | Paper |
Special issue in memory of Misha Alekhnovich. Foreword
Computational Complexity | 2012-06-26 | Paper |
Parameterized bounded-depth Frege is not optimal
Automata, Languages and Programming | 2011-07-06 | Paper |
On minimal unsatisfiability and time-space trade-offs for \(k\)-DNF resolution
Automata, Languages and Programming | 2011-07-06 | Paper |
On 3-hypergraphs with forbidden 4-vertex configurations
SIAM Journal on Discrete Mathematics | 2011-06-17 | Paper |
Sergei Ivanovich Adian (on his eightieth birthday)
Russian Mathematical Surveys | 2011-06-17 | Paper |
An \(\Omega (n^{1/3})\) lower bound for bilinear group based private information retrieval
Theory of Computing | 2011-05-24 | Paper |
Diameter of polyhedra: limits of abstraction
Mathematics of Operations Research | 2011-04-27 | Paper |
The Sign-Rank of AC$^0$
SIAM Journal on Computing | 2010-11-04 | Paper |
Almost Euclidean subspaces of \ell_1^N via expander codes
(available as arXiv preprint) | 2010-08-06 | Paper |
Complexity of propositional proofs (invited talk)
Computer Science – Theory and Applications | 2010-06-22 | Paper |
The Ackermann Award 2009
Computer Science Logic | 2009-11-12 | Paper |
Resolution Is Not Automatizable Unless W[P Is Tractable]
SIAM Journal on Computing | 2009-08-20 | Paper |
On the Minimal Density of Triangles in Graphs
Combinatorics, Probability and Computing | 2008-09-29 | Paper |
An upper bound on the threshold quantum decoherence rate
(available as arXiv preprint) | 2008-09-03 | Paper |
Flag algebras
Journal of Symbolic Logic | 2008-02-25 | Paper |
| scientific article; zbMATH DE number 5145337 (Why is no real title available?) | 2007-04-23 | Paper |
| scientific article; zbMATH DE number 2226428 (Why is no real title available?) | 2005-11-08 | Paper |
| scientific article; zbMATH DE number 2221981 (Why is no real title available?) | 2005-11-02 | Paper |
Guessing More Secrets via List Decoding
Internet Mathematics | 2005-10-27 | Paper |
Automata, Languages and Programming
Lecture Notes in Computer Science | 2005-08-24 | Paper |
| scientific article; zbMATH DE number 2174386 (Why is no real title available?) | 2005-06-08 | Paper |
Quantum communication complexity of symmetric predicates
Izvestiya: Mathematics | 2005-05-17 | Paper |
Pseudorandom Generators in Propositional Proof Complexity
SIAM Journal on Computing | 2005-02-21 | Paper |
Resolution lower bounds for perfect matching principles
Journal of Computer and System Sciences | 2004-10-04 | Paper |
| scientific article; zbMATH DE number 2102736 (Why is no real title available?) | 2004-09-24 | Paper |
| scientific article; zbMATH DE number 2087215 (Why is no real title available?) | 2004-08-11 | Paper |
Lower bounds for polynomial calculus in the case of nonbinomial ideals.
Doklady Mathematics | 2004-06-15 | Paper |
Read-once branching programs, rectangular proofs of the pigeonhole principle and the transversal calculus
Combinatorica | 2003-12-14 | Paper |
Lower bounds for the polynomial calculus
Computational Complexity | 2003-12-07 | Paper |
Resolution lower bounds for the weak functional pigeonhole principle.
Theoretical Computer Science | 2003-08-17 | Paper |
Space Complexity in Propositional Calculus
SIAM Journal on Computing | 2002-09-29 | Paper |
| scientific article; zbMATH DE number 1559594 (Why is no real title available?) | 2001-03-01 | Paper |
On P versus NP\(\cap\)co-NP for decision trees and read-once branching programs
Computational Complexity | 2000-11-20 | Paper |
Exponential lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields.
Applicable Algebra in Engineering, Communication and Computing | 2000-08-08 | Paper |
| scientific article; zbMATH DE number 1361490 (Why is no real title available?) | 1999-11-10 | Paper |
Improved lower bounds on the rigidity of Hadamard matrices
Mathematical Notes | 1999-03-15 | Paper |
Neither reading few bits twice nor reading illegally helps much
Discrete Applied Mathematics | 1998-08-20 | Paper |
Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
Computational Complexity | 1998-06-29 | Paper |
Natural proofs
Journal of Computer and System Sciences | 1997-12-03 | Paper |
On the shrinkage exponent for read-once formulae
Theoretical Computer Science | 1997-09-29 | Paper |
| scientific article; zbMATH DE number 981681 (Why is no real title available?) | 1997-09-07 | Paper |
| scientific article; zbMATH DE number 806753 (Why is no real title available?) | 1996-06-06 | Paper |
| scientific article; zbMATH DE number 848041 (Why is no real title available?) | 1996-02-26 | Paper |
Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
Izvestiya: Mathematics | 1996-02-25 | Paper |
Constructing Small Sets that are Uniform in Arithmetic Progressions
Combinatorics, Probability and Computing | 1994-11-20 | Paper |
ON THE PARAMETERIZATION OF SOLUTIONS FOR EQUATIONS IN FREE GROUPS
International Journal of Algebra and Computation | 1994-08-14 | Paper |
| scientific article; zbMATH DE number 440483 (Why is no real title available?) | 1993-12-05 | Paper |
On lower bounds for read-\(k\)-times branching programs
Computational Complexity | 1993-08-30 | Paper |
Majority gates vs. general weighted threshold gates
Computational Complexity | 1993-08-08 | Paper |
\(n^{{\Omega{}}(\log{} n)}\) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom
Information Processing Letters | 1993-06-29 | Paper |
| scientific article; zbMATH DE number 176870 (Why is no real title available?) | 1993-05-18 | Paper |
| scientific article; zbMATH DE number 177818 (Why is no real title available?) | 1993-05-18 | Paper |
On the distributional complexity of disjointness
Theoretical Computer Science | 1993-04-22 | Paper |
The gap between the chromatic number of a graph and the rank of its adjacency matrix is superlinear
Discrete Mathematics | 1993-01-17 | Paper |
| scientific article; zbMATH DE number 50286 (Why is no real title available?) | 1992-09-18 | Paper |
Lower bounds of the complexity of symmetric Boolean functions of contact- rectifier circuits
Mathematical Notes | 1992-06-25 | Paper |
Applications of matrix methods to the theory of lower bounds in computational complexity
Combinatorica | 1990-01-01 | Paper |
| scientific article; zbMATH DE number 4193610 (Why is no real title available?) | 1990-01-01 | Paper |
| scientific article; zbMATH DE number 4172394 (Why is no real title available?) | 1990-01-01 | Paper |
| scientific article; zbMATH DE number 4101415 (Why is no real title available?) | 1989-01-01 | Paper |
| scientific article; zbMATH DE number 4095383 (Why is no real title available?) | 1988-01-01 | Paper |
Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
Mathematical Notes | 1987-01-01 | Paper |
Periodic groups and Lie algebras
Russian Mathematical Surveys | 1987-01-01 | Paper |
| scientific article; zbMATH DE number 4095386 (Why is no real title available?) | 1987-01-01 | Paper |
| scientific article; zbMATH DE number 3997703 (Why is no real title available?) | 1986-01-01 | Paper |
Lower estimates of the dimension of schemes of bounded depth in the basis $ \{\&,\vee,\oplus\}$
Russian Mathematical Surveys | 1986-01-01 | Paper |
| scientific article; zbMATH DE number 4008289 (Why is no real title available?) | 1985-01-01 | Paper |
ON SYSTEMS OF EQUATIONS IN A FREE GROUP
Mathematics of the USSR-Izvestiya | 1985-01-01 | Paper |
Lower bounds on monotone complexity of the logical permanent
Mathematical Notes | 1985-01-01 | Paper |
