Our mission is to identify problems with natural connections to algorithms and randomness. To help solve these problems and understand related phenomena by suggesting provable algorithms and algorithmic explanations. To formulate general tools based on the solutions and the insights behind them and thereby extend and solidify the theory of algorithms. To represent an algorithms and randomness think tank that scientists across campus can use as a resource.

Collections in this community

Recent Submissions

  • Distribution testing: Classical and new paradigms 

    Aliakbarpour, Maryam (2020-03-02)
    One of the most fundamental problems in learning theory is to view input data as random samples from an unknown distribution and then to make statistical inferences about the underlying distribution. In this talk, we focus ...
  • Improved Analysis of Higher Order Random Walks and Applications 

    Alev, Vedat Levi (2020-02-10)
    Local spectral expansion is a very useful method for arguing about the spectral properties of several random walk matrices over simplicial complexes. The motivation of this work is to extend this method to analyze the ...
  • Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model 

    Liu, Kuikui (2020-01-27)
    We say a probability distribution µ is spectrally independent if an associated correlation matrix has a bounded largest eigenvalue for the distribution and all of its conditional distributions. We prove that if µ is ...
  • Robust Mean Estimation in Nearly-Linear Time 

    Hopkins, Samuel (2019-12-02)
    Robust mean estimation is the following basic estimation question: given i.i.d. copies of a random vector X in d-dimensional Euclidean space of which a small constant fraction are corrupted, how well can you estimate the ...
  • Some new approaches to the heavy hitters problem 

    Nelson, Jelani (2019-09-16)
    In the 'frequent items' problem one sees a sequence of items in a stream (e.g. a stream of words coming into a search query engine like Google) and wants to report a small list of items containing all frequent items. In ...
  • Fast Approximation Algorithms and Complexity Analysis for Design of Networked Systems 

    Yi, Yuhao (2019-11-18)
    This talk focuses on network design algorithms for optimizing average consensus dynamics, dynamics that are widely used for information diffusion and distributed coordination in networked control systems. Network design ...
  • Rapidly Mixing Random Walks via Log-Concave Polynomials (Part 2) 

    Anari, Nima (2019-11-06)
    (This is Part 2, continuation of Tuesday's lecture.) A fundamental tool used in sampling, counting, and inference problems is the Markov Chain Monte Carlo method, which uses random walks to solve computational problems. ...
  • Rapidly Mixing Random Walks via Log-Concave Polynomials (Part 1) 

    Anari, Nima (2019-11-05)
    A fundamental tool used in sampling, counting, and inference problems is the Markov Chain Monte Carlo method, which uses random walks to solve computational problems. The main parameter defining the efficiency of this ...
  • Algorithmic Discrete Choice 

    Kumar, Ravi (2019-11-04)
    In this talk we consider random utility models for discrete choice. In discrete choice, the task is to select exactly one element from a discrete set of alternatives. We focus on algorithmic questions in this and related ...
  • What 2-layer neural nets can we optimize? 

    Ge, Rong (2019-10-28)
    Optimizing neural networks is a highly nonconvex problem, and even optimizing a 2-layer neural network can be challenging. In the recent years many different approaches were proposed to learn 2-layer neural networks under ...
  • Partial Function Extension with Applications to Learning and Property Testing 

    Bhaskar, Umang (2019-10-18)
    In partial function extension, we are given a partial function consisting of points from a domain and a function value at each point. Our objective is to determine if this partial function can be extended to a total ...
  • Linear Size Sparsifier and the Geometry of the Operator Norm Ball 

    Rothvoss, Thomas (2019-10-07)
    The Matrix Spencer Conjecture asks whether given n symmetric matrices in ℝn×n with eigenvalues in [−1,1] one can always find signs so that their signed sum has singular values bounded by O(n‾√). The standard approach in ...
  • Lagrangian Duality in Mechanism Design 

    Devanur, Nikhil (2019-09-30)
    This talk surveys the usage of Lagrangian Duality in the design and analysis of auctions. Designing optimal (revenue maximizing) auctions in multi-parameter settings has been among the most active areas in algorithmic ...
  • Thompson Sampling for learning in online decision making 

    Agrawal, Shipra (2019-09-23)
    Modern online marketplaces feed themselves. They rely on historical data to optimize content and user-interactions, but further, the data generated from these interactions is fed back into the system and used to optimize ...
  • Approximating Profile Maximum Likelihood Efficiently 

    Charikar, Moses (2019-09-09)
    Symmetric properties of distributions arise in multiple settings. For each of these, separate estimators and analysis techniques have been developed. Recently, Orlitsky et al showed that a single estimator that maximizes ...
  • The Power of Factorization Mechanisms in Differential Privacy 

    Nikolov, Aleksandar (2019-08-19)
    A central goal in private data analysis is to estimate statistics about an unknown distribution from a dataset possibly containing sensitive information, so that the privacy of any individual represented in the dataset is ...
  • Solving Linear Programs in the Current Matrix Multiplication Time 

    Lee, Yin Tat (2019-05-20)
    We show how to solve linear programs with accuracy epsilon in time n^{omega+o(1)} log(1/epsilon) where omega~2.3728639 is the current matrix multiplication constant. This hits a natural barrier of solving linear programs ...
  • 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 ...
  • 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 ...
  • 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 ...

View more