Faster Pricing of Convertible Bonds (2008)
Jean-noël Dordain, Nabil Kahale, Arnaud Vinciguerra
Senior members of the research team at trading and risk management system specialist Sophis, discuss their latest pricing model for Convertibles We study the pricing of convertible bonds using...
Nabil Kahale, Tom Leighton, Yuan Ma, C. Greg Plaxton, Torsten Suel
7 We establish a lower bound of (1:12 \Gamma o(1)) n log n on the size of any n-input sorting network; this is the first lower bound that improves upon the trivial information-theoretic bound by more...
E. G. Coffman, Anja Feldmann, Nabil Kahale, Bjorn Poonen
We study call admission rates in a linear communication network with each call identified by an arrival time, duration, bandwidth requirement, and origin-destination pair. Network links all have the...
E. G. Coffman, Anja Feldmann, Nabil Kahale, Bjorn Poonen
We study call admission rates in a linear communication network with each call identified by an arrival time, duration, bandwidth requirement, and origin-destination pair. Network links all have the...
E. G. Coffman, Nabil Kahale, F. T. Leighton
We consider N processors communicating unidirectionally over a closed transmission channel, or ring. Each message is assembled into a fixed-length packet. Packets to be sent are generated at random...
Analytic crossing probabilities for certain barriers by Brownian motion (2007)
We calculate crossing probabilities and one-sided last exit time densities for a class of moving barriers on an interval $[0,T]$ via Schwartz distributions. We derive crossing probabilities and first...
Isoperimetric Inequalities and Eigenvalues (1997)
An upper bound is given on the minimum distance between i subsets of the same size of a regular graph in terms of the i-th largest eigenvalue in absolute value. This yields a bound on the diameter in...
Isoperimetric Inequalities and Eigenvalues (1997)
An upper bound is given on the minimum distance between i subsets of same size of a regular graph in terms of the i-th largest eigenvalue in absolute value. This yields a bound on the diameter in...
Isoperimetric Inequalities and Eigenvalues (1997)
An upper bound is given on the minimum distance between i subsets of same size of a regular graph in terms of the i-th largest eigenvalue in absolute value. This yields a bound on the diameter in...
Dynamic Global Packet Routing in Wireless Networks (1997)
We consider schemes for reuse-efficient packet access in wireless data networks. We show that computing the maximum ergodic packet arrival rate is NPhard. We give an upper bound on the maximum...
Bounds on the Chromatic Polynomial and on the Number of Acyclic Orientations of a Graph (1996)
Nabil Kahale, Leonard J. Schulman
An upper bound is given on the number of acyclic orientations of a graph, in terms of the spectrum of its Laplacian. It is shown that this improves upon the previously known bound, which depended on...
Bounds on the Chromatic Polynomial and on the Number of Acyclic Orientations of a Graph (1996)
Nabil Kahale, Leonard J. Schulman
An upper bound is given on the number of acyclic orientations of a graph, in terms of the spectrum of its Laplacian. It is shown that this improves upon the previously known bound, which depended on...
Processor-Ring Communication: A Tight Asymptotic Bound on Packet Waiting Times (1996)
E. G. Coffman, Nabil Kahale, F. T. Leighton
We consider N processors communicating unidirectionally over a closed transmission channel, or ring. Each message is assembled into a fixed-length packet. Packets to be sent are generated at random...
Fault diagnosis in a flash (1995)
Richard Beigel, William Hurwood, Nabil Kahale
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...
Greedy Dynamic Routing on Arrays (1995)
We study the problem of dynamic routing on arrays. We prove that a large class of greedy algorithms perform very well on average. In the dynamic case, when the arrival rate of packets in an N \Theta...
Eigenvalues and Expansion of Regular Graphs (1995)
The spectral method is the best currently known technique to prove lower bounds on expansion. Ramanujan graphs, which have asymptotically optimal second eigenvalue, are the best known explicit...
A Semidefinite Bound for Mixing Rates of Markov Chains (1995)
. We study the method of bounding the spectral gap of a reversible Markov chain by establishing canonical paths between the states. We provide natural examples where improved bounds can be obtained...
Lower Bounds for Sorting Networks (1995)
Nabil Kahale, Tom Leighton, Yuan Ma, C. Greg Plaxton, Torsten Suel, Endre Szemerédi
We establish a lower bound of (1:12 \Gamma o(1)) n log n on the size of any n-input sorting network; this is the first lower bound that improves upon the trivial information-theoretic bound by more...
A Semidefinite Bound for Mixing Rates of Markov Chains (1995)
. We study general geometric techniques for bounding the spectral gap of a reversible Markov chain. We show that the best bound obtainable using these techniques can be computed in polynomial time...
Approximating the Independence Number Via the Theta-Function (1995)
We describe an approximation algorithm for the independence number of a graph. If a graph on n vertices has an independence number n=k + m for some fixed integer k 3 and some m ? 0, the algorithm...
A semidefinite bound for mixing rates of Markov chains (1995)
We study the method of bounding the spectral gap of a reversible Markov chain by establishing canonical paths between the states. We provide examples where improved bounds can be obtained by allowing...
A spectral technique for coloring random 3-colorable graphs (1994)
Abstract. Let G3n,p,3 be a random 3-colorable graph on a set of 3n vertices generated as follows. First, split the vertices arbitrarily into three equal color classes, and then choose every pair of...
A spectral technique for coloring random 3-colorable graphs (1994)
Abstract. Let G 3n,p,3 be a random 3-colorable graph on a set of 3n vertices generated as follows. First, split the vertices arbitrarily into three equal color classes, and then choose every pair of...
Approximating the Independence Number Via the Theta-Function (1994)
Abstract We study the relationship between the independence number of a graph and its semi-definite relaxation, the Lov'asz `-function. We deduce an improved approximation algorithm for the...
Fault Diagnosis in a Flash (1994)
Richard Beigel, William Hurwood, Nabil Kahale
. We consider the fault diagnosis problem: how to use parallel testing rounds to identify which processors in a set are faulty. We prove that 4 rounds suffice when 3% or less of the processors are...
A Spectral Technique for Coloring Random 3-Colorable Graphs (1994)
Let G 3n;p;3 be a random 3-colorable graph on a set of 3n vertices generated as follows. First, split the vertices arbitrarily into three equal color classes and then choose every pair of vertices of...
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1993.
Expander graphs /--by Nabil Kahale. (1993)
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1993.
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1993.
On Reducing the Cut Ratio to the Multicut Problem (1993)
We compare two multicommodity flow problems, the maximum sum of flow, and the maximum concurrent flow. We show that, for a given graph and a given set of k commodities with specified demands, if the...
Large deviation bounds for Markov chains
We study the fraction of time that a Markov chain spends in a given subset of states. We give an exponential bound on the probability that it exceeds its expectation by a constant factor. Our bound...