Switch to compact view

Draft DOI Preprint
1 Alexander S. Kulikov, Vladimir V. Podolskii.
Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates.
Proceedings of 34th International Symposium on Theoretical Aspects of Computer Science (STACS 2017). To appear.
pdf DOI ECCC
2 Fedor V. Fomin, Petr A. Golovach, Nikolay Karpov, Alexander S. Kulikov.
Parameterized Complexity of Secluded Connectivity Problems.
Theory of Computing Systems. Pp. 1–25. 2016.
pdf DOI arXiv
3 Ivan Bliznets, Fedor V. Fomin, Petr A. Golovach, Nikolay Karpov, Alexander S. Kulikov, Saket Saurabh.
Parameterized Complexity of Superstring Problems.
Algorithmica. 2016.
pdf DOI arXiv
4 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.
pdf DOI ECCC
5 Alexander Golovnev, Edward A. Hirsch, Alexander Knop, Alexander S. Kulikov.
On the Limits of Gate Elimination.
Proceedings of 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). LIPIcs 58, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, pp. 46:1–46:13, 2016.
pdf DOI ECCC
6 Alexander Golovnev, Alexander S. Kulikov, Alexander V. Smal, Suguru Tamaki.
Circuit Size Lower Bounds and #SAT Upper Bounds Through a General Framework.
Proceedings of 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). LIPIcs 58, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, pp. 45:1–45:16, 2016.
pdf DOI ECCC
7 Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin.
Families with Infants: Speeding Up Algorithms for NP-Hard Problems Using FFT.
ACM Transactions on Algorithms, Volume 12, Issue 3, Article No. 35, 2016.
pdf DOI arXiv
8 Alexander Golovnev, Alexander S. Kulikov.
Weighted Gate Elimination: Boolean Dispersers for Quadratic Varieties Imply Improved Circuit Lower Bounds.
Proceedings of 7th Innovations in Theoretical Computer Science (ITCS 2016). ACM, pp. 405-411, 2016.
pdf DOI ECCC
9 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 27th ACM-SIAM Symposium on Discrete Algorithms (SODA 2016). SIAM, pp. 1643–1649. 2016.
pdf DOI arXiv
10 Fedor V. Fomin, Petr Golovach, Nikolay Karpov, Alexander S. Kulikov.
Parameterized Complexity of Secluded Connectivity Problems.
Proceedings of 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). LIPIcs 45, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, pp. 408–419, 2015.
pdf DOI arXiv
11 Evgeny Demenkov, Alexander S. Kulikov, Olga Melanich, Ivan Mihajlin.
New Lower Bounds on Circuit Size of Multi-output Functions.
Theory of Computing Systems, Volume 56, Issue 4, pp 630-642. 2015.
pdf DOI
12 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.
pdf DOI arXiv
13 Ivan Bliznets, Fedor V. Fomin, Petr Golovach, Nikolay Karpov, Alexander S. Kulikov, Saket Saurabh.
Parameterized Complexity of Superstring Problems.
Proceedings of 26th Annual Symposium on Combinatorial Pattern Matching (CPM 2015). Lecture Notes in Computer Science 9133, Springer, pp. 89-99, 2015.
pdf DOI arXiv
14 Alexander S. Kulikov, Sergey Savinov, Evgeniy Sluzhaev.
Greedy Conjecture for Strings of Length 4.
Proceedings of 26th Annual Symposium on Combinatorial Pattern Matching (CPM 2015). Lecture Notes in Computer Science 9133, Springer, pp. 307-315, 2015.
pdf DOI
15 Alexander Golovnev, Alexander S. Kulikov, Ivan MIhajlin.
Families with Infants: A General Approach to Solve Hard Partition Problems.
Proceedings of 41st International Colloquium on Automata, Languages, and Programming (ICALP 2014). Lecture Notes in Computer Science 8572, Springer, pp. 551-562, 2014.
pdf DOI
16 Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin.
Solving SCS for Bounded Length Strings in Fewer than 2n Steps.
Information Processing Letters. Volume 114, Issue 8, pp 421–425. 2014.
pdf DOI
17 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.
pdf DOI
18 Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin.
Approximating the Shortest Superstring Problem Using de Bruijn Graphs.
Proceedings of 24th Annual Symposium on Combinatorial Pattern Matching (CPM 2013), Lecture Notes in Computer Science 7922, Springer, pp. 120–129, 2013.
pdf DOI
19 Alexander S. Kulikov, Olga Melanich, Ivan Mihajlin.
A 5n-o(n) Lower Bound on the Circuit Size over U_2 of a Linear Boolean Function.
Proceedings of Computability in Europe (CiE 2012), Lecture Notes in Computer Science 7318, Springer, pp. 432–439, 2012.
pdf DOI
20 Evgeny Demenkov, Alexander S. Kulikov, Ivan Mihajlin, Hiroki Morizumi.
Computing All MOD-functions Simultaneously.
Proceedings of 7th International Computer Science Symposium in Russia (CSR 2012), Lecture Notes in Computer Science 7353, Springer, pp. 81–88, 2012.
pdf DOI
21 Anton Bankevich, Sergey Nurk, Dmitry Antipov, Alexey Gurevich, Mikhail Dvorkin, Alexander S. Kulikov, Valery M. Lesin, Sergey I. Nikolenko, Son Pham, Andrey Prjibelski, Alexey V. Pyshkin, Alexander V. Sirotkin, Nikolay Vyahhi, Glenn Tesler, Max A. Alekseyev, Pavel Pevzner.
SPAdes: A New Genome Assembly Algorithm and Its Applications to Single-Cell Sequencing.
Journal of Computational Biology, 19(5), pp. 455-477, 2012.
pdf DOI
22 Evgeny Demenkov, Alexander S. Kulikov.
An Elementary Proof of a 3n − o(n) Lower Bound on the Circuit Complexity of Affine Dispersers.
Proceedings of 36th International Symposium on Mathematical Foundations of Computer Science (MFCS 2011), Lecture Notes in Computer Science 6907, Springer, pp. 256–265, 2011.
pdf DOI
23 Arist Kojevnikov, Alexander S. Kulikov.
Circuit Complexity and Multiplicative Complexity of Boolean Functions.
Proceedings of Computability in Europe (CiE 2010), Lecture Notes in Computer Science 6158, pp. 239–245, 2010.
pdf DOI
24 Pavel Hrubes, Stasys Jukna, Alexander S. Kulikov, Pavel Pudlak.
On Convex Complexity Measures.
Theoretical Computer Science 411, Elsevier, pp. 1842-1854, 2010.
pdf DOI
25 Evgeny Demenkov, Arist Kojevnikov, Alexander S. Kulikov, Grigory Yaroslavtsev.
New Upper Bounds on the Boolean Circuit Complexity of Symmetric Functions.
Information Processing Letters 110(7), pp. 264-267, 2010.
pdf DOI
26 Alexander S. Kulikov, Konstantin Kutzkov.
New Bounds for MAX-SAT by Clause Learning.
Discrete Mathematics and Applications, vol. 19 (2), pp. 155-172, 2009.
pdf DOI
27 Arist Kojevnikov, Alexander S. Kulikov, Grigory Yaroslavtsev.
Finding Efficient Circuits Using SAT-solvers.
Proceedings of the Twelfth International Conference on Theory and Applications of Satisfiability Testing (SAT 2009), Lecture Notes in Computer Science 5584, Springer, pp. 32-44, 2009.
pdf DOI
28 Stasys Jukna, Alexander S. Kulikov.
On Covering Graphs by Complete Bipartite Subgraphs.
Discrete Mathematics 309(10), Elsevier, pp. 3399-3403, 2009.
pdf DOI
29 Edward A. Hirsch, Arits Kojevnikov, A. S. Kulikov, and Sergey I. Nikolenko.
Complexity of Semialgebraic Proofs with Restricted Degree of Falsity.
Journal on Satisfiability, Boolean Modeling and Computation 6, IOS Press, pp. 53-69, 2008.
pdf
30 Alexander S. Kulikov, Konstantin Kutzkov.
New Bounds for MAX-SAT by Clause Learning.
Proceedings of the 2nd International Computer Science Symposium in Russia (CSR 2007), Lecture Notes in Computer Science 4649, Springer, pp. 194-204, 2007.
pdf DOI
31 Alexander S. Kulikov.
Automated Proofs of Upper Bounds for NP-hard Problems: Implementation Details.
PDMI preprint 21/2006.
pdf
32 Sergey S. Fedin, Alexander S. Kulikov.
Automated Proofs of Upper Bounds on the Running Time of Splitting Algorithms.
Proceedings of the International Workshop on Parameterized and Exact Computation (IWPEC 2006), Lecture Notes in Computer Science 3162, pp. 248-259, 2006.
pdf DOI
33 Arist Kojevnikov, Alexander S. Kulikov.
Complexity of Semialgebraic Proofs with Restricted Degree of Falsity.
Proceedings of the Ninth International Conference on Theory and Applications of Satisfiability Testing (SAT 2006), Lecture Notes in Computer Science 4121, Springer, pp. 11-21, 2006.
pdf DOI
34 Sergey S. Fedin, Alexander S. Kulikov.
Automated Proofs of Upper Bounds on the Running Time of Splitting Algorithms.
Journal of Mathematical Sciences 134(5), pp.2383-2391, 2006.
pdf DOI
35 Arist Kojevnikov, Alexander S. Kulikov.
A New Approach to Proving Upper Bounds for MAX-2-SAT.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), pp.11-17, 2006.
pdf DOI
36 Alexander S. Kulikov.
An Upper Bound O(2^{0.16254n}) for Exact 3-Satisfiability: A Simpler Proof.
Journal of Mathematical Sciences 126(3), pp. 1195-1199, 2005.
pdf DOI
37 Sergey S. Fedin, Alexander S. Kulikov.
A 2{|E|/4}-Time Algorithm for MAX-CUT.
Journal of Mathematical Sciences 126(3), Springer, pp 1200-1204, 2005.
pdf DOI
38 Alexander S. Kulikov.
Automated Generation of Simplification Rules for SAT and MAXSAT.
Proceedings of the Eighth International Conference on Theory and Applications of Satisfiability Testing (SAT 2005), Lecture Notes in Computer Science 3569, Springer, pp.430-436, 2005.
pdf DOI