17 citations · 97 across the 38 of their papers we have counts for
4 papers · 1 filter
An Improved Trickle-Down Theorem for Partite Complexes
Dorna Abdolazimi, Shayan Oveis Gharan
We prove a strengthening of the trickle down theorem for partite complexes. Given a -partite -dimensional simplicial complex, we show that if "on average" the links of fa…
On the Bias of Reed-Muller Codes over Odd Prime Fields
Paul Beame, Shayan Oveis Gharan, Xin Yang
We study the bias of random bounded-degree polynomials over odd prime fields and show that, with probability exponentially close to 1, such polynomials have exponentially small bia…
A Simply Exponential Upper Bound on the Maximum Number of Stable Matchings
Anna R. Karlin, Shayan Oveis Gharan, Robbie Weber
Stable matching is a classical combinatorial problem that has been the subject of intense theoretical and empirical study since its introduction in 1962 in a seminal paper by Gale…
A Universal upper bound on Graph Diameter based on Laplacian Eigenvalues
Shayan Oveis Gharan, Luca Trevisan
We prove that the diameter of any unweighted connected graph G is O(k log n/lambda_k), for any k>= 2. Here, lambda_k is the k smallest eigenvalue of the normalized laplacian of G.…