The SCEAS System
Navigation Menu

Search the dblp DataBase

Title:
Author:

Allan Borodin: [Publications] [Author Rank by year] [Co-authors] [Prefers] [Cites] [Cited by]

Publications of Author

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

  84. Invited Talk II The Power and Limitations of Simple Algorithms: A Partial Case Study of Greedy Mechanisim Design for Combinatorial Actions. [Citation Graph (, )][DBLP]


  85. Extracting and ranking viral communities using seeds and content similarity. [Citation Graph (, )][DBLP]


  86. Elimination Graphs. [Citation Graph (, )][DBLP]


  87. On the Limitations of Greedy Mechanism Design for Truthful Combinatorial Auctions. [Citation Graph (, )][DBLP]


  88. On the Relative Merits of Simple Local Search Methods for the MAX-SAT Problem. [Citation Graph (, )][DBLP]


  89. Price of Anarchy for Greedy Auctions. [Citation Graph (, )][DBLP]


  90. Cluster Based Personalized Search. [Citation Graph (, )][DBLP]


  91. Price of Anarchy for Greedy Auctions [Citation Graph (, )][DBLP]


Search in 0.019secs, Finished in 0.025secs
NOTICE1
System may not be available sometimes or not working properly, since it is still in development with continuous upgrades
NOTICE2
The rankings that are presented on this page should NOT be considered as formal since the citation info is incomplete in DBLP
 
System created by asidirop@csd.auth.gr [http://users.auth.gr/~asidirop/] © 2002
for Data Engineering Laboratory, Department of Informatics, Aristotle University © 2002