Lecture

Title: Some results on spectral Turán's type problem

Title: Generating k EPR-pairs from an n-party resource state

Abstract: Motivated by quantum network applications over classical channels, we initiate the study of n-party resource states from which LOCC protocols can create EPR-pairs between any k disjoint pairs of parties.

Title: Approximation algorithm for stochastic k-TSP

Abstract: The input of the deterministic k-TSP problem consists of a metric complete graph with root p in which the nodes are assigned a fixed non-negative reward. The objective is to construct a p-rooted path of minimum length that collects total reward at least k. In this talk we will explore a stochastic variant of this problem in which the rewards assigned to the nodes are independent random variables, and the objective is to derive a policy that minimizes the expected length of a p-rooted path that collects total reward at least k. We will discuss approximation algorithms for this problem proposed in a paper by Ene, Nagarajan and Saket, and a paper by Jiang, Li, Liu and Singla.

Title: Probabilistic root finding in code-based cryptography

Abstract: Factorization of polynomials over finite fields, and the particular subproblem of finding roots of polynomials, have many applications in diverse areas such as computer algebra, cryptography and coding theory, among many others. In practice, fast factorization algorithms are probabilistic.

Titile: Global geometric reductions for some bottleneck questions in hardness of approximation

Abstract: I will describe the classical "local gadget reduction" paradigm for proving hardness of approximation results and then list some important optimization problems that resist all such attacks. With a focus on problems that can be cast as quadratic maximization over convex sets, I will describe some successes in bypassing the aforementioned bottleneck using ideas from geometry. Time permitting I will also describe some compelling new frontiers where answering some questions in convex geometry could be the path forward.

Title: Boosted Sampling

Abstract: We will discuss the boosted sampling technique introduced by Gupta et al. which approximates the stochastic version of problems by using nice approximation algorithms for the deterministic version of the problem. We will focus on rooted stochastic Steiner trees as an example, though other problems are covered by this approach (such as vertex cover and facility location). The problem is given to us in two stages: in the first stage we may choose some elements at a cheaper cost, and in the second stage our actual requirements are revealed to us, and we can buy remaining needed elements at a more expensive cost (where costs get scaled by some factor in the second stage). We will see that if our problem is sub-additive, and we have an alpha-approximation algorithm for the deterministic version of our problem with a beta-strict cost-sharing function then we can get an (alpha + beta)-approximation for the stochastic version of our problem. We also discuss related problems, for example the (not sub-additive!) unrooted stochastic Steiner tree problem.

Title: Algorithms for Analytic Combinatorics in Several Variables

Abstract: In this presentation we will see how to apply the theory of complex analysis to study multivariate generating series by looking at several examples. Specifically, given a rational bivariate generating function G(x, y)/H(x, y) with coefficients f_{i, j} the objective is algorithmically determine asymptotic formulas to approximate f_{rn, sn} as n goes to infinity, for fixed positive integers r and s.

Title: Approximation algorithms for stochastic orienteering  

Abstract: This week we revisit the stochastic orienteering problem in which we are given a metric graph where each node has a deterministic reward and a random size. The goal is to adaptively decide on which nodes to visit to maximize the expected reward, while not exceeding the budget B on the distance plus the size of jobs processed.

Title: Approximating Weighted Connectivity Augmentation below Factor 2

Abstract:  The Weighted Connectivity Augmentation Problem (WCAP) asks to increase the edge-connectivity of a graph in the cheapest possible way by adding edges from a given set. It is one of the most elementary network design problems for which no better-than-2 approximation algorithm has been known, whereas 2-approximations can be easily obtained through a variety of well-known techniques.

Title: Recursions and Proofs in Coxeter-Catalan combinatorics

Abstract:  The collection of parking functions under a natural Sn-action (which has Catalan-many orbits) has been a central object in Algebraic Combinatorics since the work of Haiman more than 30 years ago. One of the lines of research spawned around it was towards defining and studying analogous objects for real and complex reflection groups W; the main candidates are known as the W-non-nesting and W-non-crossing parking functions.