Ashish Goel ’s Research

Publications:	Chronological By Subject A small representative set PhD Thesis
Research Interests:	Methodological: Algorithms, optimization, stochastics, graph theory. Applications: Networks, self-assembly, Internet commerce, social networks and reputation systems, fairness. Help!! What is the largest known instance of precise counting in nature?
Committees:	Current ACM Conference on Electronic Commerce (EC 2007) 13th International meeting on DNA computing, 2007 Old SPAA 2006 ACM Electronic Commerce 2006 IEEE FOCS 2005 ACM Sigmetrics 2005 DNA based computers, 2005 IEEE Infocom 2004 Combinatorial and Algorithmic Aspects of Networking (CAAN) 2004 ACM Sigmetrics 2003 ACM-SIAM Symposium on Discrete Algorithms (SODA) 2002 Informs Telecommunications Conference 2002 APPROX 2002
PhD Students:	Current Rajat Bhattacharjee Ho-Lin Chen Mihaela Enachescu Hamid Nazerzadeh (jointly advised with Amin Saberi) Chris Luhrs Mei Wang Graduated Sung-Woo Cho Pablo Moisset de espanes Sanatan Rai Hui Zhang Debojyoti Dutta Rishi Bhargava (MS)

Chronological list of publications:

Algorithms and incentives for robust ranking. . R. Bhattacharjee and A. Goel. To appear in SODA 2007. This is a follow up to an earlier position paper, Incentive based ranking mechanisms in NetEcon 2006.
Truthful auctions for pricing search keywords. G. Aggarwal, A. Goel, and R. Motwani. ACM conference on Electronic Commerce, 2006.
Pricing for fairness: distributed resource allocation for multiple objectives. S. Cho and A. Goel. ACM Symposium on Theory of Computing, 2006.
Routers with very small buffers. M. Enachescu, Y. Ganjali, A. Goel, N. McKeown, and T. Roughgarden. IEEE Infocom, 2006. Preliminary version appeared as an invited short note in ACM computer communications review.
Asking the right questions: Model-driven Optimization using Probes . A. Goel, S. Guha, and K. Munagala. ACM Symposium on Principles of Database Systems (PODS) 2006.
Embedding Bounded Bandwidth Graphs into L1 . D. Carroll, A. Goel, and A. Meyerson. International Colloquium on Automata, Languages, and Programming (ICALP) 2006.
Avoiding ballot-stuffing in eBay-like reputation systems. R. Bhattacharjee and A. Goel. Third international workshop on economics of peer-to-peer systems, 2005.
Making eigenvector-based reputation systems robust to collusion. H. Zhang, A. Goel, R. Govindan, K. Mason, and B. Van Roy. Workshop on Algorithms and Models for the Web Graph (WAW) 2004.
Bandwidth allocation in networks: a single dual-update subroutine for multiple objectives. S. Cho and A. Goel. Workshop on Combinatorial and Algorithmic Aspects of Networking (CAAN) 2004.
Lower Bounds for Embedding into Distributions over Excluded Minor Graph Families. D. E. Carroll and A. Goel. Proceedings of the 12th European Symposium on Algorithms, 2004.
Error Free Self-Assembly with Error Prone Tiles. H. Chen and A. Goel. Proceedings of the 10th International Meeting on DNA Based Computers, 2004.
Scale Free Aggregation in Sensor Networks . M. Enachescu, A. Goel, R. Govindan, and R. Motwani. Proceedings of the First International Workshop on Algorithmic Aspects of Wireless Sensor Networks (Algosensors), 2004.
Multi-processor scheduling to minimize flow time with ε-resource augmentation. C. Chekuri, A. Goel, S. Khanna, and A. Kumar. ACM Symposium on Theory of Computing, 2004.
Sharp thresholds for monotone properties in random geometric graphs. A. Goel, S. Rai, and B. Krishnamachari. To appear in Annals of Applied Probability. Preliminary version in ACM Symposium on Theory of Computing, 2004.
Set K-Cover Algorithms for Energy Efficient Monitoring in Wireless Sensor Networks. Z. Abrams, A. Goel, and S. Plotkin. The Third International Symposium on Information Processing in Sensor Networks (IPSN), 2004.
Optimal self-assembly of counters at temperature two. Q. Cheng, A. Goel, and P. Moisset(invited paper). Proceedings of the first conference on Foundations of nanoscience: self-assembled architectures and devices, April 2004.
Towards Protocol Equilibrium with Oblivious Routers. D. Dutta, A. Goel, and J. Heidemann. IEEE Infocom 2004.
Invadable Self-Assembly: Combining Robustness with Efficiency. H. Chen, Q. Cheng, A. Goel, M.-D.Huang, and P. Moisset. ACM-SIAM Symposium on Discrete Algorithms, 2004.
Instability of FIFO at Arbitrarily Low Rates in the Adversarial Queueing Model. R. Bhattacharjee and A. Goel. IEEE Foundations of Computer Science, 2003.
The Design of a Distributed Rating Scheme for Peer-to-peer Systems. D. Dutta, A. Goel, R. Govindan, and H. Zhang. Workshop on Economic Issues in Peer-to-Peer Systems, Berkeley, CA (June 5-6, 2003).
Incrementally Improving Lookup Latency in Distributed Hash Table Systems. H. Zhang, A. Goel, and R. Govindan. ACM Sigmetrics, 2003. A more complete version with proofs is available as USC Computer Science technical report 03-786.
Oblivious AQM and Nash Equilibria. D. Dutta, A. Goel, and J. Heidemann. IEEE Infocom, 2003.
Simultaneous Optimization for Concave Costs: Single Sink Aggregation or Single Source Buy-at-Bulk. A. Goel and D. Estrin. ACM-SIAM Symposium on Discrete Algorithms, 2003.
Energy-efficient Broadcast in Wireless Ad-hoc Networks: Lower bounds and Algorithms. F. Bian, A. Goel, C. Raghavendra, and X. Li. Journal of Interconnection Networks, 3(3-4), September & December 2002, pages 149-166.
Combinatorial optimization problems in self-assembly. L. Adleman, Q. Cheng, A. Goel, M.-D. Huang, D. Kempe, P. Moisset de espanes, and P. W. K. Rothemund. ACM Symposium on Theory of Computing, 2002.
Exact Sampling of TCP Window States. A. Goel and M. Mitzenmacher. IEEE Infocom, 2002.
Using the Small-World Model to Improve Freenet Performance. H. Zhang, A. Goel, and R. Govindan. IEEE Infocom, 2002.
SCADDAR: An Efficient Randomized Technique to Reorganize Continuous Media Blocks. A. Goel, C. Shahabi, S.-Y. Yao, and R. Zimmerman. International Conference on Data Engineering, 2002.
Source routing and scheduling in packet networks. M. Andrews, A. Fernandez, A. Goel, and L. Zhang, IEEE Foundations of Computer Science, 2001.
Exact sampling in machine scheduling problems. With S. Cho. RANDOM 2001.
Linear self-assemblies: Equilibria, entropy, and convergence rates. With L. Adleman, Q. Cheng, M.-D. Huang, and H. Wasserman. Sixth International Conference on Difference Equations and Applications, 2001 (To appear as "New progress in difference equations"; Editors: Elaydi, Ladas, and Aulbach; Pub: Taylor and Francis, London).
a) Using approximate majorization to characterize protocol fairness. R. Bhargava, A. Goel, and A.Meyerson. This is the full version of a poster paper in ACM SIGMETRICS, 2001, and does not actually appear in print anywhere.
b) Simultaneous optimization via approximate majorization for concave profits or convex costs. A. Goel and A. Meyerson. To appear in Algorithmica. This is a more comprehensive and formal treatment of the same topic, but omits some of the illustrative examples.
Running time and program size for self-assembled squares. With L. Adleman, Q. Cheng, and M.-D. Huang. ACM Symposium on Theory of Computing, 2001.
Efficient computation of delay-sensitive routes from one source to all destinations. With K.G. Ramakrishnan, D. Kataria, and D. Logothetis. IEEE Infocom, 2001.
Reductions Among High Dimensional Proximity Problems. With P. Indyk and K. Varadarajan. ACM-SIAM Symposium on Discrete Algorithms 2001.
Approximate Majorization and Fair Online Load Balancing. With A. Meyerson and S. Plotkin. ACM-SIAM Symposium on Discrete Algorithms 2001.
Distributed Admission Control, Scheduling, and Routing with Stale Information. With A. Meyerson and S. Plotkin. ACM-SIAM Symposium on Discrete Algorithms 2001.
Combining Fairness with Throughput: Online Routing with Multiple Objectives. With A. Meyerson and S. Plotkin. ACM Symposium on Theory of Computing, 2000.
Extending Greedy Multicast Routing to Delay Sensitive Applications. With K. Munagala. Stanford University Tech Note STAN-CS-TN-99-89. Short abstract in ACM-SIAM Symposium on Discrete Algorithms 2000. To appear as an invited paper in special issue of Algorithmica on Internet Algorithms.
Stochastic Load Balancing and Related Problems . With P. Indyk. In IEEE Foundations of Computer Science, 1999.
Stochastic Analysis of Stable Marriages in Combined Input Output Queued Switches. With B. Prabhakar. Invited to IEEE Conference on Design and Control, 1999.
Scheduling Data Transfers in a Network and the Set Scheduling Problem. With M.R. Henzinger, S. Plotkin, and E. Tardos. In ACM Symposium on Theory of Computing, 1999.
Matching Output Queueing with a Combined Input Output Queued Switch. With S. Chuang, N. McKeown, and B. Prabhakar. In IEEE Infocom'99 and in the Journal on Selected Areas in Communication, June '99. (Invited talk at the Gigabit Networking Workshop, Infocom'98).
Stability of Networks and Protocols in the Adversarial Queueing Model for Packet Routing . ACM-SIAM Symposium on Discrete Algorithms, 1999 (short abstract), and Networks , 37(4):219--224, 2001. Here is a note about an omission in the paper.
Approximating arbitrary metrics by O(n log n) trees. With M. Charikar, C. Chekuri, S. Guha, and S. Plotkin. IEEE Foundations of Computer Science, 1998.
Rounding via trees: deterministic approximation algorithms for group Steiner trees and k-median. With M. Charikar, C. Chekuri, and S. Guha. In ACM Symposium on Theory Of Computing, 1998.
Approximation Algorithms for Directed Steiner Problems. With M. Charikar, C. Chekuri, T. Cheung, Z. Dai, S. Guha, and M. Li. In ACM-SIAM Symposium on Discrete Algorithms, 1998.
Online Throughput-Competitive Algorithm for Multicast Routing and Admission Control. With M. Henzinger and S. Plotkin. In ACM-SIAM Symposium on Discrete Algorithms, 1998.

(Technical notes, drafts etc):

A Security Protocol Gateway for a Scalable Web Service. With D. L. Caswell. Hewlett Packard Labs Technical Report HPL-96-07.

Publications, roughly classified by topic (sometimes duplicated, sometimes omitted):

Under construction; sorry!

A small representative set of publications: If you would like to get a quick flavor of my research (e.g., if you are a student), please look at the following papers. There are not my “best papers”, and I wouldn’t know how to define such a set, but they best represent my current and evolving research interests.

Truthful auctions for pricing search keywords. G. Aggarwal, A. Goel, and R. Motwani. To appear in the ACM conference on Electronic Commerce, 2006.

2. Pricing for fairness: distributed resource allocation for multiple objectives. S. Cho and A. Goel. To appear in ACM Symposium on Theory of Computing, 2006.

3. Routers with very small buffers. M. Enachescu, Y. Ganjali, A. Goel, N. McKeown, and T. Roughgarden. To appear in IEEE Infocom, 2006.

4. Sharp thresholds for monotone properties in random geometric graphs. A. Goel, S. Rai, and B. Krishnamachari. To appear in Annals of Applied Probability. Preliminary version in ACM Symposium on Theory of Computing, 2004.

5. Error Free Self-Assembly with Error Prone Tiles. H. Chen and A. Goel. Proceedings of the 10th International Meeting on DNA Based Computers, 2004.

6. Instability of FIFO at Arbitrarily Low Rates in the Adversarial Queueing Model. R. Bhattacharjee and A. Goel. IEEE Foundations of Computer Science, 2003.

7. Running time and program size for self-assembled squares. With L. Adleman, Q. Cheng, and M.-D. Huang. ACM Symposium on Theory of Computing, 2001.

8. Matching Output Queueing with a Combined Input Output Queued Switch. With S. Chuang, N. McKeown, and B. Prabhakar. In IEEE Infocom'99 and in the Journal on Selected Areas in Communication, June '99. (Invited talk at the Gigabit Networking Workshop, Infocom'98).

Thesis: Algorithms for Network Routing, Multicasting, Switching, and Design. Computer Science Department, Stanford University. July, 1999. Advisor: Serge Plotkin.

Copyright Notice: Since most of these papers are published, the copyright has been transferred to the respective publishers. Therefore, the papers cannot be duplicated for commercial purposes. The following is ACM's copyright notice; other publishers have similar ones.

Copyright © 199x by the Association for Computing Machinery, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that new copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted.