Learning algorithms from natural proofs ML Carmosino, R Impagliazzo, V Kabanets, A Kolokolova 31st Conference on Computational Complexity (CCC 2016), 2016 | 70 | 2016 |

Mining circuit lower bound proofs for meta-algorithms R Chen, V Kabanets, A Kolokolova, R Shaltiel, D Zuckerman Computational Complexity 24 (2), 333-392, 2015 | 68 | 2015 |

Completeness for first-order properties on sparse structures with algorithmic applications J Gao, R Impagliazzo, A Kolokolova, R Williams ACM Transactions on Algorithms (TALG) 15 (2), 1-35, 2018 | 50 | 2018 |

A second-order system for polytime reasoning based on Grädel's theorem S Cook, A Kolokolova Annals of Pure and Applied Logic 124 (1-3), 193-231, 2003 | 39 | 2003 |

An axiomatic approach to algebrization R Impagliazzo, V Kabanets, A Kolokolova Proceedings of the forty-first annual ACM symposium on Theory of computing …, 2009 | 24 | 2009 |

AC0 [p] lower bounds against MCSP via the coin problem A Golovnev, R Ilango, R Impagliazzo, V Kabanets, A Kolokolova, A Tal ICALP, 2019 | 22 | 2019 |

Stabbing planes P Beame, N Fleming, R Impagliazzo, A Kolokolova, D Pankratov, T Pitassi, ... arXiv preprint arXiv:1710.03219, 2017 | 22 | 2017 |

Systems of bounded arithmetic from descriptive complexity. A Kolokolova | 22 | 2005 |

On the complexity of model expansion A Kolokolova, Y Liu, D Mitchell, E Ternovska International Conference on Logic for Programming Artificial Intelligence …, 2010 | 19 | 2010 |

Tighter connections between derandomization and circuit lower bounds ML Carmosino, R Impagliazzo, V Kabanets, A Kolokolova Approximation, Randomization, and Combinatorial Optimization. Algorithms and …, 2015 | 18 | 2015 |

A second-order theory for NL S Cook, A Kolokolova Proceedings of the 19th Annual IEEE Symposium on Logic in Computer Science …, 2004 | 11 | 2004 |

The proof complexity of SMT solvers R Robere, A Kolokolova, V Ganesh International Conference on Computer Aided Verification, 275-293, 2018 | 8 | 2018 |

Closure properties of weak systems of bounded arithmetic A Kolokolova International Workshop on Computer Science Logic, 369-383, 2005 | 8 | 2005 |

Compression improves image classification accuracy N Ozah, A Kolokolova Canadian Conference on Artificial Intelligence, 525-530, 2019 | 7 | 2019 |

Agnostic learning from tolerant natural proofs ML Carmosino, R Impagliazzo, V Kabanets, A Kolokolova Approximation, Randomization, and Combinatorial Optimization. Algorithms and …, 2017 | 6 | 2017 |

Expander construction in VNC1 S Buss, V Kabanets, A Kolokolova, M Koucký Annals of Pure and Applied Logic 171 (7), 102796, 2020 | 5 | 2020 |

Compression of Boolean Functions. V Kabanets, A Kolokolova Electron. Colloquium Comput. Complex. 20, 24, 2013 | 5 | 2013 |

Complexity of expanding a finite structure and related tasks A Kolokolova, Y Liu, D Mitchell, E Ternovska Logic and Computational Complexity, workshop associated with LICS 6, 2006 | 4 | 2006 |

Algorithms from Natural Lower Bounds. ML Carmosino, R Impagliazzo, V Kabanets, A Kolokolova Electron. Colloquium Comput. Complex. 23, 8, 2016 | 3 | 2016 |

Does Looking Inside a Circuit Help? R Impagliazzo, V Kabanets, A Kolokolova, P McKenzie, S Romani 42nd International Symposium on Mathematical Foundations of Computer Science …, 2017 | 2 | 2017 |