기초과학연구원 이산수학그룹
Let $F_{k,d}(n)$ be the maximal size of a set ${A}\subseteq $ such that the equation \ has no solution with $a_1,a_2,\ldots,a_k\in A$ and integer $x$. Erdős, Sárközy and T. Sós studied $F_{k,2}$, and gave bounds when $k=2,3,4,6$ and also in the general case. We study the problem for $d=3$, and provide bounds for $k=2,3,4,6$ and …
Let A be a random n×n matrix with independent entries, and suppose that the entries are “uniformly anticoncentrated” (for example, A could be a uniformly random n×n matrix with ±1 entries). We prove that the permanent of A is exponentially anticoncentrated, significantly improving previous bounds of Tao and Vu. Our proof also works for the …
We present a dynamic data structure that maintains a tree decomposition of width at most 9k+8 of a dynamic graph with treewidth at most k, which is updated by edge insertions and deletions. The amortized update time of our data structure is $2^{O(k)} \log n$, where n is the number of vertices. The data structure …
Given a prime power $q \equiv 1 \pmod 4$, the Paley graph of order $q$ is the graph defined over $\mathbb{F}_q$ (the finite field with $q$ elements), such that two vertices are adjacent if and only if their difference is a square in $\mathbb{F}_q$. In this talk, I will present some recent progress on the …
We present a new cryptomorphic definition of orthogonal matroids with coefficients using Grassmann-Plücker functions. The equivalence is motivated by Cayley's identities expressing principal and almost-principal minors of a skew-symmetric matrix in terms of its pfaffians. As a corollary of the new cryptomorphism, we deduce that each component of the orthogonal Grassmannian is parameterized by certain …
Since the development of the first randomized polynomial-time algorithm for volume computation by Dyer, Frieze, and Kannan in 1989, convex-body sampling has been a central problem at the intersection of algorithms, geometry, and probability. A major milestone came in 1997, when Kannan, Lovász, and Simonovits analyzed the Ball Walk and formulated the influential KLS conjecture. …
In , Fabianski et. al. developed a simple, yet surprisingly powerful algorithmic framework to develop efficient parameterized graph algorithms. Notably they derive a simple parameterized algorithm for the dominating set problem on a variety of graph classes, including powers of nowhere dense classes and biclique-free classes. These results encompass a wide range of previously known …
Boolean function analysis for the hypercube $\{ 0, 1 \}^n$ is a well-developed field and has many famous results such as the FKN Theorem or Nisan-Szegedy Theorem. One easy example is the classification of Boolean degree $1$ functions: If $f$ is a real, $n$-variate affine function which is Boolean on the $n$-dimensional hypercube (that is, …
The planar separator theorem by Lipton and Tarjan states that any planar graph with $n$ vertices has a balanced separator of size $O(\sqrt{n})$ that can be found in linear time. This landmark result kicked off decades of research on designing linear or nearly linear-time algorithms on planar graphs. In an attempt to generalize Lipton-Tarjan's theorem …
We give a strongly polynomial algorithm for minimum cost generalized flow, and hence for optimizing any linear program with at most two non-zero entries per row, or at most two non-zero entries per column. Primal and dual feasibility were shown by Végh (MOR ’17) and Megiddo (SICOMP ’83) respectively. Our result can be viewed as …