Distinguished lectures, colloquia, seminars and speakers of interest to the Algorithms, Randomness and Complexity Center

Recent Submissions

  • 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 ...
  • 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 ...
  • 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 ...
  • 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. ...
  • 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 ...