Search Mailing List Archives

Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[theory-seminar] TCS+ talk: Wednesday, December 12, Julia Chuzhoy, TTIC

Clement Louis Arthur Canonne ccanonne at
Wed Dec 12 10:20:09 PST 2018

In case you are late but interested, we moved to Gates 496 (given the numbers).

-- Clément

On Dec 11, 2018 3:57 PM, Clement Louis Arthur Canonne <ccanonne at> wrote:
Reminder: this is tomorrow, usual room (4th floor)!

-- Clément

On Dec 7, 2018 6:22 AM, Clément Canonne <ccanonne at> wrote:
Hi everyone,

For the next TCS+ talk*, and last of the Fall season, Julia Chuzhoy will
be speaking about an "Almost Polynomial Hardness of Node-Disjoint Paths
in Grids."

Come next Wednesday (12th) at 10am (actually, come at 9:55 for
breakfast) to see it!


-- Clément

* for the people in the back: this is an online, interactive talk we can
all watch from Gates while sipping coffee and asking questions to the

Speaker: Julia Chuzhoy (TTIC)
Title: Almost Polynomial Hardness of Node-Disjoint Paths in Grids

Abstract: In the classical Node-Disjoint Paths (NDP) problem,  we are
given an n-vertex graph G, and a collection of pairs of its vertices,
called demand pairs. The goal is to route as many of the demand pairs as
possible, where to route a pair we need to select a path connecting it,
so that all selected paths are disjoint in their vertices.

The best current algorithm for NDP achieves an
$O(\sqrt{n})$-approximation, while, until recently, the best negative
result was a roughly $\Omega(\sqrt{\log n})$-hardness of approximation.
Recently, an improved $2^{\Omega(\sqrt{\log n})}$-hardness of
approximation for NDP was shown, even if the underlying graph is a
subgraph of a grid graph, and all source vertices lie on the boundary of
the grid. Unfortunately, this result does not extend to grid graphs.

The approximability of NDP in grids has remained a tantalizing open
question, with the best upper bound of $\tilde{O}(n^{1/4})$, and the
best lower bound of APX-hardness. In this talk we come close to
resolving this question, by showing an almost polynomial hardness of
approximation for NDP in grid graphs.

Our hardness proof performs a reduction from the 3COL(5) problem to NDP,
using a new graph partitioning problem as a proxy. Unlike the more
standard approach of employing Karp reductions to prove hardness of
approximation, our proof  is a Cook-type reduction, where, given an
input instance of 3COL(5), we produce a large number of instances of
NDP, and apply an approximation algorithm for NDP to each of them. The
construction of each new instance of NDP crucially depends on  the
solutions to the previous instances that were found by the approximation

Joint work with David H.K. Kim and Rachit Nimavat.

theory-seminar mailing list
theory-seminar at

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the theory-seminar mailing list