Chronological list of most of my publications:
- Liquidity
in Credit Networks: A Little Trust Goes a Long Way. P. Dandekar, A. Goel, R. Govindan, and I. Post. Preliminary version presented
at NetEcon 2010.
- Fast
Incremental and Personalized PageRank. B. Bahmani, A. Chowdhury, and
A. Goel. To appear in VLDB 2011.
- Improved
Approximation Results for Stochastic Knapsack Problems. A. Bhalgat, A. Goel, and S. Khanna. ACM-SIAM Symposium on Discrete Algorithms
(SODA), 2011.
- 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.
- Similarity
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
SIGMETRICS, 2010.
- An
incentive-based architecture for social recommendations. R. Bhattacharjee, A. Goel, and
K. Kollias. RecSys
2009.
- Renewable, Time-Responsive DNA Logic Gates for
Scalable Digital Circuits. A. Goel and M. Ibrahimi. DNA 2009.
- Hybrid
keyword search auctions. A. Goel and K. Munagala. In the 18th World Wide Web conference
(www2009), 2009. Winner of the best
paper award.
- 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,
Brad).
- 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
2008.
- 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
(IWQoS), 2008.
- 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
(SODA) 2008,1145-1153.
- 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)
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. (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.)
- 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).
- 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):
Internet commerce, social networks, and game theory.
- Liquidity in Credit Networks: A Little Trust Goes
a Long Way. P. Dandekar, A. Goel, R. Govindan, and I. Post. Preliminary version presentes at NetEcon 2010.
- Fast Incremental and Personalized PageRank. B. Bahmani, A. Chowdhury, and
A. Goel. To appear in VLDB 2011.
- An incentive-based architecture for social
recommendations. R. Bhattacharjee, A. Goel, and K. Kollias. RecSys 2009.
- Hybrid keyword search auctions. A. Goel and K. Munagala. In the
18th World Wide Web conference (www2009), 2009. Winner of the best paper award.
- 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, Brad).
- 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 (SODA) 2008,1145-1153.
- 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.
- 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.
- 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.
- 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.
- Towards
Protocol Equilibrium with Oblivious Routers. D. Dutta, A. Goel, and J. Heidemann. IEEE Infocom
2004.
- 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).
- Oblivious AQM
and Nash Equilibria. D. Dutta, A. Goel, and J. Heidemann. IEEE Infocom,
2003.
- Stochastic
Load Balancing and Related Problems. With P. Indyk. In IEEE
Foundations of Computer Science, 1999.
Internet and network algorithms.
- Small Subset Queries and Bloom Filters Using
Ternary Associative Memories, with Applications. A. Goel and P. Gupta.
ACM SIGMETRICS, 2010.
- 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
2008.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- Towards Protocol Equilibrium with Oblivious
Routers. D. Dutta, A. Goel,
and J. Heidemann. IEEE Infocom
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.
- 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.
- Source routing and scheduling in packet networks. M. Andrews, A. Fernandez, A. Goel, and L. Zhang, IEEE Foundations of Computer
Science, 2001.
- 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.
- Efficient computation of delay-sensitive routes
from one source to all destinations. With K.G. Ramakrishnan,
D. Kataria, and D. Logothetis.
IEEE Infocom, 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 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.
- Online Throughput-Competitive Algorithm for
Multicast Routing and Admission Control. With M. Henzinger and
S. Plotkin. In ACM-SIAM Symposium on Discrete
Algorithms, 1998.
Molecular Algorithms.
During the last
decade, bio-chemical molecules such as nucleic acids and proteins have been
used in ingenious ways to perform engineering tasks in a laboratory setting in vitro (i.e. outside any biological
cell). DNA and RNA in particular are very promising since their functionality
is largely combinatorial which allows us to reason about these molecules
algorithmically. The algorithmic primitives provided by nucleic acids and
enzymes are both rich and powerful. How can we use these basic primitives (such
as base pairing, enzymatic reactions, strand invasion etc) to perform
programmable engineering tasks such as self-assembly, computation, and
actuation? While the hard work in this field is being done by
experimentalists, I believe that theory also has an important role to
play.
- Renewable,
Time-Responsive DNA Logic Gates for Scalable Digital Circuits. A. Goel and M. Ibrahimi. DNA
2009.
- Towards
programmable molecular machines. H. Chen, A.
De, A. Goel. Presented (by Holin)
at FNANO 2008.
- 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.
- Error Free
Self-Assembly with Error Prone Tiles. H. Chen and
A. Goel. Proceedings of the 10th International
Meeting on DNA Based Computers, 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.
- 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.
- 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.
- 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).
- 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.
General algorithms/theory papers.
- Improved Approximation Results for Stochastic
Knapsack Problems. A. Bhalgat, A. Goel,
and S. Khanna. ACM-SIAM Symposium on Discrete
Algorithms (SODA), 2011.
- 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.
- Similarity
Search and Locality Sensitive Hashing using TCAMs. R. Shinde, A. Goel, P. Gupta, D. Dutta. ACM
SIGMOD, 2010.
- 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,
Brad).
- 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.
- Pricing for
fairness: distributed resource allocation for multiple objectives. S.
Cho and A. Goel. ACM Symposium on Theory of
Computing, 2006.
- 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.
- 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.)
- 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.
- Instability of FIFO
at Arbitrarily Low Rates in the Adversarial Queueing
Model. R. Bhattacharjee and A. Goel. IEEE Foundations of Computer Science, 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.
- 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.
- 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.
- 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.
- 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.
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.
- Liquidity
in Credit Networks: A Little Trust Goes a Long Way. P. Dandekar, A. Goel, R. Govindan, and I. Post. Preliminary version presented
at NetEcon 2010.
- Fast
Incremental and Personalized PageRank. B. Bahmani, A. Chowdhury, and
A. Goel. To appear in VLDB 2011.
- 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.
- Similarity
Search and Locality Sensitive Hashing using TCAMs.
R. Shinde, A. Goel, P.
Gupta, D. Dutta. ACM SIGMOD, 2010.
- Hybrid
keyword search auctions. A. Goel and K. Munagala. In the 18th World Wide Web conference
(www2009), 2009. Winner of the best
paper award.
- Truthful
auctions for pricing search keywords. G. Aggarwal,
A. Goel, and R. Motwani.
To appear in the ACM conference on Electronic Commerce, 2006.
- 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.
- Instability of FIFO
at Arbitrarily Low Rates in the Adversarial Queueing
Model. R. Bhattacharjee and A. Goel. IEEE Foundations of Computer Science, 2003.
- 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.
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 notice itself copied from Chandra Chekuri’s webpageJ).
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.