NS Seminar

Date and Location

May 10, 2017 - 4:45pm to 5:45pm
Bldg 434, rm 122

Abstract

Generating random spanning trees more quickly than the cover time (presented by Shadi Mohagheghi, Dept of Electrical and Computer Engineering)

Wilson, D. B. (1996, July). Generating random spanning trees more quickly than the cover time. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing (pp. 296-303). ACM.

This paper gives a new algorithm for generating random spanning trees. It too is simple, easy to code up, and has nice proofs. The new algorithm also has the following advantages: On graphs for which the old algorithm works, the new algorithm is never slower (by more than a factor of two), and is usually much faster. It also works for directed graphs. It yields the current fastest algorithm for sampling from the stationary probability distribution of a Markov chain whose transition probabilities are unknown. Additionally, the proofs double as proofs for an identity and an inequality.

 

A study of LoRa: Long range & low power networks for the internet of things (presented by Haleigh Wright, Dept of Computer Science)

Augustin, A., Yi, J., Clausen, T., & Townsley, W. M. (2016). A study of LoRa: Long range & low power networks for the internet of things. Sensors, 16(9), 1466.

LoRa is a long-range, low-power, low-bitrate, wireless telecommunications system, promoted as an infrastructure solution for the Internet of Things: end-devices use LoRa across a single wireless hop to communicate to gateway(s), connected to the Internet and which act as transparent bridges and relay messages between these end-devices and a central network server. This paper provides an overview of LoRa and an in-depth analysis of its functional components. The physical and data link layer performance is evaluated by field tests and simulations. Based on the analysis and evaluations, some possible solutions for performance enhancements are proposed.

As part of her presentation, Haleigh will also discuss the International Telecommunication Union (ITU)'s "IoT Network Planning" Presentation, given at their international conference held in Asia Pacific in Dec 2016.