Journal Papers


2020

  • Advice complexity of priority algorithms, A. Borodin,J.Boyar,K.S.Larsen,D. Pankratov. Theory of Computing Systems, voume 64, number 4, May 2020, pp 593-625.
  • An experimental study of algorithms for online bipartite matching A. Borodin, C. Karavasilis, D. Pankratov. ACM Journal of Experimental Algorithms, volume 25, number 1, article 1.4, March 2020.
  • 2019

  • On conceptually simple algorithms for variants of online bipartite matching, A. Borodin, D. Pankratov, A. Salehi-Abari. Theory of Computing Systems, voume 63, number 8, March 2019, pp 1781-1818.
  • On extensions of the deterministic online model for bipartite matching and max-sat, N. Pena and A. Borodin. Theorteical Computer Science (TCS), volume 770, May 2019, pp 1-24.
  • 2017

  • Sequential Posted-Price Mechanisms with Correlated Valuations, M. Adamczyk, A. Borodin, D. Ferraioli, B. de Keijzer, S. Leonardi. ACM Transactions on Economics and Computation, volume 5, number 4, December 2017, pp. 22:1-22:39.
  • Max-Sum Diversification, Monotone Submodular Functions and Dynamic Updates, A. Borodin, A. Jain, H.C. Lee, Y. Ye. ACM Transactions on Algorithms, volume 13, number 3, August 2017, pp. 41:1-41:25 .
  • Strategyproof Mechanisms for Competitive Influence in Networks, A. Borodin, M. Braverman, B. Lucier and J. Oren. Algorithmica, volume 78, June 2017, pp. 425-452.
  • Equilibria of Greedy Combinatorial Auctions, B. Lucier and A. Borodin. Siam Journal on Computing, volume 46, number 2, May 2017, pp. 620-660.
  • 2016

  • On the Limitations of Greedy Mechanism Design for Truthful Combinatorial Auctions. A. Borodin and B. Lucier. ACM Transactions on Economics and Computation, volume 5, number 1, November 2016, pp. 2:1-2:23.
  • 2012

  • On Sum Coloring for Restricted Classes of Graphs, A, Borodin, I. Ivan, Y. Ye and B. Zimny. Theoretical Computer Science, volume 418, February 2012, pp. 1-13.
  • Elimination Graphs, Y. Ye and A. Borodin. Transactions on Algorithms (TALG), volume 8, number 2, April 2012.
  • 2011

  • Cluster Based Personalized Search, H.C. Lee and A. Borodin. Internet Mathematics, volume 6, number 3, March 2011, pp. 399-435.
  • How well can Primal-Dual and Local-Ratio algorithms perform?, A. Borodin, D. Cashman and A. Magen. ACM Transactions on Algorithms (TALG), volume 7, number 3, July 2011, pp 29:1-29:26.
  • Toward a Model for Backtracking and Dynamic Programming, A. Alekhnovich, A. Borodin, J. Buresh-Oppenheim, R. Impagliazzo, A. Magen, T. Pitassi. Computational Complexity, volume 20, number 4, December 2011, pp. 679-740.
  • 2010

  • Priority algorithms for graph optimization problems, A. Borodin, J. Boyar, K.S. Larsen and N. Mirohammadi. Theoretical Computer Science, volume 411, number 1, January 2010, pp.239-258.
  • Randomized Priority Algorithms S. Angelopoulos and A. Borodin. Theoretical Computer Science, volume 411, numbers 26-28, June 2010, pp. 2542-2558.
  • 2008

  • Priority algorithms for the subset-sum problem Y. Ye and A. Borodin. Journal of Combinatorial Optimization, volume 16, number 3, October 2008, pp. 198-228.
  • 2005

  • Link Analysis Ranking: Algorithms, Theory and Experiments, A. Borodin, G. O. Roberts, J. S. Rosenthal, and P. Tsaparas. ACM Transactions on Internet Technology, volume 5, number 1, February 2005, pp. 231-297.
  • 2004

  • On the Power of Priority Algorithms for Facility Location and Set Cover S. Angelopoulos and A. Borodin. Algorithmica, volume 40, number 4, December 2004, pp. 271-291.
  • Subquadratic Approximation Algorithms For Clustering Problems in High Dimensional Spaces, A. Borodin, R. Ostrovsky and Y. Rabani. Machine Learning, volume 56, numbers 1-3, July 2004, pp. 153-167.
  • Can We Learn to Beat the Best Stock?, A. Borodin, R. El-Yaniv and V. Gogan. Journal of Artificial Intelligence Research 21, pp. 579-594.
  • Stability Preserving Transformations: Packet Routing Networks with Edge Capacities and Speeds, A. Borodin, R. Ostrovsky and Y. Rabani. Journal of Interconnection Networks, volume 5, number 1, March 2004, pp. 1-12.
  • 2003

  • Lower Bounds for High Dimensional Nearest Neighbor Search and Related Problems, A. Borodin, R. Ostrovsky and Y. Rabani. Discrete and Computational Geometry {The Goodman-Polack-Festschrift}, B. Aronov, S. Basu, J. Pach, M. Sharir, eds., Algorithms and Combinatorics, volume 25, May 2003, pp 255-276.
  • (Incremental) Priority algorithms, A. Borodin, M. Nielsen and C. Rackoff. Algorithmica, volume 37, number 4, December 2003, pp 295-326.
  • 2001

  • Adversarial queuing theory, A. Borodin, J. Kleinberg, P. Raghavan, M. Sudan, and D. P. Williamson. Journal of the ACM, volume 48, number 1, January 2001, pp 13-38.
  • 1999

  • On Randomization in Online Computation, A. Borodin, and R. El-Yaniv. Information and Control, volume 150, number 2, May 1999, pp. 244-267.
  • A Time-Space Tradeoff for Undirected Graph Traversal by Walking Automata, A. Borodin, P. Beame, P. Raghavan, W.L. Ruzzo, and M. Tompa. SIAM Journal of Computing, volume 28, number 3, June 1999, pp. 1051-1072.
  • 1997

  • Deterministic Many-to-Many Hot Potato Routing, A. Borodin, Y. Rabani, and B. Schieber. IEEE Transactions on Parallel and Distributed Computing, volume 8, number 6, June 1997, pp. 587-596.
  • How Much Can Hardware Help Routing?, A. Borodin, P. Raghavan, B. Schieber, and E. Upfal. Journal of the ACM, volume 44, number 5, September 1997, pp. 726-741.
  • 1996

  • Time-Space Tradeoffs for Undirected Graph Traversal by Graph Automata, A. Borodin, P. Beame, P. Raghavan, W.L. Ruzzo, and M.Tompa. Information and Computation, November 1996, pp. 101-129.
  • 1995

  • Competitive Paging with Locality of Reference, A. Borodin, S. Irani, P. Raghavan, and B. Schieber. Journal of Computer and System Sciences, April 1995, pp. 244-258.
  • 1994

  • A New Measure for the Study of Online Algorithms, A. Borodin, and S. Ben-David. Algorithmica, volume 11, 1994, pp. 73-91.
  • On the Power of Randomization in On-line Algorithms, A. Borodin, S. Ben-David, R. Karp, G. Tardos, and A. Wigderson. Algorithmica, volume 11, 1994, pp. 2-14.
  • 1993

  • On Lower Bounds for Read-k Times Branching Programs, A. Borodin, A. Razborov, and R. Smolensky. Computational Complexity, volume 3, 1993, pp. 1-18.
  • 1992

  • An Optimal Online Algorithm for Metrical Task Systems, A. Borodin, N. Linial, and M. Saks. Journal of the ACM, volume 3, number 4, pp. 745-763, 1992.
  • On Lower Bounds on the Length of Universal Traversal Sequences, A. Borodin, W.L. Ruzzo, and M. Tompa. Journal of Computer and System Sciences, volume 45, number 2, October 1992, pp. 180-203.
  • 1991

  • On the Decidability of Sparse Univariate Polynomial Interpolation, A. Borodin, and P. Tiwari. Computational Complexity, volume 1, number 1, 1991, pp. 67-90.
  • 1989

  • Resource Allocation with Immunity to Limited Process Failure, A. Borodin, J. Burns, M. Fischer, N. Lynch, J. Burns and A. Borodin. ACM Transactions on Programming Languages and Systems, volume 11, number 1, January 1989, pp. 90-114.
  • Bounds on Universal Sequences, A. Borodin, A. Bar Noy, M. Karchmer, N. Linial, and M. Werman. SIAM Journal on Computing, volume 18, number 2, April 1989, pp. 268-277.
  • Two Applications for Complementation via Inductive Counting, A. Borodin, S.A. Cook, P. Dymond, W.L. Ruzzo, and M. Tompa. SIAM Journal on Computing, volume 18, number 3, June 1989, pp. 559-578.
  • 1988

  • A Tradeoff Between Search and Update Time for the Implicit Dictionary Problem, A. Borodin, F. Fich, F. Meyer auf der Heide, E. Upfal, and A. Wigderson. Theoretical Computer Science, volume 58, June 1988, pp. 57-68.
  • 1987

  • A Time Space Tradeoff for Element Distinctness, A. Borodin, F. Fich, F. Meyer auf der Heide, E. Upfal, and A. Wigderson. SIAM Journal on Computing, volume 16, number 1, February 1987, pp. 97-99.
  • 1986

  • Bounds for Width Two Branching Programs, A. Borodin, D. Dolev, F. Fich, and W. Paul. SIAM Journal on Computing, volume 15, number 2, May 1986, pp. 549-560.
  • 1985

  • Decreasing the Nesting Depth of Expressions Involving Square Roots, A. Borodin, R. Fagin, J. Hopcroft, and M. Tompa. Journal of Symbolic Computation, volume 1, 1985, pp. 169-188.
  • Routing, Merging and Sorting on Parallel Models of Computation, A. Borodin, and J. Hopcroft. Journal of Computer and System Sciences, volume 30, number 1, February 1985, pp. 130-145.
  • 1983

  • Parallel Computation for Well Endowed Rings and Space Bounded Probabilistic Machines, A. Borodin, S. Cook, and N. Pippenger. Information and Control, volume 58, numbers 1-3, July 1983, pp. 113-136.
  • 1982

  • Structured vs. General Models in Computational Complexity, A. Borodoin. Monographie no.30 de L'Enseignement Mathematique, 1982, pp. 47-66.
  • Fast Parallel Matrix and GCD Computations, A. Borodin, J. von zur Gathen, and J. Hopcroft. Information and Control, volume 52, March 1982, pp. 241-256.
  • Time-Space Tradeoffs for Sorting on a General Sequential Model of Computation, A. Borodin, and S. Cook. SIAM Journal on Computing, volume 11, number 2, May 1982, pp. 287-297.
  • 1981

  • A Time-Space Tradeoff for Sorting on Non Oblivious Machines, A. Borodin, M. Fischer, D. Kirkpatrick, N.Lynch, and M. Tompa. Journal of Computer and System Sciences, volume 22, number 3, June 1981, pp. 351-364.
  • Efficient Searching Using Partial Ordering, A. Borodin, L. Guibas, N. Lynch, and A. Yao. Information Processing Letters, volume 12, April 1981, pp. 71-75.
  • 1977

  • On Relating Time and Space to Size and Depth, A. Borodin. SIAM Journal on Computing, volume 6, December 1977, pp. 733-744.
  • 1976

  • On the Number of Additions to Compute Specific Polynomials, A. Borodin. SIAM Journal on Computing, volume 5, March 1976, pp. 146-157.
  • 1974

  • Fast Modular Transforms, A. Borodin, and R. Moenck. Journal of Computer and System Sciences, volume 8, July 1974, pp. 366-386.
  • 1972

  • Computers and Employment, A. Borodin, and C.C. Gotlieb. Communications of the ACM, volume 15, number 7, July 1972, pp. 695-702.
  • Computational Complexity and the Existence of Complexity Gaps A. Borodin. JACM, vol 19, number 1, pp. 158-174.
  • Corrigendum:Computational Complexity and the Existence of Complexity Gaps A. Borodin. JACM, vol 19, number 3, page 576.
  • Subrecursive Programming Languages, Part I: efficiency and program structure R. Constable and A. Borodin. JACM, vol 19, number 3, pp. 526-568.
  • Efficient Evaluation of Polynomial Forms, A. Borodin, and I. Munro. Journal of Computer and System Sciences, volume 6, December 1972, pp. 625-638.
  • 1971

  • Evaluating Polynomials at Many Points, A. Borodin, and I. Munro. Information Processing Letters, volume 1, number 2, July 1971, pp. 66-68.