Best Paper Awards

Best Paper Awards and Best Student Paper Awards are given to the authors of papers selected by the Program Committee from those accepted to the CSR conference. In 2007-2019, these awards were sponsored by Yandex. Since 2019 Best Paper Awards and Best Student Paper Awards are sponsored by Springer (in 2019 these awards were sponsored by both Yandex and Springer).
The recepients were
 
  1. Best Paper:
    Artur Jez and Alexander Okhotin: Conjunctive grammars over a unary alphabet: undecidability and unbounded growth.
    Yury Lifshits and Dirk Nowotka: Estimation of the click volume by large scale regression analysis.
    Best Student Paper:
    Maxim Babenko: A fast algorithm for path 2-packing problem.
  2. Best Paper:
    Marius Zimand: Two sources are better than one for increasing the Kolmogorov complexity of infinite sequences.
    Laura Kovács: Invariant generation for P-solvable loops with assignments.
    Best Student Paper:
    Vladimir Podolskii: A uniform lower bound on weights of perceptrons.
  3. Best Student Paper:
    Dmitry Itsykson: Structural complexity of AvgBPP.
    Yuri Pritykin and Julya Ulyashkina: Aperiodicity measure for infinite sequences.
  4. Best Paper:
    Dmitry Itsykson: Lower Bound on Average-Case Complexity of Inversion of Goldreich's Function by Drunken Backtracking Algorithms.
    Best Student Paper:
    Junhua Yu: Prehistoric Phenomena and Self-referentiality.
  5. Best Paper:
    Scott Aaronson: The Equivalence of Sampling and Searching.
    Best Student Paper:
    Daniil Musatov: Improving the Space-Bounded Version of Muchnik's Conditional Complexity Theorem via "Naive" Derandomization.
  6. Best Paper:
    Christos Kapoutsis and Giovanni Pighizzini: Two-way automata characterizations of L/poly versus NL.
    Best Student Paper:
    Evgeny Demenkov: A Lower Bound on Circuit Complexity of Vector Function in U2.
  7. Best Paper:
    Mark Braverman, Ankit Garg, Denis Pankratov, and Omri Weinstein: Information Lower Bounds via Self-Reducibility.
    Best Student Paper:
    Luke Friedman and Yixin Xu: Exponential Lower Bounds for Refuting Random Formulas Using Ordered Binary Decision Diagrams.
  8. Best Paper:
    Akinori Kawachi, Benjamin Rossman, Osamu Watanabe, The Query Complexity of Witness Finding.
    Best Student Paper:
    Konrad Schwerdtfeger, The Connectivity of Boolean Satisfiability: Dichotomies for Formulas and Circuits.
  9. Best Paper:
    Volker Diekert, Florent Martin, Gerard Senizergues, Pedro V. Silva, Equations over Free Inverse Monoids with Idempotent Variables.
    Best Student Paper:
    Alexey Milovanov, Some Properties of Antistochastic Strings.
    Vincent Penelle, Rewriting Higher-Order Stack Trees.
  10. Best Paper:
    Meena Mahajan and Nitin Saurabh, Some Complete and Intermediate Polynomials in Algebraic Complexity Theory.
    Best Student Paper:
    Alexander Kozachinskiy, On Slepian-Wolf Theorem with Interaction.
  11. Best Paper:
    Alexei Miasnikov, Svetla Vassileva, and Armin Weiss The Conjugacy Problem in Free Solvable Groups and Wreath Products of Abelian Groups is in TC0 .
    Lukas Fleischer and Manfred Kufleitner, Green's Relations in Finite Transformation Group.
    Best Student Paper:
    Alexey Milovanov, On Algorithmic Statistics for Space-Bounded Algorithms.
  12. Best Paper:
    Jayakrishnan Madathil, Saket Saurabh, and Meirav Zehavi, Max-Cut Above Spanning Tree Is Fixed Parameter Tractable.
    Best Student Paper:
    Alexander Kozachinskiy, Recognizing Read-Once Functions from Depth-Three Formulas.
  13. Best Paper:
    Ludmila Glinskih and Dmitry Itsykson, On Tseitin formulas, read-once branching programs and treewidth.
    Best Student Paper:
    Jan-Hendrik Lorenz, On the Complexity of Restarting.
  14. Best Paper:
    Fedor Fomin and Vijayaragunathan Ramamoorthi, On the Parameterized Complexity of the Expected Coverage Problem.
    Best Student Paper:
    Onur Çağırıcı, On embeddability of unit disk graphs onto straight lines.
  15. Best Paper and Best Student Paper:
    Pranjal Dutta, Real tau-Conjecture for sum-of-squares: A unified approach to lower bound and derandomization.