The$(k, z)$-Clusteringproblem in Euclidean space$\mathbb {R}^{d}$has been extensively studied. Given the scale of data involved, compression methods for the Euclidean$(k, z)$-Clusteringproblem, such as data compression and dimension reduction, have received significant attention in the literature. However, the space complexity of the clustering problem, specifically, the number of bits required to compress the cost function within a multiplicative error$\varepsilon $, remains unclear in existing literature. This paper initiates the study of space complexity for Euclidean$(k, z)$-Clusteringand offers both upper and lower bounds. Our space bounds are nearly tight whenkis constant, indicating that storing a coreset, a well-known data compression approach, serves as the optimal compression scheme. Furthermore, our lower bound result for$(k, z)$-Clusteringestablishes a tight space bound of$\Theta (n d)$for terminal embedding, wherenrepresents the dataset size. Our technical approach leverages new geometric insights for principal angles and discrepancy methods, which may hold independent interest.

The $(k, z)$-Clustering problem in Euclidean space $\mathbb{R}^d$ has been extensively studied. Given the scale of data involved, compression methods for the Euclidean $(k, z)$-Clustering problem, such as data compression and dimension reduction, have received significant attention in the literature. However, the space complexity of the clustering problem, specifically, the number of bits required to compress the cost function within a multiplicative error $\varepsilon$, remains unclear in existing literature. This paper initiates the study of space complexity for Euclidean $(k, z)$-Clustering and offers both upper and lower bounds. Our space bounds are nearly tight when $k$ is constant, indicating that storing a coreset, a well-known data compression approach, serves as the optimal compression scheme. Furthermore, our lower bound result for $(k, z)$-Clustering establishes a tight space bound of $Θ( n d )$ for terminal embedding, where $n$ represents the dataset size. Our technical approach leverages new geometric insights for principal angles and discrepancy methods, which may hold independent interest.

Problems in the area of distributed computing have been extensively studied. In this paper, we focus on the Distributed Thresholded Counting problem in the coordinator model. In this problem, we have k sites holding their input and communicating with a central coordinator. The coordinator's task is to determine whether the sum of inputs is larger than a threshold. While the communication complexity of this basic problem has been studied for decades, it is still not well understood. Our work considers the worst-case communication cost for an algorithm that uses limited interaction - i.e. a bounded number of rounds of communication. Algorithms in previous research usually need O(łogłog N) or O(k) rounds. In comparison, in the deterministic case, our algorithm achieves optimal communication complexity in only α(k) rounds, where α(k) denotes the inverse Ackermann function and is nearly constant. We also give a randomized algorithm that balances communication, rounds, and error probability.

Federated learning (FL) is a distributed learning framework that allows clients to build models without disclosing local data. However, in resource-constrained scenarios, it is costly to participate in FL for all clients. Hence, selection strategy should be designed to select the most appropriate client groups. Current selection strategies are mainly cost and accuracy oriented, ignoring the autonomy of clients, which leads to the inability of clients to make autonomous decisions when participating in model training and updating. To realize autonomous selection of clients, we design a novel model accuracy-aware bidirectional client selection (MABCS) algorithm. The MABCS algorithm implements selection from both server and client dimensions. Specifically, the server evaluates the contributions of clients and design an accuracy-aware dynamic incentive mechanism. The client measures participation autonomy based on the reward and cost to decide whether or not to participate in FL. Thus, the client selection problem is modeled as a joint nonconvex optimization problem that maximizes the system revenue by optimizing the selection strategy and resource allocation strategy. The block coordinate descent algorithm is utilized to decouple the selection strategy and resource allocation strategy, and a linear approximation is employed to transform the selection strategy problem into a convex problem. An alternating optimization algorithm is used for the subproblems after the decomposition to obtain a near-optimal solution. Simulation results indicate that the MABCS algorithm exhibits superior convergence performance compared with other benchmark schemes.