dblp.uni-trier.dewww.uni-trier.de

Frank Thomson Leighton

Tom Leighton

List of publications from the DBLP Bibliography Server - FAQ
Coauthor Index - Ask others: ACM DL/Guide - CiteSeer - CSB - Google - MSN - Yahoo
Home Page

2009
171EETom Leighton: Improving performance on the internet. Commun. ACM 52(2): 44-51 (2009)
2008
170EEAnkur Moitra, Tom Leighton: Some Results on Greedy Embeddings in Metric Spaces. FOCS 2008: 337-346
169EESteve Butler, Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, Tom Leighton: Hat Guessing Games. SIAM J. Discrete Math. 22(2): 592-605 (2008)
2007
168EETom Leighton: The Akamai approach to achieving performance and reliability on the internet. PODC 2007: 2
167EEMohammad Taghi Hajiaghayi, Robert Kleinberg, Tom Leighton: Semi-oblivious routing: lower bounds. SODA 2007: 929-938
166EEMohammad 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)
165EEAntonio Fernández, Tom Leighton, José Luis López-Presa: Containment properties of product and power graphs. Discrete Applied Mathematics 155(3): 300-311 (2007)
164EEWilliam Aiello, Frank Thomson Leighton: Hamming Codes, Hypercube Embeddings, and Fault Tolerance. SIAM J. Comput. 37(3): 783-803 (2007)
163EEBaruch 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
162EEMohammad Taghi Hajiaghayi, Robert D. Kleinberg, Frank Thomson Leighton: Improved lower and upper bounds for universal TSP in planar metrics. SODA 2006: 649-658
161EEMohammad Taghi Hajiaghayi, Robert D. Kleinberg, Frank Thomson Leighton, Harald Räcke: New lower bounds for oblivious routing in undirected graphs. SODA 2006: 918-927
160EEMohammad Taghi Hajiaghayi, Robert D. Kleinberg, Tom Leighton: Semi-oblivious routing. SPAA 2006: 234
159EEMohammad 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
158 Frank Thomson Leighton: The Challenges of Delivering Content and Applications on the Internet. NSDI 2005
157EEBaruch Awerbuch, Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, Tom Leighton: Online client-server load balancing without global information. SODA 2005: 197-206
156EEMohammad Taghi Hajiaghayi, Robert D. Kleinberg, Tom Leighton, Harald Räcke: Oblivious routing on node-capacitated and directed graphs. SODA 2005: 782-790
155EEMohammad Taghi Hajiaghayi, Jeong Han Kim, Tom Leighton, Harald Räcke: Oblivious routing in directed graphs with random demands. STOC 2005: 193-201
2004
154EEFrank Thomson Leighton: The Challenges of Delivering Content and Applications on the Internet. RIDE 2004: 65
2003
153EEMarkus Jakobsson, Frank Thomson Leighton, Silvio Micali, Michael Szydlo: Fractal Merkle Tree Representation and Traversal. CT-RSA 2003: 314-326
152EERobert D. Kleinberg, Frank Thomson Leighton: The Value of Knowing a Demand Curve: Bounds on Regret for Online Posted-Price Auctions. FOCS 2003: 594-605
151EERobert D. Kleinberg, Frank Thomson Leighton: Consistent load balancing via spread minimization. STOC 2003: 565-574
150EEFrank Thomson Leighton: JACM 1991-1997. J. ACM 50(1): 19 (2003)
2001
149EEFrank Thomson Leighton: The Challenges of Delivering Content on the Internet. NCA 2001: 214
148EEFrank Thomson Leighton: The Challenges of Delivering Content on the Internet. PODS 2001
147EEFan R. K. Chung, Ronald L. Graham, Frank Thomson Leighton: Guessing secrets. SODA 2001: 723-726
146EEFrank Thomson Leighton: The Challenges of Delivering Content on the Internet. WADS 2001: 338
145EEFan R. K. Chung, Ronald L. Graham, Frank Thomson Leighton: Guessing Secrets. Electr. J. Comb. 8(1): (2001)
144EEAntonio 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)
143EEMatthew 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)
142 Micah Adler, Frank Thomson Leighton: Compression Using Efficient Multicasting. J. Comput. Syst. Sci. 63(1): 127-145 (2001)
141EEFrank 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
140EEMicah Adler, Frank Thomson Leighton: Compression using efficient multicasting. STOC 2000: 153-162
139EEMatthew 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
138EEJin Suk Kim, Eric Lehman, Frank Thomson Leighton: Oblivious Deadlock-Free Routing in a Faulty Hypercube. IPPS/SPDP 1999: 312-319
137EEMor Harchol-Balter, Frank Thomson Leighton, Daniel Lewin: Resource Discovery in Distributed Networks. PODC 1999: 229-237
136EEFrank Thomson Leighton, Satish Rao, Aravind Srinivasan: New Algorithmic Aspects of the Local Lemma with Applications to Routing and Partitioning. SODA 1999: 643-652
135EEFrank Thomson Leighton, Eric J. Schwabe: Efficient Algorithms for Dynamic Allocation of Distributed Memo. Algorithmica 24(2): 139-171 (1999)
134EEFrank 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)
133 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): (1999)
132EEBonnie Berger, Jon M. Kleinberg, Frank Thomson Leighton: Reconstructing a Three-Dimensional Model with Arbitrary Errors. J. ACM 46(2): 212-235 (1999)
131EEFrank Thomson Leighton, Satish Rao: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM 46(6): 787-832 (1999)
130 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)
129 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)
128 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)
127 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
126EEBonnie Berger, Frank Thomson Leighton: Protein folding in the hydrophobic-hydrophilic (HP) is NP-complete. RECOMB 1998: 30-39
125 Nabil Kahale, Frank Thomson Leighton: Greedy Dynamic Routing on Arrays. J. Algorithms 29(2): 390-410 (1998)
124 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)
123 Frank Thomson Leighton, C. Greg Plaxton: Hypercubic Sorting Networks. SIAM J. Comput. 27(1): 1-47 (1998)
122EEEdward 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)
121EEFrank 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
120EEMatthew 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
119 Stephen Guattery, Frank Thomson Leighton, Gary L. Miller: The Path Resistance Method for Bounding lambda2 of a Laplacian. SODA 1997: 201-210
118EEDavid 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
117 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)
116EEIngemar 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)
115EERichard 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)
114 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)
113 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)
112 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)
111 Frank Thomson Leighton, Yuan Ma, Torsten Suel: On Probabilistic Networks for Selection, Merging, and Sorting. Theory Comput. Syst. 30(6): 559-582 (1997)
1996
110 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
109 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
108 Ingemar J. Cox, Joe Kilian, Frank Thomson Leighton, Talal Shamoon: A Secure, Robust Watermark for Multimedia. Information Hiding 1996: 185-206
107 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
106EEMatthew Andrews, Frank Thomson Leighton, Panagiotis Takis Metaxas, Lisa Zhang: Automatic Methods for Hiding Latency in High Bandwidth Networks (Extended Abstract). STOC 1996: 257-265
105EEBonnie Berger, Jon M. Kleinberg, Frank Thomson Leighton: Reconstructing a Three-Dimensional Model with Arbitrary Errors. STOC 1996: 449-458
104EEBaruch 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
103EESandeep 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)
102 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)
101 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)
100 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)
99 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
98EEJoe Kilian, Frank Thomson Leighton: Fair Cryptosystems, Revisited: A Rigorous Approach to Key-Escrow (Extended Abstract). CRYPTO 1995: 208-221
97EEFrank Thomson Leighton, Bruce M. Maggs: Fast algorithms for finding O(congestion+dilation) packet routing schedules. HICSS (2) 1995: 555-563
96 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
95 Nabil Kahale, Frank Thomson Leighton: Greedy Dynamic Routing on Arrays. SODA 1995: 558-566
94EEFrank Thomson Leighton, Yuan Ma, Torsten Suel: On Probabilistic Networks for Selection, Merging, and Sorting. SPAA 1995: 106-118
93EENabil Kahale, Frank Thomson Leighton, Yuan Ma, C. Greg Plaxton, Torsten Suel, Endre Szemerédi: Lower bounds for sorting networks. STOC 1995: 437-446
92EEBhaskar 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
91 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)
90EEBonnie 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)
89 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)
88EESandeep 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
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
84EEDonald D. Chinn, Frank Thomson Leighton, Martin Tompa: Minimal Adaptive Routing on the Mesh with Bounded Queue Size. SPAA 1994: 354-363
83EESandeep 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
82EEEric A. Brewer, Frederic T. Chong, Tom Leighton: Scalable expanders: exploiting hierarchical random wiring. STOC 1994: 144-152
81EEBaruch 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)
78EEFrank 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
76EEFrank 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
72EEFrank Thomson Leighton, Yuan Ma: Tight Bounds on the Size of Fault-Tolerant Merging and Sorting Networks With Destructive Faults. SPAA 1993: 30-41
71EELeslie 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
55EEWilliam 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
44EEFrank Thomson Leighton: Average Case Analysis of Greedy Routing algorithms on Arrays. SPAA 1990: 2-10
43EEWilliam 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
38EEThang 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
36EEFrank Thomson Leighton, Mark Newman, Abhiram G. Ranade, Eric J. Schwabe: Dynamic Tree Embeddings in Butterflies and Hypercubes. SPAA 1989: 224-234
35EEFrank 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
3EEFrank 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

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

Colors in the list of coauthors

Copyright © Sun May 17 03:24:02 2009 by Michael Ley (ley@uni-trier.de)