Euiwoong Lee (이의웅), Faster Exact and Approximate Algorithms for k-Cut

September 8th, 2018
Faster Exact and Approximate Algorithms for k-Cut
Euiwoong Lee (이의웅)
Courant Institute of Mathematical Sciences, NYU, New York, USA
2018/11/13 Tue 5PM (Bldg. E6-1, Room 1401)
In the k-cut problem, we are given an edge-weighted graph G and an integer k, and have to remove a set of edges with minimum total weight so that G has at least k connected components. This problem has been studied various algorithmic perspectives including randomized algorithms, fixed-parameter tractable algorithms, and approximation algorithms. Their proofs of performance guarantees often reveal elegant structures for cuts in graphs.
It has still remained an open problem to (a) improve the runtime of exact algorithms, and (b) to get better approximation algorithms. In this talk, I will give an overview on recent progresses on both exact and approximation algorithms. Our algorithms are inspired by structural similarities between k-cut and the k-clique problem.

Euiwoong Lee (이의웅), Bridging Continuous and Discrete Optimization through the Lens of Approximation

September 8th, 2018

[FYI: Colloquium, School of Computing]

Bridging Continuous and Discrete Optimization through the Lens of Approximation
Euiwoong Lee (이의웅)
Courant Institute of Mathematical Sciences, NYU, New York, USA
2018/11/12 Mon 4PM (Bldg. E3-1, Room 1501)
Mathematical optimization is a field that studies algorithms, given an objective function and a feasible set, to find the element that maximizes or minimizes the objective function from the feasible set. While most interesting optimization problems are NP-hard and unlikely to admit efficient algorithms that find the exact optimal solution, many of them admit efficient “approximation algorithms” that find an approximate optimal solution.
Continuous and discrete optimization are the two main branches of mathematical optimization that have been primarily studied in different contexts. In this talk, I will introduce my recent results that bridge some of important continuous and discrete optimization problems, such as matrix low-rank approximation and Unique Games. At the heart of the connection is the problem of approximately computing the operator norm of a matrix with respect to various norms, which will allow us to borrow mathematical tools from functional analysis.

Jineon Baek, On the off-diagonal Erdős-Szekeres convex polygon problem

August 29th, 2018
On the off-diagonal Erdős-Szekeres convex polygon problem
2018/09/10 Mon 5PM-6PM (Room 1401 of Bldg. E6-1)
The infamous Erdős-Szekeres conjecture, posed in 1935, states that the minimum number ES(n) of points on a plane in general position (that is, no three colinear points) that guarantees a subset of n points in convex position is equal to 2(n-2) + 1. Despite many years of effort, the upper bound of ES(n) had not been better than O(4n – o(n)) until Suk proved the groundbreaking result ES(n)≤2n+o(n) in 2016.
In this talk, we focus on a variant of this problem by Erdős, Tuza and Valtr regarding the number ETV(a, b, n) of points needed to force either an a-cup, b-cap or a convex n-gon for varying a, b and n. They showed ETV(a, b, n) > \sum_{i=n-b}^{a-2} \binom{n}{i-2} by supplying a set of points with no a-cup, b-cap nor a n-gon of that many number, and conjectured that the inequality cannot be improved. Due to their construction, the conjecture is in fact equivalent to the Erdős-Szekeres conjecture. However, even the simplest equality ETV(4, n, n) = \binom{n+1}{2} + 1, which must be true if the Erdős-Szekeres conjecture is, has not been verified yet. To the best of our knowledge, the bound ETV(4, n, n) ≤ \binom{n + 2}{2} – 1, mentioned by Balko and Valtr in 2015, is currently the best bound known in literature.
The talk is divided into two parts. First, we introduce the mentioned works on the Erdős-Szekeres conjecture and observe that the argument of Suk can be directly adapted to prove an improved bound of ETV(a, n, n). Then we show the bound ETV(4, n, n) ≤ \binom{n+2}{2} – C \sqrt{n} for a fixed constant C>0, improving the previously known best bound of Balko and Valtr.

Hong Liu, Enumerating sets of integers with multiplicative constraints

August 24th, 2018
Enumerating sets of integers with multiplicative constraints
Hong Liu
Mathematics Institute, University of Warwick, Warwick, UK
2018/9/3 Mon 5PM
Counting problems on sets of integers with additive constraints have been extensively studied. In contrast, the counting problems for sets with multiplicative constraints remain largely unexplored. In this talk, we will discuss two such recent results, one on primitive sets and the other on multiplicative Sidon sets. Based on joint work with Peter Pach, and with Peter Pach and Richard Palincza.

Tillmann Miltzow, The Art Gallery Problem is ∃R-complete

June 26th, 2018
The Art Gallery Problem is ∃R-complete
Tillmann Miltzow
Computer Science Department, Université Libre de Bruxelles, Brussels
2018/7/24 Tue 5PM-6PM (Room 3434, Bldg. E6-1)
We prove that the art gallery problem is equivalent under polynomial time reductions to deciding whether a system of polynomial equations over the real numbers has a solution. The art gallery problem is a classical problem in computational geometry. Given a simple polygon P and an integer k, the goal is to decide if there exists a set G of k guards within P such that every point p∈P is seen by at least one guard g∈G. Each guard corresponds to a point in the polygon P, and we say that a guard g sees a point p if the line segment pg is contained in P. The art gallery problem has stimulated extensive research in geometry and in algorithms. However, the complexity status of the art gallery problem has not been resolved. It has long been known that the problem is NP-hard, but no one has been able to show that it lies in NP. Recently, the computational geometry community became more aware of the complexity class ∃R. The class ∃R consists of problems that can be reduced in polynomial time to the problem of deciding whether a system of polynomial equations with integer coefficients and any number of real variables has a solution. It can be easily seen that NP⊆∃R. We prove that the art gallery problem is ∃R-complete, implying that (1) any system of polynomial equations over the real numbers can be encoded as an instance of the art gallery problem, and (2) the art gallery problem is not in the complexity class NP unless NP=∃R. As a corollary of our construction, we prove that for any real algebraic number α there is an instance of the art gallery problem where one of the coordinates of the guards equals α in any guard set of minimum cardinality. That rules out many geometric approaches to the problem. This is joint work with Mikkel Abrahamsen and Anna Adamaszek.