Публикации

Type Link
journal

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

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

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, 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

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

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

proceedings

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

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

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

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

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

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

preprint

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

journal

Anton Alekseev, Sergey Nikolenko. Word Embeddings of User Profiling in Online Social Networks. Computación y Sistemas, Vol 21, No 2, 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

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

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

journal

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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.

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

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

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.

preprint

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

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

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

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

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

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.

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.

preprint

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

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.

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

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

preprint

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

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.