Seri Khoury

Seri Khoury
Are you Seri Khoury?

Claim your profile, edit publications, add additional information:

Contact Details

Name
Seri Khoury
Affiliation
Location

Pubs By Year

Pub Categories

 
Computer Science - Data Structures and Algorithms (2)
 
Computer Science - Distributed; Parallel; and Cluster Computing (2)

Publications Authored By Seri Khoury

We present the first super-linear lower bounds for natural graph problems in the CONGEST model, answering a long-standing open question. Specifically, we show that any exact computation of a minimum vertex cover or a maximum independent set requires $\Omega(n^2/\log^2{n})$ rounds in the worst case in the CONGEST model, as well as any algorithm for $\chi$-coloring a graph, where $\chi$ is the chromatic number of the graph. We further show that such strong lower bounds are not limited to NP-hard problems, by showing two simple graph problems in P which require a quadratic and near-quadratic number of rounds. Read More

We develop a new technique for constructing sparse graphs that allow us to prove near-linear lower bounds on the round complexity of computing distances in the CONGEST model. Specifically, we show an $\widetilde{\Omega}(n)$ lower bound for computing the diameter in sparse networks, which was previously known only for dense networks [Frishknecht et al., SODA 2012]. Read More