기초과학연구원 이산수학그룹
Transductions are a general formalism for expressing transformations of graphs (and more generally, of relational structures) in logic. We prove that a graph class C can be FO-transduced from a …
SATNet is a differentiable constraint solver with a custom backpropagation algorithm, which can be used as a layer in a deep-learning system. It is a promising proposal for bridging deep …
We show that if $L_1$ and $L_2$ are linear transformations from $\mathbb{Z}^d$ to $\mathbb{Z}^d$ satisfying certain mild conditions, then, for any finite subset $A$ of $\mathbb{Z}^d$, \ This result corrects …
One of the important work in graph theory is the graph minor theory developed by Robertson and Seymour in 1980-2010. This provides a complete description of the class of graphs …
Twin-width is a recently introduced graph parameter based on vertex contraction sequences. On classes of bounded twin-width, problems expressible in FO logic can be solved in FPT time when provided …
The sphere packing problem asks for the densest packing of nonoverlapping equal-sized balls in the space. This is an old and difficult problem in discrete geometry. In this talk, we …
Given a set $E$ and a point $y$ in a vector space over a finite field, the radial projection $\pi_y(E)$ of $E$ from $y$ is the set of lines that …
One interesting difference between (nondegenerate) Graph Turán problem and Hypergraph Turán problem is that the hypergraph families can have at least two very different extremal constructions. In this talk, we …
This talk will highlight recent results establishing a beautiful computational phase transition for approximate counting/sampling in (binary) undirected graphical models (such as the Ising model or on weighted independent sets). The computational problem is to …
A hole in a graph $G$ is an induced cycle of length at least four, and for every hole $H$ in $G$, a vertex $h\in G\setminus H$ is called a …