Now showing items 1-20 of 60

    • 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 ...
    • 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 ...
    • 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 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 ...
    • Differentially Private Analysis of Graphs 

      Raskhodnikova, Sofya (2016-11-07)
      Many types of data can be represented as graphs, where nodes correspond to individuals and edges capture relationships between them. Examples include datasets capturing “friendships” in an online social network, financial ...
    • Distributed PCP Theorems for Hardness of Approximation in P 

      Rubinstein, Aviad (2017-11-06)
      We present a new model of probabilistically checkable proof (PCP), which we call "Distributed PCP": A satisfying assignment (x in {0,1}^n) to a CNF formula is shared between two parties (Alice knows x_1, ... x_{n/2}, ...
    • Entropy, Log-Concavity, and a Deterministic Approximation Algorithm for Counting Bases of Matroids 

      Anari, Nima (2018-04-30)
      We give a deterministic 2^O(rank) approximation algorithm to count the number of bases of a given matroid and the number of common bases of any two matroids. Based on a lower bound of Azar et al., this is almost the best ...
    • Explicit Two-Source Extractors and Resilient Functions 

      Zuckerman, David (2016-11-14)
      We explicitly construct an extractor for two independent sources on n bits, each with min-entropy at least log^C n for a large enough constant C. Our extractor outputs one bit and has error n^{-\Omega(1)}. The best previous ...