Alexander S. Kulikov

96 papers A* 6A 12B 12C 2Misc 6Journal 52Unranked 6
YearRankTypeTitle / Venue / Authors
2026 A conf
Conditional Complexity Hardness: Monotone Circuit Size, Matrix Rigidity, and Tensor Rank.
STACS
Nikolai Chukhin, Alexander S. Kulikov, Ivan Mihajlin, Arina Smirnova
2026 A conf
Smaller Circuits for Bit Addition.
STACS
Mikhail Goncharov, Alexander S. Kulikov, Georgie Levtsov
2025 A* conf
Cirbo: A New Tool for Boolean Circuit Analysis and Synthesis.
AAAI
Daniil Averkov, Tatiana Belova, Gregory Emdin, Mikhail Goncharov, Viktoriia Krivogornitsyna, Alexander S. Kulikov, Fedor Kurmazov, Daniil Levtsov, Georgie Levtsov, Vsevolod Vaskin, Aleksey Vorobiev
2025 J jnl
Conditional Complexity Hardness: Monotone Circuit Size, Matrix Rigidity, and Tensor Rank Under NSETH and Beyond.
Electron. Colloquium Comput. Complex.
Nikolai Chukhin, Alexander S. Kulikov, Ivan Mihajlin, Arina Smirnova
2025 J jnl
New Challenges in Combinatorial Optimization.
J. Comb. Optim.
Bo Chen, Alexander S. Kulikov, Silvano Martello
2025 J jnl
Polynomial Formulations as a Barrier for Reduction-Based Hardness Proofs.
ACM Trans. Algorithms
Tatiana Belova, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Denil Sharipov
2025 J jnl
Simplifier: A New Tool for Boolean Circuit Simplification.
CoRR
Daniil Averkov, Gregory Emdin, Viktoriia Krivogornitsyna, Alexander S. Kulikov, Fedor Kurmazov, Alexander Smal, Vsevolod Vaskin
2025 J jnl
Smaller Circuits for Bit Addition.
CoRR
Mikhail Goncharov, Alexander S. Kulikov, Georgie Levtsov
2025 A conf
Toward Better Depth Lower Bounds: Strong Composition of XOR and a Random Function.
STACS
Nikolai Chukhin, Alexander S. Kulikov, Ivan Mihajlin
2024 J jnl
CNF Encodings of Symmetric Functions.
Theory Comput. Syst.
Gregory Emdin, Alexander S. Kulikov, Ivan Mihajlin, Nikita Slezkin
2024 J jnl
Cirbo: A New Tool for Boolean Circuit Analysis and Synthesis.
CoRR
Daniil Averkov, Tatiana Belova, Gregory Emdin, Mikhail Goncharov, Viktoriia Krivogornitsyna, Alexander S. Kulikov, Fedor Kurmazov, Daniil Levtsov, Georgie Levtsov, Vsevolod Vaskin, Aleksey Vorobiev
2024 A* conf
Computations with polynomial evaluation oracle: ruling out superlinear SETH-based lower bounds.
SODA
Tatiana Belova, Alexander S. Kulikov, Ivan Mihajlin, Olga Ratseeva, Grigory Reznikov, Denil Sharipov
2024 J jnl
Deriving Nonuniform Lower Bounds from Uniform Nondeterministic Lower Bounds.
CoRR
Nikolai Chukhin, Alexander S. Kulikov, Ivan Mihajlin, Arina Smirnova
2024 — conf
If Edge Coloring is Hard under SETH, then SETH is False.
SOSA
Alexander S. Kulikov, Ivan Mihajlin
2024 A conf
Improved Space Bounds for Subset Sum.
ESA
Tatiana Belova, Nikolai Chukhin, Alexander S. Kulikov, Ivan Mihajlin
2024 J jnl
Improved Space Bounds for Subset Sum.
CoRR
Tatiana Belova, Nikolai Chukhin, Alexander S. Kulikov, Ivan Mihajlin
2024 J jnl
Toward Better Depth Lower Bounds: Strong Composition of XOR and a Random Function.
CoRR
Nikolai Chukhin, Alexander S. Kulikov, Ivan Mikhajlin
2023 J jnl
Computations with polynomial evaluation oracle: ruling out superlinear SETH-based lower bounds.
CoRR
Tatiana Belova, Alexander S. Kulikov, Ivan Mihajlin, Olga Ratseeva, Grigory Reznikov, Denil Sharipov
2023 J jnl
Improving 3N Circuit Complexity Lower Bounds.
Comput. Complex.
Magnus Gausdal Find, Alexander Golovnev, Edward A. Hirsch, Alexander S. Kulikov
2023 A* conf
Polynomial formulations as a barrier for reduction-based hardness proofs.
SODA
Tatiana Belova, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Denil Sharipov
2022 B conf
CNF Encodings of Parity.
MFCS
Gregory Emdin, Alexander S. Kulikov, Ivan Mihajlin, Nikita Slezkin
2022 J jnl
CNF Encodings of Parity.
CoRR
Gregory Emdin, Alexander S. Kulikov, Ivan Mihajlin, Nikita Slezkin
2022 Misc ed.
Computer Science - Theory and Applications - 17th International Computer Science Symposium in Russia, CSR 2022, Virtual Event, June 29 - July 1, 2022, Proceedings
CSR
Alexander S. Kulikov, Sofya Raskhodnikova
2022 J jnl
Polynomial formulations as a barrier for reduction-based hardness proofs.
CoRR
Alexander S. Kulikov, Ivan Mihajlin
2022 B conf
SAT-Based Circuit Local Improvement.
MFCS
Alexander S. Kulikov, Danila Pechenev, Nikita Slezkin
2021 A conf
Circuit Depth Reductions.
ITCS
Alexander Golovnev, Alexander S. Kulikov, R. Ryan Williams
2021 A conf
Minimum Common String Partition: Exact Algorithms.
ESA
Marek Cygan, Alexander S. Kulikov, Ivan Mihajlin, Maksim Nikolaev, Grigory Reznikov
2021 J jnl
SAT-based Circuit Local Improvement.
CoRR
Alexander S. Kulikov, Nikita Slezkin
2021 J jnl
SAT-based Circuit Local Improvement.
Electron. Colloquium Comput. Complex.
Alexander S. Kulikov, Nikita Slezkin
2019 — conf
Collapsing Superstring Conjecture.
APPROX-RANDOM
Alexander Golovnev, Alexander S. Kulikov, Alexander Logunov, Ivan Mihajlin, Maksim Nikolaev
2019 B conf
Complexity of Linear Operators.
ISAAC
Alexander S. Kulikov, Ivan Mikhailin, Andrey Mokhov, Vladimir V. Podolskii
2019 J jnl
Complexity of Linear Operators.
Electron. Colloquium Comput. Complex.
Alexander S. Kulikov, Ivan Mikhailin, Andrey Mokhov, Vladimir V. Podolskii
2019 J jnl
Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates.
Theory Comput. Syst.
Alexander S. Kulikov, Vladimir V. Podolskii
2018 J jnl
Circuit Depth Reductions.
CoRR
Alexander Golovnev, Alexander S. Kulikov
2018 J jnl
Circuit Depth Reductions.
Electron. Colloquium Comput. Complex.
Alexander Golovnev, Alexander S. Kulikov
2018 J jnl
Collapsing Superstring Conjecture.
CoRR
Alexander Golovnev, Alexander S. Kulikov, Alexander Logunov, Ivan Mihajlin
2018 J jnl
Complexity of Linear Operators.
CoRR
Alexander S. Kulikov, Ivan Mikhailin, Andrey Mokhov, Vladimir V. Podolskii
2018 J jnl
Gate elimination: Circuit size lower bounds and #SAT upper bounds.
Theor. Comput. Sci.
Alexander Golovnev, Alexander S. Kulikov, Alexander V. Smal, Suguru Tamaki
2018 A conf
Improving circuit size upper bounds using SAT-solvers.
DATE
Alexander S. Kulikov
2018 Misc conf
Lower Bounds for Unrestricted Boolean Circuits: Open Problems.
CSR
Alexander S. Kulikov
2018 J jnl
On the limits of gate elimination.
J. Comput. Syst. Sci.
Alexander Golovnev, Edward A. Hirsch, Alexander Knop, Alexander S. Kulikov
2018 J jnl
Preface to the Special Issue on Computer Science in Russia 2016.
Theory Comput. Syst.
Alexander S. Kulikov, Gerhard J. Woeginger
2017 A conf
Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates.
STACS
Alexander S. Kulikov, Vladimir V. Podolskii
2017 J jnl
Parameterized Complexity of Secluded Connectivity Problems.
Theory Comput. Syst.
Fedor V. Fomin, Petr A. Golovach, Nikolay Karpov, Alexander S. Kulikov
2017 J jnl
Parameterized Complexity of Superstring Problems.
Algorithmica
Ivan Bliznets, Fedor V. Fomin, Petr A. Golovach, Nikolay Karpov, Alexander S. Kulikov, Saket Saurabh
2017 J jnl
Tight Lower Bounds on Graph Embedding Problems.
J. ACM
Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, Arkadiusz Socala
2016 A* conf
A Better-Than-3n Lower Bound for the Circuit Complexity of an Explicit Function.
FOCS
Magnus Gausdal Find, Alexander Golovnev, Edward A. Hirsch, Alexander S. Kulikov
2016 B conf
Circuit Size Lower Bounds and #SAT Upper Bounds Through a General Framework.
MFCS
Alexander Golovnev, Alexander S. Kulikov, Alexander V. Smal, Suguru Tamaki
2016 J jnl
Circuit size lower bounds and #SAT upper bounds through a general framework.
Electron. Colloquium Comput. Complex.
Alexander Golovnev, Alexander S. Kulikov, Alexander Smal, Suguru Tamaki
2016 Misc ed.
Computer Science - Theory and Applications - 11th International Computer Science Symposium in Russia, CSR 2016, St. Petersburg, Russia, June 9-13, 2016, Proceedings
CSR
Alexander S. Kulikov, Gerhard J. Woeginger
2016 J jnl
Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates.
CoRR
Alexander S. Kulikov, Vladimir V. Podolskii
2016 J jnl
Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates.
Electron. Colloquium Comput. Complex.
Alexander S. Kulikov, Vladimir V. Podolskii
2016 B ed.
Experimental Algorithms - 15th International Symposium, SEA 2016, St. Petersburg, Russia, June 5-8, 2016, Proceedings
SEA
Andrew V. Goldberg, Alexander S. Kulikov
2016 J jnl
Families with Infants: Speeding Up Algorithms for NP-Hard Problems Using FFT.
ACM Trans. Algorithms
Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
2016 B conf
On the Limits of Gate Elimination.
MFCS
Alexander Golovnev, Edward A. Hirsch, Alexander Knop, Alexander S. Kulikov
2016 J jnl
On the Limits of Gate Elimination.
Electron. Colloquium Comput. Complex.
Alexander Golovnev, Edward A. Hirsch, Alexander Knop, Alexander S. Kulikov
2016 A* conf
Tight Bounds for Graph Homomorphism and Subgraph Isomorphism.
SODA
Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, Arkadiusz Socala
2016 J jnl
Tight Lower Bounds on Graph Embedding Problems.
CoRR
Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, Arkadiusz Socala
2016 A conf
Weighted Gate Elimination: Boolean Dispersers for Quadratic Varieties Imply Improved Circuit Lower Bounds.
ITCS
Alexander Golovnev, Alexander S. Kulikov
2015 J jnl
A better-than-3n lower bound for the circuit complexity of an explicit function.
Electron. Colloquium Comput. Complex.
Magnus Gausdal Find, Alexander Golovnev, Edward A. Hirsch, Alexander S. Kulikov
2015 B conf
Greedy Conjecture for Strings of Length 4.
CPM
Alexander S. Kulikov, Sergey Savinov, Evgeniy Sluzhaev
2015 — conf
Lower Bounds for the Graph Homomorphism Problem.
ICALP (1)
Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
2015 J jnl
Lower Bounds for the Graph Homomorphism Problem.
CoRR
Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
2015 J jnl
New Lower Bounds on Circuit Size of Multi-output Functions.
Theory Comput. Syst.
Evgeny Demenkov, Alexander S. Kulikov, Olga Melanich, Ivan Mihajlin
2015 — conf
Parameterized Complexity of Secluded Connectivity Problems.
FSTTCS
Fedor V. Fomin, Petr A. Golovach, Nikolay Karpov, Alexander S. Kulikov
2015 J jnl
Parameterized Complexity of Secluded Connectivity Problems.
CoRR
Fedor V. Fomin, Petr A. Golovach, Nikolay Karpov, Alexander S. Kulikov
2015 B conf
Parameterized Complexity of Superstring Problems.
CPM
Ivan Bliznets, Fedor V. Fomin, Petr A. Golovach, Nikolay Karpov, Alexander S. Kulikov, Saket Saurabh
2015 J jnl
Parameterized Complexity of Superstring Problems.
CoRR
Ivan Bliznets, Fedor V. Fomin, Petr A. Golovach, Nikolay Karpov, Alexander S. Kulikov, Saket Saurabh
2015 J jnl
Tight Bounds for Subgraph Isomorphism and Graph Homomorphism.
CoRR
Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
2015 J jnl
Weighted gate elimination: Boolean dispersers for quadratic varieties imply improved circuit lower bounds.
Electron. Colloquium Comput. Complex.
Alexander Golovnev, Alexander S. Kulikov
2014 B ed.
Combinatorial Pattern Matching - 25th Annual Symposium, CPM 2014, Moscow, Russia, June 16-18, 2014. Proceedings
CPM
Alexander S. Kulikov, Sergei O. Kuznetsov, Pavel A. Pevzner
2014 — conf
Families with Infants: A General Approach to Solve Hard Partition Problems.
ICALP (1)
Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
2014 J jnl
Families with infants: speeding up algorithms for NP-hard problems using FFT.
CoRR
Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
2014 J jnl
Solving SCS for bounded length strings in fewer than 2
Inf. Process. Lett.
Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
2013 B conf
Approximating Shortest Superstring Problem Using de Bruijn Graphs.
CPM
Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
2013 J jnl
Families with infants: a general approach to solve hard partition problems.
CoRR
Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
2013 B conf
Solving 3-Superstring in 3 n/3 Time.
MFCS
Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
2012 C conf
A 5n - o(n) Lower Bound on the Circuit Size over U 2 of a Linear Boolean Function.
CiE
Alexander S. Kulikov, Olga Melanich, Ivan Mihajlin
2012 Misc conf
Computing All MOD-Functions Simultaneously.
CSR
Evgeny Demenkov, Alexander S. Kulikov, Ivan Mihajlin, Hiroki Morizumi
2012 J jnl
SPAdes: A New Genome Assembly Algorithm and Its Applications to Single-Cell Sequencing.
J. Comput. Biol.
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
2011 J jnl
An Elementary Proof of 3n-o(n) Lower Bound on the Circuit Complexity of Affine Dispersers.
Electron. Colloquium Comput. Complex.
Evgeny Demenkov, Alexander S. Kulikov
2011 B conf
An Elementary Proof of a 3n - o(n) Lower Bound on the Circuit Complexity of Affine Dispersers.
MFCS
Evgeny Demenkov, Alexander S. Kulikov
2011 Misc ed.
Computer Science - Theory and Applications - 6th International Computer Science Symposium in Russia, CSR 2011, St. Petersburg, Russia, June 14-18, 2011. Proceedings
CSR
Alexander S. Kulikov, Nikolay K. Vereshchagin
2010 C conf
Circuit Complexity and Multiplicative Complexity of Boolean Functions.
CiE
Arist Kojevnikov, Alexander S. Kulikov
2010 J jnl
Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)
CoRR
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
2010 J jnl
New upper bounds on the Boolean circuit complexity of symmetric functions.
Inf. Process. Lett.
Evgeny Demenkov, Arist Kojevnikov, Alexander S. Kulikov, Grigory Yaroslavtsev
2010 J jnl
On convex complexity measures.
Theor. Comput. Sci.
Pavel Hrubes, Stasys Jukna, Alexander S. Kulikov, Pavel Pudlák
2009 J jnl
Complexity of Semialgebraic Proofs with Restricted Degree of Falsity.
J. Satisf. Boolean Model. Comput.
Edward A. Hirsch, Arist Kojevnikov, Alexander S. Kulikov, Sergey I. Nikolenko
2009 A conf
Finding Efficient Circuits Using SAT-Solvers.
SAT
Arist Kojevnikov, Alexander S. Kulikov, Grigory Yaroslavtsev
2009 J jnl
On convex complexity measures.
Electron. Colloquium Comput. Complex.
Pavel Hrubes, Stasys Jukna, Alexander S. Kulikov, Pavel Pudlák
2009 J jnl
On covering graphs by complete bipartite subgraphs.
Discret. Math.
Stasys Jukna, Alexander S. Kulikov
2007 Misc conf
New Bounds for MAX-SAT by Clause Learning.
CSR
Alexander S. Kulikov, Konstantin Kutzkov
2006 A* conf
A new approach to proving upper bounds for MAX-2-SAT.
SODA
Arist Kojevnikov, Alexander S. Kulikov
2006 A conf
Complexity of Semialgebraic Proofs with Restricted Degree of Falsity.
SAT
Arist Kojevnikov, Alexander S. Kulikov
2005 A conf
Automated Generation of Simplification Rules for SAT and MAXSAT.
SAT
Alexander S. Kulikov
2004 — conf
Automated Proofs of Upper Bounds on the Running Time of Splitting Algorithms.
IWPEC
Sergey S. Fedin, Alexander S. Kulikov