Projects per year
Abstract
We give a lineartime algorithm that approximately uniformly generates a random simple graph with a powerlaw degree sequence whose exponent is at least 2.8811. While sampling graphs with powerlaw degree sequence of exponent at least 3 is fairly easy, and many samplers work efficiently in this case, the problem becomes dramatically more difficult when the exponent drops below 3; ours is the first provably practicable sampler for this case. We also show that with an appropriate rejection scheme, our algorithm can be tuned into an exact uniform sampler. The running time of the exact sampler is O(n2:107) with high probability, and O(n4:081) in expectation.
Original language  English 

Title of host publication  Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms 
Subtitle of host publication  29th Annual ACMSIAM Symposium on Discrete Algorithms, SODA 2018; Astor Crowne Plaza  New Orleans French QuarterNew Orleans; United States; 7 January 2018 through 10 January 2018 
Editors  Artur Czumaj 
Publisher  Association for Computing Machinery (ACM) 
Pages  17411758 
Number of pages  18 
ISBN (Electronic)  9781611975031 
DOIs  
Publication status  Published  1 Jan 2018 
Event  ACMSIAM Symposium on Discrete Algorithms, 2018  New Orleans, United States of America Duration: 7 Jan 2018 → 10 Jan 2018 Conference number: 29th 
Conference
Conference  ACMSIAM Symposium on Discrete Algorithms, 2018 

Abbreviated title  SODA 2018 
Country/Territory  United States of America 
City  New Orleans 
Period  7/01/18 → 10/01/18 
Other  This symposium focuses on research topics related to efficient algorithms and data structures for discrete problems. In addition to the design of such methods and structures, the scope also includes their use, performance analysis, and the mathematical problems related to their development or limitations. Performance analyses may be analytical or experimental and may address worstcase or expectedcase performance. Studies can be theoretical or based on data sets that have arisen in practice and may address methodological issues involved in performance analysis. 
Projects
 1 Finished

New approaches to the random generation of combinatorial objects
Wormald, N. & Gao, P.
Australian Research Council (ARC), Monash University
4/04/16 → 30/06/20
Project: Research