# Search for tag: "algorithms"

#### 0422-SlicerJSam

From  Scott Dinerman A year ago 1 views 0

#### 86 Years of Ramsey R(3,k) (and counting!) - Joel Spencer

The search for the asymptotics of the Ramsey function R(3,k) has a long and fascinating history. It begins in the hill country surrounding Budapest and winding over the decades through Europe,…

From  Kathryn Gentilello 7 Months ago 28 views 0

#### A characterization of $L_p$ mixing, cutoff and hypercontractivity via maximal inequalities and hitting times - Jonathan Hermon

There are several works characterizing the total-variation mixing time of a reversible Markov chain in term of natural probabilistic concepts such as stopping times and hitting times. In contrast,…

From  Kathryn Gentilello 6 Months ago 7 views 0

#### A Computer Science View of the Brain - Santosh Vempala

Computational perspectives on scientific phenomena have often proven to be remarkably insightful. Rapid advances in computational neuroscience, and the resulting plethora of data and models highlight…

From  Kathryn Gentilello A year ago 36 views 0

#### A constant-factor approximation algorithm for the asymmetric traveling salesman problem - László A. Végh

We give a constant-factor approximation algorithm for the asymmetric traveling salesman problem. Our approximation guarantee is analyzed with respect to the standard LP relaxation, and thus our…

From  Kathryn Gentilello 8 Months ago 10 views 0

#### A Fast and Simple Unbiased Estimator for Network (Un)reliability - David Karger

The following procedure yields an unbiased estimator for the disconnection probability of an n-vertex graph with minimum cut c if every edge fails independently with probability p: (i) contract every…

From  Kathryn Gentilello A year ago 32 views 0

#### A Friendly Smoothed Analysis of the Simplex Method - Daniel Dadush

Explaining the excellent practical performance of the simplex method for linear programming has been a major topic of research for over 50 years. One of the most successful frameworks for…

From  Kathryn Gentilello 3 Weeks ago 8 views 0

#### A polynomial-time approximation algorithm for all-terminal network reliability - Mark Jerrum

Let G be an undirected graph in which each edge is assigned a failure probability. Suppose the edges fail independently with the given probabilities. We are interested in computing the probability…

From  Kathryn Gentilello 4 Weeks ago 9 views 0

#### An algorithmic version of Banaszczyk's discrepancy theorem - Nikhil Bansal

In the 90's Banaszczyk developed a very powerful method for discrepancy problems, that goes beyond the partial coloring method. His result was based on deep results from convex geometry and was…

From  Kathryn Gentilello 3 Weeks ago 6 views 0

#### An almost-linear time algorithm for uniform random spanning tree generation - Aaron Schild

We give an $m^{1+o(1)}\beta^{o(1)}$-time algorithm for generating uniformly random spanning trees in weighted graphs with max-to-min weight ratio $\beta$. In the process, we illustrate how…

From  Kathryn Gentilello 3 Months ago 8 views 0

#### Approximate Gaussian Elimination for Laplacians: Fast, Sparse, and Simple - Rasmus Kyng

We show how to perform sparse approximate Gaussian elimination for Laplacian matrices. We present a simple, nearly linear time algorithm that approximates a Laplacian by a matrix with a sparse…

From  Kathryn Gentilello A year ago 48 views 0

#### Approximation Schemes for Planar Graphs: A Survey of Methods - Philip Klein

In addressing an NP-hard problem in combinatorial optimization, one way to cope is to use an approximation scheme, an algorithm that, for any given ϵ>0, produces a solution whose value is within a…

From  Kathryn Gentilello A year ago 13 views 0