I conduct research in the design, analysis, and applications
of algorithms. I also use techniques from optimization,
probability, stochastics, and game theory in my research. I
like to get deep into applications, with the goal being
tangible impact in the application domain, not just
collaborations with practitioners or papers in applied
venues. Current application interests include Social Networks
; Internet Commerce; Reputation, Recommendation,
and Trust Systems; Algorithms for large scale data
processing. In addition to advancing technology, I am also
excited about developing algorithms that improve how we
interact with each other and the networked world around
I get asked often about my Twitter
Chronological list of selected publications
- Re-incentivizing Discovery: Mechanisms for Partial-Progress Sharing in Research. S. Banerjee, A. Goel, and A. Krishnaswamy. To appear in EC 2014.
- Disjoint Set Union with Randomized Linking. A. Goel, S. Khanna, D. Larkin, and R. E. Tarjan, SODA 2014.
- On the precision of social and information networks. R. Bosgah-Zadeh, A. Goel, K. Munagala, and A. Sharma. Proceedings of the first ACM Conference on Social Networks (COSN 2013).
- Dimension independent similarity computation. R. Bosagh Zadeh and A. Goel, Journal of Machine Learning Research, 2013. Also, see the blog post at Twitter.
WTF: The Who To Follow service at Twitter.
P. Gupta, A. Goel, J. Lin, A. Sharma, D. Wang, R. Zadeh, WWW 2013.
- Biased assimilation, homophily, and the dynamics of
polarization. P. Dandekar and A. Goel and D. T. Lee. Proceedings
of the National Academy of Sciences, 2013.
Efficient distributed locality sensitive hashing.
B. Bahmani, A. Goel, R. Shinde, CIKM 2012.
On the communication and streaming complexity of maximum bipartite matching.
Ashish Goel, Michael Kapralov, Sanjeev Khanna, SODA 2012.
A Game-Theoretic Model of Attention in Social Networks.
A. Goel and F. Ronaghi, WAW 2012 (Workshop on Algorithms and Models for the Web Graph).
Triadic Consensus - A Randomized Algorithm for Voting in a Crowd.
A. Goel and D. Lee, WINE 2012.
Partitioned multi-indexing: bringing order to social search.
B. Bahmani, A. Goel, WWW 2012.
Strategic formation of credit networks.
P. Dandekar, A. Goel, M. Wellman, B. Wiedenbeck, WWW 2012.
in Credit Networks: A Little Trust Goes a Long Way. P. Dandekar, A. Goel, R. Govindan, and I. Post. EC 2011. Preliminary version presented
at NetEcon 2010.
Incremental and Personalized PageRank. B. Bahmani, A. Chowdhury, and
A. Goel. VLDB 2011.
Approximation Results for Stochastic Knapsack Problems. A. Bhalgat, A. Goel, and S. Khanna. ACM-SIAM Symposium on Discrete Algorithms
- One Tree
Suffices: A Simultaneous O(1)-Approximation for
Single-Sink Buy-at-Bulk. A. Goel and I. Post.
IEEE FOCS 2011.
- Perfect matchings in O(n log n) time
in regular bipartite graphs. A. Goel, M. Kapralov, and S. Khanna. ACM
Symposium on Theory of Computing (STOC), 2010.
Search and Locality Sensitive Hashing using TCAMs.
R. Shinde, A. Goel, P.
Gupta, D. Dutta. ACM SIGMOD, 2010.
- Small Subset
Queries and Bloom Filters Using Ternary Associative Memories, with
Applications. A. Goel and P. Gupta. ACM
incentive-based architecture for social recommendations. R. Bhattacharjee, A. Goel, and
K. Kollias. RecSys
- Renewable, Time-Responsive DNA Logic Gates for
Scalable Digital Circuits. A. Goel and M. Ibrahimi. DNA 2009.
keyword search auctions. A. Goel and K. Munagala. In the 18th World Wide Web conference
(www2009), 2009. Winner of the best
- Perfect matchings via uniform sampling in regular bipartite
graphs. A. Goel, M. Kapralov,
and S. Khanna. In the ACM-SIAM Symposium on
Discrete Algorithms (SODA), 2009.
- The Ratio
Index for Budgeted Learning, with Applications. A. Goel, S. Khanna, and B. Null. To appear in the ACM-SIAM
Symposium on Discrete Algorithms (SODA), 2009 (a part of this paper was
the finalist for the 2008 Nicholson student paper prize – congratulations,
- On the Network Coding Advantage for Wireless
Multicast in Euclidean Space. A. Goel and S. Khanna. The Seventh International Symposium on
Information Processing in Sensor Networks (IPSN), 2008: 64-69.
- Reducing Maximum Stretch in Compact Routing. M. Enachescu, M.
Wang, A. Goel. IEEE Infocom
- Towards programmable molecular machines. H. Chen, A. De, A. Goel.
Presented (by Holin) at FNANO 2008.
- Obtaining high throughput in networks with tiny
buffers. Neda Beheshti,
Yashar Ganjali, Ashish Goel, and Nick McKeown. International Workshop on Quality of Service
- Advertisement Allocation for Generalized Second
Pricing Schemes. A. Goel, M. Mahdian,
H. Nazerzadeh, and Amin
Saberi, fourth Workshop on Ad Auctions, 2008.
- Price based protocols for fair resource
allocation: convergence time analysis and extension to Leontief utilities. A, Goel, H. Nazerzadeh. ACM-SIAM Symposium on Discrete Algorithm
- Dimension augmentation and combinatorial criteria
for efficient error-resistant DNA self-assembly. H. Chen, A. Goel, C. Luhrs. ACM-SIAM Symposium on Discrete Algorithms
(SODA) 2008: 409-418.
- Toward Minimum Size Self-Assembled Counters. A. Goel and P. Moisset de espanes. Proceedings of the thirteenth International
meeting on DNA based computers (DNA) 2007, and journal of natural compting (volume 7, number 3, pages 317-334).
- Self-Assembling Tile Systems that Heal from Small
Fragments. H. Chen, A. Goel, C. Luhrs, and E. Winfree. Presented
at the thirteenth International meeting on DNA based computers (DNA) 2007.
(winner of the best student paper award –
congratulations, Holin and Chris).
- Reducing Facet Nucleation during Algorithmic
Self-Assembly. H. Chen, R. Schulman, A. Goel, E. Winfree. Nano letters, 7(9);
2913-2919. This is an experimental exploration of the scheme n the paper
on error free self-assembly with error prone tiles.
- Algorithms and incentives for robust ranking. R. Bhattacharjee and A. Goel.
ACM-SIAM Symposium on Discrete Algorithms (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)
- 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. (Note:
there was a small error in the original version which
was pointed out to us by Alex Jaffe and his advisor James Lee. The error
has been corrected in the arxiv version linked
- Error Free Self-Assembly with Error Prone Tiles. H. Chen and A. Goel.
Proceedings of the 10th International Meeting on DNA Based Computers,
- 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,
- Towards Protocol Equilibrium with Oblivious
Routers. D. Dutta, A. Goel,
and J. Heidemann. IEEE Infocom
- 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,
- Instability of FIFO at Arbitrarily Low Rates in
the Adversarial Queueing Model. R. Bhattacharjee and
A. Goel. IEEE Foundations of Computer Science,
- 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
- 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,
- Using the Small-World Model to Improve Freenet Performance. H. Zhang, A. Goel,
and R. Govindan. IEEE Infocom,
- 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
- 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).
- 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
- Approximate Majorization
and Fair Online Load Balancing. With A. Meyerson
and S. Plotkin. ACM-SIAM Symposium on Discrete
- Distributed Admission Control, Scheduling, and
Routing with Stale Information. With A. Meyerson and
S. Plotkin. ACM-SIAM Symposium on Discrete
- Combining Fairness with Throughput: Online
Routing with Multiple Objectives. With A. Meyerson and
S. Plotkin. ACM Symposium on Theory of
- 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
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 notice itself copied from Chandra Chekuri’s webpage)
_ 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.