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.

Publications:

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.

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.

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:

Amit Agarwal and Elad Hazan. ECCC Report.

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.

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.

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).

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