Pu Gao

SODA Conference 2020 Conference Paper

Sandwiching random regular graphs between binomial random graphs

• Pu Gao
• Mikhail Isaev
• Brendan D. McKay

SODA Conference 2020 Conference Paper

The rank of sparse random matrices

• Amin Coja-Oghlan
• Alperen Ali Ergür
• Pu Gao
• Samuel Hetterich
• Maurice Rolvien

We determine the rank of a random matrix A over an arbitrary field with prescribed numbers of non-zero entries in each row and column. As an application we obtain a formula for the rate of low-density parity check codes. This formula vindicates a conjecture of Lelarge [Proc. IEEE Information Theory Workshop 2013]. The proofs are based on coupling arguments and a novel random perturbation, applicable to any matrix, that likely diminishes the number of short linear relations.

FOCS Conference 2019 Conference Paper

Fast Uniform Generation of Random Graphs with Given Degree Sequences

• Andrii Arman
• Pu Gao
• Nicholas C. Wormald

In this paper we provide an algorithm that generates a graph with given degree sequence uniformly at random. Provided that Δ 4 =O(m), where Δ is the maximal degree and m is the number of edges, the algorithm runs in expected time O(m). Our algorithm significantly improves the previously most efficient uniform sampler, which runs in expected time O(m 2 Δ 2 ) for the same family of degree sequences. Our method uses a novel ingredient which progressively relaxes restrictions on an object being generated uniformly at random, and we use this to give fast algorithms for uniform sampling of graphs with other degree sequences as well. Using the same method, we also obtain algorithms with expected run time which is (i) linear for power-law degree sequences in cases where the previous best was O(n 4. 081 ), and (ii) O(nd+d 4 ) for d-regular graphs when d=o(√ n), where the previous best was O(nd 3 ).

SODA Conference 2018 Conference Paper

Uniform generation of random graphs with power-law degree sequences

• Pu Gao
• Nicholas C. Wormald

We give a linear-time algorithm that approximately uniformly generates a random simple graph with a power-law degree sequence whose exponent is at least 2. 8811. While sampling graphs with power-law 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 ( n 2. 107 ) with high probability, and O ( n 4. 081 ) in expectation.

FOCS Conference 2015 Conference Paper

Uniform Generation of Random Regular Graphs

• Pu Gao
• Nicholas C. Wormald

We develop a new approach for uniform generation of combinatorial objects, and apply it to derive a uniform sampler REG for d-regular graphs. REG can be implemented such that each graph is generated in expected time O(nd 3 ), provided that d = o(√n). Our result significantly improves the previously best uniform sampler, which works efficiently only when d = O(n 1/3 ), with essentially the same running time for the same d. We also give a linear-time approximate sampler REG*, which generates a random d-regular graph whose distribution differs from the uniform by o(1) in total variation distance, when d = o(√n).

SODA Conference 2014 Conference Paper

Arboricity and spanning-tree packing in random graphs with an application to load balancing

• Pu Gao
• Xavier Pérez-Giménez
• Cristiane M. Sato

STOC Conference 2010 Conference Paper

Load balancing and orientability thresholds for random hypergraphs

• Pu Gao
• Nicholas C. Wormald