Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Computer Science – Theory and Applications

16th International Computer Science Symposium in Russia, CSR 2021, Sochi, Russia, June 28–July 2, 2021, Proceedings

  • Conference proceedings
  • © 2021

Overview

Editors:
  1. Rahul Santhanam

    1. University of Oxford, Oxford, UK

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Daniil Musatov

    1. Innovations & HighTech, Moscow Institute of Physics and Technology, Moscow, Russia

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 12730)

Part of the book sub series: Theoretical Computer Science and General Issues (LNTCS)

Included in the following conference series:

Conference proceedings info: CSR 2021.

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

eBook USD 39.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

About this book

This book constitutes the proceedings of the 16th International Computer Science Symposium in Russia, CSR 2021, held in Sochi, Russia, in June/July 2021.

The 28 full papers were carefully reviewed and selected from 68 submissions. The papers cover a broad range of topics, such as formal languages and automata theory, geometry and discrete structures; theory and algorithms for application domains and much more.

Similar content being viewed by others

Keywords

Table of contents (28 papers)

  1. Front Matter

    Pages i-xi
    Download chapter PDF

  2. Computational Complexity of Multi-player Evolutionarily Stable Strategies

    • Manon Blanc, Kristoffer Arnsfelt Hansen
    Pages 1-17

  3. Injective Colouring for H-Free Graphs

    • Jan Bok, Nikola Jedličková, Barnaby Martin, Daniël Paulusma, Siani Smith
    Pages 18-30

  4. Variants of the Determinant Polynomial and the \(\textsf {VP}\)-Completeness

    • Prasad Chaugule, Nutan Limaye, Shourya Pandey
    Pages 31-55

  5. Dynamic Complexity of Expansion

    • Samir Datta, Anuj Tawari, Yadu Vasudev
    Pages 56-77

  6. Real \(\tau \)-Conjecture for Sum-of-Squares: A Unified Approach to Lower Bound and Derandomization

    • Pranjal Dutta
    Pages 78-101

  7. Dichotomy Result on 3-Regular Bipartite Non-negative Functions

    • Austen Z. Fan, Jin-Yi Cai
    Pages 102-115

  8. Upper Bounds on Communication in Terms of Approximate Rank

    • Anna Gál, Ridwan Syed
    Pages 116-130

  9. Approximation Schemes for Multiperiod Binary Knapsack Problems

    • Zuguang Gao, John R. Birge, Varun Gupta
    Pages 131-146

  10. Limitations of Sums of Bounded Read Formulas and ABPs

    • Purnata Ghosal, B. V. Raghavendra Rao
    Pages 147-169

  11. On the Computational Complexity of Reaction Systems, Revisited

    • Markus Holzer, Christian Rauch
    Pages 170-185

  12. Average-Case Rigidity Lower Bounds

    • Xuangui Huang, Emanuele Viola
    Pages 186-205

  13. Analysis of an Efficient Reduction Algorithm for Random Regular Expressions Based on Universality Detection

    • Florent Koechlin, Pablo Rotondo
    Pages 206-222

  14. Bit-Complexity of Solving Systems of Linear Evolutionary Partial Differential Equations

    • Ivan Koswara, Gleb Pogudin, Svetlana Selivanova, Martin Ziegler
    Pages 223-241

  15. A Secure Three-Input AND Protocol with a Standard Deck of Minimal Cards

    • Hiroto Koyama, Daiki Miyahara, Takaaki Mizuki, Hideaki Sone
    Pages 242-256

  16. Upper Bound for Torus Polynomials

    • Vaibhav Krishan
    Pages 257-263

  17. A PCP of Proximity for Real Algebraic Polynomials

    • Klaus Meer
    Pages 264-282

  18. Predictions and Algorithmic Statistics for Infinite Sequences

    • Alexey Milovanov
    Pages 283-295

  19. Lower Bounds and Hardness Magnification for Sublinear-Time Shrinking Cellular Automata

    • Augusto Modanese
    Pages 296-320

  20. Approximation Algorithms for Connectivity Augmentation Problems

    • Zeev Nutov
    Pages 321-338
Back to top

Other volumes

  1. Computer Science – Theory and Applications

Editors and Affiliations

  • University of Oxford, Oxford, UK

    Rahul Santhanam

  • Innovations & HighTech, Moscow Institute of Physics and Technology, Moscow, Russia

    Daniil Musatov

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation