Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDFrank Thomson Leighton
Tom Leighton
Person information
- affiliation: MIT, Cambridge, US
- award: National Inventors Hall of Fame
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
Journal Articles
- 2014
[j80]Noga Alon, Erik D. Demaine, MohammadTaghi Hajiaghayi, Panagiotis Kanellopoulos
, Tom Leighton:
Correction: Basic Network Creation Games. SIAM J. Discret. Math. 28(3): 1638-1640 (2014)- 2013
- [j79]Noga Alon, Erik D. Demaine, Mohammad Taghi Hajiaghayi, Tom Leighton:
Basic Network Creation Games. SIAM J. Discret. Math. 27(2): 656-668 (2013) - 2010
- [j78]Tom Leighton, Ankur Moitra:
Some Results on Greedy Embeddings in Metric Spaces. Discret. Comput. Geom. 44(3): 686-705 (2010) - 2009
- [j77]Tom Leighton:
Improving performance on the internet. Commun. ACM 52(2): 44-51 (2009) - [j76]Steve Butler, Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, Tom Leighton:
Hat Guessing Games. SIAM Rev. 51(2): 399-413 (2009) - 2008
- [j75]Tom Leighton:
Improving Performance on the Internet. ACM Queue 6(6): 20-29 (2008) - [j74]Steve Butler, Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, Tom Leighton:
Hat Guessing Games. SIAM J. Discret. Math. 22(2): 592-605 (2008) - 2007
- [j73]Antonio Fernández, Tom Leighton, José Luis López-Presa:
Containment properties of product and power graphs. Discret. Appl. Math. 155(3): 300-311 (2007) - [j72]William Aiello, Frank Thomson Leighton:
Hamming Codes, Hypercube Embeddings, and Fault Tolerance. SIAM J. Comput. 37(3): 783-803 (2007) - [j71]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) - [j70]Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, Harald Räcke, Tom Leighton:
Oblivious routing on node-capacitated and directed graphs. ACM Trans. Algorithms 3(4): 51 (2007) - 2006
- [j69]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) - 2003
- [j68]Frank Thomson Leighton:
JACM 1991-1997. J. ACM 50(1): 19 (2003) - 2001
- [j67]Fan R. K. Chung, Ronald L. Graham, Frank Thomson Leighton:
Guessing Secrets. Electron. J. Comb. 8(1) (2001) - [j66]Antonio Fernández, Tom Leighton, José Luis López-Presa:
Containment Properties of Product and Power Graphs. Electron. Notes Discret. Math. 7: 46-49 (2001) - [j65]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) - [j64]Micah Adler, Frank Thomson Leighton:
Compression Using Efficient Multicasting. J. Comput. Syst. Sci. 63(1): 127-145 (2001) - [j63]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
- [j62]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
- [j61]Frank Thomson Leighton, Eric J. Schwabe:
Efficient Algorithms for Dynamic Allocation of Distributed Memo. Algorithmica 24(2): 139-171 (1999) - [j60]Frank Thomson Leighton, Bruce M. Maggs, Andréa W. Richa:
Fast Algorithms for Finding O(Congestion + Dilation) Packet Routing Schedules. Comb. 19(3): 375-401 (1999) - [j59]Stephen Guattery, Frank Thomson Leighton, Gary L. Miller:
The Path Resistance Method For Bounding The Smallest Nontrivial Eigenvalue Of A Laplacian. Comb. Probab. Comput. 8(5): 441-460 (1999) - [j58]Bonnie Berger, Jon M. Kleinberg, Frank Thomson Leighton:
Reconstructing a Three-Dimensional Model with Arbitrary Errors. J. ACM 46(2): 212-235 (1999) - [j57]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) - [j56]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) - [j55]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) - [j54]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) - [j53]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
- [j52]Nabil Kahalé, Frank Thomson Leighton:
Greedy Dynamic Routing on Arrays. J. Algorithms 29(2): 390-410 (1998) - [j51]Bonnie Berger, Frank Thomson Leighton:
Protein Folding in the Hydrophobic-Hydrophilic(HP) Model is NP-Complete. J. Comput. Biol. 5(1): 27-40 (1998) - [j50]Frank Thomson Leighton, C. Greg Plaxton:
Hypercubic Sorting Networks. SIAM J. Comput. 27(1): 1-47 (1998) - [j49]Edward G. Coffman Jr., Nabil Kahalé, Frank Thomson Leighton:
Processor-Ring Communication: A Tight Asymptotic Bound on Packet Waiting Times. SIAM J. Comput. 27(5): 1221-1236 (1998) - [j48]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
- [j47]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) - [j46]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) - [j45]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) - [j44]Frank Thomson Leighton, Yuan Ma, Torsten Suel:
On Probabilistic Networks for Selection, Merging, and Sorting. Theory Comput. Syst. 30(6): 559-582 (1997) - [j43]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) - [j42]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) - [j41]Ingemar J. Cox, Joe Kilian, Frank Thomson Leighton, Talal Shamoon:
Secure spread spectrum watermarking for multimedia. IEEE Trans. Image Process. 6(12): 1673-1687 (1997) - 1996
- [j40]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) - [j39]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 Distributed Comput. 33(1): 55-68 (1996) - [j38]Donald D. Chinn, Frank Thomson Leighton, Martin Tompa:
Minimal Adaptive Routing on the Mesh with Bounded Queue Size. J. Parallel Distributed Comput. 34(2): 154-170 (1996) - [j37]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) - [j36]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
- [j35]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) - [j34]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) - [j33]Frank Thomson Leighton, Fillia Makedon, Serge A. Plotkin, Clifford Stein, Éva Tardos, Spyros Tragoudas:
Fast Approximation Algorithms for Multicommodity Flow Problems. J. Comput. Syst. Sci. 50(2): 228-243 (1995) - [j32]Sandeep N. Bhatt, Fan R. K. Chung, Frank Thomson Leighton, Arnold L. Rosenberg:
Salvage-Embeddings of Complete Trees. SIAM J. Discret. Math. 8(4): 617-637 (1995) - 1994
- [j31]Frank Thomson Leighton, Bruce M. Maggs, Satish Rao:
Packet Routing and Job-Shop Scheduling in O(Congestion + Dilation) Steps. Comb. 14(2): 167-186 (1994) - [j30]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) - [j29]Frank Thomson Leighton:
A 2d-1 Lower Bound for Two-Layer Knock-Knee Channel Routing. SIAM J. Discret. Math. 7(2): 230-237 (1994) - [j28]Keith Nabors, F. T. Korsmeyer, Frank Thomson Leighton, Jacob K. White:
Preconditioned, Adaptive, Multipole-Accelerated Iterative Methods for Three-Dimensional First-Kind Integral Equations of Potential Theory. SIAM J. Sci. Comput. 15(3): 713-735 (1994) - [j27]Frank Thomson Leighton:
Methods for Message Routing in Parallel Machines. Theor. Comput. Sci. 128(1&2): 31-62 (1994) - 1993
- [j26]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
- [j25]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) - [j24]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) - [j23]Lenwood S. Heath, Frank Thomson Leighton, Arnold L. Rosenberg:
Comparing Queues and Stacks as Mechanisms for Laying out Graphs. SIAM J. Discret. Math. 5(3): 398-412 (1992) - [j22]Maria M. Klawe, Frank Thomson Leighton:
A Tight Lower Bound on the Size of Planar Permutation Networks. SIAM J. Discret. Math. 5(4): 558-563 (1992) - [j21]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) - 1991
- [j20]Andrea S. LaPaugh, Frank Thomson Leighton:
Editors' Introduction. Algorithmica 6(1): 1-3 (1991) - [j19]Frank Thomson Leighton:
Letter from the Editor. J. ACM 38(3): 515-515 (1991) - [j18]William Aiello, Frank Thomson Leighton, Bruce M. Maggs, Mark Newman:
Fast Algorithms for Bit-Serial Routing on a Hypercube. Math. Syst. Theory 24(4): 253-271 (1991) - [j17]Frank Thomson Leighton:
Selected Papers from the Symposium on Parallel Algorithms and Architectures. SIGARCH Comput. Archit. News 19(1): 5 (1991) - 1990
- [j16]Alok Aggarwal, Frank Thomson Leighton:
A Tight Lower Bound for the Train Reversal Problem. Inf. Process. Lett. 35(6): 301-304 (1990) - [j15]Francine Berman, David S. Johnson, Frank Thomson Leighton, Peter W. Shor, Larry Snyder:
Generalized Planar Matching. J. Algorithms 11(2): 153-184 (1990) - 1989
- [j14]Jon Louis Bentley, Frank Thomson Leighton, Margaret Lepley, Donald F. Stanat, J. Michael Steele:
A Randomized Data Structure for Ordered Sets. Adv. Comput. Res. 5: 413-428 (1989) - [j13]Tom Leighton, Peter W. Shor:
Tight bounds for minimax grid matching wit applications to the average case analysis of algorithms. Comb. 9(2): 161-187 (1989) - [j12]Edward G. Coffman Jr., Frank Thomson Leighton:
A Provably Efficient Algorithm for Dynamic Storage Allocation. J. Comput. Syst. Sci. 38(1): 2-35 (1989) - [j11]Sandeep N. Bhatt, Fan R. K. Chung, Frank Thomson Leighton, Arnold L. Rosenberg:
Universal Graphs for Bounded-Degree Trees and Planar Graphs. SIAM J. Discret. Math. 2(2): 145-155 (1989) - 1987
- [j10]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) - [j9]Thang Nguyen Bui, Soma Chaudhuri, Frank Thomson Leighton, Michael Sipser:
Graph bisection algorithms with good average case behavior. Comb. 7(2): 171-191 (1987) - 1986
- [j8]Frank Thomson Leighton, Arnold L. Rosenberg:
Three-Dimensional Circuit Layouts. SIAM J. Comput. 15(3): 793-813 (1986) - [j7]Frank Thomson Leighton, Ronald L. Rivest:
Estimating a probability using finite memory. IEEE Trans. Inf. Theory 32(6): 733-742 (1986) - 1985
- [j6]Frank Thomson Leighton:
Tight Bounds on the Complexity of Parallel Sorting. IEEE Trans. Computers 34(4): 344-354 (1985) - [j5]Frank Thomson Leighton, Charles E. Leiserson:
Wafer-Scale Integration of Systolic Arrays. IEEE Trans. Computers 34(5): 448-461 (1985) - 1984
- [j4]Sandeep N. Bhatt, Frank Thomson Leighton:
A Framework for Solving VLSI Graph Layout Problems. J. Comput. Syst. Sci. 28(2): 300-343 (1984) - [j3]Frank Thomson Leighton:
New Lower Bound Techniques for VLSI. Math. Syst. Theory 17(1): 47-70 (1984) - 1983
- [j2]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
- [j1]Frank Thomson Leighton:
Finite common coverings of graphs. J. Comb. Theory B 33(3): 231-238 (1982)
Conference and Workshop Papers
- 2010
- [c107]Moses Charikar, Tom Leighton, Shi Li, Ankur Moitra:
Vertex Sparsifiers and Abstract Rounding Algorithms. FOCS 2010: 265-274 - [c106]Noga Alon, Erik D. Demaine, MohammadTaghi Hajiaghayi, Tom Leighton:
Basic network creation games. SPAA 2010: 106-113 - [c105]Frank Thomson Leighton, Ankur Moitra:
Extensions and limits to vertex sparsification. STOC 2010: 47-56 - 2008
- [c104]Ankur Moitra, Tom Leighton:
Some Results on Greedy Embeddings in Metric Spaces. FOCS 2008: 337-346 - 2007
- [c103]Tom Leighton:
The Akamai approach to achieving performance and reliability on the internet. PODC 2007: 2 - [c102]Mohammad Taghi Hajiaghayi, Robert Kleinberg, Tom Leighton:
Semi-oblivious routing: lower bounds. SODA 2007: 929-938 - 2006
- [c101]Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, Frank Thomson Leighton:
Improved lower and upper bounds for universal TSP in planar metrics. SODA 2006: 649-658 - [c100]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 - [c99]Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, Tom Leighton:
Semi-oblivious routing. SPAA 2006: 234 - 2005
- [c98]Frank Thomson Leighton:
The Challenges of Delivering Content and Applications on the Internet. NSDI 2005 - [c97]Baruch Awerbuch, Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, Tom Leighton:
Online client-server load balancing without global information. SODA 2005: 197-206 - [c96]Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, Tom Leighton, Harald Räcke:
Oblivious routing on node-capacitated and directed graphs. SODA 2005: 782-790 - [c95]Mohammad Taghi Hajiaghayi, Jeong Han Kim, Tom Leighton, Harald Räcke:
Oblivious routing in directed graphs with random demands. STOC 2005: 193-201 - 2004
- [c94]Frank Thomson Leighton:
The Challenges of Delivering Content and Applications on the Internet. RIDE 2004: 65 - 2003
- [c93]Markus Jakobsson, Frank Thomson Leighton, Silvio Micali, Michael Szydlo:
Fractal Merkle Tree Representation and Traversal. CT-RSA 2003: 314-326 - [c92]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 - [c91]Robert D. Kleinberg, Frank Thomson Leighton:
Consistent load balancing via spread minimization. STOC 2003: 565-574 - 2001
- [c90]Frank Thomson Leighton:
The Challenges of Delivering Content on the Internet. NCA 2001: 214 - [c89]Frank Thomson Leighton:
The Challenges of Delivering Content on the Internet. PODS 2001 - [c88]Fan R. K. Chung, Ronald L. Graham, Frank Thomson Leighton:
Guessing secrets. SODA 2001: 723-726 - [c87]Frank Thomson Leighton:
The Challenges of Delivering Content on the Internet. WADS 2001: 338 - 2000
- [c86]Micah Adler, Frank Thomson Leighton:
Compression using efficient multicasting. STOC 2000: 153-162 - 1999
- [c85]Jin Suk Kim, Eric Lehman, Frank Thomson Leighton:
Oblivious Deadlock-Free Routing in a Faulty Hypercube. IPPS/SPDP 1999: 312-319 - [c84]Mor Harchol-Balter, Frank Thomson Leighton, Daniel Lewin:
Resource Discovery in Distributed Networks. PODC 1999: 229-237 - [c83]Frank Thomson Leighton, Satish Rao, Aravind Srinivasan:
New Algorithmic Aspects of the Local Lemma with Applications to Routing and Partitioning. SODA 1999: 643-652 - 1998
- [c82]Tom Leighton, Satish Rao, Aravind Srinivasan:
Multicommodity Flow and Circuit Switching. HICSS (7) 1998: 459-465 - [c81]Bonnie Berger, Frank Thomson Leighton:
Protein folding in the hydrophobic-hydrophilic (HP) is NP-complete. RECOMB 1998: 30-39 - 1997
- [c80]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 - [c79]Stephen Guattery, Frank Thomson Leighton, Gary L. Miller:
The Path Resistance Method for Bounding lambda2 of a Laplacian. SODA 1997: 201-210 - [c78]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 - 1996
- [c77]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 - [c76]Ingemar J. Cox, Joe Kilian, Tom Leighton, Talal Shamoon:
Secure spread spectrum watermarking for images, audio and video. ICIP (3) 1996: 243-246 - [c75]Ingemar J. Cox, Joe Kilian, Frank Thomson Leighton, Talal Shamoon:
A Secure, Robust Watermark for Multimedia. Information Hiding 1996: 185-206 - [c74]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 - [c73]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 - [c72]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 - [c71]Bonnie Berger, Jon M. Kleinberg, Frank Thomson Leighton:
Reconstructing a Three-Dimensional Model with Arbitrary Errors. STOC 1996: 449-458 - [c70]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 - 1995
- [c69]Joe Kilian, Frank Thomson Leighton:
Fair Cryptosystems, Revisited: A Rigorous Approach to Key-Escrow (Extended Abstract). CRYPTO 1995: 208-221 - [c68]Frank Thomson Leighton, Bruce M. Maggs:
Fast algorithms for finding O(congestion+dilation) packet routing schedules. HICSS (2) 1995: 555-563 - [c67]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 - [c66]Nabil Kahalé, Frank Thomson Leighton:
Greedy Dynamic Routing on Arrays. SODA 1995: 558-566 - [c65]Frank Thomson Leighton, Yuan Ma, Torsten Suel:
On Probabilistic Networks for Selection, Merging, and Sorting. SPAA 1995: 106-118 - [c64]Nabil Kahalé, Frank Thomson Leighton, Yuan Ma, C. Greg Plaxton, Torsten Suel, Endre Szemerédi:
Lower bounds for sorting networks. STOC 1995: 437-446 - [c63]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 - 1994
- [c62]Daniel J. Kleitman, Frank Thomson Leighton, Yuan Ma:
On the Design of Reliable Boolean Circuits that Contain Partially Unreliable Gates. FOCS 1994: 332-346 - [c61]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 - [c60]Frederic T. Chong, Eric A. Brewer, Frank Thomson Leighton, Thomas F. Knight Jr.:
Building a better butterfly: the multiplexed metabutterfly. ISPAN 1994: 65-72 - [c59]Frederic T. Chong, Eric A. Brewer, Frank Thomson Leighton, Thomas F. Knight Jr.:
Packaging and Multiplexing of Hierarchical Scalable Expanders. PCRCW 1994: 200-214 - [c58]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 - [c57]Donald D. Chinn, Frank Thomson Leighton, Martin Tompa:
Minimal Adaptive Routing on the Mesh with Bounded Queue Size. SPAA 1994: 354-363 - [c56]Eric A. Brewer, Frederic T. Chong, Tom Leighton:
Scalable expanders: exploiting hierarchical random wiring. STOC 1994: 144-152 - [c55]Baruch Awerbuch, Tom Leighton:
Improved approximation algorithms for the multi-commodity flow problem and local competitive routing in dynamic networks. STOC 1994: 487-496 - 1993
- [c54]Frank Thomson Leighton, Silvio Micali:
Secret-Key Agreement without Public-Key Cryptography. CRYPTO 1993: 456-479 - [c53]Baruch Awerbuch, Frank Thomson Leighton:
A Simple Local-Control Approximation Algorithm for Multicommodity Flow. FOCS 1993: 459-468 - [c52]Frank Thomson Leighton, Yuan Ma:
Breaking the Theta(n log ^2 n) Barrier for Sorting with Faults (Extended Abstract). FOCS 1993: 734-743 - [c51]Baruch Awerbuch, Frank Thomson Leighton:
Multicommodity Flows: A Survey of Recent Research. ISAAC 1993: 297-302 - [c50]Frank Thomson Leighton, Yuan Ma:
Tight Bounds on the Size of Fault-Tolerant Merging and Sorting Networks With Destructive Faults. SPAA 1993: 30-41 - [c49]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 - 1992
- [c48]Sandeep N. Bhatt, Fan R. K. Chung, Frank Thomson Leighton, Arnold L. Rosenberg:
Tolerating Faults in Synchronization Networks. CONPAR 1992: 1-12 - [c47]Frank Thomson Leighton, Bruce M. Maggs, Ramesh K. Sitaraman:
On the Fault Tolerance of Some Popular Bounded-Degree Networks. FOCS 1992: 542-552 - [c46]Frank Thomson Leighton, Bruce M. Maggs:
The Role of Randomness in the Design of Interconnection Networks. IFIP Congress (1) 1992: 291-305 - [c45]Frank Thomson Leighton, Bruce M. Maggs:
The Role of Randomness in the Design of Interconnection Networks. Heinz Nixdorf Symposium 1992: 131-145 - [c44]Frank Thomson Leighton:
Methods for Message Routing in Parallel Machines. STOC 1992: 77-96 - [c43]Dinesh Bhatia, Frank Thomson Leighton, Fillia Makedon, Carolyn Haibt Norton:
Improved Algorithms for Routing on Two-Dimensional Grids. WG 1992: 114-122 - 1991
- [c42]Frank Thomson Leighton, Yuan Ma, C. Greg Plaxton:
Highly Fault-Tolerant Sorting Circuits. FOCS 1991: 458-469 - [c41]Frank Thomson Leighton, Eric J. Schwabe:
Efficient Algorithms for Dynamic Allocation of Distributed Memory. FOCS 1991: 470-479 - [c40]Sandeep N. Bhatt, David S. Greenberg, Frank Thomson Leighton, Pangfeng Liu:
Tight Bounds for On-Line Tree Embeddings. SODA 1991: 344-350 - [c39]William Aiello, Frank Thomson Leighton:
Coding Theory, Hypercube Embeddings, and Fault Tolerance. SPAA 1991: 125-136 - [c38]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 - 1990
- [c37]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 - [c36]Frank Thomson Leighton, C. Greg Plaxton:
A (fairly) Simple Circuit that (usually) Sorts. FOCS 1990: 264-274 - [c35]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 - [c34]Tom Leighton, Derek Linsinski, Bruce M. Maggs:
Empirical evaluation of randomly-wire multistage networks. ICCD 1990: 380-385 - [c33]Dinesh Bhatia, Frank Thomson Leighton, Fillia Makedon:
Efficient Reconfiguration of WSI Arrays. ICSI 1990: 47-56 - [c32]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 - [c31]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 - [c30]Frank Thomson Leighton:
Average Case Analysis of Greedy Routing algorithms on Arrays. SPAA 1990: 2-10 - [c29]William Aiello, Frank Thomson Leighton, Bruce M. Maggs, Mark Newman:
Fast Algorithms for Bit-Serial Routing on a Hypercube. SPAA 1990: 55-64 - [c28]Sanjeev Arora, Frank Thomson Leighton, Bruce M. Maggs:
On-line Algorithms for Path Selection in a Nonblocking Network (Extended Abstract). STOC 1990: 149-158 - [c27]Alok Aggarwal, Mark Hansen, Frank Thomson Leighton:
Solving Query-Retrieval Problems by Compacting Voronoi Diagrams (Extended Abstract). STOC 1990: 331-340 - 1989
- [c26]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 - [c25]Frank Thomson Leighton, Bruce M. Maggs:
Expanders Might Be Practical: Fast Algorithms for Routing Around Faults on Multibutterflies. FOCS 1989: 384-389 - [c24]Frank Thomson Leighton, Mark Newman, Abhiram G. Ranade, Eric J. Schwabe:
Dynamic Tree Embeddings in Butterflies and Hypercubes. SPAA 1989: 224-234 - [c23]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 - [c22]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 - [c21]Johan Håstad, Frank Thomson Leighton, Mark Newman:
Fast Computation Using Faulty Hypercubes (Extended Abstract). STOC 1989: 251-263 - 1988
- [c20]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 - [c19]Frank Thomson Leighton, Bruce M. Maggs, Satish Rao:
Universal Packet Routing Algorithms (Extended Abstract). FOCS 1988: 256-269 - [c18]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 - [c17]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
- [c16]Johan Håstad, Frank Thomson Leighton, Brian Rogoff:
Analysis of Backoff Protocols for Multiple Access Channels (Extended Abstract). STOC 1987: 241-253 - [c15]Johan Håstad, Frank Thomson Leighton, Mark Newman:
Reconfiguring a Hypercube in the Presence of Faults (Extended Abstract). STOC 1987: 274-284 - 1986
- [c14]Sandeep N. Bhatt, Fan R. K. Chung, Frank Thomson Leighton, Arnold L. Rosenberg:
Optimal Simulations of Tree Machines (Preliminary Version). FOCS 1986: 274-282 - [c13]Edward G. Coffman Jr., Frank Thomson Leighton:
A Provably Efficient Algorithm for Dynamic Storage Allocation. STOC 1986: 77-90 - [c12]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 - 1984
- [c11]Thang Nguyen Bui, Soma Chaudhuri, Frank Thomson Leighton, Michael Sipser:
Graph Bisection Algorithms with Good Average Case Behavior. FOCS 1984: 181-192 - [c10]Frank Thomson Leighton:
Tight Bounds on the Complexity of Parallel Sorting. STOC 1984: 71-80 - [c9]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 - 1983
- [c8]Frank Thomson Leighton, Ronald L. Rivest:
Estimating a Probability Using Finite Memory (Extended Abstract). FCT 1983: 255-269 - [c7]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 - [c6]Brenda S. Baker, Sandeep N. Bhatt, Frank Thomson Leighton:
An Approximation Algorithm for Manhattan Routing (Extended Abstract). STOC 1983: 477-486 - [c5]Tom Leighton:
Parallel Computation Using Meshes of Trees. WG 1983: 200-218 - 1982
- [c4]Frank Thomson Leighton, Charles E. Leiserson:
Wafer-Scale Integration of Systolic Arrays (Extended Abstract). FOCS 1982: 297-311 - [c3]Frank Thomson Leighton:
A Layout Strategy for VLSI which Is Provably Good (Extended Abstract). STOC 1982: 85-98 - 1981
- [c2]Frank Thomson Leighton:
New Lower Bound Techniques for VLSI. FOCS 1981: 1-12 - [c1]Daniel J. Kleitman, Frank Thomson Leighton, Margaret Lepley, Gary L. Miller:
New Layouts for the Shuffle-Exchange Graph (Extended Abstract). STOC 1981: 278-292
Editorship
- 1999
- [e7]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, ISBN 1-58113-067-8 [contents] - 1997
- [e6]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, ISBN 0-89791-888-6 [contents] - 1995
- [e5]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, ISBN 0-89791-718-9 [contents] - 1994
- [e4]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, ISBN 0-89791-663-8 [contents] - 1991
- [e3]Tom Leighton:
Proceedings of the 3rd Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA '91, Hilton Head, South Carolina, USA, July 21-24, 1991. ACM 1991, ISBN 0-89791-438-4 [contents] - 1990
- [e2]Frank Thomson Leighton:
Proceedings of the 2nd Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA '90, Island of Crete, Greece, July 2-6, 1990. ACM 1990, ISBN 0-89791-370-1 [contents] - 1989
- [e1]Frank Thomson Leighton:
Proceedings of the ACM Symposium on Parallel Algorithms and Architectures, SPAA '89, Santa Fe, New Mexico, USA, June 18-21, 1989. ACM 1989, ISBN 0-89791-323-X [contents]
Informal and Other Publications
- 2010
- [i1]Moses Charikar, Tom Leighton, Shi Li, Ankur Moitra:
Vertex Sparsifiers and Abstract Rounding Algorithms. CoRR abs/1006.4536 (2010)
Coauthor Index
a service of 
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-07-09 04:35 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
