Alexander S. Kulikov

Proceedings of the 2024 Symposium on Simplicity in Algorithms, 2024

Computations with polynomial evaluation oracle: ruling out superlinear SETH-based lower bounds.

[BibT_eX]

[DOI]

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Improved Space Bounds for Subset Sum.

[BibT_eX]

[DOI]

Proceedings of the 32nd Annual European Symposium on Algorithms, 2024

2023

Improving 3N Circuit Complexity Lower Bounds.

[BibT_eX]

[DOI]

Comput. Complex., December, 2023

Polynomial formulations as a barrier for reduction-based hardness proofs.

[BibT_eX]

[DOI]

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

2022

Polynomial formulations as a barrier for reduction-based hardness proofs.

[BibT_eX]

[DOI]

CoRR, 2022

SAT-Based Circuit Local Improvement.

[BibT_eX]

[DOI]

Danila Pechenev

Nikita Slezkin

Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science, 2022

CNF Encodings of Parity.

[BibT_eX]

[DOI]

Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science, 2022

2021

SAT-based Circuit Local Improvement.

[BibT_eX]

[DOI]

Nikita Slezkin

Electron. Colloquium Comput. Complex., 2021

Circuit Depth Reductions.

[BibT_eX]

[DOI]

R. Ryan Williams

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Minimum Common String Partition: Exact Algorithms.

[BibT_eX]

[DOI]

Proceedings of the 29th Annual European Symposium on Algorithms, 2021

2019

Complexity of Linear Operators.

[BibT_eX]

[DOI]

Ivan Mikhailin

Andrey Mokhov

Vladimir V. Podolskii

Electron. Colloquium Comput. Complex., 2019

Collapsing Superstring Conjecture.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2019

2018

Gate elimination: Circuit size lower bounds and #SAT upper bounds.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2018

Preface to the Special Issue on Computer Science in Russia 2016.

[BibT_eX]

[DOI]

Gerhard J. Woeginger

Theory Comput. Syst., 2018

On the limits of gate elimination.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2018

Circuit Depth Reductions.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

Collapsing Superstring Conjecture.

[BibT_eX]

[DOI]

CoRR, 2018

Improving circuit size upper bounds using SAT-solvers.

[BibT_eX]

[DOI]

Proceedings of the 2018 Design, Automation & Test in Europe Conference & Exhibition, 2018

Lower Bounds for Unrestricted Boolean Circuits: Open Problems.

[BibT_eX]

[DOI]

Proceedings of the Computer Science - Theory and Applications, 2018

2017

Parameterized Complexity of Secluded Connectivity Problems.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2017

Tight Lower Bounds on Graph Embedding Problems.

[BibT_eX]

[DOI]

J. ACM, 2017

Parameterized Complexity of Superstring Problems.

[BibT_eX]

[DOI]

Algorithmica, 2017

2016

Families with Infants: Speeding Up Algorithms for NP-Hard Problems Using FFT.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2016

Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates.

[BibT_eX]

[DOI]

Vladimir V. Podolskii

Electron. Colloquium Comput. Complex., 2016

Circuit size lower bounds and #SAT upper bounds through a general framework.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

Tight Bounds for Graph Homomorphism and Subgraph Isomorphism.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

2015

New Lower Bounds on Circuit Size of Multi-output Functions.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2015

Weighted gate elimination: Boolean dispersers for quadratic varieties imply improved circuit lower bounds.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

A better-than-3n lower bound for the circuit complexity of an explicit function.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

Tight Bounds for Subgraph Isomorphism and Graph Homomorphism.

[BibT_eX]

[DOI]

CoRR, 2015

Lower Bounds for the Graph Homomorphism Problem.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

Greedy Conjecture for Strings of Length 4.

[BibT_eX]

[DOI]

Sergey Savinov

Evgeniy Sluzhaev

Proceedings of the Combinatorial Pattern Matching - 26th Annual Symposium, 2015

2014

Solving SCS for bounded length strings in fewer than 2<sup>n</sup> steps.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2014

Families with Infants: A General Approach to Solve Hard Partition Problems.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

2013

Solving 3-Superstring in 3 n/3 Time.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2013, 2013

Approximating Shortest Superstring Problem Using de Bruijn Graphs.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Pattern Matching, 24th Annual Symposium, 2013

2012

SPAdes: A New Genome Assembly Algorithm and Its Applications to Single-Cell Sequencing.

[BibT_eX]

[DOI]

J. Comput. Biol., 2012

Computing All MOD-Functions Simultaneously.

[BibT_eX]

[DOI]

Proceedings of the Computer Science - Theory and Applications, 2012

A 5n - o(n) Lower Bound on the Circuit Size over U 2 of a Linear Boolean Function.

[BibT_eX]

[DOI]

Olga Melanich

Proceedings of the How the World Computes, 2012

2011

An Elementary Proof of 3n-o(n) Lower Bound on the Circuit Complexity of Affine Dispersers.

[BibT_eX]

[DOI]

Evgeny Demenkov

Electron. Colloquium Comput. Complex., 2011

2010

On convex complexity measures.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2010

New upper bounds on the Boolean circuit complexity of symmetric functions.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2010

Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)

[BibT_eX]

[DOI]

CoRR, 2010

Circuit Complexity and Multiplicative Complexity of Boolean Functions.

[BibT_eX]

[DOI]

Proceedings of the Programs, Proofs, Processes, 6th Conference on Computability in Europe, 2010

2009

Complexity of Semialgebraic Proofs with Restricted Degree of Falsity.

[BibT_eX]

[DOI]

J. Satisf. Boolean Model. Comput., 2009

On covering graphs by complete bipartite subgraphs.

[BibT_eX]

[DOI]

Stasys Jukna

Discret. Math., 2009

Finding Efficient Circuits Using SAT-Solvers.

[BibT_eX]

[DOI]

Grigory Yaroslavtsev

Proceedings of the Theory and Applications of Satisfiability Testing, 2009

2007

New Bounds for MAX-SAT by Clause Learning.

[BibT_eX]

[DOI]

Konstantin Kutzkov

Proceedings of the Computer Science, 2007

2006

A new approach to proving upper bounds for MAX-2-SAT.

[BibT_eX]

[DOI]

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Complexity of Semialgebraic Proofs with Restricted Degree of Falsity.

[BibT_eX]

[DOI]

Proceedings of the Theory and Applications of Satisfiability Testing, 2006

2005

Automated Generation of Simplification Rules for SAT and MAXSAT.

[BibT_eX]

[DOI]

Proceedings of the Theory and Applications of Satisfiability Testing, 2005

2004

Automated Proofs of Upper Bounds on the Running Time of Splitting Algorithms.

[BibT_eX]

[DOI]

Sergey S. Fedin