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

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

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

** 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 ManagementAmit Agarwal and Elad Hazan. ECCC Report.

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,

**Fax**: 6092581771.

**Email**: aagarwal@cs.princeton.edu