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 and Social Algorithms; Crowdsourced Democracy; 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 us.

I have also spent significant time in industry, including Twitter (brief writeup) , Teapot (acquired by Stripe), and Stripe.

Why social choice?

Chronological list of selected publications (sorry, I gave up, use google scholar!)

  1. FAST-PPR: Scaling Personalized PageRank Estimation for Large Graphs P. Lofgren, S. Banerjee, A. Goel, C. Seshadhri. KDD 2014.
  2. Re-incentivizing Discovery: Mechanisms for Partial-Progress Sharing in Research. S. Banerjee, A. Goel, and A. Krishnaswamy. EC 2014.
  3. Large-Scale Decision-Making via Small Group Interactions: The Importance of Triads. A. Goel and D. Lee. In the 5th International Workshop on Computational Social Choice (COMSOC), 2014.
  4. Crowdsourcing for Participatory Democracies: Efficient Elicitation of Social Choice Functions. D. Lee, A. Goel, T. Aitamurto, H. Landemore. To appear in HCOOMP 2014 (the paper linked here is an earlier version from SCUGC 2014).
  5. Disjoint Set Union with Randomized Linking. A. Goel, S. Khanna, D. Larkin, and R. E. Tarjan, SODA 2014.
  6. 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).
  7. Dimension independent similarity computation. R. Bosagh Zadeh and A. Goel, Journal of Machine Learning Research, 2013. Also, see the blog post at Twitter.
  8. WTF: The Who To Follow service at Twitter. P. Gupta, A. Goel, J. Lin, A. Sharma, D. Wang, R. Zadeh, WWW 2013.
  9. 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.
  10. Efficient distributed locality sensitive hashing. B. Bahmani, A. Goel, R. Shinde, CIKM 2012.
  11. On the communication and streaming complexity of maximum bipartite matching. Ashish Goel, Michael Kapralov, Sanjeev Khanna, SODA 2012.
  12. 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).
  13. Triadic Consensus - A Randomized Algorithm for Voting in a Crowd. A. Goel and D. Lee, WINE 2012.
  14. Partitioned multi-indexing: bringing order to social search. B. Bahmani, A. Goel, WWW 2012.
  15. Strategic formation of credit networks. P. Dandekar, A. Goel, M. Wellman, B. Wiedenbeck, WWW 2012.
  16. Liquidity 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.
  17. Fast Incremental and Personalized PageRank. B. Bahmani, A. Chowdhury, and A. Goel. VLDB 2011.
  18. Improved Approximation Results for Stochastic Knapsack Problems. A. Bhalgat, A. Goel, and S. Khanna. ACM-SIAM Symposium on Discrete Algorithms (SODA), 2011.
  19. One Tree Suffices: A Simultaneous O(1)-Approximation for Single-Sink Buy-at-Bulk. A. Goel and I. Post. IEEE FOCS 2011.
  20. 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.
  21. Similarity Search and Locality Sensitive Hashing using TCAMs. R. Shinde, A. Goel, P. Gupta, D. Dutta. ACM SIGMOD, 2010.
  22. Small Subset Queries and Bloom Filters Using Ternary Associative Memories, with Applications. A. Goel and P. Gupta. ACM SIGMETRICS, 2010.
  23. An incentive-based architecture for social recommendations. R. Bhattacharjee, A. Goel, and K. Kollias. RecSys 2009.
  24. Renewable, Time-Responsive DNA Logic Gates for Scalable Digital Circuits. A. Goel and M. Ibrahimi. DNA 2009.
  25. Hybrid keyword search auctions. A. Goel and K. Munagala. In the 18th World Wide Web conference (www2009), 2009. Winner of the best paper award.
  26. 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.
  27. 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 (This paper has a substantial bug that we are trying to fix. Many thanks to Joe Halpern for pointing this bug out. Please do not cite in the meantime. Please let us know if you would like to understand and/or try to fix the bug.)
  28. 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.
  29. Reducing Maximum Stretch in Compact Routing. M. Enachescu, M. Wang, A. Goel. IEEE Infocom 2008.
  30. Towards programmable molecular machines. H. Chen, A. De, A. Goel. Presented (by Holin) at FNANO 2008.
  31. Obtaining high throughput in networks with tiny buffers. Neda Beheshti, Yashar Ganjali, Ashish Goel, and Nick McKeown. International Workshop on Quality of Service (IWQoS), 2008.
  32. Advertisement Allocation for Generalized Second Pricing Schemes. A. Goel, M. Mahdian, H. Nazerzadeh, and Amin Saberi, fourth Workshop on Ad Auctions, 2008.
  33. 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 (SODA) 2008,1145-1153.
  34. 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.
  35. 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).
  36. 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).
  37. 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.
  38. 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.
  39. Truthful auctions for pricing search keywords. G. Aggarwal, A. Goel, and R. Motwani. ACM conference on Electronic Commerce, 2006.
  40. Pricing for fairness: distributed resource allocation for multiple objectives. S. Cho and A. Goel. ACM Symposium on Theory of Computing, 2006.
  41. 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.
  42. 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.
  43. Embedding Bounded Bandwidth Graphs into L1 . D. Carroll, A. Goel, and A. Meyerson. International Colloquium on Automata, Languages, and Programming (ICALP) 2006.
  44. Avoiding ballot-stuffing in eBay-like reputation systems. R. Bhattacharjee and A. Goel. Third international workshop on economics of peer-to-peer systems, 2005.
  45. 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.
  46. 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.
  47. 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 to here.)
  48. Error Free Self-Assembly with Error Prone Tiles. H. Chen and A. Goel. Proceedings of the 10th International Meeting on DNA Based Computers, 2004.
  49. 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.
  50. 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.
  51. 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.
  52. 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.
  53. 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.
  54. Towards Protocol Equilibrium with Oblivious Routers. D. Dutta, A. Goel, and J. Heidemann. IEEE Infocom 2004.
  55. 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.
  56. Instability of FIFO at Arbitrarily Low Rates in the Adversarial Queueing Model. R. Bhattacharjee and A. Goel. IEEE Foundations of Computer Science, 2003.
  57. 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).
  58. 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.
  59. Oblivious AQM and Nash Equilibria. D. Dutta, A. Goel, and J. Heidemann. IEEE Infocom, 2003.
  60. 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.
  61. 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.
  62. 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.
  63. Exact Sampling of TCP Window States. A. Goel and M. Mitzenmacher. IEEE Infocom, 2002.
  64. Using the Small-World Model to Improve Freenet Performance. H. Zhang, A. Goel, and R. Govindan. IEEE Infocom, 2002.
  65. 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.
  66. Source routing and scheduling in packet networks. M. Andrews, A. Fernandez, A. Goel, and L. Zhang, IEEE Foundations of Computer Science, 2001.
  67. Exact sampling in machine scheduling problems. With S. Cho. RANDOM 2001.
  68. 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).
  69. 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.
  70. 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.
  71. Efficient computation of delay-sensitive routes from one source to all destinations. With K.G. Ramakrishnan, D. Kataria, and D. Logothetis. IEEE Infocom, 2001.
  72. Reductions Among High Dimensional Proximity Problems. With P. Indyk and K. Varadarajan. ACM-SIAM Symposium on Discrete Algorithms 2001.
  73. Approximate Majorization and Fair  Online Load Balancing. With A.  Meyerson and S. Plotkin. ACM-SIAM Symposium on Discrete Algorithms 2001.
  74. Distributed Admission Control, Scheduling, and Routing with Stale Information. With A. Meyerson and S. Plotkin. ACM-SIAM Symposium on Discrete Algorithms 2001.
  75. Combining Fairness with Throughput: Online Routing with Multiple Objectives. With A. Meyerson and S. Plotkin. ACM Symposium on Theory of Computing, 2000.
  76. 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.
  77. Stochastic Load Balancing and Related Problems. With P. Indyk. In  IEEE Foundations of Computer Science, 1999.
  78. Stochastic Analysis of Stable Marriages in Combined Input Output Queued Switches. With B. Prabhakar. Invited to IEEE Conference on Design and Control, 1999.
  79. 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.
  80. 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). 
  81. 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.
  82. 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.
  83. 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.
  84. 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. 
  85. Online Throughput-Competitive Algorithm for Multicast Routing and Admission Control. With M. Henzinger and S. Plotkin. In ACM-SIAM Symposium on Discrete Algorithms, 1998. 

 

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)

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.