Selected papers

Bibliography

Chukhin, N. (2026). A Note on Conditional Complexity Hardness of Matrix Rigidity and Tensor Rank. [ECCC]
```
@short{shortWorking2,
  author = {Chukhin, Nikolai},
  title = {A Note on Conditional Complexity Hardness of Matrix Rigidity and Tensor Rank},
  year = {2026},
  month = apr,
  conference = {ECCC},
  file = {eccc-tr26-041.pdf}
}
```
Chukhin, N., Kulikov, A. S., Mihajlin, I., & Smirnova, A. (2026). Conditional Complexity Hardness: Monotone Circuit Size, Matrix Rigidity, and Tensor Rank. [STACS]
```
@short{shortDBLP:conf/stacs/ChukhinKMS26,
  author = {Chukhin, Nikolai and Kulikov, Alexander S. and Mihajlin, Ivan and Smirnova, Arina},
  title = {Conditional Complexity Hardness: Monotone Circuit Size, Matrix Rigidity, and Tensor Rank},
  year = {2026},
  month = mar,
  conference = {STACS},
  file = {conditional-complexity-hardness-stacs2026.pdf}
}
```
Chukhin, N., Kulikov, A. S., & Mikhajlin, I. (2025). Toward Better Depth Lower Bounds: Strong Composition of XOR and a Random Function. [STACS]
```
@short{shortDBLP:journals/corr/abs-2410-10189,
  author = {Chukhin, Nikolai and Kulikov, Alexander S. and Mikhajlin, Ivan},
  title = {Toward Better Depth Lower Bounds: Strong Composition of {XOR} and
                    a Random Function},
  year = {2025},
  conference = {STACS},
  file = {andreevstacs2025.pdf}
}
```
Belova, T., Chukhin, N., Kulikov, A. S., & Mihajlin, I. (2024). Improved Space Bounds for Subset Sum. [ESA]
```
@short{shortDBLP:conf/esa/BelovaCKM24,
  author = {Belova, Tatiana and Chukhin, Nikolai and Kulikov, Alexander S. and Mihajlin, Ivan},
  title = {Improved Space Bounds for Subset Sum},
  year = {2024},
  conference = {ESA},
  file = {SubsetSumESA2024.pdf}
}
```

STACS 2026 paper

Series-parallel circuit decomposition diagram

Either \(E^{\mathrm{NP}}\) requires superlinear series-parallel circuits or \(\mathrm{coNP}\) requires monotone circuit size \(2^{\Omega(n / \log n)}\).

STACS 2025 paper

Strong Karchmer-Wigderson composition holds for \(\mathrm{XOR}\) and a random function.

ESA 2024 paper

Subset Sum can be solved in time \(2^{0.5n}\) and space \(2^{0.246n}\).

ESA 2024 paper

4-SUM to Circuit SAT implication diagram

If \(4\text{-}\mathrm{SUM}\) is not in time \(n^{2-\varepsilon}\), then \(\mathrm{CircuitSAT}\) is not in time \(O(g 2^{(1-\varepsilon)n})\).