Publications
Type | Link | |
---|---|---|
journal |
D. V. Karpov. Large contractible subgraphs of a 3-connected graph. Discussiones Mathematicae Graph Theory. In press |
DOI |
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 |
DOI |
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 |
DOI |
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 |
DOI |
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 |
DOI |
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 |
DOI |
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 |
DOI |
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 |
DOI |
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 |
DOI |
proceedings |
P.A. Golovach. Editing to a connected graph of given degrees. Information and Computation, Volume 256, 2017, Pages 131-147 |
DOI |
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 |
DOI |
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 |
DOI |
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 |
DOI |
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 |
DOI |
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 |
DOI |
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 |
DOI |
preprint |
Nikolai Karpov, Marcin Pilipczuk, Anna Zych-Pawlewicz. An exponential lower bound for cut sparsifiers in planar graphs. 2017 |
arXiv |
journal |
Anton Alekseev, Sergey Nikolenko. Word Embeddings of User Profiling in Online Social Networks. Computación y Sistemas, Vol 21, No 2, 2017 |
DOI |
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 |
DOI |
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. |
DOI |
journal |
P. A. Golovach, G. B. Mertzios. Graph editing to a given degree sequence. Theoretical Computer Science, Volume 665, 2017, Pages 1-12 |
DOI |
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 |
DOI |
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 |
DOI |
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 |
DOI |
journal |
Yu. V. Matiyasevich. Riemann's zeta function and finite Dirichlet series. St. Petersburg Math. J. 27 (2016), 985-1002 |
DOI |
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. |
DOI |
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 |
DOI |
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 |
DOI |
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 |
DOI |
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 |
DOI |
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 |
DOI |
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 |
DOI |
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 |
DOI |
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 |
DOI |
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 |
DOI |
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 |
DOI |
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 |
DOI |
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 |
DOI |
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 |
DOI |
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 |
DOI |
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 |
DOI |
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 |
DOI |
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 |
DOI |
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. |
DOI |
preprint |
Ivan Bliznets, Marek Cygan, Pawel Komosa, Lukas Mach. Kernelization lower bound for Permutation Pattern Matching. To appear in Information Processing Letters, 2015. |
arXiv |
preprint |
Dmitry Itsykson, Alexander Knop, Dmitry Sokolov. Heuristic time hierarchies via hierarchies for sampling distributions. ECCC 2014 report. |
ECCC |
preprint |
Alexander Knop. Circuit Lower Bounds for Average MA. ECCC 2014 report. |
ECCC |
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. |
DOI |
preprint |
Dmitry Itsykson, Anna Malova, Vsevolod Oparin, Dmitry Sokolov. Tree-like resolution complexity of two planar problems. CoRR abs/1412.1124 |
arXiv |
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. |
DOI |
journal |
Sergey I. Nikolenko, Kirill Kogan. Single and Multiple Buffer Processing. Encyclopedia of Algorithms, pp 1-9, 2014. |
DOI |
preprint |
Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin. Families with infants: speeding up algorithms for NP-hard problems using FFT. CoRR abs/1410.2209 |
arXiv |
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. |
DOI |
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. |
DOI |
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. |
DOI |
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. |
DOI |
preprint |
Dmitry Itsykson, Mikhail Slabodkin, Dmitry Sokolov. Resolution complexity of perfect mathcing principles for sparse graphs. ECCC 2014 report. |
ECCC |
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. |
DOI |
journal |
Fedor V. Fomin, Petr A. Golovach. Long Circuits and Large Euler Subgraphs. SIAM Journal on Discrete Mathematics, 28(2), pp. 878-892, 2014. |
DOI |
journal |
Maxim Vsemirnov. On a conjecture of Guo and Krattenthaler. International Journal of Number Theory, Volume 10, Issue 06, 2014. |
DOI |
preprint |
Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin. Families with infants: a general approach to solve hard partition problems. CoRR abs/1311.2456. |
arXiv |
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. |
DOI |