[Colloquium] Reminder: Show & Tell Series at TTI-C (Today @ 12:15)-lunch

[Katherine Cumming]

TOYOTA TECHNOLOGICAL INSTITUTE 
SHOW AND TELL SERIES TALK
 
Speaker: Jaikumar Radhakrishnan
Speaker's homepage: http://www.tti-c.org/radhakrishnan.html
 
Time: Tuesday November 16th, 12:15pm
Place: TTI-C conference room (1427 E. 60th St. - 2nd Floor) Lunch
provided
 
 
Title: Completely Connected Partitions in Graphs
 
Abstract: A completely connected partition in a graph is a partition of
the vertex set such that there is an edge connecting every two sets in
the partition. Let cp(G) denote the size of the largest completely
connected partition of the graph G, where the size of a partition is the
number of sets in it. I will present the following results.
 
 * There is a randomized polynomial-time algorithm that given a graph
   G, produces a completely connected partition of G of size
   Omega(cp(G)/sqrt{log |V(G)|}). This algorithm can be derandomized.
 
 * This algorithm is essentially the best possible.  If a
   polynomial-time algorithm approximates the size of the largest
   complete partition to within a factor o(sqrt{log |V(G)|}),
   then NP is in RTime(n^{O(loglog n)}). 
 
I hope to present the first result in detail. The second part uses
inapproximability arguments based on probabilistically checkable proofs.
I will review these arguments and sketch how our result can be derived
from them.
 
[These results were obtained in joint work with Guy Kortsarz (Rutgers
University, New Jersey), Magnus Halldorsson (Reykjavik, Iceland) and
Sivaramakrishnan Sivasubramanian (Tata Institute, Mumbai, India).]
 
 
If you have questions, or would like to meet the speaker, please contact
Katherine at 4-1994 or kcumming at tti-c.org.  For information on future
TTI-C talks or events, please go to the TTI-C Events page:
http://www.tti-c.org/events.shtml. 
 
 
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20041116/520d931a/attachment.htm