Research Papers

It is my aim, and every effort bent, that the sum and history of my life, which in the same sentence is my obit and epitaph too, shall be them both: He made the books and he died.
William Faulkner, Writer (1897-1962)








  • Clique Is Hard on Average for Regular Resolution, joint with Albert Atserias, Ilario Bonacina, Susanna de Rezende, Massimo Lauria and Jakob Nordström, 2018.
  • On Space and Depth in Resolution, 2016.
  • On the Width of Semi-Algebraic Proofs and Algorithms, in Mathematics of Operations Research, Vol. 42, No 4, 2017, pages 1106-1134.
  • A New Kind of Tradeoffs in Propositional Proof Complexity, in Journal of the ACM, Vol. 62, No 3, 2016, article 16.
  • On the Density of Transitive Tournaments, joint with Leonardo Coregliano, in Journal of Graph Theory, Vol. 85, No 1, 2017, pages 12-21.
  • On the $AC^0$ Complexity of Subgraph Isomorphism, joint with Yuan Li and Benjamin Rossman, in SIAM Journal on Computing, Vol. 46, No 3, 2017, pages 936-971. © Society for Industrial and Applied Mathematics.
  • Real Advantage, joint with Emanuele Viola, in ACM Transactions on Computation Theory, Vol. 5, 2013, article 17.
  • On Turan's (3,4)-Problem with Forbidden Configurations, in Matematicheskie Zametki, Vol. 95, No 2, 2014, pages 271-281.
  • Asymptotic Structure of Graphs with the Minimum Number of Triangles, joint with Oleg Pikhurko, in Combinatorics, Probability and Computing, Vol. 26, No 1, 2017, pages 138-160.
  • On the Caccetta-Haggkvist Conjecture with Forbidden Subgraphs, in Journal of Graph Theory, Vol. 74, No 2, 2013, pages 236-248.
  • Non-Three-Colorable Common Graphs Exist, joint with Hamed Hatami, Jan Hladky, Daniel Kral and Sergey Norin, in Combinatorics, Probability and Computing, Vol. 21, No 5, 2012, pages 734-742. © Cambridge University Press
  • On the Number of Pentagons in Triangle-Free Graphs, joint with Hamed Hatami, Jan Hladky, Daniel Kral and Sergey Norin, in Journal of Combinatorial Theory, Series A, Vol. 120, No 3, 2013, pages 722-732.
  • Parameterized Bounded-Depth Frege is Not Optimal, joint with Olaf Beyersdorff, Nicola Galesi and Massimo Lauria, in ACM Transactions on Computation Theory, Vol. 4, 2012, article 7.
  • On the Fon-der-Flaass Interpretation of Extremal Examples for Turan's (3,4)-problem, in Proceedings of the Steklov Institute of Mathematics, Vol. 274, 2011, pages 247-266. Russian version.
  • On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution, joint with Jakob Nordström, 2009.
  • Diameter of Polyhedra: Limits of Abstraction, joint with Friedrich Eisenbrand, Nicolai Hähnle and Thomas Rothvoß, in Mathematics of Operations Research, Vol. 35, 2010, pages 786 - 794.
  • On 3-hypergraphs with forbidden 4-vertex configurations, in SIAM Journal on Discrete Mathematics, Vol. 24, No 3, 2010, pages 946-963. © Society for Industrial and Applied Mathematics.
  • A simple proof of Bazzi's theorem, in ACM Transactions on Computation Theory, Vol.1, No 1, 2009.
  • The Sign-Rank of $AC^0$, joint with Alexander Sherstov, in SIAM Journal on Computing, Vol. 39, No 5, 2010, pages 1833-1855. © Society for Industrial and Applied Mathematics.
  • Almost Euclidean subspaces of $ell_1^N$ via expander codes, joint with Venkatesan Guruswami and James Lee, in Combinatorica, Vol. 30, No 1, 2010, pages 47-68.
  • A Product Theorem in Free Groups, in Annals of Mathematics, Vol, 179, No 2, 2014, pages 405-429.
  • On the Minimal Density of Triangles in Graphs, in Combinatorics, Probability and Computing, Vol. 17, No 4, 2008, pages 603-618. Maple worksheet helping to verify some calculations in the paper
  • An Omega(n^{1/3}) Lower Bound for Bilinear Group Based Private Information Retrieval, joint with S. Yekhanin, in Theory of Computing, Vol. 3, 2007, pages 221-238.
  • Flag Algebras, in Journal of Symbolic Logic, Vol. 72, No 4, 2007, pages 1239-1282.
  • Guessing More Secrets via List Decoding, in Internet Mathematics, Vol. 2, No 1, 2005, pages 21-30.
  • Why Are There So Many Loop Formulas?, joint with V. Lifschitz, in ACM Transactions on Computational Logic, Vol. 7, No 2, 2006, pages 261-268.
  • An Upper Bound on the Threshold Quantum Decoherence Rate, in Quantum Information and Computation, Vol. 4, No 3, 2004, pages 222-228.
  • Pseudorandom Generators Hard for k-DNF Resolution and Polynomial Calculus Resolution, Annals of Mathematics, Vol. 181, No 2, 2015, pages 415-472.
  • Satisfiability, Branch-Width and Tseitin Tautologies, joint with M. Alekhnovich, in Computational Complexity, Vol. 20, 2011, pages 649-678.
  • Quantum Communication Complexity of Symmetric Predicates, in Izvestiya: Mathematics, Vol. 67, No 1, 2003, pages 145-159. Russian version in Izvestiya Rossiiskoi Academii Nauk (seriya matematicheskaya), Vol. 67, No 1, 2003, pages 159-176.
  • Resolution Lower Bounds for Perfect Matching Principles, in Journal of Computer and System Sciences, Vol. 69, No 1, 2004, pages 3-27.
  • Resolution Lower Bounds for the Weak Functional Pigeonhole Principle, in Theoretical Computer Science, Vol. 303, No 1, 2003, pages 233-243.
  • Improved Resolution Lower Bounds for the Weak Pigeonhole Principle, 2001, Electronic Colloquium on Computational Complexity.
  • Resolution is Not Automatizable Unless W[P] is Tractable, joint with M. Alekhnovich, in SIAM Journal on Computing, Vol. 38, No 4, 2008, pages 1347-1363. © Society for Industrial and Applied Mathematics
  • Lower Bounds for Polynomial Calculus: Non-Binomial Case, joint with M. Alekhnovich, in Proceedings of the Steklov Institute of Mathematics, Vol. 242, 2003, pages 18-35. Russian version.
  • Pseudorandom Generators in Propositional Proof Complexity, joint with M. Alekhnovich, E. Ben-Sasson and A. Wigderson, in SIAM Journal on Computing, Vol. 34, No 1, 2004, pages 67-88. © Society for Industrial and Applied Mathematics
  • Space Complexity in Propositional Calculus, joint with M. Alekhnovich, E. Ben-Sasson and A. Wigderson, in SIAM Journal on Computing, Vol. 31, No 4, 2002, pages 1184-1211. © Society for Industrial and Applied Mathematics
  • One Property of Cross-Intersecting Families, joint with N. Vereshchagin, in the volume Research Communications of the conference held in the memory of Paul Erdos in Budapest, Hungary, July 4-11, 1999, pages 218-220.
  • Exponential Complexity Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions Over Finite Fields, joint with D. Grigoriev, in Applicable Algebra in Engineering, Communication and Computing, Vol. 10, No 6, 2000, pages 465-487. © Springer-Verlag
  • On P versus NP$\cap$co-NP for Decision Trees and Read-Once Branching Programs, joint with S. Jukna, P. Savicky and I. Wegener, in Computational Complexity, Vol. 8, No 4, 1999, pages 357-370. © Birkhäuser Verlag
  • Improved Lower Bounds on the Rigidity of Hadamard Matrices (Russian), joint with B. Kashin, in Matematicheskie Zametki, Vol. 63, No 4, 1998, pages 535-540. English translation is available here.
  • Lower Bounds for the Polynomial Calculus, in Computational Complexity, Vol. 7, No 4, 1998, pages 291-324. © Birkhäuser Verlag
  • Read-Once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and the Transversal Calculus, joint with A. Wigderson and A. Yao, in Combinatorica, Vol. 22, No 4, 2002, pages 555-574.
  • Neither Reading Few Bits Twice nor Reading Illegally Helps Much, joint with S. Jukna, in Discrete Applied Mathematics, Vol. 85, No 3, 1998, pages 223-238.
  • Proof Complexity in Algebraic Systems and Bounded Depth Frege Systems with Modular Counting, joint with S. Buss, R. Impagliazzo, J. Krajicek, P. Pudlak and J. Sgall, in Computational Complexity, Vol. 6, No 3, 1996/1997, pages 256-298. © Birkhäuser Verlag
  • On Provably Disjoint NP-pairs, 1994, Basic Research in Computer Science Center.
  • Unprovability of Lower Bounds on the Circuit Size in Certain Fragments of Bounded Arithmetic, in Izvestiya of the Russian Academy of Science, mathematics, Vol. 59, No 1, 1995, pages 201-224.
  • Natural Proofs, joint with S. Rudich, in Journal of Computer and System Sciences, Vol. 55, No 1, 1997, pages 24-35.
  • Bounded Arithmetic and Lower Bounds in Boolean Complexity, in the volume Feasible Mathematics II, 1995, pages 344-386. © Birkhäuser Verlag
  • On Small Size Approximation Models, in the volume The Mathematics of Paul Erdos I. Algorithms and Combinatorics, 1996, pages 385-392.
  • On the Parameterization of Solutions for Equations in Free Groups, in International Journal of Algebra and Computation, Vol. 3, No 3, 1993, pages 251-273.
  • Constructing Small Sets that are Uniform in Arithmetic Progressions, joint with E. Szemeredi and A. Wigderson, in Combinatorics, Probability and Computing, Vol. 2, 1993, pages 513-518.
  • $n^{\Omega(\log n)}$ Lower Bounds on the Size of Depth 3 Threshold Circuits with AND Gates at the Bottom, joint with A. Wigderson, in Information Processing Letters, Vol. 45, 1993, pages 303-307.
  • On the Shrinkage Exponent for Read-Once Formulae, joint with J. Håstad and A. Yao, in Theoretical Computer Science, Vol. 141, 1995, pages 269-282.
  • An Equivalence between Second Order Bounded Domain Bounded Arithmetic and First Order Bounded Arithmetic, in the volume Arithmetic, Proof Theory and Computational Complexity, 1992, pages 247-277.
  • Majority Gates vs. General Weighted Threshold Gates, joint with M. Goldmann and J. Håstad, in Computational Complexity, Vol. 2, 1992, pages 277-300.
  • On Lower Bounds for Read-k-Times Branching Programs, joint with A. Borodin and R. Smolensky, in Computational Complexity, Vol. 3, No 1, 1993, pages 1-18.
  • The Set of Minimal Braids is co-NP-complete, joint with M. Paterson, in Journal of Algorithms, Vol. 12, 1991, pages 393-408.
  • Applications of Matrix Methods to the Theory of Lower Bounds in Computational Complexity, in Combinatorica, Vol. 10, No 1, 1990, pages 81-93.
  • Lower bounds on the size of switching-and-rectifier networks for symmetric Boolean functions (Russian), in Matematicheskie Zametki, Vol. 48, No 6, 1990, pages 79-91. English translation in Mathematical Notes of the Academy of Sci. of the USSR.
  • On Submodular Complexity Measures, in the volume Boolean Function Complexity. London Math. Soc. Lecture Note Series, 169, 1992, pages 76-83.
  • On the Distributional Complexity of Disjointness, in Theoretical Computer Science, Vol. 106, 1992, pages 385-390.
  • The Gap between the Chromatic Number of a Graph and the Rank of its Adjacency Matrix is Superlinear, in Discrete Mathematics, Vol. 108, 1992, pages 393-396.
  • On Rigid Matrices (Russian), 1989, Steklov Mathematical Institute.
  • On the Method of Approximation, in Proc. of the 21st ACM STOC, 1989, pages 169-176. Note: the file above includes hand-written corrections of the (many!) typos in the published version
  • Bounded-depth formulae over the basis {AND, XOR} and some combinatorial problems (Russian), in the volume Problems of Cybernetics. Complexity Theory and Applied Mathematical Logic, 1988, pages 149-166.
  • New! On systems of equations in a free group, PhD thesis, Moscow State University, 1987. Significantly extended and expanded version of the Izvestiya paper.
  • Periodical groups and Lie algebras, joint with S. I. Adian, in Uspekhi Matematicheskikh nauk, Vol. 42, No 2, 1987, pages 3-68. English translation in Russian Mathematical Surveys, 42(2):3-68, 1987.
  • Lower bounds on the size of bounded-depth networks over a complete basis with logical addition (Russian), in Matematicheskie Zametki, Vol. 41, No 4, 1987, pages 598-607. English translation in Mathematical Notes of the Academy of Sci. of the USSR, 41(4):333-338, 1987.
  • Lower bounds of monotone complexity of the logical permanent function, in Matematicheskie Zametki, Vol. 37, No 6, 1985, pages 887-900. English translation in Mathematical Notes of the Academy of Sci. of the USSR, 37:485-493, 1985.
  • Lower bounds for the monotone complexity of some Boolean functions, in Doklady Akademii Nauk SSSR, Vol. 281, No 4, 1985, pages 798-801. English translation in Soviet Math. Doklady, 31:354-357, 1985 and is available here.
  • On systems of equations in a free group, in Izvestiya Academii Nauk SSSR (seriya matematicheskaya), Vol. 48, No 4, 1985, pages 779-832. English translation in Math. USSR Izvestiya, 25(1):115-162, 1985.