Simons Collaboration on Algorithms and Geometry Monthly Meeting, January 2020

Date & Time

  • Agendaplus--large
    9:30 - 10:15 AM Breakfast
    10:15 - 11:00 AMEden Prywes,
    Quasiconformal and Quasiregular Mappings
    11:00 - 11:15 AMBreak
    11:15 - 12:00 PMVijay Bhattiprolu,
    On the Computational Approximability of Operator Norms
    12:00 - 1:30 PMLunch
    1:30 - 2:15 PMNicholas Marshall,
    Randomized approximation of Mixed Hölder functions
    2:15 - 2:30 PMBreak
    2:30 - 3:15 PMAnrold Filtser,
    Scattering and Sparse Partitions, and their Applications
    3:15 - 3:30 PMBreak
    3:30 - 4:15 PMFotis Illiopoulos,
    Stochastic local search and the Lovasz Local Lemma
  • Abstractsplus--large

    Eden Prywes
    Quasiconformal and Quasiregular Mappings

    I will discuss the theory of quasiconformal and quasiregular mappings in dimensions greater than two.  Quasiconformal and quasiregular mappings are higher dimensional analogs of conformal and holomorphic mappings in complex analysis.  The theory first was developed in the planar case where it was noticed that many of the theorems that applied to holomorphic mappings can be shown for the much more general class of quasiregular mappings.  This remarkably includes Picard's theorem and the Riemann Mapping theorem.  The talk will review generalizations of these results to dimensions larger than two.

    Vijay Bhattiprolu
    On the Computational Approximability of Operator Norms
    Grothendieck’s inequality implies that for any matrix A, the quantity sup_{||x||_infty,||y||_infty<=1} <y, A x> (which is the l_infinity->l_1 operator norm of A) is approximated within a constant by a natural semidefinite programming relaxation. Replacing l_infinity^n above with other families of norms defines a rich class of problems that captures well studied optimization problems in various areas. We will discuss generalizations of the algorithm implicit in Grothendieck’s inequality to other families of norms towards the goal of characterizing when constant factor approximations are possible.

    Based on joint works with subsets of Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Assaf Naor and Madhur Tulsiani.

    Nicholas Marshall
    Randomized approximation of Mixed Hölder functions

    In this talk, I will discuss randomized methods of approximating mixed Hölder functions on [0,1]^d. Additionally, I will describe applications of these methods to data analysis.

    Arnold Filtser
    Scattering and Sparse Partitions, and their Applications

    A partition \(\mathcal{P}\) of a weighted graph \(G\) is \((\sigma,\tau,\Delta)\)-sparse if every cluster has diameter at most \(\Delta\), and every ball of radius \(\Delta/\sigma\) intersects at most \(\tau\) clusters. Similarly, \(\mathcal{P}\) is \((\sigma,\tau,\Delta)\)-scattering if instead for balls we require that every shortest path of length at most \(\Delta/\sigma\) intersects at most \(\tau\) clusters. Given a graph \(G\) that admits a \((\sigma,\tau,\Delta)\)-sparse partition for all \(\Delta>0\), Jia et al. [STOC05] constructed a solution for the Universal Steiner Tree problem (and also Universal TSP) with stretch \(O(\tau\sigma^2\log_\tau n)\). Given a graph \(G\) that admits a \((\sigma,\tau,\Delta)\)-scattering partition for all \(\Delta>0\), we construct a solution for the Steiner Point Removal problem with stretch \(O(\tau^3\sigma^3)\). We then construct sparse and scattering partitions for various different graph families,
    receiving new results for the Universal Steiner Tree and Steiner Point Removal

    Fotis Iliopoulos
    Stochastic local search  and the Lovasz Local Lemma

    Numerous problems in computer science and combinatorics can be formulated as searching for objects lacking certain bad properties, or “flaws”. For example, constraint satisfaction problems like satisfiability can be seen as searching for objects (truth assignments) that are flawless in the sense that they do not violate any constraint. A large class of practical algorithms for finding flawless
    objects employ “stochastic local search”; such algorithms start with a flawed object and try to make it flawless via small randomized changes that in each step focus on eradicating a specific flaw (while potentially introducing others). 

    In this talk, I will present a general framework for the design and analysis of stochastic local search algorithms, inspired by and extending the Lovasz Local Lemma.  I will also talk about its applications in solving  “pseudo-random” instances of constraint satisfaction problems.

  • Contactsplus--large

    General Meeting Assistance
    Emily Klein
    MPS Event Coordinator, Simons Foundation
    (646) 751-1262

Subscribe to MPS announcements and other foundation updates