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

  • 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 ...
  • 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 ...
  • A Tight Net with Respect to a Random Matrix Norm and Applications to Estimating Singular Values 

    Livshyts, Galyna (2019-02-11)
    In this talk we construct a net around the unit sphere with good properties. We show that with exponentially high probability, the value of |Ax| on the sphere can be approximated well using this net, where A is any random ...
  • Towards Understanding First Order Algorithms for Nonconvex Optimization in Machine Learning 

    Zhao, Tuo (2019-02-11)
    Stochastic Gradient Descent-type (SGD) algorithms have been widely applied to many non-convex optimization problems in machine learning, e.g., training deep neural networks, variational Bayesian inference and collaborative ...
  • Learning and Efficiency of Outcomes in Games 

    Tardos, Éva (2019-02-11)
    Selfish behavior can often lead to suboptimal outcome for all participants, a phenomenon illustrated by many classical examples in game theory. Over the last decade we have studied Nash equilibria of games, and developed ...
  • The polymorphic gateway between structure and algorithms: Beyond CSPs 

    Guruswami, Venkat (2018-12-03)
    What underlying mathematical structure (or lack thereof) in a computational problem governs its efficient solvability (or dictates its hardness)? In the realm of constraint satisfaction problems (CSPs), the algebraic ...
  • 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 ...
  • 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 ...
  • Fairness in Algorithmic Decision Making 

    Kannan, Sampath (2018-10-29)
    In this talk we survey some formulations of fairness requirements for decision making under uncertainty. We then discuss results from 3 recent papers: 1) Treating individuals fairly is not in conflict with long-term ...
  • The Paulsen problem, continuous operator scaling, and smoothed analysis 

    Lau, Lap Chi (2018-10-15)
    The Paulsen problem is a basic open problem in operator theory. We define a continuous version of the operator scaling algorithm to solve this problem. A key step is to show that the continuous operator scaling algorithm ...
  • Improved Decoding of Folded Reed-Solomon and Multiplicity Codes 

    Wootters, Mary (2018-10-01)
    List-decoding is an important primitive in the theory of error correcting codes, and it has long been a goal to obtain explicit constructions of capacity-achieving, efficiently list-decodable codes. Folded Reed-Solomon ...
  • (Nearly) Efficient Algorithms for the Graph Matching Problem in Correlated Random Graphs 

    Schramm, Tselil (2018-09-24)
    The Graph Matching problem is a robust version of the Graph Isomorphism problem: given two not-necessarily-isomorphic graphs, the goal is to find a permutation of the vertices which maximizes the number of common edges. ...
  • On the Complexity of Clustering Problems 

    Louis, Anand (2018-09-10)
    Euclidean k-means clustering, a problem having numerous applications, is NP-hard in the worst case but often solved efficiently in practice using simple heuristics. A quest for understanding the properties of real-world ...
  • 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, ...
  • A Friendly Smoothed Analysis of the Simplex Method 

    Dadush, Daniel (2018-05-17)
    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 understanding the simplex method ...
  • On the infection time of the Duarte model: the role of energy barriers 

    Martinelli, Fabio (2018-05-15)
    In the Duarte model each vertex of Z<sup>2</sup> can be either infected or healthy. In the bootstrap percolation model version, infected vertices stay infected while a healthy vertex becomes infected if at least two of its ...
  • Sphere packings, codes, and kissing numbers via hard core models 

    Perkins, Will (2018-05-17)
    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. These results allows us to improve ...

View more