Nabil Kahalé

FOCS Conference 1995 Conference Paper

Fault Diagnosis in a Flash

• Richard Beigel
• William Hurwood
• Nabil Kahalé

Consider a set of n processors that can communicate with each other. Assume that each processor can be either "good" or "faulty". Also assume that the processors can test each other. We consider how to use parallel testing rounds to identify the faulty processors, given an upper bound t on their number. We prove that 4 rounds are necessary and sufficient when 2/spl radic/(2n)/spl les/0. 03n (for n sufficiently large). Furthermore, at least 5 rounds are necessary when t/spl ges/0. 49n (for n sufficiently large), and 10 rounds are sufficient when t<0. 5n (for all n). (It is well known that no general solution is possible when t/spl ges/0. 5n).

SODA Conference 1995 Conference Paper

Greedy Dynamic Routing on Arrays

• Nabil Kahalé
• Frank Thomson Leighton

STOC Conference 1995 Conference Paper

Lower bounds for sorting networks

• Nabil Kahalé
• Frank Thomson Leighton
• Yuan Ma
• C. Greg Plaxton
• Torsten Suel
• Endre Szemerédi

STOC Conference 1994 Conference Paper

A spectral technique for coloring random 3-colorable graphs (preliminary version)

• Noga Alon
• Nabil Kahalé

FOCS Conference 1992 Conference Paper

On the Second Eigenvalue and Linear Expansion of Regular Graphs

• Nabil Kahalé

The authors investigate the relation between the second eigen-value and the linear expansion of regular graphs. The spectral method is the best currently known technique to prove lower bounds on the expansion. He improves this technique by showing that the expansion coefficient of linear-sized subsets of a k-regular graph G is at least k/2(1- square root max(0, 1-/sub lambda 1(G)2//sup 4k-4/))/sup -/, where lambda /sub 1/(G) is the second largest eigenvalue of the graph. In particular, the linear expansion of Ramanujan graphs, which have the property that the second largest eigenvalue is at most 2 square root k-1, is at least (k/2)/sup -/. This improves upon the best previously known lower bound of 3(k-2)/8. For any integer k such that k-1 is prime, he explicitly constructs an infinite family of k-regular graphs G/sub n/ on n vertices whose linear expansion is k/2 and such that lambda /sub 1/(G/sub n/) >

FOCS Conference 1991 Conference Paper

Better Expansion for Ramanujan Graphs

• Nabil Kahalé

The expansion properties of regular graphs are investigated. The best previously known expansion of subsets of linear size of explicit k-regular graphs is k/4. This bound is achieved by nonbipartite Ramanujan graphs of degree k=p+1, which have the property that all but the largest eigenvalue have absolute value at most 2 square root p. The expansion coefficient for linear subsets for nonbipartite Ramanujan graphs is improved to 3(k-2)/8. Other results are established, including improved results about random walks on expanders. >