@unpublished{AngluinAK2012, author = {Dana Angluin and James Aspnes and Aryeh Kontorovich}, title = {On the learnability of shuffle ideals}, month = may, year = 2012, note = "Submitted to ALT 2012", } @unpublished{Aspnes2012, author = {James Aspnes}, title = {Faster randomized consensus with an oblivious adversary}, month = may, year = 2012, note = "To appear, PODC 2012", } @unpublished{AspnesACHE2012, author = {James Aspnes and Hagit Attiya and Keren Censor-Hillel and Faith Ellen}, title = {Faster than optimal snapshots (for a while)}, month = may, year = 2012, note = "To appear, PODC 2012", } @unpublished{AspnesACHH2012, author = {James Aspnes and Hagit Attiya and Keren Censor-Hillel and Danny Hendler}, title = {Lower bounds for restricted-use objects}, month = apr, year = 2012, note = "To appear, SPAA 2012", } @article{AspnesY2012, author = {James Aspnes and Yitong Yin}, title = {Randomized load balancing by joining and splitting bins}, month=apr, year = 2012, journal="Information Processing Letters", volume=112, number={8--9}, pages={309--313} } @inproceedings{AlistarhAGG2011, author = {Dan Alistarh and James Aspnes and Seth Gilbert and Rachid Guerraoui}, title = {The complexity of renaming}, month = oct, year = 2011, booktitle={Fifty-Second Annual IEEE Symposium on Foundations of Computer Science}, pages={718--727} } @inproceedings{Aspnes2011, author = {James Aspnes}, title = {Randomized consensus in expected {$O(n^2)$} total work using single-writer registers}, month =sep, year = 2011, booktitle="Distributed Computing: 25th International Symposium, DISC 2011", series="Lecture Notes in Computer Science", volume=6950, publisher="Springer-Verlag", pages={363--373}, } @inproceedings{AlistarhA2011, author = {Dan Alistarh and James Aspnes}, title = {Sub-logarithmic test-and-set against a weak adversary}, month = sep, year = 2011, booktitle="Distributed Computing: 25th International Symposium, DISC 2011", series="Lecture Notes in Computer Science", volume=6950, publisher="Springer-Verlag", pages={97--109}, } @inproceedings{AlistarhACHGZ2011, author = {Dan Alistarh and James Aspnes and Keren Censor-Hillel and Seth Gilbert and Morteza Zadimoghaddam}, title = {Optimal-time adaptive tight renaming, with applications to counting}, month = jun, year = 2011, booktitle = {Proceedings of the Thirtieth Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing}, pages={239--248}, } @inproceedings{AspnesE2011, author = {James Aspnes and Faith Ellen}, title = {Tight bounds for anonymous adopt-commit objects}, month = jun, year = 2011, pages={317--324}, booktitle={23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures} } @inproceedings{AngluinABV2011, author = {Dana Angluin and James Aspnes and Barbosa Vargas, Raonne}, title = {Mutation systems}, month = may, year = 2011, booktitle = {Language and Automata Theory and Applications: 5th International Conference, LATA 2011, Tarragona, Spain, May 26-31, 2011. Proceedings}, series={Lecture Notes in Computer Science}, volume=6638, pages={92--104}, } @techreport{Aspnes2010splitters, author = {James Aspnes}, title = {Slightly smaller splitter networks}, institution="Yale University Department of Computer Science", number="YALEU/DCS/TR-1438", month=nov, year = 2010 } @unpublished{AngluinAR2010connectivity, author = {Dana Angluin and James Aspnes and Lev Reyzin}, title = {Network construction with subgraph connectivity constraints}, month=nov, year = 2010, note="Unpublished manuscript" } @inproceedings{AngluinAR2010outbreaks, author = {Dana Angluin and James Aspnes and Lev Reyzin}, title = {Inferring social networks from outbreaks}, month=oct, year = 2010, pages = {104--118}, booktitle = {Algorithmic Learning Theory, 21st International Conference, ALT 2010, Canberra, Australia, October 6-8, 2010. Proceedings}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, volume = {6331} } @inproceedings{AngluinABCEK2010, author = {Dana Angluin and James Aspnes and Rida A. Bazzi and Jiang Chen and David Eisenstat and Goran Konjevod}, title = {Storage capacity of labeled graphs}, month=sep, year = 2010, booktitle = {Stabilization, Safety, and Security of Distributed Systems: 12th International Symposium, SSS 2010, New York, NY, USA, September 20--22, 2010. Proceedings}, publisher = {Springer-Verlag}, series={Lecture Notes in Computer Science}, volume=6366, pages={573--587} } @article{Aspnes2012modular, author = {James Aspnes}, title = {A modular approach to shared-memory consensus, with applications to the probabilistic-write model}, month=may, year = 2012, journal="Distributed Computing", volume=25, number=2, pages={179--188} } @inproceedings{AspnesBDORU2010, author = {James Aspnes and Eric Blais and Murat Demirbas and Ryan O'Donnell and Atri Rudra and Steve Uurtamo}, title = {$k^+$ decision trees}, month=jul, year = 2010, booktitle={Algorithms for Sensor Systems: 6th International Workshop on Algorithms for Sensor Systems, Wireless Ad Hoc Networks, and Autonomous Mobile Entities, ALGOSENSORS 2010, Bordeaux, France, July 5, 2010, Revised Selected Papers}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, volume = 6451, pages = {74--88} } @inproceedings{AspnesEY2010, author = {James Aspnes and David Eisenstat and Yitong Yin}, title = {Low-contention data structures}, month=jun, year = 2010, booktitle = {SPAA 2010: Proceedings of the 22nd Annual ACM Symposium on Parallel Algorithms and Architectures, Thira, Santorini, Greece, June 13-15, 2010}, pages = {345--354} } @article{AspnesAC2010, author = {James Aspnes and Hagit Attiya and Keren Censor}, title = {Combining shared coin algorithms}, month=mar, year = 2010, journal = {Journal of Parallel and Distributed Computing}, volume = 70, number = 3, pages = {317--322} } @article{AspnesAC2012, author = {James Aspnes and Hagit Attiya and Keren Censor}, title = {Polylogarithmic concurrent data structures from monotone circuits}, journal=jacm, month=feb, year = 2012, volume=59, number=1, pages={2:1--2:24} } @article{AspnesC2010, author = {Aspnes, James and Censor, Keren}, title = {Approximate shared-memory counting despite a strong adversary}, journal = {ACM Transactions on Algorithms}, volume = {6}, number = {2}, year = {2010}, issn = {1549-6325}, pages = {1--23}, doi = {http://doi.acm.org/10.1145/1721837.1721841}, publisher = {ACM}, address = {New York, NY, USA}, } @article{AngluinAR2010networks, author = {Dana Angluin and James Aspnes and Lev Reyzin}, title = {Optimally learning social networks with activations and suppressions}, month=jun, year = 2010, journal = {Theoretical Computer Science}, volume = 411, number = {29--30}, pages = {2729--2740} } @inproceedings{AspnesAC2008, author = {James Aspnes and Hagit Attiya and Keren Censor}, title = {Randomized consensus in expected {$O(n \log n)$} individual work}, month=aug, year = 2008, booktitle = {PODC '08: Proceedings of the Twenty-Seventh ACM Symposium on Principles of Distributed Computing}, pages = {325--334} } @article{AngluinACER2009, author = {Dana Angluin and James Aspnes and Jiang Chen and David Eisenstat and Lev Reyzin}, title = {Learning acyclic probabilistic circuits using test paths}, month=aug, year = 2009, journal = {Journal of Machine Learning Research}, pages = {1881--1911}, volume = 10, number = {Aug} } @inproceedings{AspnesSY2008, author = {James Aspnes and Muli Safra and Yitong Yin}, title = {Ranged hash functions and the price of churn}, month = jan, year = {2008}, booktitle="Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms", pages = {1066--1075} } @inproceedings{AspnesW2007, author = {James Aspnes and Yinghua Wu}, title = {{$O(\log n)$}-time overlay network construction from graphs with out-degree {$1$}}, month = dec, year = 2007, booktitle = {Principles of Distributed Systems; 11th International Conference, OPODIS 2007, Gaudaloupe, French West Indies, December 17--20, 2007. Proceedings}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, volume = 4878, pages={286--300}} @inproceedings{AspnesRS2007, author = {James Aspnes and Navin Rustagi and Jared Saia}, title = {Worm Versus Alert: Who Wins in a Battle for Control of a Large-Scale Network?}, month = dec, year = 2007, booktitle = {Principles of Distributed Systems; 11th International Conference, OPODIS 2007, Gaudaloupe, French West Indies, December 17--20, 2007. Proceedings}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, volume = 4878, pages={443--456}} @article(AngluinAER2007, title="The computational power of population protocols", author="Dana Angluin and James Aspnes and David Eisenstat and Eric Ruppert", journal={Distributed Computing}, volume=20, number=4, pages={279--304}, month = nov, year = 2007, ) @article{AspnesR2007, author = {James Aspnes and Eric Ruppert}, title = {An introduction to population protocols}, journal = {Bulletin of the European Association for Theoretical Computer Science}, volume=93, pages={98--117}, month=oct, year = 2007} @incollection{AspnesR2009, author = {James Aspnes and Eric Ruppert}, title = {An introduction to population protocols}, booktitle = {Middleware for Network Eccentric and Mobile Applications}, editor = {Beno\^it Garbinato and Hugo Miranda and Lu\'is Rodrigues}, pages={97--120}, publisher = {Springer-Verlag}, year = 2009} @article{AngluinAE2008majority, author = {Dana Angluin and James Aspnes and David Eisenstat}, title = {A simple population protocol for fast robust approximate majority}, journal = {Distributed Computing}, volume=21, number=2, month = jul, year = 2008, pages= {87--102}, } @article{AngluinACR2008, author = {Dana Angluin and James Aspnes and Jiang Chen and Lev Reyzin}, title = {Learning large-alphabet and analog circuits with value injection queries}, journal = {Machine Learning}, volume = {72}, number = {1-2}, month = aug, year = {2008}, pages = {113-138}, } @inproceedings{AspnesYY2007, author = {James Aspnes and Yang Richard Yang and Yitong Yin}, title = {Path-independent load balancing with unreliable machines}, month = jan, year = {2007}, booktitle="Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms", pages = {814--823} } @article(AspnesEGMWYAB2006, title="A theory of network localization", author="J. Aspnes and T. Eren and D. K. Goldenberg and A. S. Morse and W. Whiteley and Y. R. Yang and B. D. O. Anderson and P. N. Belhumeur", journal="IEEE Transactions on Mobile Computing", volume=5, number=12, pages={1663--1678}, month=dec, year=2006 ) @article{AspnesBD+2006, author = {James Aspnes and Costas Busch and Shlomi Dolev and Panagiota Fatourou and Chryssis Georgiou and Alex Shvartsman and Paul Spirakis and Roger Wattenhofer}, title = {Eight open problems in distributed computing}, journal = {Bulletin of the European Association for Theoretical Computer Science}, volume = 90, pages = {109--126}, month = oct, year = 2006} @article(AngluinAE2008fast, title="Fast computation by population protocols with a leader", author="Dana Angluin and James Aspnes and David Eisenstat", journal="Distributed Computing", volume=21, number=3, month=sep, year=2008, pages={183--199} ) @inproceedings{AngluinAE2006semilinear, author = {Dana Angluin and James Aspnes and David Eisenstat}, title = {Stably computable predicates are semilinear}, booktitle = {PODC '06: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing}, year = {2006}, isbn = {1-59593-384-0}, pages = {292--299}, location = {Denver, Colorado, USA}, doi = {http://doi.acm.org/10.1145/1146381.1146425}, publisher = {ACM Press}, address = {New York, NY, USA}, } @article{AngluinACW2009, author = {Dana Angluin and James Aspnes and Jiang Chen and Yinghua Wu}, title = {Learning a circuit by injecting values}, journal = {Journal of Computer and System Sciences}, month = jan, year = {2009}, pages = {60--77}, volume = 75, number = 1, } @inproceedings(AngluinAER2005, title="On the power of anonymous one-way communication", author="Dana Angluin and James Aspnes and David Eisenstat and Eric Ruppert", booktitle="Principles of Distributed Systems; 9th International Conference, OPODIS 2005; Pisa, Italy; December 2005; Revised Selected Papers", series="Lecture Notes in Computer Science", volume=3974, month=dec, year=2005, pages={396--411} ) @article(AngluinAFJ2008, title="Self-stabilizing population protocols", author="Dana Angluin and James Aspnes and Michael J. Fischer and Hong Jiang", journal="ACM Transactions on Autonomous and Adaptive Systems", volume=3, number=4, pages={13}, month=nov, year=2008, ) @inproceedings(AbrahamAY2005, title="Skip {B}-trees", author="Ittai Abraham and James Aspnes and Jian Yuan", booktitle="Principles of Distributed Systems; 9th International Conference, OPODIS 2005; Pisa, Italy; December 2005; Revised Selected Papers", series="Lecture Notes in Computer Science", volume=3974, month=dec, year=2005, pages={366--380} ) @inproceedings(AspnesDGPY2005, title="Spreading alerts quietly and the subgroup escape problem", author="James Aspnes and Zo{\"e} Diamadi and Kristian Gj\o{}steen and Ren\'e Peralta and Aleksandr Yampolskiy", booktitle="Advances in Cryptology --- ASIACRYPT 2005: 11th International Conference on the Theory and Application of Cryptology and Information Security, Chennai, India, December 4--8, 2005. Proceedings.", publisher="Springer-Verlag", series="Lecture Notes in Computer Science", volume="3788", month=dec, year=2005, pages={253--272} ) @incollection(AspnesS2005, title="Distributed data structures for {P2P} systems", author="James Aspnes and Gauri Shah", booktitle="Theoretical and Algorithmic Aspects of Sensor, Ad Hoc Wireless and Peer-to-Peer Networks", editor="Jie Wu", publisher="CRC press", month=aug, pages={685--700}, year=2005 ) @techreport(AspnesJK2005, title="Exposing computationally-challenged {B}yzantine impostors", author="James Aspnes and Collin Jackson and Arvind Krishnamurthy", institution="Yale University Department of Computer Science", number="YALEU/DCS/TR-1332", month=jul, year=2005 ) @inproceedings(AngluinACWY2005, title="Fast construction of overlay networks", author="Dana Angluin and James Aspnes and Jiang Chen and Yinghua Wu and Yitong Yin", booktitle="Seventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures", month=jul, year=2005, pages={145--154} ) @article(AspnesW2009, title="The expansion and mixing time of skip graphs with applications", author="James Aspnes and Udi Wieder", journal="Distributed Computing", month=mar, year=2009, pages={385--393} ) @inproceedings(AngluinACFJP2005, title="Stably computable properties of network graphs", author="Dana Angluin and James Aspnes and Melody Chan and Michael J. Fischer and Hong Jiang and Ren\'e Peralta", booktitle="Distributed Computing in Sensor Systems: First IEEE International Conference, DCOSS 2005, Marina del Rey, CA, USE, June/July, 2005, Proceedings", editor="Viktor K. Prasanna and Sitharama Iyengar and Paul Spirakis and Matt Welsh", series="Lecture Notes in Computer Science", publisher="Springer-Verlag", pages = {63--74}, volume="3560", month=jun, year=2005 ) @article(AspnesCY2006, title="Inoculation strategies for victims of viruses and the sum-of-squares partition problem", author="James Aspnes and Kevin Chang and Aleksandr Yampolskiy", journal=jcss, volume=72, number=6, pages={1077--1093}, month=sep, year=2006, ) @article(AspnesFR2006, title="Relationships between broadcast and shared memory in reliable anonymous distributed systems", author="James Aspnes and Faith Ellen Fich and Eric Ruppert", journal={Distributed Computing}, volume=18, number=3, month=feb, year=2006, pages={209--219} ) @article(AspnesFYZ2007, title="Towards a theory of data entanglement", author="James Aspnes and Joan Feigenbaum and Aleksandr Yampolskiy and Sheng Zhong", journal="Theoretical Computer Science", volume=389, number={1--2}, month=dec, year=2007, ) @article(AngluinADFP2006, title="Computation in networks of passively mobile finite-state sensors", author="Dana Angluin and James Aspnes and Zo{\"e} Diamadi and Michael J. Fischer and Ren\'e Peralta", journal="Distributed Computing", month=mar, year=2006, pages={235--253} ) @inproceedings(AspnesKK2004, title="Load balancing and locality in range-queriable data structures", author="James Aspnes and Jonathan Kirsch and Arvind Krishnamurthy", booktitle="Twenty-Third ACM Symposium on Principles of Distributed Computing", month=jul, year=2004, pages={115--124} ) @inproceedings(AspnesGY2004, title="On the computational complexity of sensor network localization", author="James Aspnes and David Goldenberg and Yang Richard Yang", booktitle="Algorithmic Aspects of Wireless Sensor Networks: First International Workshop, ALGOSENSORS 2004, Turku, Finland, July 16, 2004. Proceedings.", series={Lecture Notes in Computer Science}, volume=3121, publisher="Springer-Verlag", year=2004, pages={32--44} ) @techreport(AngluinADFP2003, title="Urn automata", author="Dana Angluin and James Aspnes and Zo{\"e} Diamadi and Michael J. Fischer and Ren\'e Peralta", institution="Yale University Department of Computer Science", number="YALEU/DCS/TR-1280", month=nov, year=2003 ) @article(Aspnes2003, title="Randomized protocols for asynchronous consensus", author="James Aspnes", journal="Distributed Computing", volume=16, number={2--3}, pages={165--175}, month=sep, year=2003 ) @inproceedings(AspnesFMP2003, title="Towards better definitions and measures of Internet security", author="James Aspnes and Joan Feigenbaum and Michael Mitzenmacher and David C. Parkes", booktitle="Workshop on Large-Scale-Network Security and Deployment Obstacles", address="Landsdowne, VA", month=mar, year=2003 ) @article(AspnesS2007, title="Skip graphs", author="James Aspnes and Gauri Shah", journal="ACM Transactions on Algorithms", month=nov, year=2007, volume=3, number=4, pages={37} ) @inproceedings(AspnesDS2002, title="Fault-tolerant routing in peer-to-peer systems", author="James Aspnes and Zo{\"e} Diamadi and Gauri Shah", booktitle="Twenty-First ACM Symposium on Principles of Distributed Computing", month=jul, year=2002, pages={223--232} ) @inproceedings(AspnesSS2002, title="Wait-free consensus with infinite arrivals", author="James Aspnes and Gauri Shah and Jatin Shah", booktitle="Thirty-Fourth Annual ACM Symposium on Theory of Computing", month=may, year=2002, pages={524--533} ) @incollection(AkcogluADK2002, title="Opportunity-cost algorithms for combinatorial auctions", author="Karhan Akcoglu and James Aspnes and Bhaskar DasGupta and Ming-Yang Kao", booktitle="Applied Optimization 74: Computational Methods in Decision-Making, Economics and Finance", editor="E. J. Kontoghiorghes and B. Rustem and S. Siokos", publisher="Kluwer Academic Publishers", year=2002, pages={455--479} ) @article(AspnesHKKS2002, title="A combinatorial toolbox for protein sequence design and landscape analysis in the {G}rand {C}anonical model", author="James Aspnes and Julia Hartling and Ming-Yang Kao and Junhyong Kim and Gauri Shah", journal="Journal of Computational Biology", volume=9, number=5, pages={721--741}, month=oct, year=2002 ) @inproceedings(AspnesFFKK2001, title="Towards understanding the predictability of stock markets from the perspective of computational complexity", author="James Aspnes and David F. Fischer and Michael J. Fischer and Ming-Yang Kao and Alok Kumar", booktitle="Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms", month=jan, year=2001, pages={745--754} ) @article(Aspnes2002, title="Fast deterministic consensus in a noisy environment", author="James Aspnes", journal={Journal of Algorithms}, volume=45, number=1, pages={16--39}, month=oct, year=2002 ) @article(Aspnes1998coin, title="Lower bounds for distributed coin-flipping and randomized consensus", author="James Aspnes", journal=jacm, volume=45, number=3, pages={415--450}, month=may, year=1998 ) @incollection(Aspnes1998competitive, title="Competitive analysis of distributed algorithms", author="James Aspnes", booktitle="Online Algorithms: The State of the Art", editor="Amos Fiat and Gerhard Woeginger", series={Lecture Notes in Computer Science}, volume=1442, publisher="Springer-Verlag", year=1998, pages={118--146} ) @article(AspnesW2005compositional, title="Compositional competitiveness for distributed algorithms", author="James Aspnes and Orli Waarts", journal={Journal of Algorithms}, volume=54, number=2, pages={127--151}, month=feb, year=2005 ) @article(AspnesH1998, title="Spreading rumors rapidly despite an adversary", author="James Aspnes and William Hurwood", journal={Journal of Algorithms}, volume=26, number=2, pages={386--411}, month=feb, year=1998 ) @article(AjtaiANRSW1998, title="Fairness in scheduling", author="Miklos Ajtai and James Aspnes and Moni Naor and Yuval Rabani and Leonard J. Schulman and Orli Waarts", journal={Journal of Algorithms}, volume=29, number=2, pages={306--357}, month=nov, year=1998 ) @inproceedings(AjtaiADW1994, title="A theory of competitive analysis for distributed algorithms", author="Miklos Ajtai and James Aspnes and Cynthia Dwork and Orli Waarts", booktitle="Thirty-Fifth IEEE Symposium on Foundations of Computer Science", month=nov, year=1994, pages={401--411} ) @article(AspnesAFPW1993, title="On-line routing of virtual circuits with applications to load balancing and machine scheduling", author="James Aspnes and Yossi Azar and Amos Fiat and Serge Plotkin and Orli Waarts", journal=jacm, volume=44, number=3, pages={486--504}, month=may, year=1997 ) @article(AspnesW1996, title="Randomized consensus in $O(n \log^2 n)$ operations per processor", author="James Aspnes and Orli Waarts", journal=sicomp, volume=25, number=5, pages={1024--1044}, month=oct, year=1996 ) @phdthesis(Aspnes1992, title="Wait-Free Consensus", author="James Aspnes", school="Carnegie-Mellon University", year=1992 ) @article(AspnesHS1994, title="Counting networks", author="James Aspnes and Maurice Herlihy and Nir Shavit", journal=jacm, volume=41, number=5, pages={1020--1048}, month=sep, year=1994 ) @article(AspnesBFR1994, title="The expressive power of voting polynomials", author="James Aspnes and Richard Beigel and Merrick Furst and Steven Rudich", journal="Combinatorica", volume=14, number=2, pages={1--14}, year=1994 ) @article(AspnesH1990consensus, title="Fast randomized consensus using shared memory", author="James Aspnes and Maurice Herlihy", journal={Journal of Algorithms}, volume=11, number=3, pages={441--461}, month=sep, year=1990 ) @article(Aspnes1993, title="Time- and space-efficient randomized consensus", author="James Aspnes", journal={Journal of Algorithms}, volume=14, number=3, pages={414--431}, month=may, year=1993 ) @inproceedings(AspnesH1990waitfree, title="Wait-free data structures in the asynchronous {PRAM} model", author="James Aspnes and Maurice Herlihy", booktitle="Second Annual ACM Symposium on Parallel Algorithms and Architectures", month=jul, year=1990, pages={340--349} ) @inproceedings(AspnesFLMW1988, title="A theory of timestamp-based concurrency control for nested transactions", author="James Aspnes and Alan Fekete and Nancy Lynch and Michael Merritt and William Weihl", booktitle="Fourteenth International Conference on Very Large Databases", month=aug, year=1988, pages={431--444} )