AKAlexander S. Kulikov
Alexander S. Kulikov
*This is an algorithmically generated author record based on publicly available information.
Research Subjects
Alexander S. Kulikov has a total of 74 co-authors. Here are the top co-authors by number of shared publications:
Ivan Mihajlin
University of California-San Diego, CA, U.S.A
10 shared publicationsAlexander Golovnev
NYU, New York, NY 10003 USA
9 shared publications- Alexander Golovnev
Georgetown University
6 shared publications - Fedor V. Fomin
Department of Informatics, University of Bergen
6 shared publications - Ivan Mihajlin
JetBrains Research
5 shared publications Arist Kojevnikov
St. Petersburg Department of Steklov Institute of Mathematics
3 shared publications
Latest Publications
- Open Access
- 8 September 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 21 (4) , 1-44
Polynomial Formulations as a Barrier for Reduction-Based Hardness Proofs
The Strong Exponential Time Hypothesis (SETH) asserts that for every \(\varepsilon > 0\) there exists k such that k -SAT requires time \((2-\varepsilon)^{n}\) . The field of fine-grained complexity has leveraged SETH to prove quite tight conditional lower bounds for dozens of problems in various domains and complexity classes, including Edit Distance, Graph Diameter, Hitting Set, Independent Set, and Orthogonal Vectors. Yet, it has been repeatedly asked in the literature whether SETH-hardness results can be proven for other fundamental problems such as Hamiltonian Path, Independent Set, Chromatic Number, MAX- k -SAT, and Set Cover. In this article, we show that fine-grained reductions implying even \(\lambda^{n}\) -hardness of these problems from SETH for any \(\lambda > 1\) , would imply new circuit lower bounds: super-linear lower bounds for Boolean series-parallel circuits or polynomial lower bounds for arithmetic circuits (each of which is a four-decade open question). We also extend this barrier result to the class of parameterized problems. Namely, for every \(\lambda > 1\) we conditionally rule out fine-grained reductions implying SETH-based lower bounds of \(\lambda^{k}\) for a number of problems parameterized by the solution size k . Our main technical tool is a new concept called polynomial formulations. In particular, we show that many problems can be represented by relatively succinct low-degree polynomials, and that any problem with such a representation cannot be proven SETH-hard (without proving new circuit lower bounds).- 8 September 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 21 (4) , 1-44
Open AccessPolynomial Formulations as a Barrier for Reduction-Based Hardness Proofs
The Strong Exponential Time Hypothesis (SETH) asserts that for every \(\varepsilon > 0\) there exists k such that k -SAT requires time \((2-\varepsilon)^{n}\) . The field of fine-grained complexity has leveraged SETH to prove quite tight conditional lower bounds for dozens of problems in various domains and complexity classes, including Edit Distance, Graph Diameter, Hitting Set, Independent Set, and Orthogonal Vectors. Yet, it has been repeatedly asked in the literature whether SETH-hardness results can be proven for other fundamental problems such as Hamiltonian Path, Independent Set, Chromatic Number, MAX- k -SAT, and Set Cover. In this article, we show that fine-grained reductions implying even \(\lambda^{n}\) -hardness of these problems from SETH for any \(\lambda > 1\) , would imply new circuit lower bounds: super-linear lower bounds for Boolean series-parallel circuits or polynomial lower bounds for arithmetic circuits (each of which is a four-decade open question). We also extend this barrier result to the class of parameterized problems. Namely, for every \(\lambda > 1\) we conditionally rule out fine-grained reductions implying SETH-based lower bounds of \(\lambda^{k}\) for a number of problems parameterized by the solution size k . Our main technical tool is a new concept called polynomial formulations. In particular, we show that many problems can be represented by relatively succinct low-degree polynomials, and that any problem with such a representation cannot be proven SETH-hard (without proving new circuit lower bounds). - 26 March 2024
- Published by Springer Nature in Theory of Computing Systems
- Vol. 68 (5) , 1-21
CNF Encodings of Symmetric Functions
- 26 March 2024
- Published by Springer Nature in Theory of Computing Systems
- Vol. 68 (5) , 1-21
CNF Encodings of Symmetric Functions
- 16 December 2023
- Published by Springer Nature in computational complexity
- Vol. 32 (2) , 1-82
Improving $3N$ Circuit Complexity Lower Bounds- 16 December 2023
- Published by Springer Nature in computational complexity
- Vol. 32 (2) , 1-82
Improving $3N$ Circuit Complexity Lower Bounds- Open Access
Computations with polynomial evaluation oracle: ruling out superlinear SETH-based lower bounds
The field of fine-grained complexity aims at proving conditional lower bounds on the time complexity of computational problems. One of the most popular assumptions, Strong Exponential Time Hypothesis (SETH), implies that SAT cannot be solved in $2^{(1-ε)n}$ time. In recent years, it has been proved that known algorithms for many problems are optimal under SETH. Despite the wide applicability of SETH, for many problems, there are no known SETH-based lower bounds, so the quest for new reductions continues. Two barriers for proving SETH-based lower bounds are known. Carmosino et al. (ITCS 2016) introduced the Nondeterministic Strong Exponential Time Hypothesis (NSETH) stating that TAUT cannot be solved in time $2^{(1-ε)n}$ even if one allows nondeterminism. They used this hypothesis to show that some natural fine-grained reductions would be difficult to obtain: proving that, say, 3-SUM requires time $n^{1.5+ε}$ under SETH, breaks NSETH and this, in turn, implies strong circuit lower bounds. Recently, Belova et al. (SODA 2023) introduced the so-called polynomial formulations to show that for many NP-hard problems, proving any explicit exponential lower bound under SETH also implies strong circuit lower bounds. We prove that for a range of problems from P, including $k$-SUM and triangle detection, proving superlinear lower bounds under SETH is challenging as it implies new circuit lower bounds. To this end, we show that these problems can be solved in nearly linear time with oracle calls to evaluating a polynomial of constant degree. Then, we introduce a strengthening of SETH stating that solving SAT in time $2^{(1-\varepsilon)n}$ is difficult even if one has constant degree polynomial evaluation oracle calls. This hypothesis is stronger and less believable than SETH, but refuting it is still challenging: we show that this implies circuit lower bounds.Open AccessComputations with polynomial evaluation oracle: ruling out superlinear SETH-based lower bounds
The field of fine-grained complexity aims at proving conditional lower bounds on the time complexity of computational problems. One of the most popular assumptions, Strong Exponential Time Hypothesis (SETH), implies that SAT cannot be solved in $2^{(1-ε)n}$ time. In recent years, it has been proved that known algorithms for many problems are optimal under SETH. Despite the wide applicability of SETH, for many problems, there are no known SETH-based lower bounds, so the quest for new reductions continues. Two barriers for proving SETH-based lower bounds are known. Carmosino et al. (ITCS 2016) introduced the Nondeterministic Strong Exponential Time Hypothesis (NSETH) stating that TAUT cannot be solved in time $2^{(1-ε)n}$ even if one allows nondeterminism. They used this hypothesis to show that some natural fine-grained reductions would be difficult to obtain: proving that, say, 3-SUM requires time $n^{1.5+ε}$ under SETH, breaks NSETH and this, in turn, implies strong circuit lower bounds. Recently, Belova et al. (SODA 2023) introduced the so-called polynomial formulations to show that for many NP-hard problems, proving any explicit exponential lower bound under SETH also implies strong circuit lower bounds. We prove that for a range of problems from P, including $k$-SUM and triangle detection, proving superlinear lower bounds under SETH is challenging as it implies new circuit lower bounds. To this end, we show that these problems can be solved in nearly linear time with oracle calls to evaluating a polynomial of constant degree. Then, we introduce a strengthening of SETH stating that solving SAT in time $2^{(1-\varepsilon)n}$ is difficult even if one has constant degree polynomial evaluation oracle calls. This hypothesis is stronger and less believable than SETH, but refuting it is still challenging: we show that this implies circuit lower bounds. - Open Access
Polynomial formulations as a barrier for reduction-based hardness proofs
The Strong Exponential Time Hypothesis (SETH) asserts that for every $\varepsilon>0$ there exists $k$ such that $k$-SAT requires time $(2-\varepsilon)^n$. The field of fine-grained complexity has leveraged SETH to prove quite tight conditional lower bounds for dozens of problems in various domains and complexity classes, including Edit Distance, Graph Diameter, Hitting Set, Independent Set, and Orthogonal Vectors. Yet, it has been repeatedly asked in the literature whether SETH-hardness results can be proven for other fundamental problems such as Hamiltonian Path, Independent Set, Chromatic Number, MAX-$k$-SAT, and Set Cover. In this paper, we show that fine-grained reductions implying even $\lambda^n$-hardness of these problems from SETH for any $\lambda>1$, would imply new circuit lower bounds: super-linear lower bounds for Boolean series-parallel circuits or polynomial lower bounds for arithmetic circuits (each of which is a four-decade open question). We also extend this barrier result to the class of parameterized problems. Namely, for every $\lambda>1$ we conditionally rule out fine-grained reductions implying SETH-based lower bounds of $\lambda^k$ for a number of problems parameterized by the solution size $k$. Our main technical tool is a new concept called polynomial formulations. In particular, we show that many problems can be represented by relatively succinct low-degree polynomials, and that any problem with such a representation cannot be proven SETH-hard (without proving new circuit lower bounds).Open AccessPolynomial formulations as a barrier for reduction-based hardness proofs
The Strong Exponential Time Hypothesis (SETH) asserts that for every $\varepsilon>0$ there exists $k$ such that $k$-SAT requires time $(2-\varepsilon)^n$. The field of fine-grained complexity has leveraged SETH to prove quite tight conditional lower bounds for dozens of problems in various domains and complexity classes, including Edit Distance, Graph Diameter, Hitting Set, Independent Set, and Orthogonal Vectors. Yet, it has been repeatedly asked in the literature whether SETH-hardness results can be proven for other fundamental problems such as Hamiltonian Path, Independent Set, Chromatic Number, MAX-$k$-SAT, and Set Cover. In this paper, we show that fine-grained reductions implying even $\lambda^n$-hardness of these problems from SETH for any $\lambda>1$, would imply new circuit lower bounds: super-linear lower bounds for Boolean series-parallel circuits or polynomial lower bounds for arithmetic circuits (each of which is a four-decade open question). We also extend this barrier result to the class of parameterized problems. Namely, for every $\lambda>1$ we conditionally rule out fine-grained reductions implying SETH-based lower bounds of $\lambda^k$ for a number of problems parameterized by the solution size $k$. Our main technical tool is a new concept called polynomial formulations. In particular, we show that many problems can be represented by relatively succinct low-degree polynomials, and that any problem with such a representation cannot be proven SETH-hard (without proving new circuit lower bounds). - Open Access
Complexity of Linear Operators
Let $A \in \{0,1\}^{n \times n}$ be a matrix with $z$ zeroes and $u$ ones and $x$ be an $n$-dimensional vector of formal variables over a semigroup $(S, \circ)$. How many semigroup operations are required to compute the linear operator $Ax$? As we observe in this paper, this problem contains as a special case the well-known range queries problem and has a rich variety of applications in such areas as graph algorithms, functional programming, circuit complexity, and others. It is easy to compute $Ax$ using $O(u)$ semigroup operations. The main question studied in this paper is: can $Ax$ be computed using $O(z)$ semigroup operations? We prove that in general this is not possible: there exists a matrix $A \in \{0,1\}^{n \times n}$ with exactly two zeroes in every row (hence $z=2n$) whose complexity is $\Theta(n\alpha(n))$ where $\alpha(n)$ is the inverse Ackermann function. However, for the case when the semigroup is commutative, we give a constructive proof of an $O(z)$ upper bound. This implies that in commutative settings, complements of sparse matrices can be processed as efficiently as sparse matrices (though the corresponding algorithms are more involved). Note that this covers the cases of Boolean and tropical semirings that have numerous applications, e.g., in graph theory. As a simple application of the presented linear-size construction, we show how to multiply two $n\times n$ matrices over an arbitrary semiring in $O(n^2)$ time if one of these matrices is a 0/1-matrix with $O(n)$ zeroes (i.e., a complement of a sparse matrix).Open AccessComplexity of Linear Operators
Let $A \in \{0,1\}^{n \times n}$ be a matrix with $z$ zeroes and $u$ ones and $x$ be an $n$-dimensional vector of formal variables over a semigroup $(S, \circ)$. How many semigroup operations are required to compute the linear operator $Ax$? As we observe in this paper, this problem contains as a special case the well-known range queries problem and has a rich variety of applications in such areas as graph algorithms, functional programming, circuit complexity, and others. It is easy to compute $Ax$ using $O(u)$ semigroup operations. The main question studied in this paper is: can $Ax$ be computed using $O(z)$ semigroup operations? We prove that in general this is not possible: there exists a matrix $A \in \{0,1\}^{n \times n}$ with exactly two zeroes in every row (hence $z=2n$) whose complexity is $\Theta(n\alpha(n))$ where $\alpha(n)$ is the inverse Ackermann function. However, for the case when the semigroup is commutative, we give a constructive proof of an $O(z)$ upper bound. This implies that in commutative settings, complements of sparse matrices can be processed as efficiently as sparse matrices (though the corresponding algorithms are more involved). Note that this covers the cases of Boolean and tropical semirings that have numerous applications, e.g., in graph theory. As a simple application of the presented linear-size construction, we show how to multiply two $n\times n$ matrices over an arbitrary semiring in $O(n^2)$ time if one of these matrices is a 0/1-matrix with $O(n)$ zeroes (i.e., a complement of a sparse matrix). - 29 November 2018
- Published by Springer Nature in Theory of Computing Systems
- Vol. 63 (5) , 956-986
Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates
- 29 November 2018
- Published by Springer Nature in Theory of Computing Systems
- Vol. 63 (5) , 956-986
Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates
- 1 September 2018
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 96, 107-119
On the limits of gate elimination
- 1 September 2018
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 96, 107-119
On the limits of gate elimination
- 25 April 2018
- Published by Springer Nature
- p. 15-22
Lower Bounds for Unrestricted Boolean Circuits: Open Problems
- 25 April 2018
- Published by Springer Nature
- p. 15-22
Lower Bounds for Unrestricted Boolean Circuits: Open Problems
- 1 April 2018
- Published by Elsevier in Theoretical Computer Science
- Vol. 719, 46-63
Gate elimination: Circuit size lower bounds and #SAT upper bounds
- 1 April 2018
- Published by Elsevier in Theoretical Computer Science
- Vol. 719, 46-63
Gate elimination: Circuit size lower bounds and #SAT upper bounds