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)







  • On the Caccetta-Haggkvist Conjecture with Forbidden Subgraphs, 2011.
  • Non-Three-Colorable Common Graphs Exist, joint with Hamed Hatami, Jan Hladky, Daniel Kral and Sergey Norin, 2011.
  • On the Number of Pentagons in Triangle-Free Graphs, joint with Hamed Hatami, Jan Hladky, Daniel Kral and Sergey Norin, 2011.
  • Parameterized Bounded-Depth Frege is Not Optimal, joint with Olaf Beyersdorff, Nicola Galesi and Massimo Lauria, 2010, Electronic Colloquium on Computational Complexity.
  • On the Fon-der-Flaass Interpretation of Extremal Examples for Turan's (3,4)-problem, final version 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, 2007.
  • 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, 2002-2003.
  • Satisfiability, Branch-Width and Tseitin Tautologies, joint with M. Alekhnovich, Proc. of the 43rd IEEE FOCS, 2002, pages 593-603.
  • 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.