기초과학연구원 이산수학그룹
|
Sunday
|
Monday
|
Tuesday
|
Wednesday
|
Thursday
|
Friday
|
Saturday
|
|---|---|---|---|---|---|---|
|
0 events,
|
0 events,
|
0 events,
|
0 events,
|
0 events,
|
0 events,
|
0 events,
|
|
0 events,
|
1 event,
-
Extremely sparse random binary matrices tend to be singular, due to the likely presence of "local combinatorial dependencies" such as all-zero columns or pairs of identical columns. We discuss this phenomenon, and some results showing that these kinds of combinatorial dependencies are in some sense the "only" causes of singularity. This is joint work with … |
1 event,
-
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 … |
0 events,
|
0 events,
|
0 events,
|
0 events,
|
|
0 events,
|
0 events,
|
1 event,
-
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 … |
0 events,
|
0 events,
|
0 events,
|
0 events,
|
|
0 events,
|
0 events,
|
0 events,
|
0 events,
|
0 events,
|
1 event,
-
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 … |
0 events,
|
|
0 events,
|
0 events,
|
1 event,
-
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. … |
0 events,
|
0 events,
|
0 events,
|
0 events,
|