Matthew Kwan, Exponential anticoncentration of the permanent
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 …
10 events found.
Discrete Math Seminar
Events
-
-
Room B332 IBS (기초과학연구원)
-
Tuukka Korhonen, Dynamic Treewidth in Logarithmic Time
Room B332 IBS (기초과학연구원)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 …
-
Chi Hoi Yip, Cliques in Paley graphs and cyclotomic graphs
Room B332 IBS (기초과학연구원)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 …
-
Donggyu Kim (김동규), Grassmann-Plücker functions for orthogonal matroids
Room B332 IBS (기초과학연구원)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 …
-
Yunbum Kook (국윤범), Sampling and volume computation
Room B332 IBS (기초과학연구원)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 …
-
-
Daniel Mock, A Simple Algorithm for the Dominating Set Problem and More
Room B332 IBS (기초과학연구원)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 …
-
Ferdinand Ihringer, Boolean Functions Analysis in the Grassmann Graph
Room B332 IBS (기초과학연구원)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 …
-
Tomáš Masařík, Separator Theorem for Minor-free Graphs in Linear Time
Room B332 IBS (기초과학연구원)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. …
-
Daniel Dadush, A Strongly Polynomial Algorithm for Linear Programs with at Most Two Non-Zero Entries per Row or Column
Room B332 IBS (기초과학연구원)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 …
-
-
Xiaofan Yuan (袁晓璠), Rainbow structures in edge colored graphs
Room B332 IBS (기초과학연구원)Let $G = (V, E)$ be a graph on $n$ vertices, and let $c : E \to P$, where $P$ is a set of colors. Let $\delta^c(G) = \min_{v \in …