Seminars and Colloquiums

Name: Yunbum Kook (국윤범), Sampling and volume computation
Start: 2025-12-30T16:30:00+09:00
End: 2025-12-30T17:30:00+09:00
Location: Room B332

S	M	T	W	T	F	S
	0 events 1 0 events, 1	0 events 2 0 events, 2	0 events 3 0 events, 3	0 events 4 0 events, 4	0 events 5 0 events, 5	0 events 6 0 events, 6
0 events 7 0 events, 7	1 event 8 1 event, 8 4:30 PM - 5:30 PM Matthew Kwan, Exponential anticoncentration of the permanent December 8 Monday @ 4:30 PM - 5:30 PM KST 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 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 … Continue Reading	1 event 9 1 event, 9 4:30 PM - 5:30 PM Tuukka Korhonen, Dynamic Treewidth in Logarithmic Time December 9 Tuesday @ 4:30 PM - 5:30 PM KST Tuukka Korhonen, Dynamic Treewidth in Logarithmic Time 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 … Continue Reading	0 events 10 0 events, 10	0 events 11 0 events, 11	0 events 12 0 events, 12	0 events 13 0 events, 13
0 events 14 0 events, 14	0 events 15 0 events, 15	1 event 16 1 event, 16 4:30 PM - 5:30 PM Chi Hoi Yip, Cliques in Paley graphs and cyclotomic graphs December 16 Tuesday @ 4:30 PM - 5:30 PM KST Chi Hoi Yip, Cliques in Paley graphs and cyclotomic graphs 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 … Continue Reading	0 events 17 0 events, 17	0 events 18 0 events, 18	0 events 19 0 events, 19	0 events 20 0 events, 20
0 events 21 0 events, 21	0 events 22 0 events, 22	0 events 23 0 events, 23	0 events 24 0 events, 24	0 events 25 0 events, 25	1 event 26 1 event, 26 4:30 PM - 5:30 PM Donggyu Kim (김동규), Grassmann-Plücker functions for orthogonal matroids December 26 Friday @ 4:30 PM - 5:30 PM KST Donggyu Kim (김동규), Grassmann-Plücker functions for orthogonal matroids 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 … Continue Reading	0 events 27 0 events, 27
0 events 28 0 events, 28	0 events 29 0 events, 29	1 event 30 1 event, 30 4:30 PM - 5:30 PM Yunbum Kook (국윤범), Sampling and volume computation December 30 Tuesday @ 4:30 PM - 5:30 PM KST Yunbum Kook (국윤범), Sampling and volume computation 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. … Continue Reading	0 events 31 0 events, 31