Publications

Typesort descending Link
journal

Ivan Bliznets, Fedor V. Fomin, Marcin Pilipczuk and Michał Pilipczuk: A Subexponential Parameterized Algorithm for Proper Interval Completion. SIAM Journal on Discrete Mathematics 2015, Vol. 29, No. 4, pp. 1961-1987

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

Ivan Bliznets, Fedor V. Fomin, Michał Pilipczuk , Yngve Villanger: Largest Chordal and Interval Subgraphs Faster than 2^n. Algorithmica Volume 73 Number 3 November 2015
pp 1-26

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

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

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

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

Ivan Bliznets, Fedor V. Fomin, Petr A. Golovach. Nikolay Karpov, Alexander S. Kulikov, Saket Saurabh. Parameterized complexity of superstring problems. Algorithmica (2016)

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

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

journal

Fedor V. Fomin, Petr A. Golovach, Nikolay Karpov, Alexander S. Kulikov. Parameterized Complexity of Secluded Connectivity Problems. Theory of Computing Systems, 2016, pp 1–25

journal

Edward A. Hirsch, Dmitry Sokolov. On the probabilistic closure of the loose unambiguous hierarchy. Information Processing Letters. vol. 115. pp. 725 - 730. 2015.

journal

Petr A. Golovach, Editing to a Graph of Given Degrees. Theor. Comp. Sci., 591, pp. 72-84, 2015

journal

Tatjana V. Abramovskaya, Fedor V. Fomin, Petr A. Golovach, Michał Pilipczuk: How to hunt an invisible rabbit on a graph. European Journal of Combinatorics, 52 Part A (2016), pp. 12–26

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

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

preprint

Magnus Find, Alexander Golovnev, Edward A. Hirsch, Alexander S. Kulikov. A better-than-3n lower bound for the circuit complexity of an explicit function.

preprint

Dmitry Itsykson, Alexander Knop, Dmitry Sokolov. Complexity of distributions and average-case hardness. 2015.

proceedings

Pavel Chuprikov, Sergey Nikolenko, Kirill Kogan: Priority queueing with multiple packet characteristics. 2015 IEEE Conference on Computer Communications (INFOCOM 2015), pp. 1418-1426, 2015

proceedings

Sergey I. Nikolenko. SVD-LDA: Topic Modeling for Full-Text Recommender Systems. Proc. 14th Mexican International Conference on Artificial Intelligence ( MICAI 2015), Lecture Notes in Artificial Intelligence, vol. 9414, Springer, 2015, pp. 67–79.

proceedings

Patrick Eugster, Alex Kesselman, Kirill Kogan, Sergey I. Nikolenko, Alexander V. Sirotkin. Essential Traffic Parameters for Shared Memory Switch Performance. 22nd International Colloquium on Structural Information and Communication Complexity ( SIROCCO 2015), Lecture Notes in Computer Science, vol. 9439, Springer, 2015, pp. 61–75

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

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

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

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

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

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

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

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

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

Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin. Lower Bounds for the Graph Homomorphism Problem. Proceedings of 42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015). Lecture Notes in Computer Science 9134, Springer, pp. 481-493. 2015.

proceedings

Dmitry Itsykson, Mikhail Slabodkin, Dmitry Sokolov. Resolution Complexity of Perfect Matching Principles for Sparse Graphs. Computer Science -- Theory and Applications. Lecture Notes in Computer Science. vol. 9139. pp. 219-230, 2015.

proceedings

Alexadner Knop. Circuit Lower Bounds for Average-Case MA. Computer Science -- Theory and Applications. Lecture Notes in Computer Science Volume 9139, 2015, pp 283-295

proceedings

Ivan Bliznets, Fedor V. Fomin, Petr A. Golovach, Nikolay Karpov, Alexander S. Kulikov, Saket Saurabh. Parameterized Complexity of Superstring Problems. Proceeidings of the 26th Annual Symposium on Combinatorial Pattern Matching (CPM 2015). Lecture Notes in Computer Science, vol. 9133, pp. 89-99, Springer, 2015

proceedings

Fedor Fomin, Petr Golovach, Nikolay Karpov, Alexander Kulikov. Parameterized Complexity of Secluded Connectivity Problems. Proceedings of the 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015), LIPIcs, Vol. 45, pp. 408-419, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015.