Frank Thomson Leighton

Affiliations:
  • MIT, Cambridge, US


According to our database1, Frank Thomson Leighton authored at least 156 papers between 1981 and 2014.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Awards

ACM Fellow

ACM Fellow 2018, "For his leadership in the establishment of content delivery networks, and his contributions to algorithm design".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2014
Correction: Basic Network Creation Games.
SIAM J. Discret. Math., 2014

2013
Basic Network Creation Games.
SIAM J. Discret. Math., 2013

2010
Some Results on Greedy Embeddings in Metric Spaces.
Discret. Comput. Geom., 2010

Extensions and limits to vertex sparsification.
Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Vertex Sparsifiers and Abstract Rounding Algorithms.
Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

2009
Improving performance on the internet.
Commun. ACM, 2009

2008
Hat Guessing Games.
SIAM J. Discret. Math., 2008

2007
Oblivious routing on node-capacitated and directed graphs.
ACM Trans. Algorithms, 2007

Localized Client-Server Load Balancing without Global Information.
SIAM J. Comput., 2007

Hamming Codes, Hypercube Embeddings, and Fault Tolerance.
SIAM J. Comput., 2007

Semi-oblivious routing: lower bounds.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

The Akamai approach to achieving performance and reliability on the internet.
Proceedings of the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing, 2007

2006
On the max-flow min-cut ratio for directed multicommodity flows.
Theor. Comput. Sci., 2006

Semi-oblivious routing.
Proceedings of the SPAA 2006: Proceedings of the 18th Annual ACM Symposium on Parallelism in Algorithms and Architectures, Cambridge, Massachusetts, USA, July 30, 2006

New lower bounds for oblivious routing in undirected graphs.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Improved lower and upper bounds for universal TSP in planar metrics.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

2005
Oblivious routing in directed graphs with random demands.
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Online client-server load balancing without global information.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

The Challenges of Delivering Content and Applications on the Internet.
Proceedings of the 2nd Symposium on Networked Systems Design and Implementation (NSDI 2005), 2005

2003
JACM 1991-1997.
J. ACM, 2003

Consistent load balancing via spread minimization.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

The Value of Knowing a Demand Curve: Bounds on Regret for Online Posted-Price Auctions.
Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

Fractal Merkle Tree Representation and Traversal.
Proceedings of the Topics in Cryptology, 2003

2001
New Algorithmic Aspects of the Local Lemma with Applications to Routing and Partitioning.
SIAM J. Comput., 2001

Compression Using Efficient Multicasting.
J. Comput. Syst. Sci., 2001

Universal-stability results and performance bounds for greedy contention-resolution protocols.
J. ACM, 2001

Containment Properties of Product and Power Graphs.
Electron. Notes Discret. Math., 2001

Guessing Secrets.
Electron. J. Comb., 2001

The Challenges of Delivering Content on the Internet.
Proceedings of the IEEE International Symposium on Network Computing and Applications (NCA 2001), 2001

2000
General Dynamic Routing with Per-Packet Delay Guarantees of <i>O</i>(Distance + 1/Session Rate).
SIAM J. Comput., 2000

1999
Tight Bounds on the Size of Fault-Tolerant Merging and Sorting Networks with Destructive Faults.
SIAM J. Comput., 1999

Tight Analyses of Two Local Load Balancing Algorithms.
SIAM J. Comput., 1999

Tight Bounds for On-Line Tree Embeddings.
SIAM J. Comput., 1999

Automatic Methods for Hiding Latency in Parallel and Distributed Computation.
SIAM J. Comput., 1999

Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms.
J. ACM, 1999

Reconstructing a Three-Dimensional Model with Arbitrary Errors.
J. ACM, 1999

The Path Resistance Method For Bounding The Smallest Nontrivial Eigenvalue Of A Laplacian.
Comb. Probab. Comput., 1999

Fast Algorithms for Finding O(Congestion + Dilation) Packet Routing Schedules.
Comb., 1999

Efficient Algorithms for Dynamic Allocation of Distributed Memo.
Algorithmica, 1999

New Algorithmic Aspects of the Local Lemma with Applications to Routing and Partitioning.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Resource Discovery in Distributed Networks.
Proceedings of the Eighteenth Annual ACM Symposium on Principles of Distributed Computing, 1999

Oblivious Deadlock-Free Routing in a Faulty Hypercube.
Proceedings of the 13th International Parallel Processing Symposium / 10th Symposium on Parallel and Distributed Processing (IPPS / SPDP '99), 1999

1998
Hypercubic Sorting Networks.
SIAM J. Comput., 1998

On the Fault Tolerance of Some Popular Bounded-Degree Networks.
SIAM J. Comput., 1998

Processor-Ring Communication: A Tight Asymptotic Bound on Packet Waiting Times.
SIAM J. Comput., 1998

Protein Folding in the Hydrophobic-Hydrophilic(HP) Model is NP-Complete.
J. Comput. Biol., 1998

Greedy Dynamic Routing on Arrays.
J. Algorithms, 1998

Protein folding in the hydrophobic-hydrophilic (<i>HP</i>) is NP-complete.
Proceedings of the Second Annual International Conference on Research in Computational Molecular Biology, 1998

Multicommodity Flow and Circuit Switching.
Proceedings of the Thirty-First Annual Hawaii International Conference on System Sciences, 1998

1997
Secure spread spectrum watermarking for multimedia.
IEEE Trans. Image Process., 1997

An Optimal Strategies for Cycle-Stealing in Networks of Workstations.
IEEE Trans. Computers, 1997

Doubly Logarithmic Communication Algorithms for Optical-Communication Parallel Computers.
SIAM J. Comput., 1997

On Probabilistic Networks for Selection, Merging, and Sorting.
Theory Comput. Syst., 1997

Breaking the Theta (n log² n) Barrier for Sorting with Faults.
J. Comput. Syst. Sci., 1997

On the Design of Reliable Boolean Circuits That Contain Partially Unreliable Gates.
J. Comput. Syst. Sci., 1997

Work-preserving emulations of fixed-connection networks.
J. ACM, 1997

Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web.
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

The Path Resistance Method for Bounding lambda<sub>2</sub> of a Laplacian.
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

General Dynamic Routing with Per-Packet Delay Guarantees of O(distance + 1 / session rate).
Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

1996
Analysis of Backoff Protocols for Multiple Access Channels.
SIAM J. Comput., 1996

On-Line Algorithms for Path Selection in a Nonblocking Network.
SIAM J. Comput., 1996

Minimal Adaptive Routing on the Mesh with Bounded Queue Size.
J. Parallel Distributed Comput., 1996

Scheduling Tree-Dags Using FIFO Queues: A Control-Memory Trade-Off.
J. Parallel Distributed Comput., 1996

Optimal Emulations by Butterfly-Like Networks.
J. ACM, 1996

Making Commitments in the Face of Uncertainty: How to Pick a Winner Almost Every Time (Extended Abstract).
Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

Automatic Methods for Hiding Latency in High Bandwidth Networks (Extended Abstract).
Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

Improved Methods for Hiding Latency in High Bandwidth Networks (Extended Abstract).
Proceedings of the 8th Annual ACM Symposium on Parallel Algorithms and Architectures, 1996

How to Pick a Winner Almost Every Time: Provably-Good Algorithms for Decision Making in the Face of Uncertainty.
Proceedings of the Fourth Israel Symposium on Theory of Computing and Systems, 1996

A Secure, Robust Watermark for Multimedia.
Proceedings of the Information Hiding, First International Workshop, Cambridge, UK, May 30, 1996

Secure spread spectrum watermarking for images, audio and video.
Proceedings of the Proceedings 1996 International Conference on Image Processing, 1996

Universal Stability Results for Greedy Contention-Resolution Protocols.
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

1995
Salvage-Embeddings of Complete Trees.
SIAM J. Discret. Math., 1995

Fast Approximation Algorithms for Multicommodity Flow Problems.
J. Comput. Syst. Sci., 1995

Nearly Optimal Algorithms and Bounds for Multilayer Channel Routing.
J. ACM, 1995

A 2n-2 Step Algorithm for Routing in an n*n Array with Constant-Size Queues.
Algorithmica, 1995

Lower bounds for sorting networks.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

The Statistical Adversary Allows Optimal Money-Making Trading Strategies.
Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 1995

Fast algorithms for finding O(congestion+dilation) packet routing schedules.
Proceedings of the 28th Annual Hawaii International Conference on System Sciences (HICSS-28), 1995

Fair Cryptosystems, Revisited: A Rigorous Approach to Key-Escrow (Extended Abstract).
Proceedings of the Advances in Cryptology, 1995

1994
Methods for Message Routing in Parallel Machines.
Theor. Comput. Sci., 1994

Preconditioned, Adaptive, Multipole-Accelerated Iterative Methods for Three-Dimensional First-Kind Integral Equations of Potential Theory.
SIAM J. Sci. Comput., 1994

A 2<i>d</i>-1 Lower Bound for Two-Layer Knock-Knee Channel Routing.
SIAM J. Discret. Math., 1994

Randomized Routing and Sorting on Fixed-Connection Networks.
J. Algorithms, 1994

Packet Routing and Job-Shop Scheduling in <i>O</i>(Congestion + Dilation) Steps.
Comb., 1994

Scalable expanders: exploiting hierarchical random wiring.
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

Improved approximation algorithms for the multi-commodity flow problem and local competitive routing in dynamic networks.
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

Scheduling Trees using FIFO Queues: A Control-Memory Tradeoff.
Proceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, 1994

Packaging and Multiplexing of Hierarchical Scalable Expanders.
Proceedings of the Parallel Computer Routing and Communication, 1994

Building a better butterfly: the multiplexed metabutterfly.
Proceedings of the International Symposium on Parallel Architectures, 1994

On-line Admission Control and Circuit Routing for High Performance Computing and Communication
Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

1993
Drawing Graphs in the Plane with High Resolution.
SIAM J. Comput., 1993

A Doubly Logarithmic Communication Algorithm for the Completely Connected Optical Communication Parallel Computer.
Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, 1993

Multicommodity Flows: A Survey of Recent Research.
Proceedings of the Algorithms and Computation, 4th International Symposium, 1993

Breaking the Theta(n log ^2 n) Barrier for Sorting with Faults (Extended Abstract)
Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

A Simple Local-Control Approximation Algorithm for Multicommodity Flow
Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

Secret-Key Agreement without Public-Key Cryptography.
Proceedings of the Advances in Cryptology, 1993

1992
Fast Algorithms for Routing Around Faults in Multibutterflies and Randomly-Wired Splitter Networks.
IEEE Trans. Computers, 1992

A Tight Lower Bound on the Size of Planar Permutation Networks.
SIAM J. Discret. Math., 1992

Comparing Queues and Stacks as Mechanisms for Laying out Graphs.
SIAM J. Discret. Math., 1992

Dynamic Tree Embeddings in Butterflies and Hypercubes.
SIAM J. Comput., 1992

Efficient Embeddings of Trees in Hypercubes.
SIAM J. Comput., 1992

Improved Algorithms for Routing on Two-Dimensional Grids.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1992

The Role of Randomness in the Design of Interconnection Networks.
Proceedings of the Algorithms, Software, Architecture, 1992

Tolerating Faults in Synchronization Networks.
Proceedings of the Parallel Processing: CONPAR 92, 1992

1991
Selected Papers from the Symposium on Parallel Algorithms and Architectures.
SIGARCH Comput. Archit. News, 1991

Fast Algorithms for Bit-Serial Routing on a Hypercube.
Math. Syst. Theory, 1991

Letter from the Editor.
J. ACM, 1991

Editors' Introduction.
Algorithmica, 1991

Coding Theory, Hypercube Embeddings, and Fault Tolerance.
Proceedings of the 3rd Annual ACM Symposium on Parallel Algorithms and Architectures, 1991

Efficient Algorithms for Dynamic Allocation of Distributed Memory
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

Highly Fault-Tolerant Sorting Circuits
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

1990
Generalized Planar Matching.
J. Algorithms, 1990

A Tight Lower Bound for the Train Reversal Problem.
Inf. Process. Lett., 1990

On-line Algorithms for Path Selection in a Nonblocking Network (Extended Abstract)
Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

Solving Query-Retrieval Problems by Compacting Voronoi Diagrams (Extended Abstract)
Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

Average Case Analysis of Greedy Routing algorithms on Arrays.
Proceedings of the 2nd Annual ACM Symposium on Parallel Algorithms and Architectures, 1990

First-Fit Storage of Linear Lists: Tight Probabilistic Bounds on Wasted Space.
Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, 1990

Efficient Reconfiguration of WSI Arrays.
Proceedings of the First International Conference on Systems Integration, 1990

Empirical evaluation of randomly-wire multistage networks.
Proceedings of the 1990 IEEE International Conference on Computer Design: VLSI in Computers and Processors, 1990

A (fairly) Simple Circuit that (usually) Sorts
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

Asymptotically Tight Bounds for Computing with Faulty Arrays of Processors (Extended Abstract)
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

1989
Universal Graphs for Bounded-Degree Trees and Planar Graphs.
SIAM J. Discret. Math., 1989

A Provably Efficient Algorithm for Dynamic Storage Allocation.
J. Comput. Syst. Sci., 1989

Tight bounds for minimax grid matching wit applications to the average case analysis of algorithms.
Comb., 1989

A Randomized Data Structure for Ordered Sets.
Adv. Comput. Res., 1989

Work-Preserving Emulations of Fixed-Connection Networks (Extended Abstract)
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

Fast Computation Using Faulty Hypercubes (Extended Abstract)
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

A 2<i>n</i>-2 Step Algorithm for Routing in an <i>nxn</i> Array with Constant Size Queues.
Proceedings of the ACM Symposium on Parallel Algorithms and Architectures, 1989

Expanders Might Be Practical: Fast Algorithms for Routing Around Faults on Multibutterflies
Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

Improving the Performance of the Kernighan-Lin and Simulated Annealing Graph Bisection Algorithms.
Proceedings of the 26th ACM/IEEE Design Automation Conference, 1989

1988
Optimal Simulations by Butterfly Networks (Preliminary Version)
Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988

An Approximate Max-Flow Min-Cut Theorem for Uniform Multicommodity Flow Problems with Applications to Approximation Algorithms
Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

Universal Packet Routing Algorithms (Extended Abstract)
Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

Applying the Classification Theorem for Finite Simple Groups to Minimize Pin Count in Uniform Permutation Architectures.
Proceedings of the VLSI Algorithms and Architectures, 3rd Aegean Workshop on Computing, 1988

1987
Graph bisection algorithms with good average case behavior.
Comb., 1987

Global Wire Routing in Two-Dimensional Arrays.
Algorithmica, 1987

Analysis of Backoff Protocols for Multiple Access Channels (Extended Abstract)
Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987

Reconfiguring a Hypercube in the Presence of Faults (Extended Abstract)
Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987

1986
Estimating a probability using finite memory.
IEEE Trans. Inf. Theory, 1986

Three-Dimensional Circuit Layouts.
SIAM J. Comput., 1986

Tight Bounds for Minimax Grid Matching, With Applications to the Average Case Analysis of Algorithms
Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986

Optimal Simulations of Tree Machines (Preliminary Version)
Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986

1985
Wafer-Scale Integration of Systolic Arrays.
IEEE Trans. Computers, 1985

Tight Bounds on the Complexity of Parallel Sorting.
IEEE Trans. Computers, 1985

1984
New Lower Bound Techniques for VLSI.
Math. Syst. Theory, 1984

A Framework for Solving VLSI Graph Layout Problems.
J. Comput. Syst. Sci., 1984

Some Unexpected Expected Behavior Results for Bin Packing
Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30, 1984

1983
An Asymptotically Optimal Layout for the Shuffle-Exchange Graph.
J. Comput. Syst. Sci., 1983

Parallel Computation Using Meshes of Trees.
Proceedings of the WG '83, 1983

An Approximation Algorithm for Manhattan Routing (Extended Abstract)
Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983

Global Wire Routing in Two-Dimensional Arrays (Extended Abstract)
Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983

Estimating a Probability Using Finite Memory (Extended Abstract).
Proceedings of the Fundamentals of Computation Theory, 1983

1982
Finite common coverings of graphs.
J. Comb. Theory, Ser. B, 1982

A Layout Strategy for VLSI which Is Provably Good (Extended Abstract)
Proceedings of the 14th Annual ACM Symposium on Theory of Computing, 1982

Wafer-Scale Integration of Systolic Arrays (Extended Abstract)
Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, 1982

1981
New Layouts for the Shuffle-Exchange Graph (Extended Abstract)
Proceedings of the 13th Annual ACM Symposium on Theory of Computing, 1981


  Loading...