Frank Thomson Leighton

Tom Leighton

	2010
182		Moses Charikar, Tom Leighton, Shi Li, Ankur Moitra: Vertex Sparsifiers and Abstract Rounding Algorithms. FOCS 2010: 265-274
181		Noga Alon, Erik D. Demaine, MohammadTaghi Hajiaghayi, Tom Leighton: Basic network creation games. SPAA 2010: 106-113
180		Frank Thomson Leighton, Ankur Moitra: Extensions and limits to vertex sparsification. STOC 2010: 47-56
179		Moses Charikar, Tom Leighton, Shi Li, Ankur Moitra: Vertex Sparsifiers and Abstract Rounding Algorithms CoRR abs/1006.4536: (2010)
178		Tom Leighton, Ankur Moitra: Some Results on Greedy Embeddings in Metric Spaces. Discrete & Computational Geometry 44(3): 686-705 (2010)
	2009
177		Tom Leighton: Improving performance on the internet. Commun. ACM 52(2): 44-51 (2009)
176		Steve Butler, Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, Tom Leighton: Hat Guessing Games. SIAM Review 51(2): 399-413 (2009)
	2008
175		Ankur Moitra, Tom Leighton: Some Results on Greedy Embeddings in Metric Spaces. FOCS 2008: 337-346
174		Tom Leighton: Improving Performance on the Internet. ACM Queue 6(6): 20-29 (2008)
173		Steve Butler, Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, Tom Leighton: Hat Guessing Games. SIAM J. Discrete Math. 22(2): 592-605 (2008)
	2007
172		Tom Leighton: The Akamai approach to achieving performance and reliability on the internet. PODC 2007: 2
171		Mohammad Taghi Hajiaghayi, Robert Kleinberg, Tom Leighton: Semi-oblivious routing: lower bounds. SODA 2007: 929-938
170		Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, Harald Räcke, Tom Leighton: Oblivious routing on node-capacitated and directed graphs. ACM Transactions on Algorithms 3(4): (2007)
169		Antonio Fernández, Tom Leighton, José Luis López-Presa: Containment properties of product and power graphs. Discrete Applied Mathematics 155(3): 300-311 (2007)
168		William Aiello, Frank Thomson Leighton: Hamming Codes, Hypercube Embeddings, and Fault Tolerance. SIAM J. Comput. 37(3): 783-803 (2007)
167		Baruch Awerbuch, Mohammad Taghi Hajiaghayi, Robert Kleinberg, Tom Leighton: Localized Client-Server Load Balancing without Global Information. SIAM J. Comput. 37(4): 1259-1279 (2007)
	2006
166		Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, Frank Thomson Leighton: Improved lower and upper bounds for universal TSP in planar metrics. SODA 2006: 649-658
165		Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, Frank Thomson Leighton, Harald Räcke: New lower bounds for oblivious routing in undirected graphs. SODA 2006: 918-927
164		Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, Tom Leighton: Semi-oblivious routing. SPAA 2006: 234
163		Mohammad Taghi Hajiaghayi, Tom Leighton: On the max-flow min-cut ratio for directed multicommodity flows. Theor. Comput. Sci. 352(1-3): 318-321 (2006)
	2005
162		Frank Thomson Leighton: The Challenges of Delivering Content and Applications on the Internet. NSDI 2005
161		Baruch Awerbuch, Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, Tom Leighton: Online client-server load balancing without global information. SODA 2005: 197-206
160		Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, Tom Leighton, Harald Räcke: Oblivious routing on node-capacitated and directed graphs. SODA 2005: 782-790
159		Mohammad Taghi Hajiaghayi, Jeong Han Kim, Tom Leighton, Harald Räcke: Oblivious routing in directed graphs with random demands. STOC 2005: 193-201
	2004
158		Frank Thomson Leighton: The Challenges of Delivering Content and Applications on the Internet. RIDE 2004: 65
	2003
157		Markus Jakobsson, Frank Thomson Leighton, Silvio Micali, Michael Szydlo: Fractal Merkle Tree Representation and Traversal. CT-RSA 2003: 314-326
156		Robert D. Kleinberg, Frank Thomson Leighton: The Value of Knowing a Demand Curve: Bounds on Regret for Online Posted-Price Auctions. FOCS 2003: 594-605
155		Robert D. Kleinberg, Frank Thomson Leighton: Consistent load balancing via spread minimization. STOC 2003: 565-574
154		Frank Thomson Leighton: JACM 1991-1997. J. ACM 50(1): 19 (2003)
	2001
153		Frank Thomson Leighton: The Challenges of Delivering Content on the Internet. NCA 2001: 214
152		Frank Thomson Leighton: The Challenges of Delivering Content on the Internet. PODS 2001
151		Fan R. K. Chung, Ronald L. Graham, Frank Thomson Leighton: Guessing secrets. SODA 2001: 723-726
150		Frank Thomson Leighton: The Challenges of Delivering Content on the Internet. WADS 2001: 338
149		Fan R. K. Chung, Ronald L. Graham, Frank Thomson Leighton: Guessing Secrets. Electr. J. Comb. 8(1): (2001)
148		Antonio Fernández, Tom Leighton, José Luis López-Presa: Containment Properties of Product and Power Graphs. Electronic Notes in Discrete Mathematics 7: 46-49 (2001)
147		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): 39-69 (2001)
146		Micah Adler, Frank Thomson Leighton: Compression Using Efficient Multicasting. J. Comput. Syst. Sci. 63(1): 127-145 (2001)
145		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): 626-641 (2001)
	2000
144		Micah Adler, Frank Thomson Leighton: Compression using efficient multicasting. STOC 2000: 153-162
143		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). SIAM J. Comput. 30(5): 1594-1623 (2000)
	1999
142		Jeffrey Scott Vitter, Lawrence L. Larmore, Frank Thomson Leighton: Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, May 1-4, 1999, Atlanta, Georgia, USA ACM 1999
141		Jin Suk Kim, Eric Lehman, Frank Thomson Leighton: Oblivious Deadlock-Free Routing in a Faulty Hypercube. IPPS/SPDP 1999: 312-319
140		Mor Harchol-Balter, Frank Thomson Leighton, Daniel Lewin: Resource Discovery in Distributed Networks. PODC 1999: 229-237
139		Frank Thomson Leighton, Satish Rao, Aravind Srinivasan: New Algorithmic Aspects of the Local Lemma with Applications to Routing and Partitioning. SODA 1999: 643-652
138		Frank Thomson Leighton, Eric J. Schwabe: Efficient Algorithms for Dynamic Allocation of Distributed Memo. Algorithmica 24(2): 139-171 (1999)
137		Frank Thomson Leighton, Bruce M. Maggs, Andréa W. Richa: Fast Algorithms for Finding O(Congestion + Dilation) Packet Routing Schedules. Combinatorica 19(3): 375-401 (1999)
136		Stephen Guattery, Frank Thomson Leighton, Gary L. Miller: The Path Resistance Method For Bounding The Smallest Nontrivial Eigenvalue Of A Laplacian. Combinatorics, Probability & Computing 8(5): 441-460 (1999)
135		Bonnie Berger, Jon M. Kleinberg, Frank Thomson Leighton: Reconstructing a Three-Dimensional Model with Arbitrary Errors. J. ACM 46(2): 212-235 (1999)
134		Frank Thomson Leighton, Satish Rao: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM 46(6): 787-832 (1999)
133		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): 258-273 (1999)
132		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): 29-64 (1999)
131		Sandeep N. Bhatt, David S. Greenberg, Frank Thomson Leighton, Pangfeng Liu: Tight Bounds for On-Line Tree Embeddings. SIAM J. Comput. 29(2): 474-491 (1999)
130		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): 615-647 (1999)
	1998
129		Bonnie Berger, Frank Thomson Leighton: Protein folding in the hydrophobic-hydrophilic (HP) is NP-complete. RECOMB 1998: 30-39
128		Nabil Kahale, Frank Thomson Leighton: Greedy Dynamic Routing on Arrays. J. Algorithms 29(2): 390-410 (1998)
127		Bonnie Berger, Frank Thomson Leighton: Protein Folding in the Hydrophobic-Hydrophilic(HP) Model is NP-Complete. Journal of Computational Biology 5(1): 27-40 (1998)
126		Frank Thomson Leighton, C. Greg Plaxton: Hypercubic Sorting Networks. SIAM J. Comput. 27(1): 1-47 (1998)
125		Edward G. Coffman Jr., Nabil Kahale, Frank Thomson Leighton: Processor-Ring Communication: A Tight Asymptotic Bound on Packet Waiting Times. SIAM J. Comput. 27(5): 1221-1236 (1998)
124		Frank Thomson Leighton, Bruce M. Maggs, Ramesh K. Sitaraman: On the Fault Tolerance of Some Popular Bounded-Degree Networks. SIAM J. Comput. 27(5): 1303-1333 (1998)
	1997
123		Frank Thomson Leighton, Peter W. Shor: Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, El Paso, Texas, USA, May 4-6, 1997 ACM 1997
122		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: 294-302
121		Stephen Guattery, Frank Thomson Leighton, Gary L. Miller: The Path Resistance Method for Bounding lambda2 of a Laplacian. SODA 1997: 201-210
120		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: 654-663
119		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): 545-557 (1997)
118		Ingemar J. Cox, Joe Kilian, Frank Thomson Leighton, Talal Shamoon: Secure spread spectrum watermarking for multimedia. IEEE Transactions on Image Processing 6(12): 1673-1687 (1997)
117		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): 104-147 (1997)
116		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): 265-304 (1997)
115		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): 385-401 (1997)
114		Leslie Ann Goldberg, Mark Jerrum, Frank Thomson Leighton, Satish Rao: Doubly Logarithmic Communication Algorithms for Optical-Communication Parallel Computers. SIAM J. Comput. 26(4): 1100-1119 (1997)
113		Frank Thomson Leighton, Yuan Ma, Torsten Suel: On Probabilistic Networks for Selection, Merging, and Sorting. Theory Comput. Syst. 30(6): 559-582 (1997)
	1996
112		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: 380-389
111		Frank Thomson Leighton: How to Pick a Winner Almost Every Time: Provably-Good Algorithms for Decision Making in the Face of Uncertainty. ISTCS 1996: 2
110		Ingemar J. Cox, Joe Kilian, Frank Thomson Leighton, Talal Shamoon: A Secure, Robust Watermark for Multimedia. Information Hiding 1996: 185-206
109		Matthew Andrews, Frank Thomson Leighton, Panagiotis Takis Metaxas, Lisa Zhang: Improved Methods for Hiding Latency in High Bandwidth Networks (Extended Abstract). SPAA 1996: 52-61
108		Matthew Andrews, Frank Thomson Leighton, Panagiotis Takis Metaxas, Lisa Zhang: Automatic Methods for Hiding Latency in High Bandwidth Networks (Extended Abstract). STOC 1996: 257-265
107		Bonnie Berger, Jon M. Kleinberg, Frank Thomson Leighton: Reconstructing a Three-Dimensional Model with Arbitrary Errors. STOC 1996: 449-458
106		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: 519-530
105		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): 293-330 (1996)
104		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 Distrib. Comput. 33(1): 55-68 (1996)
103		Donald D. Chinn, Frank Thomson Leighton, Martin Tompa: Minimal Adaptive Routing on the Mesh with Bounded Queue Size. J. Parallel Distrib. Comput. 34(2): 154-170 (1996)
102		Sanjeev Arora, Frank Thomson Leighton, Bruce M. Maggs: On-Line Algorithms for Path Selection in a Nonblocking Network. SIAM J. Comput. 25(3): 600-625 (1996)
101		Johan Håstad, Frank Thomson Leighton, Brian Rogoff: Analysis of Backoff Protocols for Multiple Access Channels. SIAM J. Comput. 25(4): 740-774 (1996)
	1995
100		Frank Thomson Leighton, Allan Borodin: Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 29 May-1 June 1995, Las Vegas, Nevada, USA ACM 1995
99		Joe Kilian, Frank Thomson Leighton: Fair Cryptosystems, Revisited: A Rigorous Approach to Key-Escrow (Extended Abstract). CRYPTO 1995: 208-221
98		Frank Thomson Leighton, Bruce M. Maggs: Fast algorithms for finding O(congestion+dilation) packet routing schedules. HICSS (2) 1995: 555-563
97		Andrew Chou, Jeremy R. Cooperstock, Ran El-Yaniv, Michael Klugerman, Frank Thomson Leighton: The Statistical Adversary Allows Optimal Money-Making Trading Strategies. SODA 1995: 467-476
96		Nabil Kahale, Frank Thomson Leighton: Greedy Dynamic Routing on Arrays. SODA 1995: 558-566
95		Frank Thomson Leighton, Yuan Ma, Torsten Suel: On Probabilistic Networks for Selection, Merging, and Sorting. SPAA 1995: 106-118
94		Nabil Kahale, Frank Thomson Leighton, Yuan Ma, C. Greg Plaxton, Torsten Suel, Endre Szemerédi: Lower bounds for sorting networks. STOC 1995: 437-446
93		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: 548-558
92		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): 291-304 (1995)
91		Bonnie Berger, Martin L. Brady, Donna J. Brown, Frank Thomson Leighton: Nearly Optimal Algorithms and Bounds for Multilayer Channel Routing. J. ACM 42(2): 500-542 (1995)
90		Frank Thomson Leighton, Fillia Makedon, Serge A. Plotkin, Clifford Stein, Éva Stein, Spyros Tragoudas: Fast Approximation Algorithms for Multicommodity Flow Problems. J. Comput. Syst. Sci. 50(2): 228-243 (1995)
89		Sandeep N. Bhatt, Fan R. K. Chung, Frank Thomson Leighton, Arnold L. Rosenberg: Salvage-Embeddings of Complete Trees. SIAM J. Discrete Math. 8(4): 617-637 (1995)
	1994
88		Frank Thomson Leighton, Michael T. Goodrich: Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 23-25 May 1994, Montréal, Québec, Canada ACM 1994
87		Daniel J. Kleitman, Frank Thomson Leighton, Yuan Ma: On the Design of Reliable Boolean Circuits that Contain Partially Unreliable Gates FOCS 1994: 332-346
86		Baruch Awerbuch, Rainer Gawlick, Frank Thomson Leighton, Yuval Rabani: On-line Admission Control and Circuit Routing for High Performance Computing and Communication FOCS 1994: 412-423
85		Frederic T. Chong, Eric A. Brewer, Frank Thomson Leighton, Thomas F. Knight Jr.: Packaging and Multiplexing of Hierarchical Scalable Expanders. PCRCW 1994: 200-214
84		Donald D. Chinn, Frank Thomson Leighton, Martin Tompa: Minimal Adaptive Routing on the Mesh with Bounded Queue Size. SPAA 1994: 354-363
83		Sandeep N. Bhatt, Fan R. K. Chung, Frank Thomson Leighton, Arnold L. Rosenberg: Scheduling Trees using FIFO Queues: A Control-Memory Tradeoff. SPAA 1994: 85-93
82		Eric A. Brewer, Frederic T. Chong, Tom Leighton: Scalable expanders: exploiting hierarchical random wiring. STOC 1994: 144-152
81		Baruch Awerbuch, Tom Leighton: Improved approximation algorithms for the multi-commodity flow problem and local competitive routing in dynamic networks. STOC 1994: 487-496
80		Frank Thomson Leighton, Bruce M. Maggs, Satish Rao: Packet Routing and Job-Shop Scheduling in O(Congestion + Dilation) Steps. Combinatorica 14(2): 167-186 (1994)
79		Frank Thomson Leighton, Bruce M. Maggs, Abhiram G. Ranade, Satish Rao: Randomized Routing and Sorting on Fixed-Connection Networks. J. Algorithms 17(1): 157-205 (1994)
78		Frank Thomson Leighton: A 2d-1 Lower Bound for Two-Layer Knock-Knee Channel Routing. SIAM J. Discrete Math. 7(2): 230-237 (1994)
77		Frank Thomson Leighton: Methods for Message Routing in Parallel Machines. Theor. Comput. Sci. 128(1&2): 31-62 (1994)
	1993
76		Frank Thomson Leighton, Silvio Micali: Secret-Key Agreement without Public-Key Cryptography. CRYPTO 1993: 456-479
75		Baruch Awerbuch, Frank Thomson Leighton: A Simple Local-Control Approximation Algorithm for Multicommodity Flow FOCS 1993: 459-468
74		Frank Thomson Leighton, Yuan Ma: Breaking the Theta(n log ^2 n) Barrier for Sorting with Faults (Extended Abstract) FOCS 1993: 734-743
73		Baruch Awerbuch, Frank Thomson Leighton: Multicommodity Flows: A Survey of Recent Research. ISAAC 1993: 297-302
72		Frank Thomson Leighton, Yuan Ma: Tight Bounds on the Size of Fault-Tolerant Merging and Sorting Networks With Destructive Faults. SPAA 1993: 30-41
71		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: 300-309
70		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): 1035-1052 (1993)
	1992
69		Sandeep N. Bhatt, Fan R. K. Chung, Frank Thomson Leighton, Arnold L. Rosenberg: Tolerating Faults in Synchronization Networks. CONPAR 1992: 1-12
68		Frank Thomson Leighton, Bruce M. Maggs, Ramesh K. Sitaraman: On the Fault Tolerance of Some Popular Bounded-Degree Networks FOCS 1992: 542-552
67		Frank Thomson Leighton, Bruce M. Maggs: The Role of Randomness in the Design of Interconnection Networks. Heinz Nixdorf Symposium 1992: 131-145
66		Frank Thomson Leighton, Bruce M. Maggs: The Role of Randomness in the Design of Interconnection Networks. IFIP Congress (1) 1992: 291-305
65		Frank Thomson Leighton: Methods for Message Routing in Parallel Machines STOC 1992: 77-96
64		Dinesh Bhatia, Frank Thomson Leighton, Fillia Makedon, Carolyn Haibt Norton: Improved Algorithms for Routing on Two-Dimensional Grids. WG 1992: 114-122
63		Frank Thomson Leighton, Bruce M. Maggs: Fast Algorithms for Routing Around Faults in Multibutterflies and Randomly-Wired Splitter Networks. IEEE Trans. Computers 41(5): 578-587 (1992)
62		Sandeep N. Bhatt, Fan R. K. Chung, Frank Thomson Leighton, Arnold L. Rosenberg: Efficient Embeddings of Trees in Hypercubes. SIAM J. Comput. 21(1): 151-162 (1992)
61		Frank Thomson Leighton, Mark Newman, Abhiram G. Ranade, Eric J. Schwabe: Dynamic Tree Embeddings in Butterflies and Hypercubes. SIAM J. Comput. 21(4): 639-654 (1992)
60		Lenwood S. Heath, Frank Thomson Leighton, Arnold L. Rosenberg: Comparing Queues and Stacks as Mechanisms for Laying out Graphs. SIAM J. Discrete Math. 5(3): 398-412 (1992)
59		Maria M. Klawe, Frank Thomson Leighton: A Tight Lower Bound on the Size of Planar Permutation Networks. SIAM J. Discrete Math. 5(4): 558-563 (1992)
	1991
58		Frank Thomson Leighton, Yuan Ma, C. Greg Plaxton: Highly Fault-Tolerant Sorting Circuits FOCS 1991: 458-469
57		Frank Thomson Leighton, Eric J. Schwabe: Efficient Algorithms for Dynamic Allocation of Distributed Memory FOCS 1991: 470-479
56		Sandeep N. Bhatt, David S. Greenberg, Frank Thomson Leighton, Pangfeng Liu: Tight Bounds for On-Line Tree Embeddings. SODA 1991: 344-350
55		William Aiello, Frank Thomson Leighton: Coding Theory, Hypercube Embeddings, and Fault Tolerance. SPAA 1991: 125-136
54		Frank Thomson Leighton, Fillia Makedon, Serge A. Plotkin, Clifford Stein, Éva Tardos, Spyros Tragoudas: Fast Approximation Algorithms for Multicommodity Flow Problems STOC 1991: 101-111
53		Andrea S. LaPaugh, Frank Thomson Leighton: Editors' Introduction. Algorithmica 6(1): 1-3 (1991)
52		Frank Thomson Leighton: Letter from the Editor. J. ACM 38(3): 515-515 (1991)
51		William Aiello, Frank Thomson Leighton, Bruce M. Maggs, Mark Newman: Fast Algorithms for Bit-Serial Routing on a Hypercube. Mathematical Systems Theory 24(4): 253-271 (1991)
	1990
50		Frank Thomson Leighton, C. Greg Plaxton: A (fairly) Simple Circuit that (usually) Sorts FOCS 1990: 264-274
49		Christos Kaklamanis, Anna R. Karlin, Frank Thomson Leighton, Victor Milenkovic, Prabhakar Raghavan, Satish Rao, Clark D. Thomborson, A. Tsantilas: Asymptotically Tight Bounds for Computing with Faulty Arrays of Processors (Extended Abstract) FOCS 1990: 285-296
48		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 FOCS 1990: 86-95
47		Dinesh Bhatia, Frank Thomson Leighton, Fillia Makedon: Efficient Reconfiguration of WSI Arrays. ICSI 1990: 47-56
46		Maria M. Klawe, Frank Thomson Leighton: A Tight Lower Bound on the Size of Planar Permutation Networks. SIGAL International Symposium on Algorithms 1990: 281-287
45		Edward G. Coffman Jr., Leopold Flatto, Frank Thomson Leighton: First-Fit Storage of Linear Lists: Tight Probabilistic Bounds on Wasted Space. SODA 1990: 272-279
44		Frank Thomson Leighton: Average Case Analysis of Greedy Routing algorithms on Arrays. SPAA 1990: 2-10
43		William Aiello, Frank Thomson Leighton, Bruce M. Maggs, Mark Newman: Fast Algorithms for Bit-Serial Routing on a Hypercube. SPAA 1990: 55-64
42		Sanjeev Arora, Frank Thomson Leighton, Bruce M. Maggs: On-line Algorithms for Path Selection in a Nonblocking Network (Extended Abstract) STOC 1990: 149-158
41		Alok Aggarwal, Mark Hansen, Frank Thomson Leighton: Solving Query-Retrieval Problems by Compacting Voronoi Diagrams (Extended Abstract) STOC 1990: 331-340
40		Alok Aggarwal, Frank Thomson Leighton: A Tight Lower Bound for the Train Reversal Problem. Inf. Process. Lett. 35(6): 301-304 (1990)
39		Francine Berman, David S. Johnson, Frank Thomson Leighton, Peter W. Shor, Larry Snyder: Generalized Planar Matching. J. Algorithms 11(2): 153-184 (1990)
	1989
38		Thang Nguyen Bui, C. Heigham, Curt Jones, Frank Thomson Leighton: Improving the Performance of the Kernighan-Lin and Simulated Annealing Graph Bisection Algorithms. DAC 1989: 775-778
37		Frank Thomson Leighton, Bruce M. Maggs: Expanders Might Be Practical: Fast Algorithms for Routing Around Faults on Multibutterflies FOCS 1989: 384-389
36		Frank Thomson Leighton, Mark Newman, Abhiram G. Ranade, Eric J. Schwabe: Dynamic Tree Embeddings in Butterflies and Hypercubes. SPAA 1989: 224-234
35		Frank Thomson Leighton, Fillia Makedon, Ioannis G. Tollis: A 2n-2 Step Algorithm for Routing in an nxn Array with Constant Size Queues. SPAA 1989: 328-335
34		Richard R. Koch, Frank Thomson Leighton, Bruce M. Maggs, Satish Rao, Arnold L. Rosenberg: Work-Preserving Emulations of Fixed-Connection Networks (Extended Abstract) STOC 1989: 227-240
33		Johan Håstad, Frank Thomson Leighton, Mark Newman: Fast Computation Using Faulty Hypercubes (Extended Abstract) STOC 1989: 251-263
32		Tom Leighton, Peter W. Shor: Tight bounds for minimax grid matching wit applications to the average case analysis of algorithms. Combinatorica 9(2): 161-187 (1989)
31		Edward G. Coffman Jr., Frank Thomson Leighton: A Provably Efficient Algorithm for Dynamic Storage Allocation. J. Comput. Syst. Sci. 38(1): 2-35 (1989)
30		Sandeep N. Bhatt, Fan R. K. Chung, Frank Thomson Leighton, Arnold L. Rosenberg: Universal Graphs for Bounded-Degree Trees and Planar Graphs. SIAM J. Discrete Math. 2(2): 145-155 (1989)
	1988
29		Larry Finkelstein, Daniel J. Kleitman, Frank Thomson Leighton: Applying the Classification Theorem for Finite Simple Groups to Minimize Pin Count in Uniform Permutation Architectures. AWOC 1988: 247-256
28		Frank Thomson Leighton, Bruce M. Maggs, Satish Rao: Universal Packet Routing Algorithms (Extended Abstract) FOCS 1988: 256-269
27		Frank Thomson Leighton, Satish Rao: An Approximate Max-Flow Min-Cut Theorem for Uniform Multicommodity Flow Problems with Applications to Approximation Algorithms FOCS 1988: 422-431
26		Sandeep N. Bhatt, Fan R. K. Chung, Jia-Wei Hong, Frank Thomson Leighton, Arnold L. Rosenberg: Optimal Simulations by Butterfly Networks (Preliminary Version) STOC 1988: 192-204
	1987
25		Johan Håstad, Frank Thomson Leighton, Brian Rogoff: Analysis of Backoff Protocols for Multiple Access Channels (Extended Abstract) STOC 1987: 241-253
24		Johan Håstad, Frank Thomson Leighton, Mark Newman: Reconfiguring a Hypercube in the Presence of Faults (Extended Abstract) STOC 1987: 274-284
23		Richard M. Karp, Frank Thomson Leighton, Ronald L. Rivest, Clark D. Thompson, Umesh V. Vazirani, Vijay V. Vazirani: Global Wire Routing in Two-Dimensional Arrays. Algorithmica 2: 113-129 (1987)
22		Thang Nguyen Bui, Soma Chaudhuri, Frank Thomson Leighton, Michael Sipser: Graph bisection algorithms with good average case behavior. Combinatorica 7(2): 171-191 (1987)
	1986
21		Sandeep N. Bhatt, Fan R. K. Chung, Frank Thomson Leighton, Arnold L. Rosenberg: Optimal Simulations of Tree Machines (Preliminary Version) FOCS 1986: 274-282
20		Edward G. Coffman Jr., Frank Thomson Leighton: A Provably Efficient Algorithm for Dynamic Storage Allocation STOC 1986: 77-90
19		Frank Thomson Leighton, Peter W. Shor: Tight Bounds for Minimax Grid Matching, With Applications to the Average Case Analysis of Algorithms STOC 1986: 91-103
18		Frank Thomson Leighton, Ronald L. Rivest: Estimating a probability using finite memory. IEEE Transactions on Information Theory 32(6): 733-742 (1986)
17		Frank Thomson Leighton, Arnold L. Rosenberg: Three-Dimensional Circuit Layouts. SIAM J. Comput. 15(3): 793-813 (1986)
	1985
16		Frank Thomson Leighton: Tight Bounds on the Complexity of Parallel Sorting. IEEE Trans. Computers 34(4): 344-354 (1985)
15		Frank Thomson Leighton, Charles E. Leiserson: Wafer-Scale Integration of Systolic Arrays. IEEE Trans. Computers 34(5): 448-461 (1985)
	1984
14		Thang Nguyen Bui, Soma Chaudhuri, Frank Thomson Leighton, Michael Sipser: Graph Bisection Algorithms with Good Average Case Behavior FOCS 1984: 181-192
13		Jon Louis Bentley, David S. Johnson, Frank Thomson Leighton, Catherine C. McGeoch, Lyle A. McGeoch: Some Unexpected Expected Behavior Results for Bin Packing STOC 1984: 279-288
12		Frank Thomson Leighton: Tight Bounds on the Complexity of Parallel Sorting STOC 1984: 71-80
11		Sandeep N. Bhatt, Frank Thomson Leighton: A Framework for Solving VLSI Graph Layout Problems. J. Comput. Syst. Sci. 28(2): 300-343 (1984)
10		Frank Thomson Leighton: New Lower Bound Techniques for VLSI. Mathematical Systems Theory 17(1): 47-70 (1984)
	1983
9		Frank Thomson Leighton, Ronald L. Rivest: Estimating a Probability Using Finite Memory (Extended Abstract). FCT 1983: 255-269
8		Richard M. Karp, Frank Thomson Leighton, Ronald L. Rivest, Clark D. Thompson, Umesh V. Vazirani, Vijay V. Vazirani: Global Wire Routing in Two-Dimensional Arrays (Extended Abstract) FOCS 1983: 453-459
7		Brenda S. Baker, Sandeep N. Bhatt, Frank Thomson Leighton: An Approximation Algorithm for Manhattan Routing (Extended Abstract) STOC 1983: 477-486
6		Daniel J. Kleitman, Frank Thomson Leighton, Margaret Lepley, Gary L. Miller: An Asymptotically Optimal Layout for the Shuffle-Exchange Graph. J. Comput. Syst. Sci. 26(3): 339-361 (1983)
	1982
5		Frank Thomson Leighton, Charles E. Leiserson: Wafer-Scale Integration of Systolic Arrays (Extended Abstract) FOCS 1982: 297-311
4		Frank Thomson Leighton: A Layout Strategy for VLSI which Is Provably Good (Extended Abstract) STOC 1982: 85-98
3		Frank Thomson Leighton: Finite common coverings of graphs. J. Comb. Theory, Ser. B 33(3): 231-238 (1982)
	1981
2		Frank Thomson Leighton: New Lower Bound Techniques for VLSI FOCS 1981: 1-12
1		Daniel J. Kleitman, Frank Thomson Leighton, Margaret Lepley, Gary L. Miller: New Layouts for the Shuffle-Exchange Graph (Extended Abstract) STOC 1981: 278-292

Coauthor Index

1	Micah Adler	[144] [146]
2	Alok Aggarwal	[40] [41]
3	William Aiello	[43] [51] [55] [168]
4	Noga Alon	[181]
5	Matthew Andrews	[108] [109] [112] [122] [130] [143] [147]
6	Sanjeev Arora	[42] [102]
7	Baruch Awerbuch	[73] [75] [81] [86] [106] [112] [147] [161] [167]
8	Yossi Azar	[106]
9	Brenda S. Baker	[7]
10	Jon Louis Bentley	[13]
11	Bonnie Berger	[91] [107] [127] [129] [135]
12	Francine Berman (Fran Berman)	[39]
13	Dinesh Bhatia	[47] [64]
14	Sandeep N. Bhatt	[7] [11] [21] [26] [30] [56] [62] [69] [83] [89] [104] [105] [119] [131]
15	Allan Borodin	[100]
16	Martin L. Brady	[91]
17	Eric A. Brewer	[82] [85]
18	Donna J. Brown	[91]
19	Thang Nguyen Bui	[14] [22] [38]
20	Steve Butler	[173] [176]
21	Moses Charikar	[179] [182]
22	Soma Chaudhuri	[14] [22]
23	Donald D. Chinn	[84] [103]
24	Frederic T. Chong	[82] [85]
25	Andrew Chou	[97]
26	Fan R. K. Chung (Fan Chung Graham)	[21] [26] [30] [62] [69] [83] [89] [104] [105] [119] [149] [151]
27	Edward G. Coffman Jr.	[20] [31] [45] [125]
28	Jeremy R. Cooperstock	[97]
29	Ingemar J. Cox	[110] [118]
30	Erik D. Demaine	[181]
31	Ran El-Yaniv	[97]
32	Antonio Fernández (Antonio Fernández Anta)	[112] [122] [143] [147] [148] [169]
33	Amos Fiat	[106]
34	Larry Finkelstein	[29]
35	Leopold Flatto	[45]
36	Michael Formann	[48] [70]
37	Rainer Gawlick	[86]
38	Bhaskar Ghosh	[93] [132]
39	Leslie Ann Goldberg (Leslie A. Henderson)	[71] [114]
40	Michael T. Goodrich	[88]
41	Ronald L. Graham	[149] [151]
42	David S. Greenberg	[56] [131]
43	Stephen Guattery	[121] [136]
44	Torben Hagerup	[48] [70]
45	Mohammad Taghi Hajiaghayi (MohammadTaghi Hajiaghayi)	[159] [160] [161] [163] [164] [165] [166] [167] [170] [171] [173] [176] [181]
46	Mark Hansen	[41]
47	James Haralambides	[48] [70]
48	Mor Harchol-Balter	[122] [140] [143]
49	Johan Håstad	[24] [25] [33] [101]
50	Lenwood S. Heath	[60]
51	C. Heigham	[38]
52	Jia-Wei Hong	[26] [105]
53	Markus Jakobsson	[157]
54	Mark Jerrum	[71] [114]
55	David S. Johnson	[13] [39]
56	Curt Jones	[38]
57	Nabil Kahale	[94] [96] [125] [128]
58	Christos Kaklamanis	[49]
59	David R. Karger	[120]
60	Anna R. Karlin	[49]
61	Richard M. Karp	[8] [23]
62	Michael Kaufmann	[48] [70]
63	Joe Kilian	[99] [110] [118]
64	Jeong Han Kim	[159]
65	Jin Suk Kim	[141]
66	Maria M. Klawe	[46] [59]
67	Jon M. Kleinberg	[107] [112] [135] [147]
68	Robert D. Kleinberg (Robert Kleinberg)	[155] [156] [160] [161] [164] [165] [166] [167] [170] [171] [173] [176]
69	Daniel J. Kleitman	[1] [6] [29] [87] [115]
70	Michael Klugerman	[97]
71	Thomas F. Knight Jr.	[85]
72	Richard R. Koch	[34] [117]
73	Andrea S. LaPaugh	[53]
74	Lawrence L. Larmore	[142]
75	Eric Lehman	[120] [141]
76	Charles E. Leiserson	[5] [15]
77	Margaret Lepley	[1] [6]
78	Matthew S. Levine	[120]
79	Daniel Lewin	[120] [140]
80	Shi Li	[179] [182]
81	Pangfeng Liu	[56] [131]
82	Zhiyong Liu	[112] [147]
83	José Luis López-Presa	[148] [169]
84	Chi-Jen Lu	[145]
85	Yuan Ma	[58] [72] [74] [87] [94] [95] [113] [115] [116] [133]
86	Bruce M. Maggs	[28] [34] [37] [42] [43] [51] [63] [66] [67] [68] [79] [80] [93] [98] [102] [117] [124] [132] [137]
87	Fillia Makedon	[35] [47] [54] [64] [90] [92]
88	Catherine C. McGeoch	[13]
89	Lyle A. McGeoch	[13]
90	Panagiotis Takis Metaxas	[108] [109] [130]
91	Silvio Micali	[76] [157]
92	Victor J. Milenkovic (Victor Milenkovic)	[49]
93	Gary L. Miller	[1] [6] [121] [136]
94	Ankur Moitra	[175] [178] [179] [180] [182]
95	S. Muthukrishnan (S. Muthu Muthukrishnan)	[93] [132]
96	Mark Newman	[24] [33] [36] [43] [51] [61]
97	Carolyn Haibt Norton	[64]
98	Bojana Obrenic	[105]
99	Rina Panigrahy	[120]
100	C. Greg Plaxton	[50] [58] [93] [94] [116] [126] [132]
101	Serge A. Plotkin	[54] [90]
102	Yuval Rabani	[86]
103	Harald Räcke	[159] [160] [165] [170]
104	Prabhakar Raghavan	[49]
105	Rajmohan Rajaraman	[93] [132]
106	Abhiram G. Ranade	[36] [61] [79]
107	Satish Rao	[27] [28] [34] [49] [71] [79] [80] [114] [117] [134] [139] [145]
108	Andréa W. Richa	[93] [132] [137]
109	Ronald L. Rivest	[8] [9] [18] [23]
110	Brian Rogoff	[25] [101]
111	Arnold L. Rosenberg	[17] [21] [26] [30] [34] [60] [62] [69] [83] [89] [104] [105] [117] [119]
112	Eric J. Schwabe	[36] [57] [61] [105] [117] [138]
113	Talal Shamoon	[110] [118]
114	Peter W. Shor	[19] [32] [39] [123]
115	Michael Sipser	[14] [22]
116	Ramesh K. Sitaraman	[68] [124]
117	Lawrence Snyder (Larry Snyder)	[39]
118	Aravind Srinivasan	[139] [145]
119	Clifford Stein	[54] [90]
120	Éva Stein	[90]
121	Torsten Suel	[94] [95] [113]
122	Antonios Symvonis	[48] [70]
123	Endre Szemerédi	[94]
124	Michael Szydlo	[157]
125	Éva Tardos	[54]
126	Robert Endre Tarjan	[93] [132]
127	Clark D. Thomborson (Clark D. Thompson)	[8] [23] [49]
128	Ioannis G. Tollis	[35] [92]
129	Martin Tompa	[84] [103]
130	Spyros Tragoudas	[54] [90]
131	A. Tsantilas	[49]
132	Umesh V. Vazirani	[8] [23]
133	Vijay V. Vazirani	[8] [23]
134	Jeffrey Scott Vitter	[142]
135	Emo Welzl	[48] [70]
136	Gerhard J. Woeginger	[48] [70]
137	Lisa Zhang	[108] [109] [122] [130] [143]
138	David Zuckerman	[93] [132]

Colors in the list of coauthors

Last update Fri Jun 1 15:44:53 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page