Amit Agarwal's Space on the Web



Since you are here, I presume you already know me. But, for the random surfers: I am a graduate student at Princeton University in the computer science department. 

Research Interests

I am basically interested in approximation algorithms, random graph theory and its applications in real-world networks like the World Wide Web and the Internet, biological networks. In addition I am working on online optimization for general concave regret functions.

Follow this link to my resume.


1. Improved Algorithms and Experimental Results for k-splittable Traffic Assignment
   A. Agarwal, T. Agarwal, S. Chopra, A. Feldmann, N. Kammenhuber, P. Krysta, and B. Voecking. Europar 2003. 

Brief Summary: We improved the k-splittable makespan algorithm developed by Krysta et al. and used it for server farm load balancing. We compared the       load allocation returned by our algorithm to that achieved by DNS rotation. The simulation results showed that the load allocation returned by our algorithm are better by about 25% than the DNS rotation based scheme.

2. On the advantage of Network Coding for Improving Network Throughput
   Amit Agarwal, and Moses Charikar. Information Theory Workshop 2004. 

Brief Summary: We show that the advantage of network coding is the same as the integrality gap of well-known Steiner tree LPs both for the directed and the undirected cases. A consequence of this result is an improvement in the best known examples on the advantage of network coding.

3. O(\sqrt{\log n}) approximation algorithms for Min UnCut, Min 2CNF Deletion, and directed cut problems

   Amit Agarwal, Moses Charikar, Konstantin Makarychev, and Yury Makarychev. In Proc. STOC 2005.  

Brief Summary: We give O(\sqrt{\log n}) approximation algorithms for a lot of directed cut problems like min-uncut, min 2-CNF deletion, etc. In addition we also prove that well-known SDP relaxations for min multicut have a O(\log n) integrality gap.

4. Whole-proteome prediction of protein function via graph-theoretic analysis of interaction maps
   Elena Nabieva, Kam Jim, Amit Agarwal, Bernard Chazelle, and Mona Singh. ISMB 2005. Invited to Bioinformatics. Winner of the Best Student Paper Award.

Brief Summary: We present detailed experimental analysis of lot of graph-theoretic algorithms for function prediction in protein interaction maps. We also present a new flow based technique which out-performs all other methods tested.

Logarithmic Regret Algorithms for Online Convex Optimization

   Elad Hazan and Amit Agarwal (Joint first authors) and Satyen Kale. Submitted to special issue of Machine Learning Journal for COLT 2006.

Brief Summary: Combination of following two papers:

5. Efficient Algorithms for Repeated Game Playing and Universal Portfolio Management

   Amit Agarwal and Elad Hazan. ECCC Report.

Brief Summary: We answer in the affirmative a conjecture about Universal Portfolios made by Ordentlich and independently by Kalai and Vempala. In particular, we show that the natural algorithm of using the best decision in hindsight, also called following the leader, gives logarithmic regret for universal portfolio management as well as a more general class of functions. For the universal portfolio management problem, our algorithm combines optimal regret with computational efficiency. For the general setting, our algorithm achieves exponentially lower regret than previous algorithms. This result applies to a variety of online optimization scenarios, which besides besides universal portfolios management, also includes regret minimization for Lipschitz regret functions, online convex optimization and online utility maximization.

6. Logarithmic Regret Algorithms for Online Convex Optimization

   Elad Hazan and Adam Kalai and Satyen Kale and Amit Agarwal. In Proc. COLT 2006.

Brief Summary: We give algorithms that achieve regret $O(\log(T))$ for an arbitrary sequence of strictly convex functions (with bounded first and second
derivatives). This mirrors what has been done for the special cases of prediction from expert advice by Kivinen and Warmuth ~\cite{kivinenwarmuth},
and Universal Portfolios by Cover~\cite{cover}. We propose several algorithms achieving logarithmic regret, which besides being more general are also much
more efficient to implement.

7. Algorithms for Portfolio Management based on the Newton Method

   Amit Agarwal and Elad Hazan and Satyen Kale and Robert Schapire. In Proc. ICML 2006.

Brief Summary: We experimentally study on-line investment algorithms first proposed by Agarwal and Hazan and extended by Hazan et al. which achieve almost the same wealth as the best constant-rebalanced portfolio determined in hindsight. These algorithms are the first to combine optimal logarithmic regret bounds with efficient deterministic computability. After analyzing the algorithm using the potential function introduced by Agarwal and Hazan, we present extensive experiments on actual financial data. These experiments confirm the theoretical advantage of our algorithms, which yield higher returns and run considerably faster than previous algorithms with optimal regret. Additionally, we perform financial analysis using mean-variance calculations and the Sharpe ratio.

8. Undecidable statements and the Zero-One Law in Random Geometric Graphs

   Amit Agarwal and Joel Spencer. Accepted at Discrete and Computational Geometry.

Brief Summary: We place $n$ vertices randomly on the unit torus and join them if their distance is less than a small constant $r$. We show that this random
graph does not satisfy the Zero-One Law by exhibiting a simple and natural first order sentence with nontrivial limiting probability. We further show that the
question of whether a first order sentence has limiting probability zero is undecidable.

9. On the price of stability in undirected networks

In preparation.

Brief Summary: We show that under fair cost allocation any Nash Equilibrium is worst by a factor O(log n / log log n) in undirected networks for constant edge costs. We also show that under arbitrary cost functions, the price of stability can be O(log n).

10. Improved approximation for directed multicut and directed sparsest cut

   Amit Agarwal, Noga Alon and Moses Charikar. To appear STOC 2007.

11. Convergence, thresholds and the Zero-One Law in Scale-free Graphs
Amit Agarwal and Joel Spencer. In preparation.

Contact Information

Address: 35 Olden Street,


                NJ - 08540.

Fax:        6092581771.