The focus of the proposed meeting is to consider three aspects in the field of algorithms: models of computation, tools, and applications. We would like to invite experts in these areas from a wide range of backgrounds and perspectives to foster cross-disciplinary insights. The goal is to better understand how algorithmic ideas and methods can be transferred, generalized, or adapted across domains. This meeting is intended as a continuation of the topic of Shonan Meeting 221, “Algorithmic tools and their applications in emerging models of computation,” building on and broadening the themes discussed.

The classical applications of algorithms include areas such as scheduling, communication networks, and optimization. Classical models of computation include serial computation, parallel computation, distributed computation. Classical tools include linear programming and dynamic programming, The algorithms community has made significant strides in the development and advancement of various algorithmic tools. These tools have proven to be essential in solving complex computational problems efficiently and effectively in sepcific settings and computational models.

We propose to hold a Shonan meeting that will aim to bring together experts from diverse disciplines, distill these algorithmic tools, and discuss possibilities for expanding their applications to various computational models such as: parallel computing, distributed computing, streaming algorithms, and quantum computing. The goal is to better understand how algorithmic ideas and methods can be transferred, generalized, or adapted across domains.

1. Interior Point Methods : Interior point methods have revolutionized the field of convex optimization by providing efficient solutions to linear and nonlinear programming problems. This methods, combined with the Laplacian Paradigm and the development of special data structures lead to dramatic improvements in classical algorithmic problems such min-cost flow. We will explore the applicability of interior point methods in emerging models of computation, and discuss their potential in solving optimization problems in these models.

2. Analysis of Random Processes: Probabilistic methods such as concentration inequalities, martingale methods, coupling arguments, and the Lov´asz Local Lemma have been foundational in the analysis of algorithms involving randomness. These techniques offer strong guarantees about performance and correctness, even under uncertainty. We will discuss extending these methods to address challenges arising in parallel, distributed, streaming, and quantum computing models.

3. Graph Decompositions: Graph decomposition techniques have played a major role in the design of parallel algorithms, distributed algorithms, and online algorithms. Recently, expander decompositions were employed in the development of new algorithms for Laplacian solvers, algorithms for dynamic graphs, and routing. We will explore the potential of decomposition methods in emerging models of computation, and discuss their efficiency and scalability in these models.

4. Beyond Worst-Case Analysis: Traditional worst-case analysis may not accurately reflect practical performance. Alternative frameworks, such as smoothed analysis and algorithms augmented with machine-learning (ML) advice, have emerged. Smoothed analysis evaluates algorithms under slight random perturbations of inputs, offering insights into their robustness. Incorporating ML advice can significantly boost algorithmic efficiency in various computational models. We will examine how these methods can inform algorithm design in emerging computational paradigms.

5. Algorithmic Discrepancy Theory: Discrepancy theory provides powerful tools for balancing complex combinatorial systems, and recent constructive methods based on random walks and optimization have made classical bounds algorithmically accessible. These techniques unify themes from random processes, geometry and continuous optimization, and discrepancy-based methods have been useful in modern applications, such as coreset construction, differentially private data analysis and design of randomized controlled trials. We will explore how these ideas can further influence algorithms for other emerging computational models.

1. In distributed computing models (e.g., LOCAL and CONGEST), a network models both the communication infrastructure and the input (i.e. topology of the network). The input may consist also of local inputs of the network nodes. Local computation by the nodes and communication across the network links take place in synchronous rounds, and the goal is to compute local outputs that satisfy some global common objective. For example, in the distributed version of the minimum spanning tree problem, in the end, each node knows which of its incident links belong to the minimum spanning tree. The goal in distributed algorithms is to design algorithms that minimize the number of communication rounds.

2. Dynamic Algorithms: Dynamic algorithms efficiently maintain solutions as inputs evolve, often with insertions, deletions, or updates occurring rapidly over time. Important examples include maintaining shortest paths, matchings, and graph connectivity. The focus will be on techniques enabling rapid updates and queries, and their implications for real-time applications.

3. Small-Space Algorithms: Algorithms operating with severely restricted memory (small-space or streaming algorithms) have become critical in handling massive data streams. The primary goal is extracting approximate solutions or statistical properties using minimal storage. We will explore recent progress and its relevance in streaming analytics and large-scale data processing.

4. Massively Parallel Model: Massively parallel computation addresses algorithm design in systems where computation is highly parallelized, typically limited by local storage capacities and communication rounds. Prominent in big-data settings, the objective is to minimize rounds and communication overhead. We will discuss novel parallelization techniques and their broader applicability.

5. Quantum Model: The quantum model, also known as quantum computing, utilizes the principles of quantum mechanics to perform computations. Quantum computers utilize quantum bits, or qubits, which can represent multiple states simultaneously, allowing for parallel processing. Quantum computing has the potential to solve certain problems more efficiently than classical computers, especially those related to factorization, optimization, and simulation. Quantum algorithms are designed to take advantage of the unique properties of quantum systems, such as superposition and entanglement, to provide computational advantages in specific domains.

6. Machine Learning Models: Algorithmic techniques enhanced by machine learning (ML) promise significant performance improvements. ML-driven approaches can provide useful guidance or predictions that improve efficiency, reduce complexity, or achieve superior approximation guarantees. Our goal is to explore ML-assisted algorithmic strategies across parallel, distributed, streaming, and quantum computation contexts.

The above fields are rather active, keep growing in popularity year by year (papers in these fields are consistently presented in all major theoretical computer science conferences such as STOC, FOCS, and SODA). These fields build on the classical field of algorithm design, while taking into account various constraints and leveraging various advantages. Many new algorithms and algorithmic techniques have been developed recently. These recent results are promising candidates for becoming the foundational basis for the field the above fields.

The proposed meeting will bring together leading researchers in the above fields so that they can share their recent results and insights. We anticipate that new ideas and collaborations will result from a meeting dedicated to the topic algorithmc tools and their applications to emerging models of computations. The potential participants of the meeting are carefully selected based on excellence in research in algorithms and excellent communication skills. We hope the proposed meeting will strengthen the academic connection between these international research communities, especially between Japanese and non-Japanese researchers.

We believe a meeting with this diverse mix of researchers can have a very positive impact on these fields, as ideas and techniques from one subfield can be applied to related subfield.