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.

(Intensive Lecture Series) Ron Aharoni, Lectures on topological methods in combinatorics

June 20th, 2018

Intensive Lecture Series

Lectures on topological methods in combinatorics
Ron Aharoni
Department of Mathematics, Technion, Israel
2018/7/17-19 2PM-5PM (Room 3434, Bldg. E6-1)
The lectures will give an introduction to the application of topological methods in matching theory, graph theory, and combinatorics.
Topics that will be covered:

– A topological extension of Hall’s theorem
– combinatorial applications of the nerve theorem
– d-Leray complexes and rainbow matchings
– Matroid complexes and applications
– Open problems

(Intensive Lecture Series) Jaehoon Kim, A course in graph embedding

May 19th, 2018

Intensive Lecture Series

A course in graph embedding
Jaehoon Kim (김재훈)
School of Mathematics, Birmingham University, Birmingham, UK
2018/6/25-29 10:30AM-12PM, 2:30PM-4PM (Room 3434, Bldg. E6-1)

In this lecture, we aim to learn several techniques to find sufficient conditions on a dense graph G to contain a sparse graph H as a subgraph.

Lecture note (PDF file)

Tentative plan for the course (June 25, 26, 27, 28, 29)
Lecture 1 : Basic probabilistic methods
Lecture 2 : Extremal number of graphs
Lecture 3 : Extremal number of even cycles
Lecture 4 : Dependent random choice
Lecture 5 : The regularity lemma and its applications
Lecture 6 : Embedding large graphs
Lecture 7 : The blow-up lemma and its applications I
Lecture 8 : The blow-up lemma and its applications II
Lecture 9 : The absorbing method I
Lecture 10 : The absorbing method II

Jinyoung Park (박진영), Coloring hypercubes

May 16th, 2018
Coloring hypercubes
Jinyoung Park (박진영)
Department of Mathematics, Rutgers, Piscataway, NJ, USA
2018/06/26 Tuesday 5PM
We discuss the number of proper colorings of hypercubes
given q colors. When q=2, it is easy to see that there are only 2
possible colorings. However, it is already highly nontrivial to figure
out the number of colorings when q=3. Since Galvin (2002) proved the
asymptotics of the number of 3-colorings, the rest cases remained open
so far. In this talk, I will introduce a recent work on the number of
4-colorings, mainly focusing on how entropy can be used in counting.
This is joint work with Jeff Kahn.

Eric Vigoda, Learning a graph via random colorings

May 15th, 2018
Learning a graph via random colorings
Eric Vigoda
College of Computing, Georgia Institute of Technology, Atlanta, GA, USA
2018/6/11 Mon 5PM-6PM
For an unknown graph G on n vertices, given random k-colorings of G, can one learn the edges of G? We present results on identifiability/non-identifiability of the graph G and efficient algorithms for learning G. The results have interesting connections to statistical physics phase transitions.
This is joint work with Antonio Blanca, Zongchen Chen, and Daniel Stefankovic.