Allan Borodin

Professor, Department of Computer Science, University of Toronto.

Some recent journal papers:

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.
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.
Elimination Graphs . Y. Ye and A. Borodin. Transactions on Algorithms (TALG), volume 8, number 2, April 2012
Cluster Based Personalized Search . H.C. Lee and A. Borodin. Internet Mathematics, volume 6, number 3, March 2011, pp. 399-435.
Randomized Priority Algorithms S. Angelopoulos and A. Borodin. Theoretical Computer Science, volume 411, numbers 26-28, June 2010, pp. 2542-2558.
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.
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.
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.
Stability Preserving Transformations: Packet Routing Networks with Edge Capacities and Speeds , A. Borodin, R. Ostrovsky and Y. Rabani. Journal of Interconnection Networks, Vol. 5, No. 1, March 2004, pp. 1-12.
(Incremental) Priority algorithms , A. Borodin, M. Nielsen and C. Rackoff. Algorithmica, volume 37, number 4, December 2003, pp 295-326.
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.

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.

Some recent unpublished, conference and workshop papers:

Strategyproof Mechanisms for Competitive Influence in Networks , A. Borodin, M. Braverman, B. Luicer and J. Oren 2012. WWW13, may 2013.

Max-Sum Diversification, Monotone Submodular Functions and Dynamic Updates , A. Borodin, H.C. Lee, and Y. Ye. PODS, May, 2012.

Threshold Models for Compeititve Influence in Social Networks , A. Borodin, Y. Filmus and J. Oren. WINE, December, 2010.

Greedy Mechanism Design for Truthful Combinatorial Auctions , A. Borodin and B. Lucier. ICALP 2010, July, 2010, pages 90-101. Journal submission of ICALP paper.

Maximum Satisfiability: the Power of Tabu Search , D. Pankratov and A. Borodin. SAT 2010, July, 2010, pages 223-236.

Price of Anarchy for Greedy Auctions , B. Lucier and A. Borodin. 21st Annual ACM-SIAM Symposium on Discrete Algoriths (SODA), January, 2010, pages 537-553.

Extracting and Ranking Viral Communities Using Seeds and (Lexical) Similarity , H.C. Lee, A. Borodin and L. Goldsmith. 19th ACM Conference on Hypertext and Hypermedia, pp 139-148, June 2008.

Teaching (Fall 2012 and Winter 2013) :

CSC Fall 12 - Spring 13: Social and Economic Networks: Models and Applications
CSC2420 Fall 2012: Algorithm Design, Analysis and Theory
CSC373 Winter 2013: Algorithm Design and Analysis

Mailing Address

Department of Computer Science
University of Toronto
Sandford Fleming Building, Room 2303B
10 Kings College Road
Toronto, ON, M5S 3G4
Canada
email: bor..at..cs.toronto.edu