# Publications

journal

D. V. Karpov. Large contractible subgraphs of a 3-connected graph. Discussiones Mathematicae Graph Theory. In press

journal

Maxim Vsemirnov. On the primitive divisors of the recurrent sequence $u_{n+1}=(4\cos^2(2\pi/7)−1)u_n−u_{n−1|$ with applications to group theory. Science China-Mathematics, Volume 61 (2018), no. 11, Pages 2101-2110

journal

Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin. Solving SCS for Bounded Length Strings in Fewer than 2^n Steps. Information Processing Letters, Volume 114, Issue 8, pp 421–425, 2014.

journal

Fedor V. Fomin, Petr A. Golovach. Long Circuits and Large Euler Subgraphs. SIAM Journal on Discrete Mathematics, 28(2), pp. 878-892, 2014.

journal

Fedor V. Fomin, Petr A. Golovach, Nikolay Karpov, Alexander S. Kulikov. Parameterized Complexity of Secluded Connectivity Problems. Theory of Computing Systems: Volume 61, Issue 3, October 2017, pp 795–819

journal

Patrick Eugster, Kirill Kogan, Sergey I. Nikolenko, Alexander V. Sirotkin. Heterogeneous packet processing in shared memory buffers. Journal of Parallel and Distributed Computing, Volume 99, January 2017, pp. 1–13

journal

Artur Kadurin, Alexander Aliper, Andrey Kazennov, Polina Mamoshina, Quentin Vanhaelen, Kuzma Khrabrov, Alex Zhavoronkov. The cornucopia of meaningful leads: Applying deep adversarial autoencoders for new moleculedevelopment in oncology. Oncotarget, Volume: 8 Issue: 7, 2017

journal

Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, Arkadiusz Socała. Tight Lower Bounds on Graph Embedding Problems. Journal of the ACM, Volume 64 Issue 3, June 2017

journal

Kiril lKogan, Alejandro López-Ortiz, Sergey I. Nikolenko, Alexander V. Sirotkin. The impact of processing order on performance: A taxonomy of semi-FIFO policies. Journal of Computer and System Sciences, Volume 88, September 2017, Pages 220-235

journal

Artur Kadurin, Sergey Nikolenko, Kuzma Khrabrov, Alex Aliper and Alex Zhavoronkov. druGAN: An Advanced Generative Adversarial Autoencoder Model for de Novo Generation of New Molecules with Desired Molecular Properties in Silico. Molecular Pharmaceutics, 14 (9), pp 3098–3104, 2017

journal

Pablo Saez, Xavier Vidaux, Maxim Vsemirnov. Optimal bounds for Büchi's problem in modular arithmetic. Journal of Number Theory, Volume 149, pp. 368–403, 2015.

journal

Maxim Vsemirnov. On a conjecture of Guo and Krattenthaler. International Journal of Number Theory, Volume 10, Issue 06, 2014.

journal

Evgeny Demenkov, Alexander S. Kulikov, Olga Melanich, Ivan Mihajlin. New Lower Bounds on Circuit Size of Multi-output Functions. Theory of Computing Systems, 2014.

journal

Anton Alekseev, Sergey Nikolenko. Word Embeddings of User Profiling in Online Social Networks. Computación y Sistemas, Vol 21, No 2, 2017

journal

Sergey I. Nikolenko, Kirill Kogan. Single and Multiple Buffer Processing. Encyclopedia of Algorithms, pp 1-9, 2014.

journal

Yu. V. Matiyasevich. Riemann's zeta function and finite Dirichlet series. St. Petersburg Math. J. 27 (2016), 985-1002

journal

K. Kogan, S.I. Nikolenko, P. Eugster, A. Shalimov, O. Rottenstreich. Efficient FIB Representations on Distributed Platforms. IEEE Transactions on Networking, vol. 25, no. 6, 2017, pp. 3309–3322

journal

Rajesh Chitnis, Fedor V. Fomin, Petr A. Golovach. Parameterized complexity of the anchored k-core problem for directed graphs. Information and Computation, vol. 247, April 2016, pp 11–22

journal

P. A. Golovach, G. B. Mertzios. Graph editing to a given degree sequence. Theoretical Computer Science, Volume 665, 2017, Pages 1-12

journal

Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin. Families with Infants: Speeding Up Algorithms for NP-Hard Problems Using FFT. ACM Transactions on Algorithms (TALG), Vol. 12 Iss. 3, June 2016
Article No. 35

journal

Dmitry Itsykson, Vsevolod Oparin, Mikhail Slabodkin, Dmitry Sokolov. Tight Lower Bounds on the Resolution Complexity of Perfect Matching Principles. Fundamenta Informaticae, vol. 145, no. 3, pp. 229-242, 2016

journal

Ivan Bliznets, Fedor V. Fomin, Michał Pilipczuk , Yngve Villanger. Largest Chordal and Interval Subgraphs Faster than 2^n. Algorithmica, Vol. 76 Iss. 2, October 2016, pp. 569-594

journal

Ivan Bliznets, Marek Cygan, Paweł Komosa, Michał Pilipczuk. Hardness of Approximation for H-free Edge Modification Problems. ACM Transactions On Computation Theory, Volume 10 Issue 2, May 2018

journal

Kirill Kogana, Alejandro López-Ortizb, Sergey I. Nikolenkoc, Gabriel Scalosube, Michael Segale. Large profits or fast gains: A dilemma in maximizing throughput with applications to network processors. Journal of Network and Computer Applications, vol. 74, October 2016, pp 31–43

journal

Alexander Golovnev, Alexander S. Kulikov, Alexander V. Smal, SuguruTamaki. Gate elimination: Circuit size lower bounds and #SAT upper bounds. Theoretical Computer Science, Volume 719, 6, April 2018, Pages 46-63

journal

Ivan Bliznets, Fedor V. Fomin, Petr A. Golovach. Nikolay Karpov, Alexander S. Kulikov, Saket Saurabh. Parameterized complexity of superstring problems. Algorithmica: Volume 79, Issue 3, November 2017, pp 798–813

journal

Alexander Golovnev, Edward A.Hirsch, Alexander Knop, Alexander S. Kulikov. On the limits of gate elimination. Journal of Computer and System Sciences, Volume 96, September 2018, Pages 107-119

journal

A. V. Pastor. On the Decomposition of a 3-Connected Graph into Cyclically 4-Edge-Connected Components. Journal of Mathematical Sciences, July 2018, Volume 232, Issue 1, pp 61–83

journal

D. V. Karpov. Lower Bounds on the Number of Leaves in Spanning Trees. Journal of Mathematical Sciences, July 2018, Volume 232, Issue 1, pp 36-43

journal

N. Y. Vlasova, D. V. Karpov. Bounds on the Dynamic Chromatic Number of a Graph in Terms of its Chromatic Number. Journal of Mathematical Sciences, July 2018, Volume 232, Issue 1, pp 21-24

preprint

Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin. Families with infants: a general approach to solve hard partition problems. CoRR abs/1311.2456.

preprint

Ivan Bliznets, Marek Cygan, Pawel Komosa, Lukas Mach. Kernelization lower bound for Permutation Pattern Matching. To appear in Information Processing Letters, 2015.

preprint

Dmitry Itsykson, Alexander Knop, Dmitry Sokolov. Heuristic time hierarchies via hierarchies for sampling distributions. ECCC 2014 report.

preprint

Dmitry Itsykson, Mikhail Slabodkin, Dmitry Sokolov. Resolution complexity of perfect mathcing principles for sparse graphs. ECCC 2014 report.

preprint

Nikolai Karpov, Marcin Pilipczuk, Anna Zych-Pawlewicz. An exponential lower bound for cut sparsifiers in planar graphs. 2017

preprint

Alexander Knop. Circuit Lower Bounds for Average MA. ECCC 2014 report.

preprint

Dmitry Itsykson, Anna Malova, Vsevolod Oparin, Dmitry Sokolov. Tree-like resolution complexity of two planar problems. CoRR abs/1412.1124

preprint

Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin. Families with infants: speeding up algorithms for NP-hard problems using FFT. CoRR abs/1410.2209

proceedings

Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, Arkadiusz Socała. Tight bounds for graph homomorphism and subgraph isomorphism. Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '16), 2016, pp. 1643-1649

proceedings

Alexander Golovnev, Alexander S. Kulikov. Weighted Gate Elimination: Boolean Dispersers for Quadratic Varieties Imply Improved Circuit Lower Bounds. ITCS '16 Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016, pp. 405-411

proceedings

Pavel Chuprikov, Sergey I. Nikolenko, Kirill Kogan. On Demand Elastic Capacity Planning for Service Auto-scaling. IEEE INFOCOM 2016 - The 35th Annual IEEE International Conference on Computer Communications, 2016, pp. 1–9

proceedings

Kirill Kogan, Danushka Menikkumbura, Gustavo Petri, YoungTae Noh, Sergey Nikolenko, Patrick Eugster. BASEL (Buffer mAnagement SpEcification Language). ANCS '16 Proceedings of the 2016 Symposium on Architectures for Networking and Communications Systems, 2016, pp. 69-74

proceedings

Sergey I. Nikolenko, Kirill Kogan, Gábor Rétvári, Erika R. Bérczi-Kovács, Alexander Shalimov. How to represent IPv6 forwarding tables on IPv4 or MPLS dataplanes. 2016 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), 2016

proceedings

Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin. Solving 3-Superstring in 3^{n/3} Time. Proceedings of 38th International Symposium on Mathematical Foundations of Computer Science (MFCS 2013), Lecture Notes in Computer Science 8087, Springer, pp. 480–491, 2013.

proceedings

Kirill Kogan, Sergey Nikolenko, Patrick Eugster, Alexander Shalimov, and Ori Rottenstreich. FIB Efficiency in Distributed Platforms. In: The 24th IEEE International Conference on Network Protocols (ICNP 2016), 8-11 November 2016, Singapore

proceedings

Magnus Find, Alexander Golovnev, Edward A. Hirsch, Alexander S. Kulikov. A Better-than-3n Lower Bound for the Circuit Complexity of an Explicit Function. Proceedings of 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016). IEEE Computer Society, pp. 89–98, 2016.

proceedings

Ivan Bliznets, Marek Cygan, Paweł Komosa, Lukáš Mach, Michał Pilipczuk. Lower bounds for the parameterized complexity of minimum fill-in and other completion problems. SODA '16 Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, 2016, pp. 1132-1151

proceedings

Petr A. Golovach. Editing to a Graph of Given Degrees. Proceedings of 9th International Symposium on Parameterized and Exact Computation (IPEC 2014), Lecture Notes in Computer Science 8894, Springer, pp. 196–207, 2014.

proceedings

Ivan Bliznets, Marek Cygan, Pawel Komosa, Michal Pilipczuk. Hardness of Approximation for H-Free Edge Modification Problems. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016), Leibniz International Proceedings in Informatics (LIPIcs), vol. 60, 2016, pp. 3:1--3:17

proceedings

Petr A. Golovach. Editing to a Connected Graph of Given Degrees. Proceedings of 39th Mathematical Foundations of Computer Science (MFCS 2014), Lecture Notes in Computer Science 8635, Springer, pp. 324–335, part 2, 2014.

proceedings

Dmitry Itsykson, Dmitry Sokolov. Lower Bounds for Splittings by Linear Combinations. Proceedings of 39th Mathematical Foundations of Computer Science (MFCS 2014), Lecture Notes in Computer Science 8635, Springer, pp. 372–383, part 2, 2014.

proceedings

Ivan Bliznets, Fedor V. Fomin, Marcin Pilipczuk, Michał Pilipczuk. A Subexponential Parameterized Algorithm for Proper Interval Completion. Proceedings of 22th Annual European Symposium (ESA 2014), Lecture Notes in Computer Science 8737, Springer, pp. 173–184, 2014.

proceedings

Dmitry Itsykson, Alexander Knop. Hard Satisfiable Formulas for Splittings by Linear Combinations. In: Gaspers S., Walsh T. (eds) Theory and Applications of Satisfiability Testing – SAT 2017. Lecture Notes in Computer Science, vol 10491, 2017

proceedings

Alex Davydow, Pavel Chuprikov, Sergey Nikolenko, Kirill Kogan. Throughput Optimization with Latency Constraints. In: The 36th IEEE International Conference on Computer Communications (IEEE INFOCOM 2017), 1-4 May 2017, Atlanta, GA, USA

proceedings

Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin. Families with Infants: A General Approach to Solve Hard Partition Problems. Proceedings of 41st International Colloquium Automata, Languages, and Programming (ICALP 2014), Lecture Notes in Computer Science 8572, Springer, pp. 551–562, 2014.

proceedings

A. V. Pastor. On critically 3-connected graphs with exactly two vertices of degree 3. Proceedings of the Fourth Russian Finnish Symposium on Discrete Mathematics, TUCS Lecture Notes, 2017

proceedings

S.I. Nikolenko, A. Alekseyev. User Profiling in Text-Based Recommender Systems Based on Distributed Word Representations. Proc. 5th International Conference on Analysis of Images, Social Networks, and Texts ( AIST 2016), 2017, pp. 196–207

proceedings

P.A. Golovach. Editing to a connected graph of given degrees. Information and Computation, Volume 256, 2017, Pages 131-147

proceedings

А.В. Пастор. О критических трехсвязных графах ровно с двумя вершинами степени 3. Записки научных семинаров ПОМИ, том 464, стр. 95-111. 2017.

proceedings

Alexander Golovnev, Edward A. Hirsch, Alexander Knop, Alexander S. Kulikov. On the Limits of Gate Elimination. 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), Leibniz International Proceedings in Informatics (LIPIcs), vol. 58, 2016, pp 46:1--46:13

proceedings

Alexander Golovnev, Alexander S. Kulikov, Alexander V. Smal, Suguru Tamaki. Circuit Size Lower Bounds and #SAT Upper Bounds Through a General Framework. 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), Leibniz International Proceedings in Informatics (LIPIcs), vol. 58, 2016, pp 45:1–45:16

proceedings

A.V. Pastor. On the Structure of C3-Critical Minimal 6-Connected Graphs. Journal of Mathematical Sciences, vol. 212, iss. 6, February 2016, pp 698–707

proceedings

Petr A. Golovach, George B. Mertzios. Graph Editing to a Given Degree Sequence. Computer Science – Theory and Applications, Volume 9691 of the series Lecture Notes in Computer Science, 2016, pp 177-191