Search for tag: "workshop on algorithms and randomness"

18 Media

A Friendly Smoothed Analysis of the Simplex… duration 50 minutes 9 seconds A Friendly Smoothed Analysis of the Simplex… A Friendly Smoothed Analysis of the Simplex Method - Daniel Dadush	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… workshop on algorithms and randomness +4 More From Katie Gentilello 38 plays 0 name Daniel Dadush Date May 17th, 2018
On the infection time of the Duarte model: the… duration 43 minutes 26 seconds On the infection time of the Duarte model: the… On the infection time of the Duarte model: the role of energy barriers - Fabio Martinelli	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… geogia tech +4 More From Katie Gentilello 8 plays 0 name Fabio Martinelli Date May 15th, 2018
Cutoff with window for the random to random… duration 35 minutes 5 seconds Cutoff with window for the random to random… Cutoff with window for the random to random shuffle - Megan Bernstein	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… workshop on algorithms and randomness +4 More From Katie Gentilello 30 plays 0 name Megan Bernstein Date May 17th, 2018
Sphere packings, codes, and kissing numbers via… duration 32 minutes 51 seconds Sphere packings, codes, and kissing numbers via… Sphere packings, codes, and kissing numbers via hard core models - Will Perkins	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.… workshop on algorithms and randomness +4 More From Katie Gentilello 60 plays 0 name Will Perkins Date May 17th, 2018
Inapproximability of the Independent Set… duration 39 minutes 31 seconds Inapproximability of the Independent Set… Inapproximability of the Independent Set Polynomial in the Complex Plane - Daniel Stefankovic	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… workshop on algorithms and randomness +4 More From Katie Gentilello 13 plays 0 name Daniel Stefankovic Date May 17th, 2018
Learning discrete Markov Random Fields with… duration 47 minutes 20 seconds Learning discrete Markov Random Fields with… Learning discrete Markov Random Fields with nearly optimal runtime and sample complexity - Raghu Meka	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… workshop on algorithms and randomness +4 More From Katie Gentilello 26 plays 0 name Raghu Meka Date May 17th, 2018
Towards Tight Approximation Bounds for Graph… duration 45 minutes 57 seconds Towards Tight Approximation Bounds for Graph… Towards Tight Approximation Bounds for Graph Diameter and Eccentricities - Virginia Vassilevska Williams	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… workshop on algorithms and randomness +4 More From Katie Gentilello 25 plays 0 name Virginia Vassilevska Williams Date May 16th, 2018
An algorithmic version of Banaszczyk's… duration 44 minutes 51 seconds An algorithmic version of Banaszczyk's… An algorithmic version of Banaszczyk's discrepancy theorem - Nikhil Bansal	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… workshop on algorithms and randomness +4 More From Katie Gentilello 37 plays 0 name Nikhil Bansal Date May 16th, 2018
Markov Chain Algorithms for Programmable Active… duration 39 minutes 18 seconds Markov Chain Algorithms for Programmable Active… Markov Chain Algorithms for Programmable Active Matter - Dana Randall	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… workshop on algorithms and randomness +4 More From Katie Gentilello 41 plays 0 name Dana Randall Date May 16th, 2018
A polynomial-time approximation algorithm for… duration 44 minutes 28 seconds A polynomial-time approximation algorithm for… A polynomial-time approximation algorithm for all-terminal network reliability - Mark Jerrum	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… workshop on algorithms and randomness +4 More From Katie Gentilello 51 plays 0 name Mark Jerrum Date May 16th, 2018
Relative Error Tensor Low Rank Approximation -… duration 52 minutes 22 seconds Relative Error Tensor Low Rank Approximation -… Relative Error Tensor Low Rank Approximation - David Woodruff	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… workshop on algorithms and randomness +4 More From Katie Gentilello 32 plays 0 name David Woodruff Date May 15th, 2018
Maximum Cut problem on sparse random hypergraphs:… duration 50 minutes 10 seconds Maximum Cut problem on sparse random hypergraphs:… Maximum Cut problem on sparse random hypergraphs: Structural results using the interpolation method and the algorithmic implications - David Gamarnik	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.,… workshop on algorithms and randomness +4 More From Katie Gentilello 59 plays 0 name David Gamarnik Date May 15th, 2018
Mixing in groups: From Ramanujan graphs to the… duration 45 minutes 39 seconds Mixing in groups: From Ramanujan graphs to the… Mixing in groups: From Ramanujan graphs to the product replacement algorithm - Yuval Peres	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… workshop on algorithms and randomness +4 More From Katie Gentilello 25 plays 0 name Yuval Peres Date May 15th, 2018
Random walks on the chambers of a hyperplane… duration 36 minutes 12 seconds Random walks on the chambers of a hyperplane… Random walks on the chambers of a hyperplane arrangement - Evita Nestoridi	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… workshop on algorithms and randomness +4 More From Katie Gentilello 16 plays 0 name Evita Nestoridi Date May 15th, 2018
Insertion time of random walk cuckoo hashing -… duration 32 minutes 37 seconds Insertion time of random walk cuckoo hashing -… Insertion time of random walk cuckoo hashing - Alan Frieze	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… workshop on algorithms and randomness +4 More From Katie Gentilello 16 plays 0 name Alan Frieze Date May 15th, 2018
Gradient Descent: The Mother of All Algorithms? -… duration 56 minutes 28 seconds Gradient Descent: The Mother of All Algorithms? -… Gradient Descent: The Mother of All Algorithms? - Aleksander Mądry	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… workshop on algorithms and randomness +4 More From Katie Gentilello 86 plays 0 name Aleksander Mądry Date May 14th, 2018