| paper | slides | |
|---|---|---|
| A. S. Kulikov, O. Melanich, I. Mihajlin.
A 5n-o(n) Lower Bound on the Circuit Size over U_2 of a Linear Boolean Function. Proceedings of Computability in Europe (CiE 2012), to appear. 2012. |
||
| E. Demenkov, A. S. Kulikov, I. Mihajlin, H. Morizumi.
Computing All MOD-functions Simultaneously. Proceedings of 7th International Computer Science Symposium in Russia (CSR 2012), to appear. 2012. |
||
| E. Demenkov, A. S. Kulikov.
An Elementary Proof of a 3n-o(n) Lower Bound on the Circuit Complexity of Affine Dispersers. Proceedings of 36th International Symposium on Mathematical Foundations of Computer Science (MFCS 2011), LNCS 6907, 2011, pp. 256–265. |
||
| A. Kojevnikov, A. S. Kulikov.
Circuit Complexity and Multiplicative Complexity of Boolean Functions. Proceedings of Computability in Europe (CiE 2010), LNCS 6158, 2010, pp. 239–245. |
||
| P. Hrubes, S. Jukna, A. S. Kulikov, P. Pudlak.
On Convex Complexity Measures. Theoretical Computer Science, vol. 411, 2010, pp. 1842-1854. |
pdf(rus) | |
| E. Demenkov, A. Kojevnikov, A. S. Kulikov, G. Yaroslavtsev.
New Upper Bounds on the Boolean Circuit Complexity of Symmetric Functions. Information Processing Letters, 110, 2010, pp. 264-267. |
||
|
A. A. Kojevnikov, A. S. Kulikov, G. N. Yaroslavtsev.
Finding Efficient Circuits Using SAT-solvers. Proceedings of the Twelfth International Conference on Theory and Applications of Satisfiability Testing (SAT 2009), LNCS 5584, 2009, pp. 32-44. |
||
| A. S. Kulikov, K. Kutzkov. New Bounds for MAX-SAT by Clause Learning. Discretnaya Matematika, vol. 21(11), 2009, pp. 139-157 (in Russian). English translation: Discrete Mathematics and Applications, vol. 19 (2), 2009, pp. 155-172. |
pdf(eng) pdf(rus) | |
| S. Jukna, A. S. Kulikov. On covering graphs by complete bipartite subgraphs. Discrete Mathematics, vol. 309(10), 2009, pp. 3399-3403. |
||
| E. A. Hirsch, A. Kojevnikov, A. S. Kulikov, and S. I. Nikolenko.
Complexity of Semialgebraic Proofs with Restricted Degree of Falsity. Journal on Satisfiability, Boolean Modeling and Computation, Vol. 6, 2008, pp. 53-69. |
||
| A. S. Kulikov, K. Kutzkov. New Bounds for MAX-SAT by Clause Learning. Proceedings of the 2nd International Computer Science Symposium in Russia (CSR 2007), LNCS 4649, 2007, pp. 194-204. |
||
| A. Kojevnikov, A. S. Kulikov. Complexity of Semialgebraic Proofs with Restricted Degree of Falsity. Proceedings of the Ninth International Conference on Theory and Applications of Satisfiability Testing (SAT 2006), LNCS 4121, 2006, pp. 11-21. |
||
| A. Kojevnikov, A. S. Kulikov. A New Approach to Proving Upper Bounds for MAX-2-SAT. Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), 2006, pp.11-17. |
||
| S. S. Fedin, A. S. Kulikov. Automated Proofs of Upper Bounds on the Running Time of Splitting Algorithms. Zapiski nauchnyh seminarov POMI, No.316, 2004, pp.111-128. English translation: Journal of Mathematical Sciences, vol. 134(5), 2006, pp.2383-2391. |
pdf(eng) pdf(rus) | |
| A. S. Kulikov. Automated Proofs of Upper Bounds for NP-hard Problems: Implementation Details. PDMI preprint 21/2006. |
||
| A. S. Kulikov. Automated Generation of Simplification Rules for SAT and MAXSAT. Proceedings of the Eighth International Conference on Theory and Applications of Satisfiability Testing (SAT 2005), LNCS 3569, 2005, pp.430-436. |
||
| S. S. Fedin, A. S. Kulikov. Automated Proofs of Upper Bounds on the Running Time of Splitting Algorithms. Proceedings of the International Workshop on Parameterized and Exact Computation (IWPEC 2004), LNCS 3162, 2004, pp.248-259. |
||
| S. S. Fedin, A. Kojevnikov, B. Konev, A. S. Kulikov, S. I. Nikolenko, V. P. Orevkov.
First Report on the Semialgebraic Prover. PDMI preprint 09/2004. |
ps.gz | |
| A. S. Kulikov. An Upper Bound O(20.16254n) for Exact 3-Satisfiability: A Simpler Proof. Zapiski nauchnyh seminarov POMI, No.293, 2002, pp.118-128. English translation: Journal of Mathematical Sciences, vol. 126(3), 2005, pp.1995-1999. |
pdf(eng) pdf(rus) | |
| S. S. Fedin, A. S. Kulikov. A 2|E|/4-Time Algorithm for MAX-CUT. Zapiski nauchnyh seminarov POMI, No.293, 2002, pp.129-138. English translation: Journal of Mathematical Sciences, vol. 126(3), 2005, pp.1200-1204. |
pdf(eng) pdf(rus) |