combinatorics, algorithms for NP-hard problems, circuit complexity. algorithms, circuit complexity
UDC:
510.52, 519.16, 510.633, 519.178, 519.7
Subject:
Combinatorics, algorithms for NP-hard problems, circuit complexity. algorithms, circuit complexity
Main publications:
Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, “Families with Infants: Speeding Up Algorithms for NP-Hard Problems Using FFT”, ACM Transactions on Algorithms, 12:3 (2016)
A. S. Kulikov, I. Mikhailin, A. Mokhov, V. V. Podolskii, “Complexity of Linear Operators”, Leibniz Internat. Proc. in Inform., 149 (2019), 17–12
2.
Alexander S. Kulikov, Vladimir V. Podolskii, “Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates”, Theory Comput. Syst., 63:5 (2019), 956–986
2017
3.
A. S. Kulikov, V. V. Podolskii, “Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates”, Leibniz Internat. Proc. in Inform., 66:49 (2017), 1–14
2009
4.
A. S. Kulikov, K. Kutskov, “New upper bounds for the problem of maximal satisfiability”, Diskr. Mat., 21:1 (2009), 139–157; Discrete Math. Appl., 19:2 (2009), 155–172
A. S. Kulikov, S. S. Fedin, “Automated proofs of upper bounds on the running time of splitting algorithms”, Zap. Nauchn. Sem. POMI, 316 (2004), 111–128; J. Math. Sci. (N. Y.), 134:5 (2006), 2383–2391
A. S. Kulikov, S. S. Fedin, “A $2^{|E|/4}$-time Algorithm for MAX-CUT”, Zap. Nauchn. Sem. POMI, 293 (2002), 129–138; J. Math. Sci. (N. Y.), 126:3 (2005), 1200–1204
A. S. Kulikov, “An upper bound $O(2^{0.16254n})$ for Exact 3-Satisfiability: a simpler proof”, Zap. Nauchn. Sem. POMI, 293 (2002), 118–128; J. Math. Sci. (N. Y.), 126:3 (2005), 1195–1199
Contact us: