|
Hi all,
We will have theory lunch tomorrow at noon in CS 4310. We are going to watch the TCS+ talk by Jason Li from CMU on "The Karger-Stein Algorithm is Optimal for k-cut."
Bring your lunch, and see you there!
Here is the spreadsheet for this semester:
Students are encouraged to sign up to give an (informal) talk. Also, professors are certainly welcome to add a note if free food will be provided.
Below is the abstract of tomorrow's talk.
Abstract:
| In the $k$-cut problem, we are given an edge-weighted graph and want to find the least-weight set of edges whose deletion breaks the graph into $k$ connected components. Algorithms due to Karger-Stein and Thorup showed how to find such a minimum $k$-cut
in time approximately $O(n^{2k-2})$. The best lower bounds come from conjectures about the solvability of the $k$-clique problem and a reduction from $k$-clique to $k$-cut, and show that solving $k$-cut is likely to require time $\Omega(n^k)$. Our recent results
have given special-purpose algorithms that solve the problem in time $n^{1.98k + O(1)}$, and ones that have better performance for special classes of graphs (e.g., for small integer weights). |
| In this work, we resolve the problem for general graphs, by showing that for any fixed $k \geq 2$, the Karger-Stein algorithm outputs any fixed minimum $k$-cut with probability at least $\widehat{O}(n^{-k})$, where $\widehat{O}(\cdot)$ hides a
$2^{O(\ln \ln n)^2}$ factor. This also gives an extremal bound of $\widehat{O}(n^k)$ on the number of minimum $k$-cuts in an $n$-vertex graph and an algorithm to compute a minimum $k$-cut in similar runtime. Both are tight up to $\widehat{O}(1)$
factors. |
| The first main ingredient in our result is a fine-grained analysis of how the graph shrinks---and how the average degree evolves---under the Karger-Stein process. The second ingredient is an extremal result bounding the number of cuts of size at most $(2-\delta)
OPT/k$, using the Sunflower lemma. |
Best,
Yifeng
From: YIFENG TENG <yifengt@xxxxxxxxxxx>
Sent: Tuesday, November 5, 2019 3:15 PM
To: Theory Students <theory-students@xxxxxxxxxxx>; theory-postdocs@xxxxxxxxxxx <theory-postdocs@xxxxxxxxxxx>; Theory Faculty <theory-faculty@xxxxxxxxxxx>
Subject: Re: Theory lunch tomorrow
There will not be pizza this week. Please bring your own lunch.
Best,
Yifeng
From: Theory-students <theory-students-bounces@xxxxxxxxxxx> on behalf of YIFENG TENG <yifengt@xxxxxxxxxxx>
Sent: Tuesday, November 5, 2019 2:38 PM
To: Theory Students <theory-students@xxxxxxxxxxx>; theory-postdocs@xxxxxxxxxxx <theory-postdocs@xxxxxxxxxxx>; Theory Faculty <theory-faculty@xxxxxxxxxxx>
Subject: [theory students] Theory lunch tomorrow
We will have theory lunch at noon tomorrow in 4310. Vasilis is going to give a practice talk on his FOCS paper. Pizza
will be served during the talk (hopefully).
The spreadsheet for this semester is as below:
Students are encouraged to sign up to give an (informal) talk. Also, professors are certainly welcome to add a note if free food will be provided.
Below is the information for tomorrow's talk.
Title: Efficient Truncated Statistics with Unknown Truncation
Abstract: We study the problem of estimating the parameters
of a Gaussian distribution when samples are only shown if they fall in some (unknown) subset $S
\subseteq \R^d$. This core problem in truncated statistics has long history going
back to Galton, Lee, Pearson and Fisher. Recent work by Daskalakis et al. (FOCS'18), provides the first efficient algorithm that works for arbitrary sets in high dimension when the set is known, but leaves as an open problem the more challenging and relevant
case of unknown truncation set.
Our main result is a computationally and sample efficient algorithm for estimating the parameters of
the Gaussian under arbitrary unknown truncation sets whose performance decays with a natural measure of complexity of the set, namely its Gaussian surface area. Notably, this algorithm works for large families of sets including intersections of halfspaces,
polynomial threshold functions and general convex sets. We show that our algorithm closely captures the tradeoff between the complexity of the set and the number of samples needed to learn the parameters by exhibiting a set with small Gaussian surface area
for which it is information theoretically impossible to learn the true Gaussian with few samples.
Thanks,
Yifeng
|
![[Computer Systems Lab]](http://www.cs.wisc.edu/pics/csl_logo.gif){kind=logo}