35 citations to https://www.mathnet.ru/rus/mmj67
-
Rhodes M., “On the Chvatal rank of the Pigeonhole Principle”, Theoret. Comput. Sci., 410:27-29 (2009), 2774–2778
-
Pitassi T., Segerlind N., “Exponential lower bounds and Integrality Gaps for Tree-like Lovasz-Schrijver Procedures”, Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009, 355–364
-
Mathieu C., Sinclair A., “Sherali-Adams Relaxations of the Matching Polytope”, Stoc'09: Proceedings of the 2009 ACM Symposium on Theory of Computing, 2009, 293–302
-
Rhodes M., “Resolution width and Cutting Plane rank are incomparable”, Mathematical Foundations of Computer Science 2008, Proceedings, Lecture Notes in Computer Science, 5162, 2008, 575–587
-
Dantchev S., “Rank Complexity Gap for Lovasz-Schrijver and Sherali-Adams Proof Systems”, Stoc 07: Proceedings of the 39th Annual ACM Symposium on Theory of Computing, Annual Acm Symposium on Theory of Computing, 2007, 311–317
-
Rhodes M., “Rank lower bounds for the sherali-adams operator”, Computation and Logic in the Real World, Proceedings, Lecture Notes in Computer Science, 4497, 2007, 648–659
-
Stefan S. Dantchev, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, 2007, 311
-
Д. М. Ицыксон, А. А. Кожевников, “Нижние оценки на длину вывода цейтинских формул в статической системе доказательств Ловаса–Схрайвера”, Комбинаторика и теория графов. I, Зап. научн. сем. ПОМИ, 340, ПОМИ, СПб., 2006, 10–32 ; D. M. Itsykson, A. A. Kojevnikov, “Lower bounds of static Lovász–Schrijver calculus proofs for Tseitin tautologies”, J. Math. Sci. (N. Y.), 145:3 (2007), 4942–4952
-
Anjos M.F., “An explicit semidefinite characterization of satisfiability for Tseitin instances on toroidal grid graphs”, Ann. Math. Artif. Intell., 48:1-2 (2006), 1–14
-
Kojevnikov A., Kulikov A.S., “Complexity of semialgebraic proofs with restricted degree of falsity”, Theory and applications of satisfiability testing—SAT 2006, Lecture Notes in Comput. Sci., 4121, Springer, Berlin, 2006, 11–21