Alexander S. Kulikov

Publication Activity (10 Years)

Years Active: 2004-2024
Publications (10 Years): 42

Top Topics

Parameterized Complexity

Subgraph Isomorphism

Top Venues

Electron. Colloquium Comput. Complex.

Theory Comput. Syst.

Publications

Tatiana Belova, Alexander S. Kulikov, Ivan Mihajlin, Olga Ratseeva, Grigory Reznikov, Denil Sharipov
Computations with polynomial evaluation oracle: ruling out superlinear SETH-based lower bounds. SODA (2024)
Alexander S. Kulikov, Ivan Mihajlin
If Edge Coloring is Hard under SETH, then SETH is False. SOSA (2024)
Tatiana Belova, Nikolai Chukhin, Alexander S. Kulikov, Ivan Mihajlin
Improved Space Bounds for Subset Sum. CoRR (2024)
Tatiana Belova, Alexander S. Kulikov, Ivan Mihajlin, Olga Ratseeva, Grigory Reznikov, Denil Sharipov
Computations with polynomial evaluation oracle: ruling out superlinear SETH-based lower bounds. CoRR (2023)
Tatiana Belova, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Denil Sharipov
Polynomial formulations as a barrier for reduction-based hardness proofs. SODA (2023)
Magnus Gausdal Find, Alexander Golovnev, Edward A. Hirsch, Alexander S. Kulikov
Improving 3N Circuit Complexity Lower Bounds. Comput. Complex. 32 (2) (2023)
Alexander S. Kulikov, Ivan Mihajlin
Polynomial formulations as a barrier for reduction-based hardness proofs. CoRR (2022)
Alexander S. Kulikov, Danila Pechenev, Nikita Slezkin
SAT-Based Circuit Local Improvement. MFCS (2022)
Gregory Emdin, Alexander S. Kulikov, Ivan Mihajlin, Nikita Slezkin
CNF Encodings of Parity. CoRR (2022)
Gregory Emdin, Alexander S. Kulikov, Ivan Mihajlin, Nikita Slezkin
CNF Encodings of Parity. MFCS (2022)
Alexander S. Kulikov, Nikita Slezkin
SAT-based Circuit Local Improvement. CoRR (2021)
Marek Cygan, Alexander S. Kulikov, Ivan Mihajlin, Maksim Nikolaev, Grigory Reznikov
Minimum Common String Partition: Exact Algorithms. ESA (2021)
Alexander S. Kulikov, Nikita Slezkin
SAT-based Circuit Local Improvement. Electron. Colloquium Comput. Complex. 28 (2021)
Alexander Golovnev, Alexander S. Kulikov, R. Ryan Williams
Circuit Depth Reductions. ITCS (2021)
Alexander S. Kulikov, Vladimir V. Podolskii
Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates. Theory Comput. Syst. 63 (5) (2019)
Alexander S. Kulikov, Ivan Mikhailin, Andrey Mokhov, Vladimir V. Podolskii
Complexity of Linear Operators. ISAAC (2019)
Alexander Golovnev, Alexander S. Kulikov, Alexander Logunov, Ivan Mihajlin, Maksim Nikolaev
Collapsing Superstring Conjecture. APPROX-RANDOM (2019)
Alexander S. Kulikov, Ivan Mikhailin, Andrey Mokhov, Vladimir V. Podolskii
Complexity of Linear Operators. Electron. Colloquium Comput. Complex. 26 (2019)
Alexander Golovnev, Alexander S. Kulikov
Circuit Depth Reductions. CoRR (2018)
Alexander S. Kulikov
Lower Bounds for Unrestricted Boolean Circuits: Open Problems. CSR (2018)
Alexander S. Kulikov, Ivan Mikhailin, Andrey Mokhov, Vladimir V. Podolskii
Complexity of Linear Operators. CoRR (2018)
Alexander S. Kulikov, Gerhard J. Woeginger
Preface to the Special Issue on Computer Science in Russia 2016. Theory Comput. Syst. 62 (3) (2018)
Alexander Golovnev, Edward A. Hirsch, Alexander Knop, Alexander S. Kulikov
On the limits of gate elimination. J. Comput. Syst. Sci. 96 (2018)
Alexander Golovnev, Alexander S. Kulikov, Alexander Logunov, Ivan Mihajlin
Collapsing Superstring Conjecture. CoRR (2018)
Alexander S. Kulikov
Improving circuit size upper bounds using SAT-solvers. DATE (2018)
Alexander Golovnev, Alexander S. Kulikov, Alexander V. Smal, Suguru Tamaki
Gate elimination: Circuit size lower bounds and #SAT upper bounds. Theor. Comput. Sci. 719 (2018)
Alexander Golovnev, Alexander S. Kulikov
Circuit Depth Reductions. Electron. Colloquium Comput. Complex. 25 (2018)
Fedor V. Fomin, Petr A. Golovach, Nikolay Karpov, Alexander S. Kulikov
Parameterized Complexity of Secluded Connectivity Problems. Theory Comput. Syst. 61 (3) (2017)
Alexander S. Kulikov, Vladimir V. Podolskii
Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates. STACS (2017)
Ivan Bliznets, Fedor V. Fomin, Petr A. Golovach, Nikolay Karpov, Alexander S. Kulikov, Saket Saurabh
Parameterized Complexity of Superstring Problems. Algorithmica 79 (3) (2017)
Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, Arkadiusz Socala
Tight Lower Bounds on Graph Embedding Problems. J. ACM 64 (3) (2017)
Alexander Golovnev, Edward A. Hirsch, Alexander Knop, Alexander S. Kulikov
On the Limits of Gate Elimination. Electron. Colloquium Comput. Complex. 23 (2016)
Magnus Gausdal Find, Alexander Golovnev, Edward A. Hirsch, Alexander S. Kulikov
A Better-Than-3n Lower Bound for the Circuit Complexity of an Explicit Function. FOCS (2016)
Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub W. Pachocki, Arkadiusz Socala
Tight Lower Bounds on Graph Embedding Problems. CoRR (2016)
Alexander S. Kulikov, Vladimir V. Podolskii
Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates. CoRR (2016)
Alexander Golovnev, Alexander S. Kulikov
Weighted Gate Elimination: Boolean Dispersers for Quadratic Varieties Imply Improved Circuit Lower Bounds. ITCS (2016)
Alexander Golovnev, Alexander S. Kulikov, Alexander Smal, Suguru Tamaki
Circuit size lower bounds and #SAT upper bounds through a general framework. Electron. Colloquium Comput. Complex. 23 (2016)
Alexander Golovnev, Alexander S. Kulikov, Alexander V. Smal, Suguru Tamaki
Circuit Size Lower Bounds and #SAT Upper Bounds Through a General Framework. MFCS (2016)
Alexander S. Kulikov, Vladimir V. Podolskii
Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates. Electron. Colloquium Comput. Complex. 23 (2016)
Alexander Golovnev, Edward A. Hirsch, Alexander Knop, Alexander S. Kulikov
On the Limits of Gate Elimination. MFCS (2016)
Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
Families with Infants: Speeding Up Algorithms for NP-Hard Problems Using FFT. ACM Trans. Algorithms 12 (3) (2016)
Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, Arkadiusz Socala
Tight Bounds for Graph Homomorphism and Subgraph Isomorphism. SODA (2016)
Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
Lower Bounds for the Graph Homomorphism Problem. CoRR (2015)
Magnus Gausdal Find, Alexander Golovnev, Edward A. Hirsch, Alexander S. Kulikov
A better-than-3n lower bound for the circuit complexity of an explicit function. Electron. Colloquium Comput. Complex. 22 (2015)
Evgeny Demenkov, Alexander S. Kulikov, Olga Melanich, Ivan Mihajlin
New Lower Bounds on Circuit Size of Multi-output Functions. Theory Comput. Syst. 56 (4) (2015)
Ivan Bliznets, Fedor V. Fomin, Petr A. Golovach, Nikolay Karpov, Alexander S. Kulikov, Saket Saurabh
Parameterized Complexity of Superstring Problems. CoRR (2015)
Alexander Golovnev, Alexander S. Kulikov
Weighted gate elimination: Boolean dispersers for quadratic varieties imply improved circuit lower bounds. Electron. Colloquium Comput. Complex. 22 (2015)
Alexander S. Kulikov, Sergey Savinov, Evgeniy Sluzhaev
Greedy Conjecture for Strings of Length 4. CPM (2015)
Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
Tight Bounds for Subgraph Isomorphism and Graph Homomorphism. CoRR (2015)
Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
Lower Bounds for the Graph Homomorphism Problem. ICALP (1) (2015)
Ivan Bliznets, Fedor V. Fomin, Petr A. Golovach, Nikolay Karpov, Alexander S. Kulikov, Saket Saurabh
Parameterized Complexity of Superstring Problems. CPM (2015)
Fedor V. Fomin, Petr A. Golovach, Nikolay Karpov, Alexander S. Kulikov
Parameterized Complexity of Secluded Connectivity Problems. CoRR (2015)
Fedor V. Fomin, Petr A. Golovach, Nikolay Karpov, Alexander S. Kulikov
Parameterized Complexity of Secluded Connectivity Problems. FSTTCS (2015)
Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
Families with Infants: A General Approach to Solve Hard Partition Problems. ICALP (1) (2014)
Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
Families with infants: speeding up algorithms for NP-hard problems using FFT. CoRR (2014)
Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
steps. Inf. Process. Lett. 114 (8) (2014)
Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
Solving 3-Superstring in 3 n/3 Time. MFCS (2013)
Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
Approximating Shortest Superstring Problem Using de Bruijn Graphs. CPM (2013)
Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
Families with infants: a general approach to solve hard partition problems. CoRR (2013)
Anton Bankevich, Sergey Nurk, Dmitry Antipov, Alexey A. Gurevich, Mikhail Dvorkin, Alexander S. Kulikov, Valery M. Lesin, Sergey I. Nikolenko, Son K. Pham, Andrey D. Prjibelski, Alex Pyshkin, Alexander Sirotkin, Nikolay Vyahhi, Glenn Tesler, Max A. Alekseyev, Pavel A. Pevzner
SPAdes: A New Genome Assembly Algorithm and Its Applications to Single-Cell Sequencing. J. Comput. Biol. 19 (5) (2012)
Evgeny Demenkov, Alexander S. Kulikov, Ivan Mihajlin, Hiroki Morizumi
Computing All MOD-Functions Simultaneously. CSR (2012)
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. CiE (2012)
Evgeny Demenkov, Alexander S. Kulikov
An Elementary Proof of 3n-o(n) Lower Bound on the Circuit Complexity of Affine Dispersers. Electron. Colloquium Comput. Complex. 18 (2011)
Evgeny Demenkov, Alexander S. Kulikov
An Elementary Proof of a 3n - o(n) Lower Bound on the Circuit Complexity of Affine Dispersers. MFCS (2011)
Pavel Hrubes, Stasys Jukna, Alexander S. Kulikov, Pavel Pudlák
On convex complexity measures. Theor. Comput. Sci. 411 (16-18) (2010)
Arist Kojevnikov, Alexander S. Kulikov
Circuit Complexity and Multiplicative Complexity of Boolean Functions. CiE (2010)
Evgeny Demenkov, Arist Kojevnikov, Alexander S. Kulikov, Grigory Yaroslavtsev
New upper bounds on the Boolean circuit complexity of symmetric functions. Inf. Process. Lett. 110 (7) (2010)
Prahladh Harsha, Moses Charikar, Matthew Andrews, Sanjeev Arora, Subhash Khot, Dana Moshkovitz, Lisa Zhang, Ashkan Aazami, Dev Desai, Igor Gorodezky, Geetha Jagannathan, Alexander S. Kulikov, Darakhshan J. Mir, Alantha Newman, Aleksandar Nikolov, David Pritchard, Gwen Spencer
Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes) CoRR (2010)
Stasys Jukna, Alexander S. Kulikov
On covering graphs by complete bipartite subgraphs. Discret. Math. 309 (10) (2009)
Pavel Hrubes, Stasys Jukna, Alexander S. Kulikov, Pavel Pudlák
On convex complexity measures. Electron. Colloquium Comput. Complex. 16 (2009)
Arist Kojevnikov, Alexander S. Kulikov, Grigory Yaroslavtsev
Finding Efficient Circuits Using SAT-Solvers. SAT (2009)
Edward A. Hirsch, Arist Kojevnikov, Alexander S. Kulikov, Sergey I. Nikolenko
Complexity of Semialgebraic Proofs with Restricted Degree of Falsity. J. Satisf. Boolean Model. Comput. 6 (1-3) (2009)
Alexander S. Kulikov, Konstantin Kutzkov
New Bounds for MAX-SAT by Clause Learning. CSR (2007)
Arist Kojevnikov, Alexander S. Kulikov
A new approach to proving upper bounds for MAX-2-SAT. SODA (2006)
Arist Kojevnikov, Alexander S. Kulikov
Complexity of Semialgebraic Proofs with Restricted Degree of Falsity. SAT (2006)
Alexander S. Kulikov
Automated Generation of Simplification Rules for SAT and MAXSAT. SAT (2005)
Sergey S. Fedin, Alexander S. Kulikov
Automated Proofs of Upper Bounds on the Running Time of Splitting Algorithms. IWPEC (2004)