This paper considers the Lipschitz bandit problem, where the set of arms is continuous and the expected reward is a Lipschitz function over the arm space. This problem has been extensively studied. Prior algorithms need to store the reward information of all visited arms, leading to significant memory consumption. We address this issue by introducing an algorithm named Log-space Lipschitz bandits (Log-Li), which achieves an optimal (up to logarithmic factors) regret of $\widetilde{O}\left(T^{\frac{d_z+1}{d_z+2}}\right)$ while only uses $O\left(\log T\right)$ bits of memory. Additionally, we provide a complexity analysis for this problem, demonstrating that $\Omega\left(\log T\right)$ bits of space are necessary for any algorithm to achieve the optimal regret. We also conduct numerical simulations, and the results show that our new algorithm achieves regret comparable to the state-of-the-art while reducing memory usage by orders of magnitude.

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.

We study the distributed tracking model, also known as distributed functional monitoring. This model involves $k$ sites each receiving a stream of items and communicating with the central server. The server's task is to track a function of all items received thus far continuously, with minimum communication cost. For count tracking, it is known that there is a $\sqrt{k}$ gap in communication between deterministic and randomized algorithms. However, existing randomized algorithms assume an "oblivious adversary" who constructs the entire input streams before the algorithm starts. Here we consider adaptive adversaries who can choose new items based on previous answers from the algorithm. Deterministic algorithms are trivially robust to adaptive adversaries, while randomized ones may not. Therefore, we investigate whether the $\sqrt{k}$ advantage of randomized algorithms is from randomness itself or the oblivious adversary assumption. We provide an affirmative answer to this question by giving a robust algorithm with optimal communication. Existing robustification techniques do not yield optimal bounds due to the inherent challenges of the distributed nature of the problem. To address this, we extend the differential privacy framework by introducing "partial differential privacy" and proving a new generalization theorem. This theorem may have broader applications beyond robust count tracking, making it of independent interest.

This paper presents a semi-deterministic groupwise channel estimation method to generate UT-group CSI of user terminal (UT) zones in the service area for the angular-based hybrid precoding (AB-HP) in multi-user massive multiple-input multiple-output (MU-mMIMO) systems based on geospatial data and the fuzzy c-Means (FCM) clustering algorithm. The slow time-varying UT-level channel state information (CSI) between the base station (BS) and all possible UTs are generated by a ray tracing algorithm and grouped into clusters by a proposed FCM clustering. The service area is then divided into a number of non-overlapping UT zones, where each is characterized by a corresponding set of clusters used as UT-group CSI for RF beamformer to eliminate the required large online CSI acquisition overhead. Simulations are performed in both outdoor and indoor scenarios to evaluate the performance of the proposed channel estimation approach. Illustrative results show that the proposed method identifies clusters robust to imprecise UT-level CSI and provides RF beamformer with the UT-group CSI for different UT zones in the service area. Meanwhile, with the UT- group CSI, the AB-HP can successfully achieve a comparable sum-rate performance as the fully-digital precoding (FDP) system for UTs in specific zones without large dimensional CSI overhead.

60 GHz wireless personal area networks (WPANs) are bringing a new wave of high data rate applications because they promise multi-Gbps level communications. This paper exploits the spatial reuse of location information aided 60 GHz multi- user beamforming systems. When the location information is available at the network coordinator, the scheduler chooses a set of maximum angularly separated links to share the same time slot simultaneously. If additional feedback of signal-to- interference and noise ratio (SINR) is known, a location-assisted scheduler is employed to increase the system overall performance. The position error sensitivity is also discussed. The results show that significant enhancement can be achieved by the proposed schedulers for 60 GHz WPAN systems and we observe an accuracy of 98% compared with the error free transmission with ultra-wideband (UWB) localization systems.

60 GHz wireless personal area networks (WPANs) offer multi-Gbps throughput, which will provide for a new wave of high data rate applications. This paper exploits the use of location information to improve the performance and enhance range of 60 GHz multi-user beamforming systems. When the location information is available at the transmitter, the scheduler chooses a set of maximum angularly separated users to share wireless resources simultaneously. If additional feedback of signal-to-interference and noise ratio (SINR) is known, a location-assisted scheduler is employed to increase the system overall performance. Both numerical and simulated results show that significant enhancement can be achieved by the proposed schedulers for 60 GHz WPAN systems.

The IEEE 802.11ad task group has published its first draft to cope with the characteristics in 60 GHz millimeter-wave (mmWave) wireless communications. In this paper, three different 2×2 multiple-input multiple-output (MIMO) techniques are considered to enhance the performance of 60 GHz wireless personal networks (WPANs). Packet Error Rate (PER) and link throughput performance are simulated under different channel conditions. In addition, the system throughput over operation range is presented in the paper. Results show that significant enhancements in both coverage and capacity can be achieved by employing space-time block codes (STBC), spatial multiplexing (SM) and three different configurations of beamforming.

Recently, the development and requirement for ultra-high data rate wireless communication applications has increased dramatically. The 60 GHz millimeter-wave wireless technology is getting increasing attention, and the IEEE 802.11 Task Group AD is making standardization efforts for multi-gigabit data rate communications on both the physical (PHY) and medium access control (MAC) layers. This paper presents a performance evaluation of the PHY and MAC layers of IEEE 802.1 lad. Packet error rate and PHY throughput are presented for different modes, and the theoretical MAC throughput is analyzed for different bit error rates, packet sizes and modes. In addition, 2×2 space-time block coding (STBC) is employed for range extension. The cross layer results show our approach enhance the throughput and coverage compared to the case of single antenna.