Search for tag: "workshop"

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 on May 25th, 2018 29 plays 0  

On the infection time of the Duarte model: the role of energy barriers - Fabio Martinelli

In the Duarte model each vertex of Z <Superscript> 2 can be either infected or healthy. In the bootstrap percolation model version, infected vertices stay infected while a healthy vertex…

From  Kathryn Gentilello on May 25th, 2018 8 plays 0  

Cutoff with window for the random to random shuffle - Megan Bernstein

Cutoff is a remarkable property of many Markov chains in which they after number of steps abruptly transition in a smaller order window from an unmixed to a mixed distribution. Most random walks on…

From  Kathryn Gentilello on May 25th, 2018 11 plays 0  

Sphere packings, codes, and kissing numbers via hard core models - Will Perkins

We prove a lower bound on the expected size of a spherical code drawn from a "hard cap" model and the expected density of a packing drawn from the hard sphere model in high dimensions.…

From  Kathryn Gentilello on May 25th, 2018 14 plays 0  

Inapproximability of the Independent Set Polynomial in the Complex Plane - Daniel Stefankovic

Hard-core model (also known as independent set polynomial) is one of the simplest models in statistical physics. The complexity of approximating the value of the partition function of the model on…

From  Kathryn Gentilello on May 24th, 2018 13 plays 0  

Learning discrete Markov Random Fields with nearly optimal runtime and sample complexity - Raghu Meka

We give an algorithm for learning the structure of an undirected graphical model that has essentially optimal sample complexity and running time. We make no assumptions on the structure of the…

From  Kathryn Gentilello on May 24th, 2018 23 plays 0  

Towards Tight Approximation Bounds for Graph Diameter and Eccentricities - Virginia Vassilevska Williams

Among the most important graph parameters is the Diameter, the largest distance between any two vertices. There are no known very efficient algorithms for computing the Diameter exactly. Thus, much…

From  Kathryn Gentilello on May 24th, 2018 12 plays 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 on May 24th, 2018 17 plays 0  

Markov Chain Algorithms for Programmable Active Matter - Dana Randall

We consider stochastic solutions to problems arising from programmable active matter based on emergent phenomena. We view active matter as a collection of simple computational elements (or…

From  Kathryn Gentilello on May 24th, 2018 30 plays 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 on May 23rd, 2018 41 plays 0  

Relative Error Tensor Low Rank Approximation - David Woodruff

We consider relative error low rank approximation of tensors with respect to the Frobenius norm: given an order-q tensor A, output a rank-k tensor B for which |A-B|_F <= (1+eps)OPT, where OPT…

From  Kathryn Gentilello on May 23rd, 2018 22 plays 0  

Maximum Cut problem on sparse random hypergraphs: Structural results using the interpolation method and the algorithmic implications - David Gamarnik

We consider a particular version of the Maximum Cut problem (to be defined in the talk) on a sparse random K-uniform hypergraph, when K is even. The goal is to compute the maximum cut value w.h.p.,…

From  Kathryn Gentilello on May 23rd, 2018 49 plays 0  

Mixing in groups: From Ramanujan graphs to the product replacement algorithm - Yuval Peres

I will survey several recent works involving mixing for random walks on groups and regular graphs. In joint work with Eyal Lubetzky, we determined precisely the mixing time of random walk on optimal…

From  Kathryn Gentilello on May 23rd, 2018 18 plays 0  

Random walks on the chambers of a hyperplane arrangement - Evita Nestoridi

The Bidigare-Hanlon-Rockmore random walk on the chambers of a real hyperplane arrangement is a Markov chain that generalizes famous examples, such as theTsetlin library and riffle shuffles. We will…

From  Kathryn Gentilello on May 23rd, 2018 10 plays 0  

Insertion time of random walk cuckoo hashing - Alan Frieze

Random Walk Cuckoo Hashing Abstract: We consider the expected insertion time of Cuckoo Hashing when clashes are resolved randomly. We prove O(1) expected time insertion in two cases.(i) d choices of…

From  Kathryn Gentilello on May 23rd, 2018 11 plays 0  

Gradient Descent: The Mother of All Algorithms? - Aleksander Mądry

More than a half of century of research in theoretical computer science brought us a great wealth of advanced algorithmic techniques. These techniques can then be combined in a variety of ways to…

From  Kathryn Gentilello on May 22nd, 2018 76 plays 0