Frank Thomson Leighton

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

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2014

Correction: Basic Network Creation Games.

Noga Alon, Erik D. Demaine, MohammadTaghi Hajiaghayi, Panagiotis Kanellopoulos, Tom Leighton

SIAM J. Discret. Math., 2014

2013

Basic Network Creation Games.

Noga Alon, Erik D. Demaine, Mohammad Taghi Hajiaghayi, Tom Leighton

SIAM J. Discret. Math., 2013

2010

Some Results on Greedy Embeddings in Metric Spaces.

Tom Leighton, Ankur Moitra

Discret. Comput. Geom., 2010

Extensions and limits to vertex sparsification.

Frank Thomson Leighton, Ankur Moitra

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Vertex Sparsifiers and Abstract Rounding Algorithms.

Moses Charikar, Tom Leighton, Shi Li, Ankur Moitra

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

2009

Hat Guessing Games.

Steve Butler, Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, Tom Leighton

SIAM Rev., 2009

2008

Improving Performance on the Internet.

Tom Leighton

ACM Queue, 2008

2007

Oblivious routing on node-capacitated and directed graphs.

Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, Harald Räcke, Tom Leighton

ACM Trans. Algorithms, 2007

Localized Client-Server Load Balancing without Global Information.

Baruch Awerbuch, Mohammad Taghi Hajiaghayi, Robert Kleinberg, Tom Leighton

SIAM J. Comput., 2007

Hamming Codes, Hypercube Embeddings, and Fault Tolerance.

William Aiello, Frank Thomson Leighton

SIAM J. Comput., 2007

Containment properties of product and power graphs.

Antonio Fernández, Tom Leighton, José Luis López-Presa

Discret. Appl. Math., 2007

Semi-oblivious routing: lower bounds.

Mohammad Taghi Hajiaghayi, Robert Kleinberg, Tom Leighton

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

The Akamai approach to achieving performance and reliability on the internet.

Tom Leighton

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.

Mohammad Taghi Hajiaghayi, Tom Leighton

Theor. Comput. Sci., 2006

Semi-oblivious routing.

Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, Tom Leighton

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.

Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, Frank Thomson Leighton, Harald Räcke

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Improved lower and upper bounds for universal TSP in planar metrics.

Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, Frank Thomson Leighton

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

2005

Oblivious routing in directed graphs with random demands.

Mohammad Taghi Hajiaghayi, Jeong Han Kim, Tom Leighton, Harald Räcke

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Online client-server load balancing without global information.

Baruch Awerbuch, Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, Tom Leighton

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

The Challenges of Delivering Content and Applications on the Internet.

Frank Thomson Leighton

Proceedings of the 2nd Symposium on Networked Systems Design and Implementation (NSDI 2005), 2005

2003

JACM 1991-1997.

Frank Thomson Leighton

J. ACM, 2003

Consistent load balancing via spread minimization.

Robert D. Kleinberg, Frank Thomson Leighton

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.

Robert D. Kleinberg, Frank Thomson Leighton

Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

Fractal Merkle Tree Representation and Traversal.

Markus Jakobsson, Frank Thomson Leighton, Silvio Micali, Michael Szydlo

Proceedings of the Topics in Cryptology, 2003

2001

New Algorithmic Aspects of the Local Lemma with Applications to Routing and Partitioning.

Frank Thomson Leighton, Chi-Jen Lu, Satish Rao, Aravind Srinivasan

SIAM J. Comput., 2001

Compression Using Efficient Multicasting.

Micah Adler, Frank Thomson Leighton

J. Comput. Syst. Sci., 2001

Universal-stability results and performance bounds for greedy contention-resolution protocols.

Matthew Andrews, Baruch Awerbuch, Antonio Fernández, Frank Thomson Leighton, Zhiyong Liu, Jon M. Kleinberg

J. ACM, 2001

Guessing Secrets.

Fan R. K. Chung, Ronald L. Graham, Frank Thomson Leighton

Electron. J. Comb., 2001

The Challenges of Delivering Content on the Internet.

Frank Thomson Leighton

Proceedings of the Algorithms and Data Structures, 7th International Workshop, 2001

2000

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

Matthew Andrews, Antonio Fernández, Mor Harchol-Balter, Frank Thomson Leighton, Lisa Zhang

SIAM J. Comput., 2000

1999

Tight Bounds on the Size of Fault-Tolerant Merging and Sorting Networks with Destructive Faults.

Frank Thomson Leighton, Yuan Ma

SIAM J. Comput., 1999

Tight Analyses of Two Local Load Balancing Algorithms.

Bhaskar Ghosh, Frank Thomson Leighton, Bruce M. Maggs, S. Muthukrishnan, C. Greg Plaxton, Rajmohan Rajaraman, Andréa W. Richa, Robert Endre Tarjan, David Zuckerman

SIAM J. Comput., 1999

Tight Bounds for On-Line Tree Embeddings.

Sandeep N. Bhatt, David S. Greenberg, Frank Thomson Leighton, Pangfeng Liu

SIAM J. Comput., 1999

Automatic Methods for Hiding Latency in Parallel and Distributed Computation.

Matthew Andrews, Frank Thomson Leighton, Panagiotis Takis Metaxas, Lisa Zhang

SIAM J. Comput., 1999

Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms.

Frank Thomson Leighton, Satish Rao

J. ACM, 1999

Reconstructing a Three-Dimensional Model with Arbitrary Errors.

Bonnie Berger, Jon M. Kleinberg, Frank Thomson Leighton

J. ACM, 1999

The Path Resistance Method For Bounding The Smallest Nontrivial Eigenvalue Of A Laplacian.

Stephen Guattery, Frank Thomson Leighton, Gary L. Miller

Comb. Probab. Comput., 1999

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

Frank Thomson Leighton, Bruce M. Maggs, Andréa W. Richa

Comb., 1999

Efficient Algorithms for Dynamic Allocation of Distributed Memo.

Frank Thomson Leighton, Eric J. Schwabe

Algorithmica, 1999

New Algorithmic Aspects of the Local Lemma with Applications to Routing and Partitioning.

Frank Thomson Leighton, Satish Rao, Aravind Srinivasan

Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Resource Discovery in Distributed Networks.

Mor Harchol-Balter, Frank Thomson Leighton, Daniel Lewin

Proceedings of the Eighteenth Annual ACM Symposium on Principles of Distributed Computing, 1999

Oblivious Deadlock-Free Routing in a Faulty Hypercube.

Jin Suk Kim, Eric Lehman, Frank Thomson Leighton

Proceedings of the 13th International Parallel Processing Symposium / 10th Symposium on Parallel and Distributed Processing (IPPS / SPDP '99), 1999

1998

Hypercubic Sorting Networks.

Frank Thomson Leighton, C. Greg Plaxton

SIAM J. Comput., 1998

On the Fault Tolerance of Some Popular Bounded-Degree Networks.

Frank Thomson Leighton, Bruce M. Maggs, Ramesh K. Sitaraman

SIAM J. Comput., 1998

Processor-Ring Communication: A Tight Asymptotic Bound on Packet Waiting Times.

Edward G. Coffman Jr., Nabil Kahalé, Frank Thomson Leighton

SIAM J. Comput., 1998

Protein Folding in the Hydrophobic-Hydrophilic(HP) Model is NP-Complete.

Bonnie Berger, Frank Thomson Leighton

J. Comput. Biol., 1998

Greedy Dynamic Routing on Arrays.

Nabil Kahalé, Frank Thomson Leighton

J. Algorithms, 1998

Protein folding in the hydrophobic-hydrophilic (<i>HP</i>) is NP-complete.

Bonnie Berger, Frank Thomson Leighton

Proceedings of the Second Annual International Conference on Research in Computational Molecular Biology, 1998

Multicommodity Flow and Circuit Switching.

Tom Leighton, Satish Rao, Aravind Srinivasan

Proceedings of the Thirty-First Annual Hawaii International Conference on System Sciences, 1998

1997

Secure spread spectrum watermarking for multimedia.

Ingemar J. Cox, Joe Kilian, Frank Thomson Leighton, Talal Shamoon

IEEE Trans. Image Process., 1997

An Optimal Strategies for Cycle-Stealing in Networks of Workstations.

Sandeep N. Bhatt, Fan R. K. Chung, Frank Thomson Leighton, Arnold L. Rosenberg

IEEE Trans. Computers, 1997

Doubly Logarithmic Communication Algorithms for Optical-Communication Parallel Computers.

Leslie Ann Goldberg, Mark Jerrum, Frank Thomson Leighton, Satish Rao

SIAM J. Comput., 1997

On Probabilistic Networks for Selection, Merging, and Sorting.

Frank Thomson Leighton, Yuan Ma, Torsten Suel

Theory Comput. Syst., 1997

Breaking the Theta (n log² n) Barrier for Sorting with Faults.

Frank Thomson Leighton, Yuan Ma, C. Greg Plaxton

J. Comput. Syst. Sci., 1997

On the Design of Reliable Boolean Circuits That Contain Partially Unreliable Gates.

Daniel J. Kleitman, Frank Thomson Leighton, Yuan Ma

J. Comput. Syst. Sci., 1997

Work-preserving emulations of fixed-connection networks.

Richard R. Koch, Frank Thomson Leighton, Bruce M. Maggs, Satish Rao, Arnold L. Rosenberg, Eric J. Schwabe

J. ACM, 1997

Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web.

David R. Karger, Eric Lehman, Frank Thomson Leighton, Rina Panigrahy, Matthew S. Levine, Daniel Lewin

Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

The Path Resistance Method for Bounding lambda₂ of a Laplacian.

Stephen Guattery, Frank Thomson Leighton, Gary L. Miller

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).

Matthew Andrews, Antonio Fernández, Mor Harchol-Balter, Frank Thomson Leighton, Lisa Zhang

Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

1996

Analysis of Backoff Protocols for Multiple Access Channels.

Johan Håstad, Frank Thomson Leighton, Brian Rogoff

SIAM J. Comput., 1996

On-Line Algorithms for Path Selection in a Nonblocking Network.

Sanjeev Arora, Frank Thomson Leighton, Bruce M. Maggs

SIAM J. Comput., 1996

Minimal Adaptive Routing on the Mesh with Bounded Queue Size.

Donald D. Chinn, Frank Thomson Leighton, Martin Tompa

J. Parallel Distributed Comput., 1996

Scheduling Tree-Dags Using FIFO Queues: A Control-Memory Trade-Off.

Sandeep N. Bhatt, Fan R. K. Chung, Frank Thomson Leighton, Arnold L. Rosenberg

J. Parallel Distributed Comput., 1996

Optimal Emulations by Butterfly-Like Networks.

Sandeep N. Bhatt, Fan R. K. Chung, Jia-Wei Hong, Frank Thomson Leighton, Bojana Obrenic, Arnold L. Rosenberg, Eric J. Schwabe

J. ACM, 1996

Making Commitments in the Face of Uncertainty: How to Pick a Winner Almost Every Time (Extended Abstract).

Baruch Awerbuch, Yossi Azar, Amos Fiat, Frank Thomson Leighton

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).

Matthew Andrews, Frank Thomson Leighton, Panagiotis Takis Metaxas, Lisa Zhang

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).

Matthew Andrews, Frank Thomson Leighton, Panagiotis Takis Metaxas, Lisa Zhang

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.

Frank Thomson Leighton

Proceedings of the Fourth Israel Symposium on Theory of Computing and Systems, 1996

A Secure, Robust Watermark for Multimedia.

Ingemar J. Cox, Joe Kilian, Frank Thomson Leighton, Talal Shamoon

Proceedings of the Information Hiding, First International Workshop, Cambridge, UK, May 30, 1996

Secure spread spectrum watermarking for images, audio and video.

Ingemar J. Cox, Joe Kilian, Tom Leighton, Talal Shamoon

Proceedings of the Proceedings 1996 International Conference on Image Processing, 1996

Universal Stability Results for Greedy Contention-Resolution Protocols.

Matthew Andrews, Baruch Awerbuch, Antonio Fernández, Jon M. Kleinberg, Frank Thomson Leighton, Zhiyong Liu

Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

1995

Salvage-Embeddings of Complete Trees.

Sandeep N. Bhatt, Fan R. K. Chung, Frank Thomson Leighton, Arnold L. Rosenberg

SIAM J. Discret. Math., 1995

Fast Approximation Algorithms for Multicommodity Flow Problems.

Frank Thomson Leighton, Fillia Makedon, Serge A. Plotkin, Clifford Stein, Éva Tardos, Spyros Tragoudas

J. Comput. Syst. Sci., 1995

Nearly Optimal Algorithms and Bounds for Multilayer Channel Routing.

Bonnie Berger, Martin L. Brady, Donna J. Brown, Frank Thomson Leighton

J. ACM, 1995

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

Frank Thomson Leighton, Fillia Makedon, Ioannis G. Tollis

Algorithmica, 1995

Lower bounds for sorting networks.

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

Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

The Statistical Adversary Allows Optimal Money-Making Trading Strategies.

Andrew Chou, Jeremy R. Cooperstock, Ran El-Yaniv, Michael Klugerman, Frank Thomson Leighton

Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 1995

Fast algorithms for finding O(congestion+dilation) packet routing schedules.

Frank Thomson Leighton, Bruce M. Maggs

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).

Joe Kilian, Frank Thomson Leighton

Proceedings of the Advances in Cryptology, 1995

1994

Methods for Message Routing in Parallel Machines.

Frank Thomson Leighton

Theor. Comput. Sci., 1994

Preconditioned, Adaptive, Multipole-Accelerated Iterative Methods for Three-Dimensional First-Kind Integral Equations of Potential Theory.

Keith Nabors, F. T. Korsmeyer, Frank Thomson Leighton, Jacob K. White

SIAM J. Sci. Comput., 1994

A 2<i>d</i>-1 Lower Bound for Two-Layer Knock-Knee Channel Routing.

Frank Thomson Leighton

SIAM J. Discret. Math., 1994

Randomized Routing and Sorting on Fixed-Connection Networks.

Frank Thomson Leighton, Bruce M. Maggs, Abhiram G. Ranade, Satish Rao

J. Algorithms, 1994

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

Frank Thomson Leighton, Bruce M. Maggs, Satish Rao

Comb., 1994

Scalable expanders: exploiting hierarchical random wiring.

Eric A. Brewer, Frederic T. Chong, Tom Leighton

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.

Baruch Awerbuch, Tom Leighton

Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

Scheduling Trees using FIFO Queues: A Control-Memory Tradeoff.

Sandeep N. Bhatt, Fan R. K. Chung, Frank Thomson Leighton, Arnold L. Rosenberg

Proceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, 1994

Packaging and Multiplexing of Hierarchical Scalable Expanders.

Frederic T. Chong, Eric A. Brewer, Frank Thomson Leighton, Thomas F. Knight Jr.

Proceedings of the Parallel Computer Routing and Communication, 1994

Building a better butterfly: the multiplexed metabutterfly.

Frederic T. Chong, Eric A. Brewer, Frank Thomson Leighton, Thomas F. Knight Jr.

Proceedings of the International Symposium on Parallel Architectures, 1994

On-line Admission Control and Circuit Routing for High Performance Computing and Communication

Baruch Awerbuch, Rainer Gawlick, Frank Thomson Leighton, Yuval Rabani

Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

1993

Drawing Graphs in the Plane with High Resolution.

Michael Formann, Torben Hagerup, James Haralambides, Michael Kaufmann, Frank Thomson Leighton, Antonios Symvonis, Emo Welzl, Gerhard J. Woeginger

SIAM J. Comput., 1993

A Doubly Logarithmic Communication Algorithm for the Completely Connected Optical Communication Parallel Computer.

Leslie Ann Goldberg, Mark Jerrum, Frank Thomson Leighton, Satish Rao

Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, 1993

Multicommodity Flows: A Survey of Recent Research.

Baruch Awerbuch, Frank Thomson Leighton

Proceedings of the Algorithms and Computation, 4th International Symposium, 1993

Breaking the Theta(n log ^2 n) Barrier for Sorting with Faults (Extended Abstract)

Frank Thomson Leighton, Yuan Ma

Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

A Simple Local-Control Approximation Algorithm for Multicommodity Flow

Baruch Awerbuch, Frank Thomson Leighton

Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

Secret-Key Agreement without Public-Key Cryptography.

Frank Thomson Leighton, Silvio Micali

Proceedings of the Advances in Cryptology, 1993

1992

Fast Algorithms for Routing Around Faults in Multibutterflies and Randomly-Wired Splitter Networks.

Frank Thomson Leighton, Bruce M. Maggs

IEEE Trans. Computers, 1992

A Tight Lower Bound on the Size of Planar Permutation Networks.

Maria M. Klawe, Frank Thomson Leighton

SIAM J. Discret. Math., 1992

Comparing Queues and Stacks as Mechanisms for Laying out Graphs.

Lenwood S. Heath, Frank Thomson Leighton, Arnold L. Rosenberg

SIAM J. Discret. Math., 1992

Dynamic Tree Embeddings in Butterflies and Hypercubes.

Frank Thomson Leighton, Mark Newman, Abhiram G. Ranade, Eric J. Schwabe

SIAM J. Comput., 1992

Efficient Embeddings of Trees in Hypercubes.

Sandeep N. Bhatt, Fan R. K. Chung, Frank Thomson Leighton, Arnold L. Rosenberg

SIAM J. Comput., 1992

Improved Algorithms for Routing on Two-Dimensional Grids.

Dinesh Bhatia, Frank Thomson Leighton, Fillia Makedon, Carolyn Haibt Norton

Proceedings of the Graph-Theoretic Concepts in Computer Science, 1992

The Role of Randomness in the Design of Interconnection Networks.

Frank Thomson Leighton, Bruce M. Maggs

Proceedings of the Algorithms, Software, Architecture, 1992

Tolerating Faults in Synchronization Networks.

Sandeep N. Bhatt, Fan R. K. Chung, Frank Thomson Leighton, Arnold L. Rosenberg

Proceedings of the Parallel Processing: CONPAR 92, 1992

1991

Selected Papers from the Symposium on Parallel Algorithms and Architectures.

Frank Thomson Leighton

SIGARCH Comput. Archit. News, 1991

Fast Algorithms for Bit-Serial Routing on a Hypercube.

William Aiello, Frank Thomson Leighton, Bruce M. Maggs, Mark Newman

Math. Syst. Theory, 1991

Letter from the Editor.

Frank Thomson Leighton

J. ACM, 1991

Editors' Introduction.

Andrea S. LaPaugh, Frank Thomson Leighton

Algorithmica, 1991

Coding Theory, Hypercube Embeddings, and Fault Tolerance.

William Aiello, Frank Thomson Leighton

Proceedings of the 3rd Annual ACM Symposium on Parallel Algorithms and Architectures, 1991

Efficient Algorithms for Dynamic Allocation of Distributed Memory

Frank Thomson Leighton, Eric J. Schwabe

Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

Highly Fault-Tolerant Sorting Circuits

Frank Thomson Leighton, Yuan Ma, C. Greg Plaxton

Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

1990

Generalized Planar Matching.

Francine Berman, David S. Johnson, Frank Thomson Leighton, Peter W. Shor, Larry Snyder

J. Algorithms, 1990

A Tight Lower Bound for the Train Reversal Problem.

Alok Aggarwal, Frank Thomson Leighton

Inf. Process. Lett., 1990

On-line Algorithms for Path Selection in a Nonblocking Network (Extended Abstract)

Sanjeev Arora, Frank Thomson Leighton, Bruce M. Maggs

Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

Solving Query-Retrieval Problems by Compacting Voronoi Diagrams (Extended Abstract)

Alok Aggarwal, Mark Hansen, Frank Thomson Leighton

Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

Average Case Analysis of Greedy Routing algorithms on Arrays.

Frank Thomson Leighton

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.

Edward G. Coffman Jr., Leopold Flatto, Frank Thomson Leighton

Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, 1990

Efficient Reconfiguration of WSI Arrays.

Dinesh Bhatia, Frank Thomson Leighton, Fillia Makedon

Proceedings of the First International Conference on Systems Integration, 1990

Empirical evaluation of randomly-wire multistage networks.

Tom Leighton, Derek Linsinski, Bruce M. Maggs

Proceedings of the 1990 IEEE International Conference on Computer Design: VLSI in Computers and Processors, 1990

A (fairly) Simple Circuit that (usually) Sorts

Frank Thomson Leighton, C. Greg Plaxton

Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

Asymptotically Tight Bounds for Computing with Faulty Arrays of Processors (Extended Abstract)

Christos Kaklamanis, Anna R. Karlin, Frank Thomson Leighton, Victor Milenkovic, Prabhakar Raghavan, Satish Rao, Clark D. Thomborson, A. Tsantilas

Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

1989

Universal Graphs for Bounded-Degree Trees and Planar Graphs.

Sandeep N. Bhatt, Fan R. K. Chung, Frank Thomson Leighton, Arnold L. Rosenberg

SIAM J. Discret. Math., 1989

A Provably Efficient Algorithm for Dynamic Storage Allocation.

Edward G. Coffman Jr., Frank Thomson Leighton

J. Comput. Syst. Sci., 1989

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

Tom Leighton, Peter W. Shor

Comb., 1989

A Randomized Data Structure for Ordered Sets.

Jon Louis Bentley, Frank Thomson Leighton, Margaret Lepley, Donald F. Stanat, J. Michael Steele

Adv. Comput. Res., 1989

Work-Preserving Emulations of Fixed-Connection Networks (Extended Abstract)

Richard R. Koch, Frank Thomson Leighton, Bruce M. Maggs, Satish Rao, Arnold L. Rosenberg

Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

Fast Computation Using Faulty Hypercubes (Extended Abstract)

Johan Håstad, Frank Thomson Leighton, Mark Newman

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.

Frank Thomson Leighton, Fillia Makedon, Ioannis G. Tollis

Proceedings of the ACM Symposium on Parallel Algorithms and Architectures, 1989

Expanders Might Be Practical: Fast Algorithms for Routing Around Faults on Multibutterflies

Frank Thomson Leighton, Bruce M. Maggs

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.

Thang Nguyen Bui, C. Heigham, Curt Jones, Frank Thomson Leighton

Proceedings of the 26th ACM/IEEE Design Automation Conference, 1989

1988

Optimal Simulations by Butterfly Networks (Preliminary Version)

Sandeep N. Bhatt, Fan R. K. Chung, Jia-Wei Hong, Frank Thomson Leighton, Arnold L. Rosenberg

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

Frank Thomson Leighton, Satish Rao

Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

Universal Packet Routing Algorithms (Extended Abstract)

Frank Thomson Leighton, Bruce M. Maggs, Satish Rao

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.

Larry Finkelstein, Daniel J. Kleitman, Frank Thomson Leighton

Proceedings of the VLSI Algorithms and Architectures, 3rd Aegean Workshop on Computing, 1988

1987

Graph bisection algorithms with good average case behavior.

Thang Nguyen Bui, Soma Chaudhuri, Frank Thomson Leighton, Michael Sipser

Comb., 1987

Global Wire Routing in Two-Dimensional Arrays.

Richard M. Karp, Frank Thomson Leighton, Ronald L. Rivest, Clark D. Thompson, Umesh V. Vazirani, Vijay V. Vazirani

Algorithmica, 1987

Analysis of Backoff Protocols for Multiple Access Channels (Extended Abstract)

Johan Håstad, Frank Thomson Leighton, Brian Rogoff

Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987

Reconfiguring a Hypercube in the Presence of Faults (Extended Abstract)

Johan Håstad, Frank Thomson Leighton, Mark Newman

Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987

1986

Estimating a probability using finite memory.

Frank Thomson Leighton, Ronald L. Rivest

IEEE Trans. Inf. Theory, 1986

Three-Dimensional Circuit Layouts.

Frank Thomson Leighton, Arnold L. Rosenberg

SIAM J. Comput., 1986

Tight Bounds for Minimax Grid Matching, With Applications to the Average Case Analysis of Algorithms

Frank Thomson Leighton, Peter W. Shor

Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986

Optimal Simulations of Tree Machines (Preliminary Version)

Sandeep N. Bhatt, Fan R. K. Chung, Frank Thomson Leighton, Arnold L. Rosenberg

Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986

1985

Wafer-Scale Integration of Systolic Arrays.

Frank Thomson Leighton, Charles E. Leiserson

IEEE Trans. Computers, 1985

Tight Bounds on the Complexity of Parallel Sorting.

Frank Thomson Leighton

IEEE Trans. Computers, 1985

1984

New Lower Bound Techniques for VLSI.

Frank Thomson Leighton

Math. Syst. Theory, 1984

A Framework for Solving VLSI Graph Layout Problems.

Sandeep N. Bhatt, Frank Thomson Leighton

J. Comput. Syst. Sci., 1984

Some Unexpected Expected Behavior Results for Bin Packing

Jon Louis Bentley, David S. Johnson, Frank Thomson Leighton, Catherine C. McGeoch, Lyle A. McGeoch

Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30, 1984

1983

An Asymptotically Optimal Layout for the Shuffle-Exchange Graph.

Daniel J. Kleitman, Frank Thomson Leighton, Margaret Lepley, Gary L. Miller

J. Comput. Syst. Sci., 1983

Parallel Computation Using Meshes of Trees.

Tom Leighton

Proceedings of the WG '83, 1983

An Approximation Algorithm for Manhattan Routing (Extended Abstract)

Brenda S. Baker, Sandeep N. Bhatt, Frank Thomson Leighton

Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983

Global Wire Routing in Two-Dimensional Arrays (Extended Abstract)

Richard M. Karp, Frank Thomson Leighton, Ronald L. Rivest, Clark D. Thompson, Umesh V. Vazirani, Vijay V. Vazirani

Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983

Estimating a Probability Using Finite Memory (Extended Abstract).

Frank Thomson Leighton, Ronald L. Rivest

Proceedings of the Fundamentals of Computation Theory, 1983

1982

Finite common coverings of graphs.

Frank Thomson Leighton

J. Comb. Theory B, 1982

A Layout Strategy for VLSI which Is Provably Good (Extended Abstract)

Frank Thomson Leighton

Proceedings of the 14th Annual ACM Symposium on Theory of Computing, 1982

Wafer-Scale Integration of Systolic Arrays (Extended Abstract)

Frank Thomson Leighton, Charles E. Leiserson

Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, 1982

1981

New Layouts for the Shuffle-Exchange Graph (Extended Abstract)

Daniel J. Kleitman, Frank Thomson Leighton, Margaret Lepley, Gary L. Miller

Proceedings of the 13th Annual ACM Symposium on Theory of Computing, 1981