CanaDAM 2017
Université Ryerson, 12 - 16 juin 2017

Computational Complexity

BUNDIT LAEKHANUKIT, Weizmann Institute of Science
Geometric Representation of Graphs and Its Application to the Complexity of the Closest Pair Problem  [PDF]

Every graph $G$ can be represented by a collection of equi-radius spheres in a $d$-dimensional metric $\Delta$ such that there is an edge $uv$ in $G$ if and only if the spheres corresponding to $u$ and $v$ intersect. The smallest integer $d$ such that $G$ can be represented by a collection of spheres (all of the same radius) in $\Delta$ is called the sphericity of G, and if the collection of spheres are non-overlapping, then the value $d$ is called the contact-dimension of $G$. In this talk, we present lower and upper bounds on the sphericity and contact dimensions of a complete bipartite graph $K_{n,n}$ in various $L^p$ metrics, and we show their connections to the complexity of the closest pair problem.

AVERY MILLER, University of Manitoba
Thick Cover-Free Sequences of Sets and the Circuit Size of Threshold Functions  [PDF]

A sequence $F$ of sets is $r$-cover-free for thickness $b$ if, for each set $S \in F$, there is no subsequence of $F$ of size $r$ whose multiset union contains the elements of $S$ at least $b$ times. In the special case of $b=1$, these correspond to $r$-cover-free families, which have been used to prove bounds for: non-adaptive group testing, the time complexity of neighbour discovery in wireless networks, and the circuit size of $(n,k)$-threshold functions. An $(n,k)$-threshold function takes $n$ binary inputs and outputs 1 if at least $k$ inputs are 1, and outputs 0 otherwise. In this talk, we will discuss results that are obtained by considering more general values for $b$. In the case of threshold functions, we are able to prove a lower bound on the size of circuits that compute $(n,k)$-threshold functions when each gate in the circuit can itself compute a simpler $(n,k')$-threshold function.

DEBAJYOTI MONDAL, University of Waterloo
Contact Systems of Axis-aligned Strings in 3D  [PDF]

A string contact representation $\Psi$ of a graph $G$ maps the vertices of $G$ to interior disjoint axis-aligned strings (simple polygonal chains), where no three strings meet at a point, and two strings share a common point if and only if their corresponding vertices are adjacent in $G$. The complexity of $\Psi$ is the minimum integer $r$ such that every string in $\Psi$ is a $B_r$-string, i.e., a string with at most $r$ bends. We prove that every graph $G$ with maximum degree 4 admits a string contact representation with complexity 4. If $G$ is Hamiltonian and triangle-free, then $G$ has a representation, where all the strings but one are $B_3$-strings. If $G$ is 3-regular and bipartite, then $G$ admits a string contact representation with complexity 2. If we further restrict $G$ to be Hamiltonian, then $G$ has a contact representation, where all the strings but one are $B_1$-strings.

DAVID NARVÁEZ, Rochester Institute of Technology
Analysis of the Hardness of SAT Formulations for Ramsey-type Problems  [PDF]

Constraint satisfaction methods can be used to model interesting and difficult combinatorial problems. This allows us to offload the combinatorial search to, for example, a Boolean satisfiability (SAT) solver. The purpose of doing this would be to leverage the continued advancements in the area of SAT solvers. Yet, some relatively small formulas resulting from encoding combinatorial problems are extremely challenging even for award-winning solvers. Studying the structural properties of these formulas can be used to better understand what makes SAT instances hard. Previous cases of such studies include the resolution of pigeonhole formulas and the space of pebbling formulas. We propose a similar analysis of Boolean formulas encoding edge coloring problems from finite Ramsey theory and related Folkman numbers, both requiring testing the arrowing predicate. Such formulas provide good benchmarks for both satisfiable and unsatisfiable instances, as well as for symmetry breaking and model enumeration techniques.

DANNY RORABAUGH, Queen's University
Logical Axioms and Computational Complexity: A Correspondence  [PDF]

Relational structure $\mathbb{A}$ is compact provided for any structure $\mathbb{B}$ of the same signature, if every finite substructure of $\mathbb{B}$ has a homomorphism to $\mathbb{A}$ then so does $\mathbb{B}$. The Constraint Satisfaction Problem (CSP) for $\mathbb{A}$ is the computational problem of determining whether finite structures have homomorphisms into $\mathbb{A}$. We explore a connection between the hierarchy of logical axioms and the complexity hierarchy of CSPs: It appears that the complexity of CSP for $\mathbb{A}$ corresponds to the strength of the axiom ``$\mathbb{A}$ is compact''. At the top, the statement ``$K_3$ is compacts'' is logically equivalent to the compactness theorem. Thus the compactness of $K_3$ implies the compactness of all finite relational structures. Moreover, the CSP for $K_3$ is NP-complete. At the bottom are width-one structures; these are provably complete from ZF and their corresponding CPSs are polynomial-time solvable.

This is joint work with Claude Tardif and David Wehlau, arXiv:1609.05221 [math.LO].


Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathmatiques The Fields Institute Pacific Institute for the Mathematical Sciences Socit mathmatique du Canada Université Ryerson Office of Naval Research Science and Technology