Allan Borodin

	2010
90		Allan Borodin, Joan Boyar, Kim S. Larsen, Nazanin Mirmohammadi: Priority algorithms for graph optimization problems. Theor. Comput. Sci. 411(1): 239-258 (2010)
	2009
89		Allan Borodin: Invited Talk II The Power and Limitations of Simple Algorithms: A Partial Case Study of Greedy Mechanisim Design for Combinatorial Actions. ALGOSENSORS 2009: 2
88		Yuli Ye, Allan Borodin: Elimination Graphs. ICALP (1) 2009: 774-785
87		Hyun Chul Lee, Allan Borodin: Cluster Based Personalized Search. WAW 2009: 167-183
86		Brendan Lucier, Allan Borodin: Price of Anarchy for Greedy Auctions CoRR abs/0909.0892: (2009)
	2008
85		Hyun Chul Lee, Allan Borodin, Leslie Goldsmith: Extracting and ranking viral communities using seeds and content similarity. Hypertext 2008: 139-148
84		Yuli Ye, Allan Borodin: Priority algorithms for the subset-sum problem. J. Comb. Optim. 16(3): 198-228 (2008)
	2007
83		Yuli Ye, Allan Borodin: Priority Algorithms for the Subset-Sum Problem. COCOON 2007: 504-514
	2006
82		Allan Borodin: Further Reflections on a Theory for Basic Algorithms. AAIM 2006: 1-9
	2005
81		Allan Borodin, David Cashman, Avner Magen: How Well Can Primal-Dual and Local-Ratio Algorithms Perform?. ICALP 2005: 943-955
80		Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen, Toniann Pitassi: Toward a Model for Backtracking and Dynamic Programming. IEEE Conference on Computational Complexity 2005: 308-322
79		Allan Borodin: Towards a Theory of Algorithms. WADS 2005: 1
78		Allan Borodin, Gareth O. Roberts, Jeffrey S. Rosenthal, Panayiotis Tsaparas: Link analysis ranking: algorithms, theory, and experiments. ACM Trans. Internet Techn. 5(1): 231-297 (2005)
	2004
77		Allan Borodin, Joan Boyar, Kim S. Larsen: Priority Algorithms for Graph Optimization Problems. WAOA 2004: 126-139
76		Spyros Angelopoulos, Allan Borodin: The Power of Priority Algorithms for Facility Location and Set Cover. Algorithmica 40(4): 271-291 (2004)
75		Allan Borodin, Ran El-Yaniv, Vincent Gogan: Can We Learn to Beat the Best Stock. J. Artif. Intell. Res. (JAIR) 21: 579-594 (2004)
74		Allan Borodin, Rafail Ostrovsky, Yuval Rabani: Stability Preserving Transformations: Packet Routing Networks with Edge Capacities and Speeds. Journal of Interconnection Networks 5(1): 1-12 (2004)
73		Allan Borodin, Rafail Ostrovsky, Yuval Rabani: Subquadratic Approximation Algorithms for Clustering Problems in High Dimensional Spaces. Machine Learning 56(1-3): 153-167 (2004)
	2003
72		Hyun Chul Lee, Allan Borodin: Perturbation of the Hyper-Linked Environment. COCOON 2003: 272-283
71		Allan Borodin, Ran El-Yaniv, Vincent Gogan: Can We Learn to Beat the Best Stock. NIPS 2003
70		Allan Borodin, Morten N. Nielsen, Charles Rackoff: (Incremental) Priority Algorithms. Algorithmica 37(4): 295-326 (2003)
	2002
69		Spyros Angelopoulos, Allan Borodin: On the Power of Priority Algorithms for Facility Location and Set Cover. APPROX 2002: 26-39
68		Allan Borodin, Morten N. Nielsen, Charles Rackoff: (Incremental) priority algorithms. SODA 2002: 752-761
	2001
67		Allan Borodin, Rafail Ostrovsky, Yuval Rabani: Stability preserving transformations: packet routing networks with edge capacities and speeds. SODA 2001: 601-610
66		Allan Borodin, Gareth O. Roberts, Jeffrey S. Rosenthal, Panayiotis Tsaparas: Finding authorities and hubs from link structures on the World Wide Web. WWW 2001: 415-429
65		Allan Borodin, Jon M. Kleinberg, Prabhakar Raghavan, Madhu Sudan, David P. Williamson: Adversarial queuing theory. J. ACM 48(1): 13-38 (2001)
	2000
64		Allan Borodin, Ran El-Yaniv, Vincent Gogan: On the Competitive Theory and Practice of Portfolio Selection (Extended Abstract). LATIN 2000: 173-196
	1999
63		Allan Borodin, Rafail Ostrovsky, Yuval Rabani: Lower Bounds for High Dimensional Nearest Neighbor Search and Related Problems. STOC 1999: 312-321
62		Allan Borodin, Rafail Ostrovsky, Yuval Rabani: Subquadratic Approximation Algorithms for Clustering Problems in High Dimensional Spaces. STOC 1999: 435-444
61		Allan Borodin, Ran El-Yaniv: On Randomization in On-Line Computation. Inf. Comput. 150(2): 244-267 (1999)
60		Paul Beame, Allan Borodin, Prabhakar Raghavan, Walter L. Ruzzo, Martin Tompa: A Time-Space Tradeoff for Undirected Graph Traversal by Walking Automata. SIAM J. Comput. 28(3): 1051-1072 (1999)
	1997
59		Allan Borodin, Ran El-Yaniv: On Ranomization in Online Computation. IEEE Conference on Computational Complexity 1997: 226-238
58		Allan Borodin: Tribute to Roman Smolensky. Computational Complexity 6(3): 195-198 (1997)
57		Allan Borodin, Yuval Rabani, Baruch Schieber: Deterministic Many-to-Many Hot Potato Routing. IEEE Trans. Parallel Distrib. Syst. 8(6): 587-596 (1997)
56		Allan Borodin, Prabhakar Raghavan, Baruch Schieber, Eli Upfal: How much can hardware help routing? J. ACM 44(5): 726-741 (1997)
	1996
55		Allan Borodin, Jon M. Kleinberg, Prabhakar Raghavan, Madhu Sudan, David P. Williamson: Adversarial Queueing Theory. STOC 1996: 376-385
54		Paul Beame, Allan Borodin, Prabhakar Raghavan, Walter L. Ruzzo, Martin Tompa: Time-Space Tradeoffs for Undirected Graph Traversal by Graph Automata. Inf. Comput. 130(2): 101-129 (1996)
	1995
53		Allan Borodin, Sandy Irani, Prabhakar Raghavan, Baruch Schieber: Competitive Paging with Locality of Reference. J. Comput. Syst. Sci. 50(2): 244-258 (1995)
	1994
52		Shai Ben-David, Allan Borodin, Richard M. Karp, Gábor Tardos, Avi Wigderson: On the Power of Randomization in On-Line Algorithms. Algorithmica 11(1): 2-14 (1994)
51		Shai Ben-David, Allan Borodin: A New Measure for the Study of On-Line Algorithms. Algorithmica 11(1): 73-91 (1994)
	1993
50		Allan Borodin: Time Space Tradeoffs (Getting Closer to the Barrier?). ISAAC 1993: 209-220
49		Allan Borodin, Prabhakar Raghavan, Baruch Schieber, Eli Upfal: How much can hardware help routing? STOC 1993: 573-582
48		Allan Borodin: Towards a Better Understanding of the Pure Packet Routing. WADS 1993: 14-25
47		Allan Borodin, Alexander A. Razborov, Roman Smolensky: On Lower Bounds for Read-K-Times Branching Programs. Computational Complexity 3: 1-18 (1993)
	1992
46		Allan Borodin: Can competitive analysis be made competitive? CASCON 1992: 359-367
45		Allan Borodin, Nathan Linial, Michael E. Saks: An Optimal On-Line Algorithm for Metrical Task System. J. ACM 39(4): 745-763 (1992)
44		Allan Borodin, Walter L. Ruzzo, Martin Tompa: Lower Bounds on the Length of Universal Traversal Sequences. J. Comput. Syst. Sci. 45(2): 180-203 (1992)
	1991
43		Allan Borodin, Sandy Irani, Prabhakar Raghavan, Baruch Schieber: Competitive Paging with Locality of Reference (Preliminary Version) STOC 1991: 249-259
42		Allan Borodin, Prasoon Tiwari: On the Decidability of Sparse Univariate Polynomial Interpolation. Computational Complexity 1: 67-90 (1991)
	1990
41		Paul Beame, Allan Borodin, Prabhakar Raghavan, Walter L. Ruzzo, Martin Tompa: Time-Space Tradeoffs for Undirected Graph Traversal FOCS 1990: 429-438
40		Shai Ben-David, Allan Borodin, Richard M. Karp, Gábor Tardos, Avi Wigderson: On the Power of Randomization in Online Algorithms (Extended Abstract) STOC 1990: 379-386
39		Allan Borodin, Prasoon Tiwari: On the Decidability of Sparse Univariate Polynomial Interpolation (Preliminary Version) STOC 1990: 535-545
	1989
38		Allan Borodin, Walter L. Ruzzo, Martin Tompa: Lower Bounds on the Length of Universal Traversal Sequences (Detailed Abstract) STOC 1989: 562-573
37		Michael J. Fischer, Nancy A. Lynch, James E. Burns, Allan Borodin: Distributed FIFO Allocation of Identical Resources Using Small Shared Space. ACM Trans. Program. Lang. Syst. 11(1): 90-114 (1989)
36		Amotz Bar-Noy, Allan Borodin, Mauricio Karchmer, Nathan Linial, Michael Werman: Bounds on Universal Sequences. SIAM J. Comput. 18(2): 268-277 (1989)
35		Allan Borodin, Stephen A. Cook, Patrick W. Dymond, Walter L. Ruzzo, Martin Tompa: Two Applications of Inductive Counting for Complementation Problems. SIAM J. Comput. 18(3): 559-578 (1989)
34		Allan Borodin, Stephen A. Cook, Patrick W. Dymond, Walter L. Ruzzo, Martin Tompa: Erratum: Two Applications of Inductive Counting for Complementation Problems. SIAM J. Comput. 18(6): 1283 (1989)
	1988
33		Allan Borodin, Faith E. Fich, Friedhelm Meyer auf der Heide, Eli Upfal, Avi Wigderson: A Tradeoff Between Search and Update Time for the Implicit Dictionary Problem. Theor. Comput. Sci. 58: 57-68 (1988)
	1987
32		Allan Borodin, Nathan Linial, Michael E. Saks: An Optimal Online Algorithm for Metrical Task Systems STOC 1987: 373-382
31		Allan Borodin, Faith E. Fich, Friedhelm Meyer auf der Heide, Eli Upfal, Avi Wigderson: A Time-Space Tradeoff for Element Distinctness. SIAM J. Comput. 16(1): 97-99 (1987)
	1986
30		Allan Borodin, Faith E. Fich, Friedhelm Meyer auf der Heide, Eli Upfal, Avi Wigderson: A Tradeoff Between Search and Update Time for the Implicit Dictionary Problem. ICALP 1986: 50-59
29		Allan Borodin, Faith E. Fich, Friedhelm Meyer auf der Heide, Eli Upfal, Avi Wigderson: A Time-Space Tradeoff for Element Distinctness. STACS 1986: 353-358
28		Allan Borodin, Danny Dolev, Faith E. Fich, Wolfgang J. Paul: Bounds for Width Two Branching Programs. SIAM J. Comput. 15(2): 549-560 (1986)
	1985
27		Allan Borodin, John E. Hopcroft: Routing, Merging, and Sorting on Parallel Models of Computation. J. Comput. Syst. Sci. 30(1): 130-145 (1985)
26		Allan Borodin, Ronald Fagin, John E. Hopcroft, Martin Tompa: Decreasing the Nesting Depth of Expressions Involving Square Roots. J. Symb. Comput. 1(2): 169-188 (1985)
	1983
25		Allan Borodin, Danny Dolev, Faith E. Fich, Wolfgang J. Paul: Bounds for Width Two Branching Programs STOC 1983: 87-93
24		Allan Borodin, Stephen A. Cook, Nicholas Pippenger: Parallel Computation for Well-Endowed Rings and Space-Bounded Probabilistic Machines Information and Control 58(1-3): 113-136 (1983)
	1982
23		Allan Borodin, Joachim von zur Gathen, John E. Hopcroft: Fast Parallel Matrix and GCD Computations FOCS 1982: 65-71
22		Allan Borodin, John E. Hopcroft: Routing, Merging and Sorting on Parallel Models of Computation (Extended Abstract) STOC 1982: 338-344
21		Allan Borodin, Joachim von zur Gathen, John E. Hopcroft: Fast Parallel Matrix and GCD Computations Information and Control 52(3): 241-256 (1982)
20		Allan Borodin, Stephen A. Cook: A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation. SIAM J. Comput. 11(2): 287-297 (1982)
	1981
19		Allan Borodin, Leonidas J. Guibas, Nancy A. Lynch, Andrew Chi-Chih Yao: Efficient Searching Using Partial Ordering. Inf. Process. Lett. 12(2): 71-75 (1981)
18		Allan Borodin, Michael J. Fischer, David G. Kirkpatrick, Nancy A. Lynch, Martin Tompa: A Time-Space Tradeoff for Sorting on Non-Oblivious Machines. J. Comput. Syst. Sci. 22(3): 351-364 (1981)
	1980
17		Allan Borodin, Stephen A. Cook: A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation STOC 1980: 294-301
	1979
16		Michael J. Fischer, Nancy A. Lynch, James E. Burns, Allan Borodin: Resource Allocation with Immunity to Limited Process Failure (Preliminary Report) FOCS 1979: 234-254
15		Allan Borodin, Michael J. Fischer, David G. Kirkpatrick, Nancy A. Lynch, Martin Tompa: A Time-Space Tradeoff for Sorting on Non-Oblivious Machines FOCS 1979: 319-327
	1977
14		Allan Borodin: On Relating Time and Space to Size and Depth. SIAM J. Comput. 6(4): 733-744 (1977)
	1976
13		Allan Borodin, Stephen A. Cook: On the Number of Additions to Compute Specific Polynomials. SIAM J. Comput. 5(1): 146-157 (1976)
	1974
12		Allan Borodin, Stephen A. Cook: On the Number of Additions to Compute Specific Polynomials (Preliminary Version) STOC 1974: 342-347
11		Allan Borodin, R. Moenck: Fast Modular Transforms. J. Comput. Syst. Sci. 8(3): 366-386 (1974)
	1972
10		R. Moenck, Allan Borodin: Fast Modular Transforms via Division FOCS 1972: 90-96
9		Allan Borodin, C. C. Gotlieb: Computers and Employment. Commun. ACM 15(7): 695-702 (1972)
8		Allan Borodin: Computational Complexity and the Existence of Complexity Gaps. J. ACM 19(1): 158-174 (1972)
7		Robert L. Constable, Allan Borodin: Subrecursive Programming Languages, Part I: efficiency and program structure. J. ACM 19(3): 526-568 (1972)
6		Allan Borodin: Corrigendum: ``Computational Complexity and the Existence of Complexity Gaps''. J. ACM 19(3): 576 (1972)
5		J. Ian Munro, Allan Borodin: Efficient Evaluation of Polynomial Forms. J. Comput. Syst. Sci. 6(6): 625-638 (1972)
	1971
4		Allan Borodin, J. Ian Munro: Evaluating Polynomials at Many Points. Inf. Process. Lett. 1(2): 66-68 (1971)
	1970
3		Robert L. Constable, Allan Borodin: On the Efficiency of Programs in Subrecursive Formalisms (Incomplete Version, Extended Abstract) FOCS 1970: 60-67
	1969
2		Allan Borodin, Robert L. Constable, John E. Hopcroft: Dense and Non-Dense Families of Complexity Classes FOCS 1969: 7-19
1		Allan Borodin: Complexity Classes of Recursive Functions and the Existence of Complexity Gaps STOC 1969: 67-78

Coauthor Index

1	Michael Alekhnovich	[80]
2	Spyros Angelopoulos	[69] [76]
3	Amotz Bar-Noy	[36]
4	Paul Beame	[41] [54] [60]
5	Shai Ben-David	[40] [51] [52]
6	Joan Boyar	[77] [90]
7	Joshua Buresh-Oppenheim (Josh Buresh-Oppenheim)	[80]
8	James E. Burns	[16] [37]
9	David Cashman	[81]
10	Robert L. Constable	[2] [3] [7]
11	Stephen A. Cook	[12] [13] [17] [20] [24] [34] [35]
12	Danny Dolev	[25] [28]
13	Patrick W. Dymond	[34] [35]
14	Ran El-Yaniv	[59] [61] [64] [71] [75]
15	Faith Ellen (Faith Ellen Fich, Faith E. Fich)	[25] [28] [29] [30] [31] [33]
16	Ronald Fagin	[26]
17	Michael J. Fischer	[15] [16] [18] [37]
18	Joachim von zur Gathen	[21] [23]
19	Vincent Gogan	[64] [71] [75]
20	Leslie Goldsmith	[85]
21	Calvin C. Gotlieb (C. C. Gotlieb)	[9]
22	Leonidas J. Guibas	[19]
23	Friedhelm Meyer auf der Heide	[29] [30] [31] [33]
24	John E. Hopcroft	[2] [21] [22] [23] [26] [27]
25	Russell Impagliazzo	[80]
26	Sandy Irani	[43] [53]
27	Mauricio Karchmer	[36]
28	Richard M. Karp	[40] [52]
29	David G. Kirkpatrick	[15] [18]
30	Jon M. Kleinberg	[55] [65]
31	Kim S. Larsen	[77] [90]
32	Hyun Chul Lee	[72] [85] [87]
33	Nathan Linial (Nati Linial)	[32] [36] [45]
34	Brendan Lucier	[86]
35	Nancy A. Lynch	[15] [16] [18] [19] [37]
36	Avner Magen	[80] [81]
37	Nazanin Mirmohammadi	[90]
38	R. Moenck	[10] [11]
39	J. Ian Munro	[4] [5]
40	Morten N. Nielsen	[68] [70]
41	Rafail Ostrovsky	[62] [63] [67] [73] [74]
42	Wolfgang J. Paul	[25] [28]
43	Nicholas Pippenger	[24]
44	Toniann Pitassi	[80]
45	Yuval Rabani	[57] [62] [63] [67] [73] [74]
46	Charles Rackoff	[68] [70]
47	Prabhakar Raghavan	[41] [43] [49] [53] [54] [55] [56] [60] [65]
48	Alexander A. Razborov	[47]
49	Gareth O. Roberts	[66] [78]
50	Jeffrey S. Rosenthal	[66] [78]
51	Walter L. Ruzzo	[34] [35] [38] [41] [44] [54] [60]
52	Michael E. Saks	[32] [45]
53	Baruch Schieber	[43] [49] [53] [56] [57]
54	Roman Smolensky	[47]
55	Madhu Sudan	[55] [65]
56	Gábor Tardos	[40] [52]
57	Prasoon Tiwari	[39] [42]
58	Martin Tompa	[15] [18] [26] [34] [35] [38] [41] [44] [54] [60]
59	Panayiotis Tsaparas	[66] [78]
60	Eli Upfal	[29] [30] [31] [33] [49] [56]
61	Michael Werman	[36]
62	Avi Wigderson	[29] [30] [31] [33] [40] [52]
63	David P. Williamson	[55] [65]
64	Andrew Chi-Chih Yao	[19]
65	Yuli Ye	[83] [84] [88]

Colors in the list of coauthors