Frank Thomson Leighton

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

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

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

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

2010
Some Results on Greedy Embeddings in Metric Spaces.
Discrete & Computational Geometry, 2010

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

Basic network creation games.
Proceedings of the SPAA 2010: Proceedings of the 22nd Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2010

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

2009
Hat Guessing Games.
SIAM Review, 2009

Improving performance on the internet.
Commun. ACM, 2009

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

Improving Performance on the Internet.
ACM Queue, 2008

Some Results on Greedy Embeddings in Metric Spaces.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 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

Containment properties of product and power graphs.
Discrete Applied Mathematics, 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

Oblivious routing on node-capacitated and directed graphs.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 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

2004
The Challenges of Delivering Content and Applications on the Internet.
Proceedings of the 14th International Workshop on Research Issues in Data Engineering (RIDE-WS-ECEG 2004), 2004

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

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

Containment Properties of Product and Power Graphs.
Electronic Notes in Discrete Mathematics, 2001

The Challenges of Delivering Content on the Internet.
Proceedings of the Algorithms and Data Structures, 7th International Workshop, 2001

Guessing secrets.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

The Challenges of Delivering Content on the Internet.
Proceedings of the Twentieth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 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 O(Distance + 1/Session Rate).
SIAM J. Comput., 2000

Compression using efficient multicasting.
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

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

The Path Resistance Method For Bounding The Smallest Nontrivial Eigenvalue Of A Laplacian.
Combinatorics, Probability & Computing, 1999

Fast Algorithms for Finding O(Congestion + Dilation) Packet Routing Schedules.
Combinatorica, 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.
Journal of Computational Biology, 1998

Protein folding in the hydrophobic-hydrophilic (HP) 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 Processing, 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

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 lambda2 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

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

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

Reconstructing a Three-Dimensional Model with Arbitrary Errors.
Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 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. Discrete 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

Tight analyses of two local load balancing algorithms.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

On Probabilistic Networks for Selection, Merging, and Sorting.
Proceedings of the 7th Annual ACM Symposium on Parallel Algorithms and Architectures, 1995

Greedy Dynamic Routing on Arrays.
Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 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. Scientific Computing, 1994

A 2d-1 Lower Bound for Two-Layer Knock-Knee Channel Routing.
SIAM J. Discrete Math., 1994

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

Packet Routing and Job-Shop Scheduling in O(Congestion + Dilation) Steps.
Combinatorica, 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

Minimal Adaptive Routing on the Mesh with Bounded Queue Size.
Proceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, 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 the Design of Reliable Boolean Circuits that Contain Partially Unreliable Gates
Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 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

Tight Bounds on the Size of Fault-Tolerant Merging and Sorting Networks With Destructive Faults.
Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, 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

Comparing Queues and Stacks as Mechanisms for Laying out Graphs.
SIAM J. Discrete Math., 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

Methods for Message Routing in Parallel Machines
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

The Role of Randomness in the Design of Interconnection Networks.
Proceedings of the Parallel Architectures and Their Efficient Use, 1992

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

On the Fault Tolerance of Some Popular Bounded-Degree Networks
Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 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 Computer Architecture News, 1991

Letter from the Editor.
J. ACM, 1991

Editors' Introduction.
Algorithmica, 1991

Fast Approximation Algorithms for Multicommodity Flow Problems
Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

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

Tight Bounds for On-Line Tree Embeddings.
Proceedings of the Second Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 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

Fast Algorithms for Bit-Serial Routing on a Hypercube.
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

A Tight Lower Bound on the Size of Planar Permutation Networks.
Proceedings of the 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

Drawing Graphs in the Plane with High Resolution
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

1989
Universal Graphs for Bounded-Degree Trees and Planar Graphs.
SIAM J. Discrete 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.
Combinatorica, 1989

A Randomized Data Structure for Ordered Sets.
Advances in Computing Research, 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

Dynamic Tree Embeddings in Butterflies and Hypercubes.
Proceedings of the ACM Symposium on Parallel Algorithms and Architectures, 1989

A 2n-2 Step Algorithm for Routing in an nxn 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.
Combinatorica, 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. Information 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

A Provably Efficient Algorithm for Dynamic Storage Allocation
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.
Mathematical Systems Theory, 1984

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

Tight Bounds on the Complexity of Parallel Sorting
Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30, 1984

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

Graph Bisection Algorithms with Good Average Case Behavior
Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 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

New Lower Bound Techniques for VLSI
Proceedings of the 22nd Annual Symposium on Foundations of Computer Science, 1981


  Loading...