Niv Buchbinder - Home Page

I am a faculty member in the Department of Mathematics and Computer Science at the Open university, Israel.

This year I am organizing the Computer Science Colloquia at the Open university.

Previously I was a post-doctoral researcher at Microsoft Research, New England at Cambridge, MA.

I completed my Ph.D. in the Computer Science dept. at the Technion - Israel Institute of Technology under the supervision of Prof Seffi Naor.

My main area of research is algorithms for combinatorial problems in offline and online settings. I am also interested in algorithmic game theory problems.

Here is my CV.

Contact Information

Phone:	972-9-7781224
E-mail:	niv.buchbinder@gmail.com

---

Survey book

• The Design of Competitive Online Algorithms via a Primal-Dual Approach. Niv Buchbinder and Joseph (Seffi) Naor. Foundations and Trends® in Theoretical Computer Science. [pdf]

Conference Publications

• The Online Set Cover Problem. Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, and Seffi Naor, 35th Annual ACM Symposium on Theory of Computing (STOC 2003), pp. 100-105. [pdf]
• Lower and Upper Bounds on Obtaining History Independence. Niv Buchbinder and Erez Petrank, 23rd Annual Int. Cryptography Conference (Crypto 2003), pp. 445-462. [pdf]
• A General Approach to Online Network Optimization Problems. Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, and Seffi Naor, ACM-SIAM Symposium on Discrete Algorithms (SODA 2004). [pdf]
• Online Primal-Dual Algorithms for Covering and Packing Problems. Niv Buchbinder and Seffi Naor, 13th Annual European Symposium on Algorithms (ESA 2005) full version [pdf]
• Fair Online Load Balancing. Niv Buchbinder and Seffi Naor, 18th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2006) [pdf]
• Improved Bounds for Online Routing and Packing via a Primal-Dual Approach. Niv Buchbinder and Seffi Naor, 47^th annual ieee Symposium on Foundations of Computer Science (FOCS 2006) [pdf]
• Online Primal-Dual Algorithms for Maximizing Ad-Auctions Revenue. Niv Buchbinder, Kamal Jain and Seffi Naor, 15th Annual European Symposium on Algorithms (ESA 2007) - Best Paper [pdf]
• An O(log²k)-competitive Algorithm for Metric Bipartite Matching. Nikhil Bansal, Niv Buchbinder, Anupam Gupta, Seffi Naor, 15th Annual European Symposium on Algorithms (ESA 2007) [pdf]
• A Primal-Dual Randomized Algorithm for Weighted Paging. Nikhil Bansal, Niv Buchbinder and Seffi Naor, 48^th annual ieee Symposium on Foundations of Computer Science (FOCS 2007).[pdf]
• Online Make-to-Order Joint Replenishment Model: Primal Dual Competitive Algorithms. Niv Buchbinder, Tracy Kimbrel, Retsef Levi, Konstantin Makarychev and Maxim Sviridenko, (SODA 2008). [pdf]
• Non-cooperative Cost Sharing Games via Subsidies. Niv Buchbinder, Liane Lewin-Eytan, Joseph (Seffi) Naor, Ariel Orda, 1st International Symposium on Algorithmic Game Theory (SAGT 2008). [pdf]
• Randomized Competitive Algorithms for Generalized Caching. Nikhil Bansal, Niv Buchbinder and Seffi Naor, 40th Annual ACM Symposium on Theory of Computing (STOC 2008). [pdf]
• Dynamic Power Allocation under Arbitrary Varying Channels -- An Online Approach. Niv Buchbinder, Liane Lewin-Eytan, Ishai Menache, Seffi Naor and Ariel Orda, 28^th Conference on Computer Communications (INFOCOM 2009). [pdf]
• Towards the Randomized k-Server Conjecture: A Primal-Dual Approach. Nikhil Bansal, Niv Buchbinder and Seffi Naor, ACM-SIAM Symposium on Discrete Algorithms (SODA 2010). [pdf]
• Dynamic Power Allocation under Arbitrary Varying Channels – The Multi-User Case. Niv Buchbinder, Liane Lewin-Eytan, Ishai Menache, Seffi Naor and Ariel Orda, 29^th Conference on Computer Communications (INFOCOM 2010). [pdf]
• Secretary Problems via Linear Programming. Niv Buchbinder, Kamal Jain and Mohit Singh, 14th Conference on Integer Programming and Combinatorial Optimization (IPCO 2010). [pdf]
• A Regularization Approach to Metrical Task Systems. Jacob Abernethy, Peter Bartlett, Niv Buchbinder and Isabelle Stanton, (ALT 2010). [pdf]
• Unfair Metrical Task Systems on HSTs and Applications. Nikhil Bansal, Niv Buchbinder and Seffi Naor, (ICALP 2010). [pdf]
• How to Allocate Goods in an Online Market? Yossi Azar, Niv Buchbinder and Kamal Jain, (ESA 2010). [pdf]
• Incentives in Online Auctions via Linear Programming. Niv Buchbinder, Kamal Jain and Mohit Singh, (WINE 2010). [pdf]
• Frequency Capping in Online Advertising. Niv Buchbinder, Moran Feldman, Arpita Ghosh and Seffi Naor, (WADS 2011).
• Polylogarithmic Competitive Algorithm for the k-Server Problem . Nikhil Bansal, Niv Buchbinder, Aleksander Madry and Seffi Naor, (FOCS 2011) - Best Paper.

Journal Publications

• Lower and Upper Bounds on Obtaining History Independence. Niv Buchbinder and Erez Petrank.
  Information and Computation, volume 204, Issue 2 (February 2006), pp. 291-337.
• A General Approach to Online Network Optimization Problems. Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, and Seffi Naor. ACM Transactions on Algorithms, Volume 2, Number 4 (October 2006), pp. 640-660.
• Non-cooperative Cost Sharing Games via Subsidies. Niv Buchbinder, Liane Lewin-Eytan, Joseph (Seffi) Naor, Ariel Orda, Theory of Computing Systems, Springer, volume  47,1, pages  15-37, 2010.
• Online Primal-Dual Algorithms for Covering and Packing Problems. Niv Buchbinder and Seffi Naor,  Mathematics of Operations Research Vol. 34, No. 2, May 2009, pp. 270-286
• The Online Set Cover Problem. Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, and Seffi Naor, SIAM J. Computing Volume 39, Issue 2, pp. 361-370 (2009)
• A Primal-Dual Randomized Algorithm for Weighted Paging. Nikhil Bansal, Niv Buchbinder and Joseph (Seffi) Naor. Accepted to JACM.
• Fair Online Load Balancing. Niv Buchbinder and Joseph (Seffi) Naor. Accepted to Journal of scheduling, 2011.
  

PhD. Thesis

• The Design of Competitive Online Algorithms via a Primal-Dual Approach. Advisor: Prof. Seffi Naor
    Computer Science Department, Technion, Israel, September 2008. [pdf]

M.Sc. Thesis

• Lower and Upper Bounds on Obtaining History Independence. Advisor: Prof. Erez Petrank

  Computer Science Department, Technion, Israel, November 2003. [pdf]

 שלום בוכבינדר  Shalom Buchbinder: חוברת זיכרון  [pdf] זכרונות ילדות,[ppt] תמונות, [pdf]