More Like this

1. Optimal Convergence and Adaptation for Utility Optimal Opportunistic Scheduling

   Neely, Michael J. ( October 2017 , PROC. ALLERTON CONFERENCE ON COMMUNICATION, CONTROL, AND COMPUTING 2017)

   This paper considers the fundamental convergence time for opportunistic scheduling over time-varying channels. The channel state probabilities are unknown and algorithms must perform some type of estimation and learning while they make decisions to optimize network utility. Existing schemes can achieve a utility within ε of optimality, for any desired ε > 0, with convergence and adaptation times of O(1/ε^2). This paper shows that if the utility function is concave and smooth, then O(log(1/ε)/ε) convergence time is possible via an existing stochastic variation on the Frank-Wolfe algorithm, called the RUN algorithm. Next, a converse result is proven to show it is impossible for any algorithm to have convergence time better than O(1/ε), provided the algorithm has no a- priori knowledge of channel state probabilities. Hence, RUN is within a logarithmic factor of convergence time optimality. However, RUN has a vanishing stepsize and hence has an infinite adaptation time. Using stochastic Frank-Wolfe with a fixed step- size yields improved O(1/ε^2) adaptation time, but convergence time increases to O(1/ε^2), similar to existing drift-plus-penalty based algorithms. This raises important open questions regarding optimal adaptation. 

   more » « less
2. Optimal Convergence and Adaptation for Utility Optimal Opportunistic Scheduling

   Neely, Michael J ( January 2017 , Proc. Allerton Conference on Communication, Control, and Computing)

   This paper considers the fundamental convergence time for opportunistic scheduling over time-varying channels. The channel state probabilities are unknown and algorithms must perform some type of estimation and learning while they make decisions to optimize network utility. Existing schemes can achieve a utility within ε of optimality, for any desired ε > 0, with convergence and adaptation times of O(1/ε^2). This paper shows that if the utility function is concave and smooth, then O(log(1/ε)/ε) convergence time is possible via an existing stochastic variation on the Frank-Wolfe algorithm, called the RUN algorithm. Next, a converse result is proven to show it is impossible for any algorithm to have convergence time better than O(1/ε), provided the algorithm has no a- priori knowledge of channel state probabilities. Hence, RUN is within a logarithmic factor of convergence time optimality. However, RUN has a vanishing stepsize and hence has an infinite adaptation time. Using stochastic Frank-Wolfe with a fixed step- size yields improved O(1/ε^2) adaptation time, but convergence time increases to O(1/ε^2), similar to existing drift-plus-penalty based algorithms. This raises important open questions regarding optimal adaptation. 

   more » « less
3. Faster Isomorphism for 𝑝-Groups of Class 2 and Exponent 𝑝

   https://doi.org/10.1145/3564246.3585250  

   Sun, Xiaorui ( June 2023 , ACM)

   The group isomorphism problem determines whether two groups, given by their Cayley tables, are isomorphic. For groups with order $n$, an algorithm with $n^{(\log n + O(1))}$ running time, attributed to Tarjan, was proposed in the 1970s (Miller, STOC 1978). Despite the extensive study over the past decades, the current best group isomorphism algorithm has an $n^{(1 / 4 + o(1))\log n}$ running time (Rosenbaum 2013). The isomorphism testing for $p$-groups of (nilpotent) class 2 and exponent $p$ has been identified as a major barrier to obtaining an $n^{o(\log n)}$ time algorithm for the group isomorphism problem. Although the $p$-groups of class 2 and exponent $p$ have much simpler algebraic structures than general groups, the best-known isomorphism testing algorithm for this group class also has an $n^{O(\log n)}$ running time. In this paper, we present an isomorphism testing algorithm for $p$-groups of class 2 and exponent $p$ with running time $n^{O((\log n)^{5/6})}$ for any prime $p > 2$. Our result is based on a novel reduction to the skew-symmetric matrix tuple isometry problem (Ivanyos and Qiao, SIAM J. Computing, 2019). To obtain the reduction, we develop several tools for matrix space analysis, including a matrix space individualization-refinement method and a characterization of the low rank matrix spaces. 

   more » « less
4. Multi-Relay Communications in the Presence of Phase Noise: A Comprehensive Approach

   https://doi.org/10.1109/TCOMM.2016.2622704  

   Salim, Omar H. ; Nasir, Ali A. ; Mehrpouyan, Hani ; Xiang, Wei ( January 2017 , IEEE Transactions on Communications)

   Abstract: Impairments such as time varying phase noise (PHN) and carrier frequency offset (CFO) result in loss of synchronization and poor performance of multi-relay communication systems. Joint estimation of these impairments is necessary in order to correctly decode the received signal at the destination. In this paper, we address spectrally efficient multi-relay transmission scenarios where all the relays simultaneously communicate with the destination. We propose an iterative pilot-aided algorithm based on the expectation conditional maximization for joint estimation of multipath channels, Wiener PHNs, and CFOs in decode-and-forward-based multi-relay orthogonal frequency division multiplexing systems. Next, a new expression of the hybrid Cramér-Rao lower bound (HCRB) for the multi-parameter estimation problem is derived. Finally, an iterative receiver based on an extended Kalman filter for joint data detection and PHN tracking is employed. Numerical results show that the proposed estimator outperforms existing algorithms and its mean square error performance is close to the derived HCRB at different signal-to-noise ratios for different PHN variances. In addition, the combined estimation algorithm and the iterative receiver can significantly improve average bit-error rate (BER) performance compared with existing algorithms. In addition, the BER performance of the proposed system is close to the ideal case of perfect channel impulse responses, PHNs, and CFOs estimation. 

   more » « less
5. Uplink Power Control and SNR-Dependent Beam Alignment Errors in MmWave Cellular Networks

   https://doi.org/10.1109/PIMRC54779.2022.9977460  

   Zia, Muhammad Saad ; Blough, Douglas M. ; Weitnauer, Mary Ann ( January 2022 , Proceedings of the IEEE International Symposium on Personal, Indoor and Mobile Radio Communications)

   Beam alignment is a critical aspect in millimeter wave (mm-wave) cellular systems. However, the inherent limitations of channel estimation result in beam alignment errors, which degrade the system performance. For systems with a large number of antennas at the base station, downlink channel estimation is performed using uplink pilot signals. The beam alignment errors, thus, depend on the user equipment (UE) transmit power, which needs to be managed properly as the UEs are battery powered. This paper investigates how the use of uplink power control for the transmission of pilot signals in a mm-wave network affects the downlink beam alignment errors, which depend on various link parameters. We use stochastic geometry and statistics of the Student's t -distribution to develop an analytical model, which captures the interplay between the uplink power control and downlink signal-to-noise ratio (SNR) coverage probability. Our results indicate that using uplink power control significantly reduces UE power consumption without adversely affecting the downlink SNR coverage. 

   more » « less