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. Accepted for publication in Computational Complexity. Journal version of CCC 2005 paper.
Elimination Graphs . Y. Ye and A. Borodin. Accepted for publication in TALG. To appear in April 2012. Journal version of ICALP 2009 paper.
Cluster Based Personalized Search . H.C. Lee and A. Borodin. Accepted for publication in Internet Mathematics. Journal version of WAW 2009 paper.
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 conference and workshop papers:

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:

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

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