Advances in Theoretical Computer Science

The field of theoretical computer science is moving towards a deeper understanding of the limitations and possibilities of efficient algorithms. Recent research has focused on the power of adaptivity in algorithms, with several papers exploring the trade-offs between time and space complexity in various settings. Non-adaptive algorithms, which make queries independently of the input, have been shown to be limited in their ability to solve certain problems efficiently. In contrast, adaptive algorithms can often achieve better performance by exploiting the structure of the input. Another area of research has been the study of local computation algorithms, which aim to solve problems by making local queries to the input. Researchers have made progress in understanding the limitations of non-adaptive local computation algorithms and have developed new techniques for analyzing their performance. Additionally, there have been advances in the study of stochastic games, with new results on the memory requirements for near-optimal play. Other areas of research have included the study of geometric spanners, which are sparse subgraphs that preserve the distances between vertices, and the development of new algorithms for solving problems in distributed computing. Notable papers include: Non-Adaptive Cryptanalytic Time-Space Lower Bounds via a Shearer-like Inequality for Permutations, which establishes sharp lower bounds on the time-space trade-offs for certain cryptanalytic problems. A Combinatorial Proof of Universal Optimality for Computing a Planar Convex Hull, which provides a new proof of the universal optimality of a certain algorithm for computing the convex hull of a planar point set. Towards Optimal Deterministic LOCAL Algorithms on Trees, which develops a new framework for constructing efficient algorithms for solving problems on trees.

Sources

Non-Adaptive Cryptanalytic Time-Space Lower Bounds via a Shearer-like Inequality for Permutations

Lower Bounds for Non-adaptive Local Computation Algorithms

A Combinatorial Proof of Universal Optimality for Computing a Planar Convex Hull

Towards Optimal Deterministic LOCAL Algorithms on Trees

Shuffling Cards When You Are of Very Little Brain: Low Memory Generation of Permutations

More efficient sifting for grid norms, and applications to multiparty communication complexity

Guarding Terrains with Guards on a Line

Stochastic Games with Limited Public Memory

PLS-completeness of string permutations

SAT-Solving the Poset Cover Problem

Light Spanners with Small Hop-Diameter

Optimal Deterministic Rendezvous in Labeled Lines

Testing Juntas Optimally with Samples

Learning Partitions with Optimal Query and Round Complexities

Sample Complexity of Identifying the Nonredundancy of Nontransitive Games in Dueling Bandits

Built with on top of