# Journal Papers

### 2017

On extensions of the deterministic online model for bipartite matching and max-sat,
N. Pana and A. Borodin.
Theorteical Computer Science (TCS), early online version, October 2018.
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. Boordin, 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.