Now showing items 1-20 of 60

    • 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 ...
    • Strongly Rayleigh distributions and their Applications in Algorithm Design 

      Gharan, Shayan Oveis (2016-09-12)
      A multivariate polynomial p(z1,...,zn) is stable if p(z1,...,zn) <> 0 whenever Im(zi)>0 for all i. Strongly Rayleigh distributions are probability distributions on 0-1 random variables whose generating polynomial is stable. ...
    • A Fast and Simple Unbiased Estimator for Network (Un)reliability 

      Karger, David (2016-09-26)
      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 edge independently ...
    • Prices, Auctions, and Combinatorial Prophet Inequalities 

      Lucier, Brendan (2016-10-03)
      The most common way to sell resources, from apples to business licenses to concert tickets, is to post prices. A choice of prices can be viewed as an algorithm for an online stochastic optimization problem, which makes ...
    • From Minimum Cut to Submodular Minimization: Leveraging the Decomposable Structure 

      Ene, Alina (2016-10-17)
      Submodular function minimization is a fundamental optimization problem that arises in several applications in machine learning and computer vision. The problem is known to be solvable in polynomial time, but general purpose ...
    • Human Decisions and Machine Predictions 

      Kleinberg, Jon (2016-10-24)
      An increasing number of domains are providing us with detailed trace data on human decisions, often made by experts with deep experience in the subject matter. This provides an opportunity to use machine-learning prediction ...
    • Robust Statistics, Revisited 

      Moitra, Ankur (2016-10-31)
      Starting from the seminal works of Tukey (1960) and Huber (1962), the field of robust statistics asks: Are there estimators that provable work in the presence of noise? The trouble is that all known provably robust estimators ...
    • 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 ...
    • 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 ...
    • 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 ...
    • Genesis of ETH and SETH 

      Paturi, Ramamohan (2017-02-13)
      Several researchers have found ETH (Exponential Time Hypothesis) and Strong ETH to be useful and proved matching lower bounds for several problems in P as well as NP based on these conjectures. In this talk, I will talk ...
    • Ten Steps of EM Suffice for Mixtures of Two Gaussians 

      Daskalakis, Constantinos (2017-03-06)
      The Expectation-Maximization (EM) algorithm is a widely used method for maximum likelihood estimation in models with latent variables. For estimating mixtures of Gaussians, its iteration can be viewed as a soft version of ...
    • Optimal Sensory Coding Theories for Neural Systems Under Biophysical Constraints 

      Rozell, Christopher (Georgia Institute of Technology, 2017-03-15)
      The natural stimuli that biological vision must use to understand the world are extremely complex. Recent advances in machine learning have shown that low-dimensional geometric models (e.g., sparsity, manifolds) can ...
    • Neural Computations for Active Perception 

      Olshausen, Bruno (Georgia Institute of Technology, 2017-03-15)
      The human visual system does not passively view the world, but actively moves its sensor array through eye, head and body movements. How do neural circuits in the brain control and exploit these movements in order to build ...
    • 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 ...
    • 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. ...
    • Statistical Query Lower Bounds for High-Dimensional Unsupervised Learning 

      Diakonikolas, Ilias (2017-09-18)
      We describe a general technique that yields the first Statistical Query lower bounds for a range of fundamental high-dimensional learning problems. Our main results are for the problems of (1) learning Gaussian mixture ...
    • Random Walks on Small World Networks 

      Galanis, Andreas (2017-09-21)
      We study the mixing time of random walks on small-world networks modelled as follows: starting with the 2-dimensional periodic grid, each pair of vertices {u,v} with distance d>1 is added as a "long-range" edge with ...
    • 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 ...
    • Variations of Submodularity and Diversity: from Robust Optimization to Markov Chains 

      Jegelka, Stefanie (2017-09-25)
      The combinatorial concept of submodular set functions has proved to be a very useful discrete structure for optimization in machine learning and its applications. In this talk, I will show recent work on generalizations ...