Computer Science – Theory and Applications

Table of Contents

1. Altmetric Badge
   Book Overview
2. Altmetric Badge
   Chapter 1 Computational Complexity of Multi-player Evolutionarily Stable Strategies
3. Altmetric Badge
   Chapter 2 Injective Colouring for H -Free Graphs
4. Altmetric Badge
   Chapter 3 Variants of the Determinant Polynomial and the $$\textsf {VP}$$ VP -Completeness
5. Altmetric Badge
   Chapter 4 Dynamic Complexity of Expansion
6. Altmetric Badge
   Chapter 5 Real $$\tau $$ τ -Conjecture for Sum-of-Squares: A Unified Approach to Lower Bound and Derandomization
7. Altmetric Badge
   Chapter 6 Dichotomy Result on 3-Regular Bipartite Non-negative Functions
8. Altmetric Badge
   Chapter 7 Upper Bounds on Communication in Terms of Approximate Rank
9. Altmetric Badge
   Chapter 8 Approximation Schemes for Multiperiod Binary Knapsack Problems
10. Altmetric Badge
    Chapter 9 Limitations of Sums of Bounded Read Formulas and ABPs
11. Altmetric Badge
    Chapter 10 On the Computational Complexity of Reaction Systems, Revisited
12. Altmetric Badge
    Chapter 11 Average-Case Rigidity Lower Bounds
13. Altmetric Badge
    Chapter 12 Analysis of an Efficient Reduction Algorithm for Random Regular Expressions Based on Universality Detection
14. Altmetric Badge
    Chapter 13 Bit-Complexity of Solving Systems of Linear Evolutionary Partial Differential Equations
15. Altmetric Badge
    Chapter 14 A Secure Three-Input AND Protocol with a Standard Deck of Minimal Cards
16. Altmetric Badge
    Chapter 15 Upper Bound for Torus Polynomials
17. Altmetric Badge
    Chapter 16 A PCP of Proximity for Real Algebraic Polynomials
18. Altmetric Badge
    Chapter 17 Predictions and Algorithmic Statistics for Infinite Sequences
19. Altmetric Badge
    Chapter 18 Lower Bounds and Hardness Magnification for Sublinear-Time Shrinking Cellular Automata
20. Altmetric Badge
    Chapter 19 Approximation Algorithms for Connectivity Augmentation Problems
21. Altmetric Badge
    Chapter 20 On Rooted k -Connectivity Problems in Quasi-bipartite Digraphs
22. Altmetric Badge
    Chapter 21 Input-Driven Pushdown Automata on Well-Nested Infinite Strings
23. Altmetric Badge
    Chapter 22 Large Clique is Hard on Average for Resolution
24. Altmetric Badge
    Chapter 23 On Closed-Rich Words
25. Altmetric Badge
    Chapter 24 Shelah-Stupp’s and Muchnik’s Iterations Revisited
26. Altmetric Badge
    Chapter 25 On Separation Between the Degree of a Boolean Function and the Block Sensitivity
27. Altmetric Badge
    Chapter 26 Approximation and Complexity of the Capacitated Geometric Median Problem
28. Altmetric Badge
    Chapter 27 A Generic Convolution Algorithm for Join Operations on Tree Decompositions
29. Altmetric Badge
    Chapter 28 A Generalization of a Theorem of Rothschild and van Lint