Frank Thomson Leighton

Publication Activity (10 Years)

Years Active: 1981-2010
Publications (10 Years): 0

Publications

Frank Thomson Leighton, Ankur Moitra
Extensions and limits to vertex sparsification. STOC (2010)
William Aiello, Frank Thomson Leighton
Hamming Codes, Hypercube Embeddings, and Fault Tolerance. SIAM J. Comput. 37 (3) (2007)
Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, Frank Thomson Leighton, Harald Räcke
New lower bounds for oblivious routing in undirected graphs. SODA (2006)
Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, Frank Thomson Leighton
Improved lower and upper bounds for universal TSP in planar metrics. SODA (2006)
Frank Thomson Leighton
The Challenges of Delivering Content and Applications on the Internet. NSDI (2005)
Frank Thomson Leighton
The Challenges of Delivering Content and Applications on the Internet. RIDE (2004)
Frank Thomson Leighton
JACM 1991-1997. J. ACM 50 (1) (2003)
Robert D. Kleinberg, Frank Thomson Leighton
The Value of Knowing a Demand Curve: Bounds on Regret for Online Posted-Price Auctions. FOCS (2003)
Markus Jakobsson, Frank Thomson Leighton, Silvio Micali, Michael Szydlo
Fractal Merkle Tree Representation and Traversal. CT-RSA (2003)
Robert D. Kleinberg, Frank Thomson Leighton
Consistent load balancing via spread minimization. STOC (2003)
Frank Thomson Leighton
The Challenges of Delivering Content on the Internet. PODS (2001)
Fan R. K. Chung, Ronald L. Graham, Frank Thomson Leighton
Guessing secrets. SODA (2001)
Fan R. K. Chung, Ronald L. Graham, Frank Thomson Leighton
Guessing Secrets. Electron. J. Comb. 8 (1) (2001)
Matthew Andrews, Baruch Awerbuch, Antonio Fernández, Frank Thomson Leighton, Zhiyong Liu, Jon M. Kleinberg
Universal-stability results and performance bounds for greedy contention-resolution protocols. J. ACM 48 (1) (2001)
Frank Thomson Leighton, Chi-Jen Lu, Satish Rao, Aravind Srinivasan
New Algorithmic Aspects of the Local Lemma with Applications to Routing and Partitioning. SIAM J. Comput. 31 (2) (2001)
Micah Adler, Frank Thomson Leighton
Compression Using Efficient Multicasting. J. Comput. Syst. Sci. 63 (1) (2001)
Frank Thomson Leighton
The Challenges of Delivering Content on the Internet. WADS (2001)
Frank Thomson Leighton
The Challenges of Delivering Content on the Internet. NCA (2001)
Micah Adler, Frank Thomson Leighton
Compression using efficient multicasting. STOC (2000)
Matthew Andrews, Antonio Fernández, Mor Harchol-Balter, Frank Thomson Leighton, Lisa Zhang
(Distance + 1/Session Rate). SIAM J. Comput. 30 (5) (2000)
Sandeep N. Bhatt, David S. Greenberg, Frank Thomson Leighton, Pangfeng Liu
Tight Bounds for On-Line Tree Embeddings. SIAM J. Comput. 29 (2) (1999)
Bonnie Berger, Jon M. Kleinberg, Frank Thomson Leighton
Reconstructing a Three-Dimensional Model with Arbitrary Errors. J. ACM 46 (2) (1999)
Mor Harchol-Balter, Frank Thomson Leighton, Daniel Lewin
Resource Discovery in Distributed Networks. PODC (1999)
Matthew Andrews, Frank Thomson Leighton, Panagiotis Takis Metaxas, Lisa Zhang
Automatic Methods for Hiding Latency in Parallel and Distributed Computation. SIAM J. Comput. 29 (2) (1999)
Jin Suk Kim, Eric Lehman, Frank Thomson Leighton
Oblivious Deadlock-Free Routing in a Faulty Hypercube. IPPS/SPDP (1999)
Frank Thomson Leighton, Satish Rao, Aravind Srinivasan
New Algorithmic Aspects of the Local Lemma with Applications to Routing and Partitioning. SODA (1999)
Bhaskar Ghosh, Frank Thomson Leighton, Bruce M. Maggs, S. Muthukrishnan, C. Greg Plaxton, Rajmohan Rajaraman, Andréa W. Richa, Robert Endre Tarjan, David Zuckerman
Tight Analyses of Two Local Load Balancing Algorithms. SIAM J. Comput. 29 (1) (1999)
Stephen Guattery, Frank Thomson Leighton, Gary L. Miller
The Path Resistance Method For Bounding The Smallest Nontrivial Eigenvalue Of A Laplacian. Comb. Probab. Comput. 8 (5) (1999)
Frank Thomson Leighton, Yuan Ma
Tight Bounds on the Size of Fault-Tolerant Merging and Sorting Networks with Destructive Faults. SIAM J. Comput. 29 (1) (1999)
Frank Thomson Leighton, Eric J. Schwabe
Efficient Algorithms for Dynamic Allocation of Distributed Memo. Algorithmica 24 (2) (1999)
Frank Thomson Leighton, Satish Rao
Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM 46 (6) (1999)
Frank Thomson Leighton, Bruce M. Maggs, Andréa W. Richa
Fast Algorithms for Finding O(Congestion + Dilation) Packet Routing Schedules. Comb. 19 (3) (1999)
Frank Thomson Leighton, Bruce M. Maggs, Ramesh K. Sitaraman
On the Fault Tolerance of Some Popular Bounded-Degree Networks. SIAM J. Comput. 27 (5) (1998)
Frank Thomson Leighton, C. Greg Plaxton
Hypercubic Sorting Networks. SIAM J. Comput. 27 (1) (1998)
Bonnie Berger, Frank Thomson Leighton
Protein Folding in the Hydrophobic-Hydrophilic(HP) Model is NP-Complete. J. Comput. Biol. 5 (1) (1998)
Bonnie Berger, Frank Thomson Leighton
) is NP-complete. RECOMB (1998)
Nabil Kahalé, Frank Thomson Leighton
Greedy Dynamic Routing on Arrays. J. Algorithms 29 (2) (1998)
Edward G. Coffman Jr., Nabil Kahalé, Frank Thomson Leighton
Processor-Ring Communication: A Tight Asymptotic Bound on Packet Waiting Times. SIAM J. Comput. 27 (5) (1998)
Frank Thomson Leighton, Yuan Ma, C. Greg Plaxton
Breaking the Theta (n log² n) Barrier for Sorting with Faults. J. Comput. Syst. Sci. 54 (2) (1997)
David R. Karger, Eric Lehman, Frank Thomson Leighton, Rina Panigrahy, Matthew S. Levine, Daniel Lewin
Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web. STOC (1997)
Daniel J. Kleitman, Frank Thomson Leighton, Yuan Ma
On the Design of Reliable Boolean Circuits That Contain Partially Unreliable Gates. J. Comput. Syst. Sci. 55 (3) (1997)
Leslie Ann Goldberg, Mark Jerrum, Frank Thomson Leighton, Satish Rao
Doubly Logarithmic Communication Algorithms for Optical-Communication Parallel Computers. SIAM J. Comput. 26 (4) (1997)
Frank Thomson Leighton, Yuan Ma, Torsten Suel
On Probabilistic Networks for Selection, Merging, and Sorting. Theory Comput. Syst. 30 (6) (1997)
Ingemar J. Cox, Joe Kilian, Frank Thomson Leighton, Talal Shamoon
Secure spread spectrum watermarking for multimedia. IEEE Trans. Image Process. 6 (12) (1997)
Stephen Guattery, Frank Thomson Leighton, Gary L. Miller
of a Laplacian. SODA (1997)
Sandeep N. Bhatt, Fan R. K. Chung, Frank Thomson Leighton, Arnold L. Rosenberg
An Optimal Strategies for Cycle-Stealing in Networks of Workstations. IEEE Trans. Computers 46 (5) (1997)
Richard R. Koch, Frank Thomson Leighton, Bruce M. Maggs, Satish Rao, Arnold L. Rosenberg, Eric J. Schwabe
Work-preserving emulations of fixed-connection networks. J. ACM 44 (1) (1997)
Matthew Andrews, Antonio Fernández, Mor Harchol-Balter, Frank Thomson Leighton, Lisa Zhang
General Dynamic Routing with Per-Packet Delay Guarantees of O(distance + 1 / session rate). FOCS (1997)
Johan Håstad, Frank Thomson Leighton, Brian Rogoff
Analysis of Backoff Protocols for Multiple Access Channels. SIAM J. Comput. 25 (4) (1996)
Bonnie Berger, Jon M. Kleinberg, Frank Thomson Leighton
Reconstructing a Three-Dimensional Model with Arbitrary Errors. STOC (1996)
Sandeep N. Bhatt, Fan R. K. Chung, Frank Thomson Leighton, Arnold L. Rosenberg
Scheduling Tree-Dags Using FIFO Queues: A Control-Memory Trade-Off. J. Parallel Distributed Comput. 33 (1) (1996)
Matthew Andrews, Frank Thomson Leighton, Panagiotis Takis Metaxas, Lisa Zhang
Automatic Methods for Hiding Latency in High Bandwidth Networks (Extended Abstract). STOC (1996)
Sanjeev Arora, Frank Thomson Leighton, Bruce M. Maggs
On-Line Algorithms for Path Selection in a Nonblocking Network. SIAM J. Comput. 25 (3) (1996)
Matthew Andrews, Frank Thomson Leighton, Panagiotis Takis Metaxas, Lisa Zhang
Improved Methods for Hiding Latency in High Bandwidth Networks (Extended Abstract). SPAA (1996)
Baruch Awerbuch, Yossi Azar, Amos Fiat, Frank Thomson Leighton
Making Commitments in the Face of Uncertainty: How to Pick a Winner Almost Every Time (Extended Abstract). STOC (1996)
Donald D. Chinn, Frank Thomson Leighton, Martin Tompa
Minimal Adaptive Routing on the Mesh with Bounded Queue Size. J. Parallel Distributed Comput. 34 (2) (1996)
Matthew Andrews, Baruch Awerbuch, Antonio Fernández, Jon M. Kleinberg, Frank Thomson Leighton, Zhiyong Liu
Universal Stability Results for Greedy Contention-Resolution Protocols. FOCS (1996)
Sandeep N. Bhatt, Fan R. K. Chung, Jia-Wei Hong, Frank Thomson Leighton, Bojana Obrenic, Arnold L. Rosenberg, Eric J. Schwabe
Optimal Emulations by Butterfly-Like Networks. J. ACM 43 (2) (1996)
Frank Thomson Leighton
How to Pick a Winner Almost Every Time: Provably-Good Algorithms for Decision Making in the Face of Uncertainty. ISTCS (1996)
Ingemar J. Cox, Joe Kilian, Frank Thomson Leighton, Talal Shamoon
A Secure, Robust Watermark for Multimedia. Information Hiding (1996)
Bonnie Berger, Martin L. Brady, Donna J. Brown, Frank Thomson Leighton
Nearly Optimal Algorithms and Bounds for Multilayer Channel Routing. J. ACM 42 (2) (1995)
Frank Thomson Leighton, Bruce M. Maggs
Fast algorithms for finding O(congestion+dilation) packet routing schedules. HICSS (2) (1995)
Frank Thomson Leighton, Fillia Makedon, Ioannis G. Tollis
A 2n-2 Step Algorithm for Routing in an n*n Array with Constant-Size Queues. Algorithmica 14 (4) (1995)
Sandeep N. Bhatt, Fan R. K. Chung, Frank Thomson Leighton, Arnold L. Rosenberg
Salvage-Embeddings of Complete Trees. SIAM J. Discret. Math. 8 (4) (1995)
Frank Thomson Leighton, Fillia Makedon, Serge A. Plotkin, Clifford Stein, Éva Tardos, Spyros Tragoudas
Fast Approximation Algorithms for Multicommodity Flow Problems. J. Comput. Syst. Sci. 50 (2) (1995)
Bhaskar Ghosh, Frank Thomson Leighton, Bruce M. Maggs, S. Muthukrishnan, C. Greg Plaxton, Rajmohan Rajaraman, Andréa W. Richa, Robert Endre Tarjan, David Zuckerman
Tight analyses of two local load balancing algorithms. STOC (1995)
Nabil Kahalé, Frank Thomson Leighton
Greedy Dynamic Routing on Arrays. SODA (1995)
Frank Thomson Leighton, Yuan Ma, Torsten Suel
On Probabilistic Networks for Selection, Merging, and Sorting. SPAA (1995)
Andrew Chou, Jeremy R. Cooperstock, Ran El-Yaniv, Michael Klugerman, Frank Thomson Leighton
The Statistical Adversary Allows Optimal Money-Making Trading Strategies. SODA (1995)
Nabil Kahalé, Frank Thomson Leighton, Yuan Ma, C. Greg Plaxton, Torsten Suel, Endre Szemerédi
Lower bounds for sorting networks. STOC (1995)
Joe Kilian, Frank Thomson Leighton
Fair Cryptosystems, Revisited: A Rigorous Approach to Key-Escrow (Extended Abstract). CRYPTO (1995)
Baruch Awerbuch, Rainer Gawlick, Frank Thomson Leighton, Yuval Rabani
On-line Admission Control and Circuit Routing for High Performance Computing and Communication FOCS (1994)
Frederic T. Chong, Eric A. Brewer, Frank Thomson Leighton, Thomas F. Knight Jr.
Building a better butterfly: the multiplexed metabutterfly. ISPAN (1994)
Daniel J. Kleitman, Frank Thomson Leighton, Yuan Ma
On the Design of Reliable Boolean Circuits that Contain Partially Unreliable Gates FOCS (1994)
Keith Nabors, F. T. Korsmeyer, Frank Thomson Leighton, Jacob White
Preconditioned, Adaptive, Multipole-Accelerated Iterative Methods for Three-Dimensional First-Kind Integral Equations of Potential Theory. SIAM J. Sci. Comput. 15 (3) (1994)
Donald D. Chinn, Frank Thomson Leighton, Martin Tompa
Minimal Adaptive Routing on the Mesh with Bounded Queue Size. SPAA (1994)
Frank Thomson Leighton
-1 Lower Bound for Two-Layer Knock-Knee Channel Routing. SIAM J. Discret. Math. 7 (2) (1994)
Frederic T. Chong, Eric A. Brewer, Frank Thomson Leighton, Thomas F. Knight Jr.
Packaging and Multiplexing of Hierarchical Scalable Expanders. PCRCW (1994)
Frank Thomson Leighton
Methods for Message Routing in Parallel Machines. Theor. Comput. Sci. 128 (1&2) (1994)
Frank Thomson Leighton, Bruce M. Maggs, Abhiram G. Ranade, Satish Rao
Randomized Routing and Sorting on Fixed-Connection Networks. J. Algorithms 17 (1) (1994)
Sandeep N. Bhatt, Fan R. K. Chung, Frank Thomson Leighton, Arnold L. Rosenberg
Scheduling Trees using FIFO Queues: A Control-Memory Tradeoff. SPAA (1994)
Frank Thomson Leighton, Bruce M. Maggs, Satish Rao
(Congestion + Dilation) Steps. Comb. 14 (2) (1994)
Baruch Awerbuch, Frank Thomson Leighton
Multicommodity Flows: A Survey of Recent Research. ISAAC (1993)
Frank Thomson Leighton, Silvio Micali
Secret-Key Agreement without Public-Key Cryptography. CRYPTO (1993)
Leslie Ann Goldberg, Mark Jerrum, Frank Thomson Leighton, Satish Rao
A Doubly Logarithmic Communication Algorithm for the Completely Connected Optical Communication Parallel Computer. SPAA (1993)
Frank Thomson Leighton, Yuan Ma
Tight Bounds on the Size of Fault-Tolerant Merging and Sorting Networks With Destructive Faults. SPAA (1993)
Frank Thomson Leighton, Yuan Ma
Breaking the Theta(n log ^2 n) Barrier for Sorting with Faults (Extended Abstract) FOCS (1993)
Michael Formann, Torben Hagerup, James Haralambides, Michael Kaufmann, Frank Thomson Leighton, Antonios Symvonis, Emo Welzl, Gerhard J. Woeginger
Drawing Graphs in the Plane with High Resolution. SIAM J. Comput. 22 (5) (1993)
Baruch Awerbuch, Frank Thomson Leighton
A Simple Local-Control Approximation Algorithm for Multicommodity Flow FOCS (1993)
Frank Thomson Leighton, Bruce M. Maggs
The Role of Randomness in the Design of Interconnection Networks. IFIP Congress (1) (1992)
Lenwood S. Heath, Frank Thomson Leighton, Arnold L. Rosenberg
Comparing Queues and Stacks as Mechanisms for Laying out Graphs. SIAM J. Discret. Math. 5 (3) (1992)
Frank Thomson Leighton, Bruce M. Maggs, Ramesh K. Sitaraman
On the Fault Tolerance of Some Popular Bounded-Degree Networks FOCS (1992)
Maria M. Klawe, Frank Thomson Leighton
A Tight Lower Bound on the Size of Planar Permutation Networks. SIAM J. Discret. Math. 5 (4) (1992)
Sandeep N. Bhatt, Fan R. K. Chung, Frank Thomson Leighton, Arnold L. Rosenberg
Efficient Embeddings of Trees in Hypercubes. SIAM J. Comput. 21 (1) (1992)
Frank Thomson Leighton
Methods for Message Routing in Parallel Machines STOC (1992)
Frank Thomson Leighton, Bruce M. Maggs
Fast Algorithms for Routing Around Faults in Multibutterflies and Randomly-Wired Splitter Networks. IEEE Trans. Computers 41 (5) (1992)
Dinesh Bhatia, Frank Thomson Leighton, Fillia Makedon, Carolyn Haibt Norton
Improved Algorithms for Routing on Two-Dimensional Grids. WG (1992)
Sandeep N. Bhatt, Fan R. K. Chung, Frank Thomson Leighton, Arnold L. Rosenberg
Tolerating Faults in Synchronization Networks. CONPAR (1992)
Frank Thomson Leighton, Bruce M. Maggs
The Role of Randomness in the Design of Interconnection Networks. Heinz Nixdorf Symposium (1992)
Frank Thomson Leighton, Mark Newman, Abhiram G. Ranade, Eric J. Schwabe
Dynamic Tree Embeddings in Butterflies and Hypercubes. SIAM J. Comput. 21 (4) (1992)

Frank Thomson Leighton.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Frank Thomson Leighton