Now showing items 1-20 of 68

    • 86 Years of Ramsey R(3,k) (and counting!) 

      Spencer, Joel (2017-11-03)
      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, America, Korea and Rio de ...
    • Abstract polymer models, the cluster expansion, and applications 

      Perkins, Will (2019-05-06)
      Will introduces abstract polymer models and the cluster expansion from statistical physics. He describes some of the original applications of these tools in statistical physics to understand phase transitions in lattice ...
    • Algorithmic Pirogov-Sinai theory 

      Perkins, Will (2018-11-05)
      We develop efficient algorithms to approximate the partition function and sample from the hard-core and Potts models on lattices at sufficiently low temperatures in the phase coexistence regime. In contrast, the Glauber ...
    • Algorithmic Pricing 

      Blum, Avrim (Georgia Institute of Technology, 2013-04-08)
      Pricing and allocating goods to buyers with complex preferences in order to maximize some desired objective (e.g., social welfare or profit) is a central problem in Algorithmic Mechanism Design. In this talk I will discuss ...
    • An algorithmic version of Banaszczyk's discrepancy theorem 

      Bansal, Nikhil (2018-05-16)
      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 non-constructive. In this ...
    • An almost-linear time algorithm for uniform random spanning tree generation 

      Schild, Aaron (2018-02-12)
      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 fundamental tradeoffs in graph ...
    • Amplification Theorems for Differentially Private Machine Learning 

      Talwar, Kunal (2019-04-01)
      A rigorous foundational approach to private data analysis has emerged in theoretical computer science in the last decade, with differential privacy and its close variants playing a central role. We have recently been able ...
    • Approximate Gaussian Elimination for Laplacians: Fast, Sparse, and Simple 

      Kyng, Rasmus (2016-11-28)
      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 Cholesky factorization – the ...
    • Approximation Schemes for Planar Graphs: A Survey of Methods 

      Klein, Philip (2017-03-27)
      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 1+ϵ factor of optimal. ...
    • Black Holes, Firewalls, and the Limits of Quantum Computers 

      Aaronson, Scott (2017-12-04)
      Quantum computers are proposed devices that would exploit quantum mechanics to solve certain specific problems dramatically faster than we know how to solve them with today's computers. In the popular press, quantum ...
    • Bloom Filters, Cuckoo Hashing, Cuckoo Filters, Adaptive Cuckoo Filters, and Learned Bloom Filters 

      Mitzenmacher, Michael (2018-11-26)
      I will go over some of my past and present work on hashing-based data structures. After presenting some background on Bloom filters and cuckoo hashing, we will describe cuckoo filters, an efficient data structure for ...
    • A characterization of $L_p$ mixing, cutoff and hypercontractivity via maximal inequalities and hitting times 

      Hermon, Jonathan (2017-11-27)
      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, there is no known analog ...
    • The Complexity of Learning Neural Networks 

      Wilmes, John (2017-10-30)
      The empirical successes of neural networks currently lack rigorous theoretical explanation. A first step might be to show that data generated by neural networks with a single hidden layer, smooth activation functions and ...
    • A Computer Science View of the Brain 

      Vempala, Santosh (Georgia Institute of Technology, 2017-03-15)
      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 the lack of an ...
    • A constant-factor approximation algorithm for asymmetric TSP [Lecture 3] 

      Svensson, Ola (2019-04-25)
      The traveling salesman problem is one of the most fundamental optimization problems. Given cities and pairwise distances, it is the problem of finding a tour of minimum distance that visits each city once. In spite of ...
    • A Constant‐Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem 

      Vegh, László A. (Georgia Institute of Technology, 2017-09-21)
      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 result confirms the conjectured ...
    • The Contextual Bandits Problem: Techniques for Learning to Make High-Reward Decisions 

      Schapire, Robert (2017-10-30)
      We consider how to learn through experience to make intelligent decisions. In the generic setting, called the contextual bandits problem, the learner must repeatedly decide which action to take in response to an observed ...
    • Cutoff with window for the random to random shuffle 

      Bernstein, Megan (2018-05-17)
      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 the symmetric group, ...
    • Decay of correlations and non-local Markov chains 

      Blanca, Antonio (2017-10-30)
      In this talk we consider Markov chains for spin systems on the integer lattice graph Z^d. It has been well known since pioneering work from the early 1990’s that a certain decay of correlation property, known as strong ...
    • Different approaches for asymmetric TSP [Lecture 2] 

      Svensson, Ola (2019-04-24)
      The traveling salesman problem is one of the most fundamental optimization problems. Given cities and pairwise distances, it is the problem of finding a tour of minimum distance that visits each city once. In spite of ...