(1) Network Science and Graph Analytics for Better Predictions


(2) Computing at Scale: How to Solve Large Problems Faster

  • image The increasing digitalization in many aspects of life leads to a proliferation of data inventory. At the same time, the emergence of software frameworks like MapReduce/Hadoop/Spark allows us to pursue large-scale problems in computer science. We are currently developing mathematical theories and software for large-scale computing with applications to cyberspace intelligence analytics. In [1], we design novel scalable graph algorithms that run on MapReduce as part of the DARPA-MIT-Amazon Graph Challenge 2018. In [2-3], we design algorithms for users to bid for high-value and low-cost computation resources in Amazon Web Services real-time spot pricing. We are also studying large-scale computing for scientific computational and artificial intelligence (AI) applications.

    [1] C. Kuo, C. N. Hang, P. Yu and C. W. Tan, Parallel Counting of Triangles in Large Graphs: Pruning and Hierarchical Clustering Algorithms, IEEE High Performance Extreme Computing, MIT-Amazon Graph Challenge 2018 (Honorable Mention).
    [2] L. Zheng, C. Joe-Wong, C. W. Tan, M. Chiang and X. Wang, How to Bid the Cloud?, ACM SIGCOMM 2015.
    [3] L. Zheng, C. Joe-Wong, C. Brinton, C. W. Tan, S. Ha and M. Chiang, On the Viability of a Cloud Virtual Service Provider, ACM SIGMETRICS 2016.

(3) Network Optimization by Perron-Frobenius Theory


(4) Information Theory

  • Information-theoretic problems often possess surprisingly beautiful structures associated with optimization theory that shed insights to designing optimal systems. In [2], we addressed the Gaussian interference channel rate optimization problem based on the discovery of an intriguing zig-zag phenomenon with the use of superposition coding. In [1], we discovered that linear programming and the idea of sparsity-induced convex relaxation can be used to automate the process of mathematically proving and disproving very large-scale information theory inequalities, which are traditionally difficult to prove by hand. We are currently working on the software automation (software forthcoming in Fall 2018) and using the software to analyze some problems in mathematics.

    [1] S. W. Ho, C. W. Tan and R. W. Yeung, Proving and Disproving Information Inequalities, Proc. of IEEE Symp. of Information Theory, 2014.
    [2] Y. Zhao, C. W. Tan, A. S. Avestimehr, S. N. Diggavi and G. J. Pottie, On the Maximum Achievable Sum-rate with Successive Decoding in Interference Channels, IEEE Transactions on Information Theory, Vol. 58, No. 6, pp. 3798-3820, 2012.

(5) Wireless Communications based on Quaternions and Convex Optimization Tools

  • imageWe have developed novel signal processing and resource allocation algorithms in wireless networks. A novel space-time communication scheme was proposed in [1] using quaternion vectors as building blocks to create robust energy-efficient transmissions. The idea is to select the best code from a family of codes induced by the geometry and statistics of quaternion vectors (code diversity) (link). Energy-efficient resource allocation algorithms in Cognitive Radio Networks were studied using convex optimization and iterative algorithm tools in [2-3] and also in a recently-edited book.

    [1] C. W. Tan and A. R. Calderbank, Multiuser Detection of Alamouti Signals, IEEE Transactions on Communications, Vol. 57, No. 7, pp. 2080-2089, 2009.
    [2] X. Zhai, L. Zheng and C. W. Tan, Energy-Infeasibility Tradeoff in Cognitive Radio Networks: Price-driven Spectrum Access Algorithms, IEEE Journal on Selected Areas in Communications, Vol. 32, No. 3, pp. 528-538, 2014.
    [3] C. W. Tan, D. P. Palomar and M. Chiang, Energy-Robustness Tradeoff in Cellular Network Power Control, IEEE/ACM Transactions on Networking, Vol. 17, No. 3, pp. 912-925, 2009.

(6) Performance Evaluation: How good is our Internet Routing Protocol?

  • A fundamental question in Internet TCP/IP engineering is: “What is the cost of routing TCP flows over a single path or multiple routes?” The answer can guide the decision on whether to support multipath routing –an expensive operation– in the Internet. We show that optimal routing can in fact be achieved using a randomized TCP/IP algorithm to load-balance large proportion of Internet traffic with only a small group of users sparsely routing over more than one path [2]. Our work in [1, 2] lend theoretical evidence that the current single-path routing, e.g., the OSPF Internet protocol, can be improvised to scale up for multipath routing in next-generation software-defined networks.

    [1] M. Wang, C. W. Tan, W. Xu and A. Tang, Cost of Not Splitting in Routing: Characterization and Estimation, IEEE/ACM Transactions on Networking, Vol. 19, No. 6, pp. 1849-1859, 2011.
    [2] Y. Bi, C. W. Tan and A. Tang, Network Utility Maximization with Path Cardinality Constraints, IEEE INFOCOM, 2016.

(7) Power Network Optimization