☰

Allan B. Borodin - Publications

Affiliations: 
University of Toronto, Toronto, ON, Canada 
Area:
Computer Science
Tree Info Similar researchers PubMed Report error

40 high-probability publications. We are testing a new system for linking publications to authors. You can help! If you notice any inaccuracies, please sign in and mark papers as correct or incorrect matches. If you identify any major omissions or other inaccuracies in the publication list, please let us know.

Year Citation  Score
2020 Borodin A, Karavasilis C, Pankratov D. An Experimental Study of Algorithms for Online Bipartite Matching Acm Journal of Experimental Algorithms. 25: 1-37. DOI: 10.1145/3379552  0.442
2020 Borodin A, Boyar J, Larsen KS, Pankratov D. Advice Complexity of Priority Algorithms Theory of Computing Systems \/ Mathematical Systems Theory. 64: 593-625. DOI: 10.1007/S00224-019-09955-7  0.446
2019 Pena N, Borodin A. On extensions of the deterministic online model for bipartite matching and max-sat Theoretical Computer Science. 770: 1-24. DOI: 10.1016/J.Tcs.2018.10.015  0.466
2019 Borodin A, Pankratov D, Salehi-Abari A. On Conceptually Simple Algorithms for Variants of Online Bipartite Matching Theory of Computing Systems \/ Mathematical Systems Theory. 63: 1781-1818. DOI: 10.1007/S00224-019-09916-0  0.485
2017 Borodin A, Jain A, Lee HC, Ye Y. Max-Sum Diversification, Monotone Submodular Functions, and Dynamic Updates Acm Transactions On Algorithms. 13: 41. DOI: 10.1145/3086464  0.447
2017 Lucier B, Borodin A. Equilibria of Greedy Combinatorial Auctions Siam Journal On Computing. 46: 620-660. DOI: 10.1137/15M1048720  0.627
2013 Borodin A, Braverman M, Lucier B, Oren J. Strategyproof mechanisms for competitive influence in networks Www 2013 - Proceedings of the 22nd International Conference On World Wide Web. 141-151. DOI: 10.1007/S00453-016-0169-0  0.594
2012 Ye Y, Borodin A. Elimination graphs Acm Transactions On Algorithms. 8. DOI: 10.1145/2151171.2151177  0.527
2012 Borodin A, Ivan I, Ye Y, Zimny B. On sum coloring and sum multi-coloring for restricted families of graphs Theoretical Computer Science. 418: 1-13. DOI: 10.1016/J.Tcs.2011.11.010  0.36
2011 Borodin A, Cashman D, Magen A. How well can primal-dual and local-ratio algorithms perform? Acm Transactions On Algorithms. 7. DOI: 10.1145/1978782.1978784  0.489
2011 Alekhnovich M, Borodin A, Buresh-Oppenheim J, Impagliazzo R, Magen A, Pitassi T. Toward a Model for Backtracking and Dynamic Programming Computational Complexity. 20: 679-740. DOI: 10.1007/S00037-011-0028-Y  0.411
2010 Angelopoulos S, Borodin A. Randomized priority algorithms Theoretical Computer Science. 411: 2542-2558. DOI: 10.1016/J.Tcs.2010.03.014  0.478
2009 Lee HC, Borodin A. Criteria for Cluster-Based Personalized Search Internet Mathematics. 6: 399-435. DOI: 10.1080/15427951.2009.10390647  0.423
2008 Ye Y, Borodin A. Priority algorithms for the subset-sum problem Journal of Combinatorial Optimization. 16: 198-228. DOI: 10.1007/S10878-007-9126-9  0.619
2005 Borodin A, Roberts GO, Rosenthal JS, Tsaparas P. Link analysis ranking: Algorithms, theory, and experiments Acm Transactions On Internet Technology. 5: 231-297. DOI: 10.1145/1052934.1052942  0.678
2005 Borodin A, Boyar J, Larsen KS. Priority algorithms for graph optimization problems Lecture Notes in Computer Science. 3351: 126-139. DOI: 10.1016/J.Tcs.2009.09.033  0.446
2004 Borodin A, El-Yaniv R, Gogan V. Can we learn to beat the best stock Journal of Artificial Intelligence Research. 21: 579-594. DOI: 10.1613/Jair.1336  0.317
2004 Borodin A, Ostrovsky R, Rabani Y. Subquadratic Approximation Algorithms for Clustering Problems in High Dimensional Spaces Machine Learning. 56: 153-167. DOI: 10.1023/B:Mach.0000033118.09057.80  0.329
2004 Angelopoulos S, Borodin A. The power of priority algorithms for facility location and set cover Algorithmica (New York). 40: 271-291. DOI: 10.1007/S00453-004-1113-2  0.49
2002 Angelopoulos S, Borodin A. On the Power of Priority Algorithms for Facility Location and Set Cover Lecture Notes in Computer Science. 26-39. DOI: 10.1007/3-540-45753-4_5  0.494
1999 Borodin A, El-Yaniv R. On randomization in on-line computation Information & Computation. 150: 244-267. DOI: 10.1006/Inco.1998.2775  0.46
1998 Beame P, Borodin A, Raghavan P, Ruzzo WL, Tompa M. A Time-Space Tradeoff for Undirected Graph Traversal by Walking Automata Siam Journal On Computing. 28: 1051-1072. DOI: 10.1137/S0097539793282947  0.328
1997 Borodin A, Raghavan P, Schieber B, Upfal E. How much can hardware help routing? Journal of the Acm. 44: 726-741. DOI: 10.1145/265910.265922  0.382
1997 Borodin A, Rabani Y, Schieber B. Deterministic many-to-many hot potato routing Ieee Transactions On Parallel and Distributed Systems. 8: 587-596. DOI: 10.1109/71.595575  0.431
1996 Beame P, Borodin A, Raghavan P, Ruzzo WL, Tompa M. Time-Space Tradeoffs for Undirected Graph Traversal by Graph Automata Information and Computation. 130: 101-129. DOI: 10.1006/Inco.1996.0085  0.418
1994 Ben-David S, Borodin A. A new measure for the study of on-line algorithms Algorithmica. 11: 73-91. DOI: 10.1007/Bf01294264  0.393
1994 Ben-David S, Borodin A, Karp R, Tardos G, Wigderson A. On the power of randomization in on-line algorithms Algorithmica. 11: 2-14. DOI: 10.1007/Bf01294260  0.44
1992 Borodin A, Linial N, Saks ME. An optimal on-line algorithm for metrical task system Journal of the Acm. 39: 745-763. DOI: 10.1145/146585.146588  0.325
1992 Borodin A, Ruzzo WL, Tompat M. Lower bounds on the length of universal traversal sequences Journal of Computer and System Sciences. 45: 180-203. DOI: 10.1016/0022-0000(92)90046-L  0.307
1991 Borodin A, Tiwari P. On the decidability of sparse univariate polynomial interpolation Computational Complexity. 1: 67-90. DOI: 10.1007/Bf01200058  0.315
1989 Fischer MJ, Lynch NA, Burns JE, Borodin A. Distributed FIFO allocation of identical resources using small shared space Acm Transactions On Programming Languages and Systems (Toplas). 11: 90-114. DOI: 10.1145/59287.59292  0.426
1989 Borodin A, Cook SA, Dymond PW, Ruzzo WL, Tompa M. Two Applications of Inductive Counting for Complementation Problems Siam Journal On Computing. 18: 559-578. DOI: 10.1137/0218038  0.418
1986 Borodin A, Dolev D, Fich FE, Paul W. Bounds for width two branching programs Siam Journal On Computing. 15: 549-560. DOI: 10.1137/0215040  0.319
1985 Borodin A, Hopcroft JE. Routing, merging, and sorting on parallel models of computation Journal of Computer and System Sciences. 30: 130-145. DOI: 10.1016/0022-0000(85)90008-X  0.378
1983 Borodin A, Cook S, Pippenger N. Parallel computation for well-endowed rings and space-bounded probabilistic machines Information and Control. 58: 113-136. DOI: 10.1016/S0019-9958(83)80060-6  0.327
1982 Borodin A, Cook SA. A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation Siam Journal On Computing. 11: 287-297. DOI: 10.1137/0211022  0.311
1981 Borodin A, Fischer MJ, Kirkpatrick DG, Lynch NA, Tompa M. A time-space tradeoff for sorting on non-oblivious machines☆ Journal of Computer and System Sciences. 22: 351-364. DOI: 10.1016/0022-0000(81)90037-4  0.363
1976 Borodin A, Cook SA. On the Number of Additions to Compute Specific Polynomials Siam Journal On Computing. 5: 146-157. DOI: 10.1137/0205013  0.315
1972 Constable RL, Borodin AB. Subrecursive Programming Languages, Part I: Efficiency and program structure Journal of the Acm (Jacm). 19: 526-568. DOI: 10.1145/321707.321721  0.593
1972 Munro I, Borodin A. Efficient evaluation of polynomial forms Journal of Computer and System Sciences. 6: 625-638. DOI: 10.1016/S0022-0000(72)80033-3  0.424
Show low-probability matches.