I am currently a 5th-year grad student at Cornell University in Computer Science. My advisor is Jon Kleinberg. I am graduating in May 2005, and am currently looking for post-doc positions in the New Jersey/New York area, as well as tenure-track and research lab openings nationwide. Here is some "useful" information:
Personal Info:
-
Born in Moscow, USSR. Started education in 1985. My family moved to the
United States in 1990, and eventually I ended up at Rice University,
where I majored in Computer Science and Mathematics. Graduated with a
B.S. in 2000.
-
My interests center in the design and analysis of algorithms, especially for
large decentralized networks. Recently I have focused on network design questions and
algorithms for networks involving strategic agents.
-
My non-research interests consist primarily of my girlfriend. I also enjoy playing old computer games and leisurely reading.
Publications:
- E. Anshelevich, A. Dasgupta, J. Kleinberg, E. Tardos, T. Wexler, T. Roughgarden. The Price of Stability for Network Design with Fair Cost Allocation. In FOCS 2004. (pdf)
We study the ratio of the best Nash equilibrium with the centralized optimum (the price of stability) in a network design context where independent agents wish to connect certain nodes. The best Nash equilibirum solution has a natural meaning of stability in this context -- it is the optimal solution that can be proposed from which no user will "defect". We show that if the edge cost allocation is done using a Shapley value fair division scheme, then the price of stability is at most O(log k), where k is the number of agents, and that a good Nash can be achieved via best-response dynamics. We also discuss and extend our results to many more general models, such as the case where the network has latencies.
- E. Anshelevich, L. Zhang. Path Decomposition under a New Cost Measure with Applications to Optical Network Design. In Proc. 12th Annual European Symposium on Algorithms (ESA 2004).(pdf) © Springer-Verlag
We consider a network design problem with a novel yet simple cost function. The underlying network must be partitioned into disjoint paths, and the cost of a connection is the number of these paths that the connection path intersects. We give a 2-approximation algorithm in the case that the connection routes are fixed, and show an optimal algorithm for that case with maximal network degree 3. For the case where both the path partition and the connection paths must be optimized, we give a log-approximation in the general case and a 3/2-approximation for the ring topology.
- E. Anshelevich, A. Dasgupta, E. Tardos, T. Wexler.
Near-Optimal Network Design with Selfish Agents.
Proc. 35th ACM Symposium on Theory of Computing, 2003.(pdf)
We study a simple network design game that models how independent selfish agents can build or maintain a large network. We show that in a restricted context, we can force these agents into a stable solution which is no worse than the centralized optimum. We also demonstrate that in a more general context, there is always an approximately stable solution which is no worse than the centralized optimum. Finally, we give poly-time algorithms to find these stable solutions.
- E. Anshelevich, D. Kempe, J. Kleinberg.
Stability of Load Balancing Algorithms in Dynamic Adversarial Systems.
Proc. 34th ACM Symposium on Theory of Computing, 2002. (pdf)
We study the load balancing and packet routing problems in a dynamic online setting, where an adversary can insert and remove jobs or packets. We give simple proofs of stability for a natural distributed algorithm against rate-1 adversaries, for load balancing with up to 2 commodities, and packet routing with a single sink. A main contribution of the paper is a new proof technique for stability proofs.
- E. Anshelevich, S. Owens, F. Lamiraux, and L. Kavraki.
Deformable Volumes in Path Planning Applications.
IEEE International Conference on Robotics and Automation 2000, 2290-2295.
We use the framework of the PRM (Probabilistic Roadmap Planner) to tackle the problem of path planning for deformable volumes. The underlying geometric model for the volume is provided by a mass-spring representation, augmented with a realistic mechanical model. We present experimental results that illustrate our path planning approach.
Selected Talks:
