[{"publication_status":"published","abstract":[{"lang":"eng","text":"Using wide-field narrow-band surveys, we provide a new measurement of the z = 6.6 Lymanα emitter (LAE) luminosity function (LF), which constraints the bright end for the first time. We use a combination of archival narrow-band NB921 data in UDS and new NB921 measurements in SA22 and COSMOS/UltraVISTA, all observed with the Subaru telescope, with a total area of ∼5 deg2. We exclude lower redshift interlopers by using broad-band optical and near-infrared photometry and also exclude three supernovae with data split over multiple epochs. Combining the UDS and COSMOS samples, we find no evolution of the bright end of the Lyα LF between z = 5.7 and 6.6, which is supported by spectroscopic follow-up, and conclude that sources with Himiko-like luminosity are not as rare as previously thought, with number densities of ∼1.5 × 10−5 Mpc−3. Combined with our wide-field SA22 measurements, our results indicate a non-Schechter-like bright end of the LF at z = 6.6 and a different evolution of observed faint and bright LAEs, overcoming cosmic variance. This differential evolution is also seen in the spectroscopic follow-up of UV-selected galaxies and is now also confirmed for LAEs, and we argue that it may be an effect of reionization. Using a toy model, we show that such differential evolution of the LF is expected, since brighter sources are able to ionize their surroundings earlier, such that Lyα photons are able to escape. Our targets are excellent candidates for detailed follow-up studies and provide the possibility to give a unique view on the earliest stages in the formation of galaxies and reionization process."}],"date_published":"2015-07-21T00:00:00Z","publisher":"Oxford University Press","title":"Identification of the brightest Lyα emitters at z = 6.6: implications for the evolution of the luminosity function in the reionization era","extern":"1","date_updated":"2022-08-19T08:25:25Z","citation":{"mla":"Matthee, Jorryt J., et al. “Identification of the Brightest Lyα Emitters at z = 6.6: Implications for the Evolution of the Luminosity Function in the Reionization Era.” Monthly Notices of the Royal Astronomical Society, vol. 451, no. 1, Oxford University Press, 2015, pp. 400–17, doi:10.1093/mnras/stv947.","short":"J.J. Matthee, D. Sobral, S. Santos, H. Röttgering, B. Darvish, B. Mobasher, Monthly Notices of the Royal Astronomical Society 451 (2015) 400–417.","chicago":"Matthee, Jorryt J, David Sobral, Sérgio Santos, Huub Röttgering, Behnam Darvish, and Bahram Mobasher. “Identification of the Brightest Lyα Emitters at z = 6.6: Implications for the Evolution of the Luminosity Function in the Reionization Era.” Monthly Notices of the Royal Astronomical Society. Oxford University Press, 2015. https://doi.org/10.1093/mnras/stv947.","ama":"Matthee JJ, Sobral D, Santos S, Röttgering H, Darvish B, Mobasher B. Identification of the brightest Lyα emitters at z = 6.6: implications for the evolution of the luminosity function in the reionization era. Monthly Notices of the Royal Astronomical Society. 2015;451(1):400-417. doi:10.1093/mnras/stv947","ista":"Matthee JJ, Sobral D, Santos S, Röttgering H, Darvish B, Mobasher B. 2015. Identification of the brightest Lyα emitters at z = 6.6: implications for the evolution of the luminosity function in the reionization era. Monthly Notices of the Royal Astronomical Society. 451(1), 400–417.","apa":"Matthee, J. J., Sobral, D., Santos, S., Röttgering, H., Darvish, B., & Mobasher, B. (2015). Identification of the brightest Lyα emitters at z = 6.6: implications for the evolution of the luminosity function in the reionization era. Monthly Notices of the Royal Astronomical Society. Oxford University Press. https://doi.org/10.1093/mnras/stv947","ieee":"J. J. Matthee, D. Sobral, S. Santos, H. Röttgering, B. Darvish, and B. Mobasher, “Identification of the brightest Lyα emitters at z = 6.6: implications for the evolution of the luminosity function in the reionization era,” Monthly Notices of the Royal Astronomical Society, vol. 451, no. 1. Oxford University Press, pp. 400–417, 2015."},"external_id":{"arxiv":["1502.07355"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","keyword":["Space and Planetary Science","Astronomy and Astrophysics"],"scopus_import":"1","arxiv":1,"intvolume":" 451","publication":"Monthly Notices of the Royal Astronomical Society","oa":1,"acknowledgement":"We thank the anonymous referee for the comments and suggestions which have improved the quality of this work. We thank Masami Ouchi for his useful comments on an earlier version of this paper. JM acknowledges the support of a Huygens PhD fellowship from Leiden University and is thankful for the hospitality of the Center for Astronomy and Astrophysics of the University of Lisbon where part of this research has been done. DS acknowledges financial support from the Netherlands Organization for Scientific research (NWO) through a Veni fellowship, from FCT through a FCT Investigator Starting Grant and Start-up Grant (IF/01154/2012/CP0189/CT0010) and from FCT grant PEstOE/FIS/UI2751/2014. HR acknowledges support from the ERC Advanced Investigator programme NewClusters 321271. We acknowledge the award of ESO DDT time (294.A-5018) for providing the possibility of a timely publication of this work.\r\nBased on observations with the Subaru Telescope (Programme IDs: our observations: S14A-086; archival: S05B-027, S06A-025, S06B-010, S07A-013, S07B-008, S08B-008 and S09A-017) and the W.M. Keck Observatory. The Subaru telescope is operated by the National Astronomical Observatory of Japan. The W.M. Keck Observatory is operated as a scientific partnership among the California Institute of Technology, the University of California and the National Aeronautics and Space Administration. Based on observations made with ESO Telescopes at the La Silla Paranal Observatory under programme ID 294.A-5018. Based on observations obtained with MegaPrime/Megacam, a joint project of CFHT and CEA/IRFU, at the Canada–France-Hawaii Telescope (CFHT) which is operated by the National Research Council (NRC) of Canada, the Institut National des Science de l’Univers of the Centre National de la Recherche Scientifique (CNRS) of France, and the University of Hawaii. This work is based in part on data products produced at Terapix available at the Canadian Astronomy Data Centre as part of the CFHT Legacy Survey, a collaborative project of NRC and CNRS. Based on data products from observations made with ESO Telescopes at the La Silla Paranal Observatory under ESO programme ID 179.A-2005 and on data products produced by TERAPIX and the Cambridge Astronomy Survey Unit on behalf of the UltraVISTA consortium.\r\nIn addition to the CFHT-LS and COSMOS-UltraVISTA surveys, we are grateful for the excellent data sets from the UKIRT-DXS, SXDF and S-COSMOS survey teams, without these legacy surveys, this research would have been impossible. We have benefited greatly from the public available programming language PYTHON, including the NUMPY, MATPLOTLIB, PYFITS, SCIPY and ASTROPY packages, the astronomical imaging tools SEXTRACTOR, SWARP and SCAMP and the indispensable TOPCAT analysis tool (Taylor 2013)","year":"2015","page":"400-417","doi":"10.1093/mnras/stv947","day":"21","month":"07","issue":"1","language":[{"iso":"eng"}],"volume":451,"article_processing_charge":"No","quality_controlled":"1","oa_version":"Preprint","author":[{"id":"7439a258-f3c0-11ec-9501-9df22fe06720","full_name":"Matthee, Jorryt J","last_name":"Matthee","first_name":"Jorryt J","orcid":"0000-0003-2871-127X"},{"last_name":"Sobral","first_name":"David","full_name":"Sobral, David"},{"full_name":"Santos, Sérgio","last_name":"Santos","first_name":"Sérgio"},{"full_name":"Röttgering, Huub","last_name":"Röttgering","first_name":"Huub"},{"full_name":"Darvish, Behnam","last_name":"Darvish","first_name":"Behnam"},{"first_name":"Bahram","last_name":"Mobasher","full_name":"Mobasher, Bahram"}],"date_created":"2022-07-14T11:57:03Z","article_type":"original","_id":"11581","type":"journal_article","status":"public","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1502.07355"}],"publication_identifier":{"eissn":["1365-2966"],"issn":["0035-8711"]}},{"oa":1,"year":"2015","doi":"10.1145/2818357","day":"05","keyword":["Algorithms","Economics","Clinching ascending auction","auctions with budgets","Sponsored search auctions"],"scopus_import":"1","intvolume":" 4","publication":"ACM Transactions on Economics and Computation","date_updated":"2023-02-09T10:03:35Z","extern":"1","citation":{"mla":"Colini-Baldeschi, Riccardo, et al. “On Multiple Keyword Sponsored Search Auctions with Budgets.” ACM Transactions on Economics and Computation, vol. 4, no. 1, 2, Association for Computing Machinery, 2015, doi:10.1145/2818357.","short":"R. Colini-Baldeschi, S. Leonardi, M.H. Henzinger, M. Starnberger, ACM Transactions on Economics and Computation 4 (2015).","ieee":"R. Colini-Baldeschi, S. Leonardi, M. H. Henzinger, and M. Starnberger, “On multiple keyword sponsored search auctions with budgets,” ACM Transactions on Economics and Computation, vol. 4, no. 1. Association for Computing Machinery, 2015.","chicago":"Colini-Baldeschi, Riccardo, Stefano Leonardi, Monika H Henzinger, and Martin Starnberger. “On Multiple Keyword Sponsored Search Auctions with Budgets.” ACM Transactions on Economics and Computation. Association for Computing Machinery, 2015. https://doi.org/10.1145/2818357.","ama":"Colini-Baldeschi R, Leonardi S, Henzinger MH, Starnberger M. On multiple keyword sponsored search auctions with budgets. ACM Transactions on Economics and Computation. 2015;4(1). doi:10.1145/2818357","ista":"Colini-Baldeschi R, Leonardi S, Henzinger MH, Starnberger M. 2015. On multiple keyword sponsored search auctions with budgets. ACM Transactions on Economics and Computation. 4(1), 2.","apa":"Colini-Baldeschi, R., Leonardi, S., Henzinger, M. H., & Starnberger, M. (2015). On multiple keyword sponsored search auctions with budgets. ACM Transactions on Economics and Computation. Association for Computing Machinery. https://doi.org/10.1145/2818357"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"lang":"eng","text":"We study multiple keyword sponsored search auctions with budgets. Each keyword has multiple ad slots with a click-through rate. The bidders have additive valuations, which are linear in the click-through rates, and budgets, which are restricting their overall payments. Additionally, the number of slots per keyword assigned to a bidder is bounded.\r\n\r\nWe show the following results: (1) We give the first mechanism for multiple keywords, where click-through rates differ among slots. Our mechanism is incentive compatible in expectation, individually rational in expectation, and Pareto optimal. (2) We study the combinatorial setting, where each bidder is only interested in a subset of the keywords. We give an incentive compatible, individually rational, Pareto-optimal, and deterministic mechanism for identical click-through rates. (3) We give an impossibility result for incentive compatible, individually rational, Pareto-optimal, and deterministic mechanisms for bidders with diminishing marginal valuations."}],"publication_status":"published","publisher":"Association for Computing Machinery","date_published":"2015-12-05T00:00:00Z","title":"On multiple keyword sponsored search auctions with budgets","date_created":"2022-07-27T11:54:56Z","type":"journal_article","_id":"11668","article_type":"original","publication_identifier":{"eissn":["2167-8383"],"issn":["2167-8375"]},"status":"public","main_file_link":[{"url":"http://eprints.cs.univie.ac.at/3510/","open_access":"1"}],"quality_controlled":"1","oa_version":"Submitted Version","author":[{"last_name":"Colini-Baldeschi","first_name":"Riccardo","full_name":"Colini-Baldeschi, Riccardo"},{"full_name":"Leonardi, Stefano","first_name":"Stefano","last_name":"Leonardi"},{"full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","last_name":"Henzinger","first_name":"Monika H"},{"first_name":"Martin","last_name":"Starnberger","full_name":"Starnberger, Martin"}],"month":"12","issue":"1","article_number":"2","language":[{"iso":"eng"}],"article_processing_charge":"No","volume":4},{"_id":"11669","type":"journal_article","article_type":"original","date_created":"2022-07-27T12:09:15Z","publication_identifier":{"issn":["2167-8375"],"eissn":["2167-8383"]},"status":"public","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1209.6448"}],"issue":"1","article_number":"4","month":"12","article_processing_charge":"No","volume":4,"language":[{"iso":"eng"}],"oa_version":"Preprint","quality_controlled":"1","author":[{"full_name":"Dütting, Paul","last_name":"Dütting","first_name":"Paul"},{"full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","first_name":"Monika H","last_name":"Henzinger"},{"last_name":"Starnberger","first_name":"Martin","full_name":"Starnberger, Martin"}],"keyword":["Algorithmic game theory","auction theory","Clinching auction","Pareto optimality","Budget limits"],"scopus_import":"1","publication":"ACM Transactions on Economics and Computation","intvolume":" 4","arxiv":1,"oa":1,"day":"05","year":"2015","doi":"10.1145/2818351","abstract":[{"lang":"eng","text":"We study individual rational, Pareto-optimal, and incentive compatible mechanisms for auctions with heterogeneous items and budget limits. We consider settings with multiunit demand and additive valuations. For single-dimensional valuations we prove a positive result for randomized mechanisms, and a negative result for deterministic mechanisms. While the positive result allows for private budgets, the negative result is for public budgets. For multidimensional valuations and public budgets we prove an impossibility result that applies to deterministic and randomized mechanisms. Taken together this shows the power of randomization in certain settings with heterogeneous items, but it also shows its limitations."}],"publication_status":"published","title":"Auctions for heterogeneous items and budget limits","publisher":"Association for Computing Machinery","date_published":"2015-12-05T00:00:00Z","citation":{"ieee":"P. Dütting, M. H. Henzinger, and M. Starnberger, “Auctions for heterogeneous items and budget limits,” ACM Transactions on Economics and Computation, vol. 4, no. 1. Association for Computing Machinery, 2015.","ista":"Dütting P, Henzinger MH, Starnberger M. 2015. Auctions for heterogeneous items and budget limits. ACM Transactions on Economics and Computation. 4(1), 4.","chicago":"Dütting, Paul, Monika H Henzinger, and Martin Starnberger. “Auctions for Heterogeneous Items and Budget Limits.” ACM Transactions on Economics and Computation. Association for Computing Machinery, 2015. https://doi.org/10.1145/2818351.","ama":"Dütting P, Henzinger MH, Starnberger M. Auctions for heterogeneous items and budget limits. ACM Transactions on Economics and Computation. 2015;4(1). doi:10.1145/2818351","apa":"Dütting, P., Henzinger, M. H., & Starnberger, M. (2015). Auctions for heterogeneous items and budget limits. ACM Transactions on Economics and Computation. Association for Computing Machinery. https://doi.org/10.1145/2818351","short":"P. Dütting, M.H. Henzinger, M. Starnberger, ACM Transactions on Economics and Computation 4 (2015).","mla":"Dütting, Paul, et al. “Auctions for Heterogeneous Items and Budget Limits.” ACM Transactions on Economics and Computation, vol. 4, no. 1, 4, Association for Computing Machinery, 2015, doi:10.1145/2818351."},"date_updated":"2022-09-09T12:08:37Z","extern":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","external_id":{"arxiv":["1209.6448"]}},{"citation":{"mla":"Dütting, Paul, et al. “An Expressive Mechanism for Auctions on the Web.” ACM Transactions on Economics and Computation, vol. 4, no. 1, 1, Association for Computing Machinery, 2015, doi:10.1145/2716312.","short":"P. Dütting, M.H. Henzinger, I. Weber, ACM Transactions on Economics and Computation 4 (2015).","ieee":"P. Dütting, M. H. Henzinger, and I. Weber, “An expressive mechanism for auctions on the web,” ACM Transactions on Economics and Computation, vol. 4, no. 1. Association for Computing Machinery, 2015.","apa":"Dütting, P., Henzinger, M. H., & Weber, I. (2015). An expressive mechanism for auctions on the web. ACM Transactions on Economics and Computation. Association for Computing Machinery. https://doi.org/10.1145/2716312","ista":"Dütting P, Henzinger MH, Weber I. 2015. An expressive mechanism for auctions on the web. ACM Transactions on Economics and Computation. 4(1), 1.","ama":"Dütting P, Henzinger MH, Weber I. An expressive mechanism for auctions on the web. ACM Transactions on Economics and Computation. 2015;4(1). doi:10.1145/2716312","chicago":"Dütting, Paul, Monika H Henzinger, and Ingmar Weber. “An Expressive Mechanism for Auctions on the Web.” ACM Transactions on Economics and Computation. Association for Computing Machinery, 2015. https://doi.org/10.1145/2716312."},"date_updated":"2023-02-09T10:08:41Z","extern":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"lang":"eng","text":"Auctions are widely used on the Web. Applications range from sponsored search to platforms such as eBay. In these and in many other applications the auctions in use are single-/multi-item auctions with unit demand. The main drawback of standard mechanisms for this type of auctions, such as VCG and GSP, is the limited expressiveness that they offer to the bidders. The General Auction Mechanism (GAM) of Aggarwal et al. [2009] takes a first step toward addressing the problem of limited expressiveness by computing a bidder optimal, envy-free outcome for linear utility functions with identical slopes and a single discontinuity per bidder-item pair. We show that in many practical situations this does not suffice to adequately model the preferences of the bidders, and we overcome this problem by presenting the first mechanism for piecewise linear utility functions with nonidentical slopes and multiple discontinuities. Our mechanism runs in polynomial time. Like GAM it is incentive compatible for inputs that fulfill a certain nondegeneracy assumption, but our requirement is more general than the requirement of GAM. For discontinuous utility functions that are nondegenerate as well as for continuous utility functions the outcome of our mechanism is a competitive equilibrium. We also show how our mechanism can be used to compute approximately bidder optimal, envy-free outcomes for a general class of continuous utility functions via piecewise linear approximation. Finally, we prove hardness results for even more expressive settings."}],"publication_status":"published","title":"An expressive mechanism for auctions on the web","publisher":"Association for Computing Machinery","date_published":"2015-12-02T00:00:00Z","year":"2015","doi":"10.1145/2716312","day":"02","acknowledgement":"We would like to thank Veronika Loitzenbauer and the anonymous referees for their valuable feedback.","keyword":["Computational Mathematics","Marketing","Economics and Econometrics","Statistics and Probability","Computer Science (miscellaneous)"],"scopus_import":"1","publication":"ACM Transactions on Economics and Computation","intvolume":" 4","oa_version":"None","quality_controlled":"1","author":[{"first_name":"Paul","last_name":"Dütting","full_name":"Dütting, Paul"},{"full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","first_name":"Monika H","last_name":"Henzinger"},{"full_name":"Weber, Ingmar","first_name":"Ingmar","last_name":"Weber"}],"issue":"1","article_number":"1","month":"12","article_processing_charge":"No","volume":4,"language":[{"iso":"eng"}],"_id":"11670","type":"journal_article","article_type":"original","date_created":"2022-07-27T12:43:18Z","status":"public","publication_identifier":{"eissn":["2167-8383"],"issn":["2167-8375"]}},{"title":"Ad exchange: Envy-free auctions with mediators","date_published":"2015-12-09T00:00:00Z","publisher":"Springer Nature","abstract":[{"text":"Ad exchanges are an emerging platform for trading advertisement slots on the web with billions of dollars revenue per year. Every time a user visits a web page, the publisher of that web page can ask an ad exchange to auction off the ad slots on this page to determine which advertisements are shown at which price. Due to the high volume of traffic, ad networks typically act as mediators for individual advertisers at ad exchanges. If multiple advertisers in an ad network are interested in the ad slots of the same auction, the ad network might use a “local” auction to resell the obtained ad slots among its advertisers.\r\n\r\nIn this work we want to deepen the theoretical understanding of these new markets by analyzing them from the viewpoint of combinatorial auctions. Prior work studied mostly single-item auctions, while we allow the advertisers to express richer preferences over multiple items. We develop a game-theoretic model for the entanglement of the central auction at the ad exchange with the local auctions at the ad networks. We consider the incentives of all three involved parties and suggest a three-party competitive equilibrium, an extension of the Walrasian equilibrium that ensures envy-freeness for all participants. We show the existence of a three-party competitive equilibrium and a polynomial-time algorithm to find one for gross-substitute bidder valuations.","lang":"eng"}],"publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","external_id":{"arxiv":["1604.05562"]},"alternative_title":["LNCS"],"citation":{"apa":"Ben-Zwi, O., Henzinger, M. H., & Loitzenbauer, V. (2015). Ad exchange: Envy-free auctions with mediators. In 11th International Conference on Web and Internet Economics (Vol. 9470, pp. 104–117). Amsterdam, Netherlands: Springer Nature. https://doi.org/10.1007/978-3-662-48995-6_8","ista":"Ben-Zwi O, Henzinger MH, Loitzenbauer V. 2015. Ad exchange: Envy-free auctions with mediators. 11th International Conference on Web and Internet Economics. WINE: International Conference on Web and Internet Economics, LNCS, vol. 9470, 104–117.","chicago":"Ben-Zwi, Oren, Monika H Henzinger, and Veronika Loitzenbauer. “Ad Exchange: Envy-Free Auctions with Mediators.” In 11th International Conference on Web and Internet Economics, 9470:104–117. Springer Nature, 2015. https://doi.org/10.1007/978-3-662-48995-6_8.","ama":"Ben-Zwi O, Henzinger MH, Loitzenbauer V. Ad exchange: Envy-free auctions with mediators. In: 11th International Conference on Web and Internet Economics. Vol 9470. Springer Nature; 2015:104–117. doi:10.1007/978-3-662-48995-6_8","ieee":"O. Ben-Zwi, M. H. Henzinger, and V. Loitzenbauer, “Ad exchange: Envy-free auctions with mediators,” in 11th International Conference on Web and Internet Economics, Amsterdam, Netherlands, 2015, vol. 9470, pp. 104–117.","mla":"Ben-Zwi, Oren, et al. “Ad Exchange: Envy-Free Auctions with Mediators.” 11th International Conference on Web and Internet Economics, vol. 9470, Springer Nature, 2015, pp. 104–117, doi:10.1007/978-3-662-48995-6_8.","short":"O. Ben-Zwi, M.H. Henzinger, V. Loitzenbauer, in:, 11th International Conference on Web and Internet Economics, Springer Nature, 2015, pp. 104–117."},"date_updated":"2023-02-10T09:06:23Z","extern":"1","publication":"11th International Conference on Web and Internet Economics","intvolume":" 9470","arxiv":1,"scopus_import":"1","year":"2015","doi":"10.1007/978-3-662-48995-6_8","page":"104–117","day":"09","oa":1,"article_processing_charge":"No","volume":9470,"language":[{"iso":"eng"}],"month":"12","author":[{"first_name":"Oren","last_name":"Ben-Zwi","full_name":"Ben-Zwi, Oren"},{"orcid":"0000-0002-5008-6530","last_name":"Henzinger","first_name":"Monika H","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"full_name":"Loitzenbauer, Veronika","first_name":"Veronika","last_name":"Loitzenbauer"}],"oa_version":"Preprint","quality_controlled":"1","conference":{"location":"Amsterdam, Netherlands","name":"WINE: International Conference on Web and Internet Economics","end_date":"2015-09-12","start_date":"2015-09-09"},"main_file_link":[{"url":"https://doi.org/10.48550/arXiv.1604.05562","open_access":"1"}],"status":"public","publication_identifier":{"isbn":["9783662489949"],"eisbn":["9783662489956"],"issn":["0302-9743"]},"_id":"11773","type":"conference","date_created":"2022-08-08T13:33:56Z"},{"conference":{"end_date":"2015-12-12","start_date":"2015-12-09","name":"WINE: International Conference on Web and Internet Economics","location":"Amsterdam, Netherlands"},"_id":"11774","type":"conference","date_created":"2022-08-08T13:54:32Z","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.1509.09147"}],"status":"public","publication_identifier":{"issn":["0302-9743"],"isbn":["9783662489949"],"eisbn":["9783662489956"]},"month":"12","volume":9470,"article_processing_charge":"No","language":[{"iso":"eng"}],"oa_version":"Preprint","quality_controlled":"1","author":[{"full_name":"Cheung, Yun Kuen","last_name":"Cheung","first_name":"Yun Kuen"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","first_name":"Monika H","last_name":"Henzinger","orcid":"0000-0002-5008-6530"},{"full_name":"Hoefer, Martin","last_name":"Hoefer","first_name":"Martin"},{"full_name":"Starnberger, Martin","first_name":"Martin","last_name":"Starnberger"}],"scopus_import":"1","publication":"11th International Conference on Web and Internet Economics","arxiv":1,"intvolume":" 9470","oa":1,"day":"09","year":"2015","doi":"10.1007/978-3-662-48995-6_17","page":"230–243","publication_status":"published","abstract":[{"lang":"eng","text":"Combinatorial auctions (CA) are a well-studied area in algorithmic mechanism design. However, contrary to the standard model, empirical studies suggest that a bidder’s valuation often does not depend solely on the goods assigned to him. For instance, in adwords auctions an advertiser might not want his ads to be displayed next to his competitors’ ads. In this paper, we propose and analyze several natural graph-theoretic models that incorporate such negative externalities, in which bidders form a directed conflict graph with maximum out-degree Δ. We design algorithms and truthful mechanisms for social welfare maximization that attain approximation ratios depending on Δ.\r\n\r\nFor CA, our results are twofold: (1) A lottery that eliminates conflicts by discarding bidders/items independent of the bids. It allows to apply any truthful 𝛼-approximation mechanism for conflict-free valuations and yields an 𝒪(𝛼Δ)-approximation mechanism. (2) For fractionally sub-additive valuations, we design a rounding algorithm via a novel combination of a semi-definite program and a linear program, resulting in a cone program; the approximation ratio is 𝒪((ΔloglogΔ)/logΔ). The ratios are almost optimal given existing hardness results.\r\n\r\nFor adwords auctions, we present several algorithms for the most relevant scenario when the number of items is small. In particular, we design a truthful mechanism with approximation ratio 𝑜(Δ) when the number of items is only logarithmic in the number of bidders."}],"title":"Combinatorial auctions with conflict-based externalities","publisher":"Springer Nature","date_published":"2015-12-09T00:00:00Z","citation":{"ieee":"Y. K. Cheung, M. H. Henzinger, M. Hoefer, and M. Starnberger, “Combinatorial auctions with conflict-based externalities,” in 11th International Conference on Web and Internet Economics, Amsterdam, Netherlands, 2015, vol. 9470, pp. 230–243.","apa":"Cheung, Y. K., Henzinger, M. H., Hoefer, M., & Starnberger, M. (2015). Combinatorial auctions with conflict-based externalities. In 11th International Conference on Web and Internet Economics (Vol. 9470, pp. 230–243). Amsterdam, Netherlands: Springer Nature. https://doi.org/10.1007/978-3-662-48995-6_17","chicago":"Cheung, Yun Kuen, Monika H Henzinger, Martin Hoefer, and Martin Starnberger. “Combinatorial Auctions with Conflict-Based Externalities.” In 11th International Conference on Web and Internet Economics, 9470:230–243. Springer Nature, 2015. https://doi.org/10.1007/978-3-662-48995-6_17.","ista":"Cheung YK, Henzinger MH, Hoefer M, Starnberger M. 2015. Combinatorial auctions with conflict-based externalities. 11th International Conference on Web and Internet Economics. WINE: International Conference on Web and Internet Economics, LNCS, vol. 9470, 230–243.","ama":"Cheung YK, Henzinger MH, Hoefer M, Starnberger M. Combinatorial auctions with conflict-based externalities. In: 11th International Conference on Web and Internet Economics. Vol 9470. Springer Nature; 2015:230–243. doi:10.1007/978-3-662-48995-6_17","short":"Y.K. Cheung, M.H. Henzinger, M. Hoefer, M. Starnberger, in:, 11th International Conference on Web and Internet Economics, Springer Nature, 2015, pp. 230–243.","mla":"Cheung, Yun Kuen, et al. “Combinatorial Auctions with Conflict-Based Externalities.” 11th International Conference on Web and Internet Economics, vol. 9470, Springer Nature, 2015, pp. 230–243, doi:10.1007/978-3-662-48995-6_17."},"extern":"1","date_updated":"2023-02-10T09:08:30Z","external_id":{"arxiv":["1509.09147"]},"alternative_title":["LNCS"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},{"conference":{"end_date":"2015-07-10","start_date":"2015-07-06","location":"Kyoto, Japan","name":"ICALP: International Colloquium on Automata, Languages, and Programming"},"date_created":"2022-08-11T08:51:32Z","_id":"11785","type":"conference","main_file_link":[{"url":"https://arxiv.org/abs/1612.03856","open_access":"1"}],"status":"public","publication_identifier":{"issn":["0302-9743"],"isbn":["9783662476710"]},"month":"01","language":[{"iso":"eng"}],"volume":9134,"article_processing_charge":"No","quality_controlled":"1","oa_version":"Preprint","author":[{"last_name":"Henzinger","first_name":"Monika H","orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H"},{"full_name":"Krinninger, Sebastian","first_name":"Sebastian","last_name":"Krinninger"},{"first_name":"Danupon","last_name":"Nanongkai","full_name":"Nanongkai, Danupon"}],"scopus_import":"1","arxiv":1,"intvolume":" 9134","publication":"42nd International Colloquium on Automata, Languages and Programming","oa":1,"page":"725 - 736","day":"01","year":"2015","doi":"10.1007/978-3-662-47672-7_59","publication_status":"published","abstract":[{"text":"Recently we presented the first algorithm for maintaining the set of nodes reachable from a source node in a directed graph that is modified by edge deletions with 𝑜(𝑚𝑛) total update time, where 𝑚 is the number of edges and 𝑛 is the number of nodes in the graph [Henzinger et al. STOC 2014]. The algorithm is a combination of several different algorithms, each for a different 𝑚 vs. 𝑛 trade-off. For the case of 𝑚=Θ(𝑛1.5) the running time is 𝑂(𝑛2.47), just barely below 𝑚𝑛=Θ(𝑛2.5). In this paper we simplify the previous algorithm using new algorithmic ideas and achieve an improved running time of 𝑂̃ (min(𝑚7/6𝑛2/3,𝑚3/4𝑛5/4+𝑜(1),𝑚2/3𝑛4/3+𝑜(1)+𝑚3/7𝑛12/7+𝑜(1))). This gives, e.g., 𝑂(𝑛2.36) for the notorious case 𝑚=Θ(𝑛1.5). We obtain the same upper bounds for the problem of maintaining the strongly connected components of a directed graph undergoing edge deletions. Our algorithms are correct with high probabililty against an oblivious adversary.","lang":"eng"}],"date_published":"2015-01-01T00:00:00Z","publisher":"Springer Nature","title":"Improved algorithms for decremental single-source reachability on directed graphs","extern":"1","date_updated":"2023-02-10T09:10:26Z","citation":{"short":"M.H. Henzinger, S. Krinninger, D. Nanongkai, in:, 42nd International Colloquium on Automata, Languages and Programming, Springer Nature, 2015, pp. 725–736.","mla":"Henzinger, Monika H., et al. “Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs.” 42nd International Colloquium on Automata, Languages and Programming, vol. 9134, Springer Nature, 2015, pp. 725–36, doi:10.1007/978-3-662-47672-7_59.","apa":"Henzinger, M. H., Krinninger, S., & Nanongkai, D. (2015). Improved algorithms for decremental single-source reachability on directed graphs. In 42nd International Colloquium on Automata, Languages and Programming (Vol. 9134, pp. 725–736). Kyoto, Japan: Springer Nature. https://doi.org/10.1007/978-3-662-47672-7_59","ista":"Henzinger MH, Krinninger S, Nanongkai D. 2015. Improved algorithms for decremental single-source reachability on directed graphs. 42nd International Colloquium on Automata, Languages and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LNCS, vol. 9134, 725–736.","chicago":"Henzinger, Monika H, Sebastian Krinninger, and Danupon Nanongkai. “Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs.” In 42nd International Colloquium on Automata, Languages and Programming, 9134:725–36. Springer Nature, 2015. https://doi.org/10.1007/978-3-662-47672-7_59.","ama":"Henzinger MH, Krinninger S, Nanongkai D. Improved algorithms for decremental single-source reachability on directed graphs. In: 42nd International Colloquium on Automata, Languages and Programming. Vol 9134. Springer Nature; 2015:725-736. doi:10.1007/978-3-662-47672-7_59","ieee":"M. H. Henzinger, S. Krinninger, and D. Nanongkai, “Improved algorithms for decremental single-source reachability on directed graphs,” in 42nd International Colloquium on Automata, Languages and Programming, Kyoto, Japan, 2015, vol. 9134, pp. 725–736."},"alternative_title":["LNCS"],"external_id":{"arxiv":["1612.03856"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},{"status":"public","publication_identifier":{"issn":["0302-9743"],"isbn":["9783662476710"]},"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1604.05337"}],"type":"conference","_id":"11786","date_created":"2022-08-11T09:28:49Z","conference":{"name":"ICALP: International Colloquium on Automata, Languages, and Programming","location":"Kyoto, Japan","start_date":"2015-07-06","end_date":"2015-07-10"},"author":[{"last_name":"Bhattacharya","first_name":"Sayan","full_name":"Bhattacharya, Sayan"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","first_name":"Monika H","last_name":"Henzinger","orcid":"0000-0002-5008-6530"},{"last_name":"Italiano","first_name":"Giuseppe F.","full_name":"Italiano, Giuseppe F."}],"oa_version":"Preprint","quality_controlled":"1","article_processing_charge":"No","volume":9134,"language":[{"iso":"eng"}],"month":"01","day":"01","doi":"10.1007/978-3-662-47672-7_17","page":"206 - 218","year":"2015","oa":1,"publication":"42nd International Colloquium on Automata, Languages and Programming","intvolume":" 9134","arxiv":1,"scopus_import":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","alternative_title":["LNCS"],"external_id":{"arxiv":["1604.05337"]},"citation":{"apa":"Bhattacharya, S., Henzinger, M. H., & Italiano, G. F. (2015). Design of dynamic algorithms via primal-dual method. In 42nd International Colloquium on Automata, Languages and Programming (Vol. 9134, pp. 206–218). Kyoto, Japan: Springer Nature. https://doi.org/10.1007/978-3-662-47672-7_17","ista":"Bhattacharya S, Henzinger MH, Italiano GF. 2015. Design of dynamic algorithms via primal-dual method. 42nd International Colloquium on Automata, Languages and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LNCS, vol. 9134, 206–218.","ama":"Bhattacharya S, Henzinger MH, Italiano GF. Design of dynamic algorithms via primal-dual method. In: 42nd International Colloquium on Automata, Languages and Programming. Vol 9134. Springer Nature; 2015:206-218. doi:10.1007/978-3-662-47672-7_17","chicago":"Bhattacharya, Sayan, Monika H Henzinger, and Giuseppe F. Italiano. “Design of Dynamic Algorithms via Primal-Dual Method.” In 42nd International Colloquium on Automata, Languages and Programming, 9134:206–18. Springer Nature, 2015. https://doi.org/10.1007/978-3-662-47672-7_17.","ieee":"S. Bhattacharya, M. H. Henzinger, and G. F. Italiano, “Design of dynamic algorithms via primal-dual method,” in 42nd International Colloquium on Automata, Languages and Programming, Kyoto, Japan, 2015, vol. 9134, pp. 206–218.","short":"S. Bhattacharya, M.H. Henzinger, G.F. Italiano, in:, 42nd International Colloquium on Automata, Languages and Programming, Springer Nature, 2015, pp. 206–218.","mla":"Bhattacharya, Sayan, et al. “Design of Dynamic Algorithms via Primal-Dual Method.” 42nd International Colloquium on Automata, Languages and Programming, vol. 9134, Springer Nature, 2015, pp. 206–18, doi:10.1007/978-3-662-47672-7_17."},"date_updated":"2023-02-10T09:13:31Z","extern":"1","title":"Design of dynamic algorithms via primal-dual method","date_published":"2015-01-01T00:00:00Z","publisher":"Springer Nature","abstract":[{"text":"In this paper, we develop a dynamic version of the primal-dual method for optimization problems, and apply it to obtain the following results. (1) For the dynamic set-cover problem, we maintain an 𝑂(𝑓2)-approximately optimal solution in 𝑂(𝑓⋅log(𝑚+𝑛)) amortized update time, where 𝑓 is the maximum “frequency” of an element, 𝑛 is the number of sets, and 𝑚 is the maximum number of elements in the universe at any point in time. (2) For the dynamic 𝑏-matching problem, we maintain an 𝑂(1)-approximately optimal solution in 𝑂(log3𝑛) amortized update time, where 𝑛 is the number of nodes in the graph.","lang":"eng"}],"publication_status":"published"},{"language":[{"iso":"eng"}],"article_processing_charge":"No","volume":9134,"month":"07","author":[{"orcid":"0000-0002-5008-6530","first_name":"Monika H","last_name":"Henzinger","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"first_name":"Sebastian","last_name":"Krinninger","full_name":"Krinninger, Sebastian"},{"first_name":"Veronika","last_name":"Loitzenbauer","full_name":"Loitzenbauer, Veronika"}],"quality_controlled":"1","oa_version":"Preprint","conference":{"start_date":"2015-07-06","end_date":"2015-07-10","location":"Kyoto, Japan","name":"ICALP: International Colloquium on Automata, Languages, and Programming"},"publication_identifier":{"issn":["0302-9743"],"isbn":["9783662476710"]},"status":"public","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1412.6466"}],"date_created":"2022-08-11T09:38:34Z","type":"conference","_id":"11787","publisher":"Springer Nature","date_published":"2015-07-06T00:00:00Z","title":"Finding 2-edge and 2-vertex strongly connected components in quadratic time","abstract":[{"text":"We present faster algorithms for computing the 2-edge and 2-vertex strongly connected components of a directed graph. While in undirected graphs the 2-edge and 2-vertex connected components can be found in linear time, in directed graphs with m edges and n vertices only rather simple O(m n)-time algorithms were known. We use a hierarchical sparsification technique to obtain algorithms that run in time 𝑂(𝑛2). For 2-edge strongly connected components our algorithm gives the first running time improvement in 20 years. Additionally we present an 𝑂(𝑚2/log𝑛)-time algorithm for 2-edge strongly connected components, and thus improve over the O(m n) running time also when 𝑚=𝑂(𝑛). Our approach extends to k-edge and k-vertex strongly connected components for any constant k with a running time of 𝑂(𝑛2log𝑛) for k-edge-connectivity and 𝑂(𝑛3) for k-vertex-connectivity.","lang":"eng"}],"publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","external_id":{"arxiv":["1412.6466"]},"alternative_title":["LNCS"],"date_updated":"2023-02-10T09:21:47Z","extern":"1","citation":{"apa":"Henzinger, M. H., Krinninger, S., & Loitzenbauer, V. (2015). Finding 2-edge and 2-vertex strongly connected components in quadratic time. In 2nd International Colloquium on Automata, Languages and Programming (Vol. 9134, pp. 713–724). Kyoto, Japan: Springer Nature. https://doi.org/10.1007/978-3-662-47672-7_58","ama":"Henzinger MH, Krinninger S, Loitzenbauer V. Finding 2-edge and 2-vertex strongly connected components in quadratic time. In: 2nd International Colloquium on Automata, Languages and Programming. Vol 9134. Springer Nature; 2015:713-724. doi:10.1007/978-3-662-47672-7_58","ista":"Henzinger MH, Krinninger S, Loitzenbauer V. 2015. Finding 2-edge and 2-vertex strongly connected components in quadratic time. 2nd International Colloquium on Automata, Languages and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LNCS, vol. 9134, 713–724.","chicago":"Henzinger, Monika H, Sebastian Krinninger, and Veronika Loitzenbauer. “Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time.” In 2nd International Colloquium on Automata, Languages and Programming, 9134:713–24. Springer Nature, 2015. https://doi.org/10.1007/978-3-662-47672-7_58.","ieee":"M. H. Henzinger, S. Krinninger, and V. Loitzenbauer, “Finding 2-edge and 2-vertex strongly connected components in quadratic time,” in 2nd International Colloquium on Automata, Languages and Programming, Kyoto, Japan, 2015, vol. 9134, pp. 713–724.","mla":"Henzinger, Monika H., et al. “Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time.” 2nd International Colloquium on Automata, Languages and Programming, vol. 9134, Springer Nature, 2015, pp. 713–24, doi:10.1007/978-3-662-47672-7_58.","short":"M.H. Henzinger, S. Krinninger, V. Loitzenbauer, in:, 2nd International Colloquium on Automata, Languages and Programming, Springer Nature, 2015, pp. 713–724."},"intvolume":" 9134","arxiv":1,"publication":"2nd International Colloquium on Automata, Languages and Programming","scopus_import":"1","year":"2015","doi":"10.1007/978-3-662-47672-7_58","page":"713 - 724","day":"06","oa":1},{"oa":1,"page":"156–167","day":"01","doi":"10.1007/978-3-319-18263-6_14","year":"2015","scopus_import":"1","arxiv":1,"intvolume":" 8952","publication":"12th International Workshop of Approximation and Online Algorithms","extern":"1","date_updated":"2023-02-10T09:26:06Z","citation":{"mla":"Dvořák, Wolfgang, and Monika H. Henzinger. “Online Ad Assignment with an Ad Exchange.” 12th International Workshop of Approximation and Online Algorithms, vol. 8952, Springer Nature, 2015, pp. 156–167, doi:10.1007/978-3-319-18263-6_14.","short":"W. Dvořák, M.H. Henzinger, in:, 12th International Workshop of Approximation and Online Algorithms, Springer Nature, 2015, pp. 156–167.","ama":"Dvořák W, Henzinger MH. Online ad assignment with an ad exchange. In: 12th International Workshop of Approximation and Online Algorithms. Vol 8952. Springer Nature; 2015:156–167. doi:10.1007/978-3-319-18263-6_14","chicago":"Dvořák, Wolfgang, and Monika H Henzinger. “Online Ad Assignment with an Ad Exchange.” In 12th International Workshop of Approximation and Online Algorithms, 8952:156–167. Springer Nature, 2015. https://doi.org/10.1007/978-3-319-18263-6_14.","ista":"Dvořák W, Henzinger MH. 2015. Online ad assignment with an ad exchange. 12th International Workshop of Approximation and Online Algorithms. WAOA: International Workshop on Approximation and Online Algorithms, LNCS, vol. 8952, 156–167.","apa":"Dvořák, W., & Henzinger, M. H. (2015). Online ad assignment with an ad exchange. In 12th International Workshop of Approximation and Online Algorithms (Vol. 8952, pp. 156–167). Wroclaw, Poland: Springer Nature. https://doi.org/10.1007/978-3-319-18263-6_14","ieee":"W. Dvořák and M. H. Henzinger, “Online ad assignment with an ad exchange,” in 12th International Workshop of Approximation and Online Algorithms, Wroclaw, Poland, 2015, vol. 8952, pp. 156–167."},"alternative_title":["LNCS"],"external_id":{"arxiv":["1604.05603"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","abstract":[{"lang":"eng","text":"Ad exchanges are becoming an increasingly popular way to sell advertisement slots on the internet. An ad exchange is basically a spot market for ad impressions. A publisher who has already signed contracts reserving advertisement impressions on his pages can choose between assigning a new ad impression for a new page view to a contracted advertiser or to sell it at an ad exchange. This leads to an online revenue maximization problem for the publisher. Given a new impression to sell decide whether (a) to assign it to a contracted advertiser and if so to which one or (b) to sell it at the ad exchange and if so at which reserve price. We make no assumptions about the distribution of the advertiser valuations that participate in the ad exchange and show that there exists a simple primal-dual based online algorithm, whose lower bound for the revenue converges to 𝑅𝐴𝐷𝑋+𝑅𝐴(1−1/𝑒), where 𝑅𝐴𝐷𝑋 is the revenue that the optimum algorithm achieves from the ad exchange and 𝑅𝐴 is the revenue that the optimum algorithm achieves from the contracted advertisers."}],"date_published":"2015-01-01T00:00:00Z","publisher":"Springer Nature","title":"Online ad assignment with an ad exchange","date_created":"2022-08-11T09:43:32Z","_id":"11788","type":"conference","publication_identifier":{"issn":["0302-9743"]},"main_file_link":[{"url":"https://arxiv.org/abs/1604.05603","open_access":"1"}],"status":"public","conference":{"start_date":"2014-09-11","end_date":"2014-09-12","name":"WAOA: International Workshop on Approximation and Online Algorithms","location":"Wroclaw, Poland"},"quality_controlled":"1","oa_version":"Preprint","author":[{"full_name":"Dvořák, Wolfgang","last_name":"Dvořák","first_name":"Wolfgang"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","first_name":"Monika H","last_name":"Henzinger","orcid":"0000-0002-5008-6530"}],"month":"01","language":[{"iso":"eng"}],"volume":8952,"article_processing_charge":"No"},{"type":"journal_article","_id":"7765","article_type":"original","date_created":"2020-04-30T11:41:08Z","year":"2015","status":"public","day":"04","doi":"10.1103/physrevlett.114.225501","publication_identifier":{"issn":["0031-9007","1079-7114"]},"publication":"Physical Review Letters","intvolume":" 114","citation":{"ieee":"C. P. Goodrich, A. J. Liu, and S. R. Nagel, “The principle of independent bond-level response: Tuning by pruning to exploit disorder for global behavior,” Physical Review Letters, vol. 114, no. 22. American Physical Society, 2015.","apa":"Goodrich, C. P., Liu, A. J., & Nagel, S. R. (2015). The principle of independent bond-level response: Tuning by pruning to exploit disorder for global behavior. Physical Review Letters. American Physical Society. https://doi.org/10.1103/physrevlett.114.225501","chicago":"Goodrich, Carl Peter, Andrea J. Liu, and Sidney R. Nagel. “The Principle of Independent Bond-Level Response: Tuning by Pruning to Exploit Disorder for Global Behavior.” Physical Review Letters. American Physical Society, 2015. https://doi.org/10.1103/physrevlett.114.225501.","ama":"Goodrich CP, Liu AJ, Nagel SR. The principle of independent bond-level response: Tuning by pruning to exploit disorder for global behavior. Physical Review Letters. 2015;114(22). doi:10.1103/physrevlett.114.225501","ista":"Goodrich CP, Liu AJ, Nagel SR. 2015. The principle of independent bond-level response: Tuning by pruning to exploit disorder for global behavior. Physical Review Letters. 114(22), 225501.","mla":"Goodrich, Carl Peter, et al. “The Principle of Independent Bond-Level Response: Tuning by Pruning to Exploit Disorder for Global Behavior.” Physical Review Letters, vol. 114, no. 22, 225501, American Physical Society, 2015, doi:10.1103/physrevlett.114.225501.","short":"C.P. Goodrich, A.J. Liu, S.R. Nagel, Physical Review Letters 114 (2015)."},"oa_version":"None","date_updated":"2021-01-12T08:15:23Z","quality_controlled":"1","extern":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"orcid":"0000-0002-1307-5074","first_name":"Carl Peter","last_name":"Goodrich","full_name":"Goodrich, Carl Peter","id":"EB352CD2-F68A-11E9-89C5-A432E6697425"},{"first_name":"Andrea J.","last_name":"Liu","full_name":"Liu, Andrea J."},{"full_name":"Nagel, Sidney R.","last_name":"Nagel","first_name":"Sidney R."}],"issue":"22","article_number":"225501","abstract":[{"lang":"eng","text":"We introduce a principle unique to disordered solids wherein the contribution of any bond to one global perturbation is uncorrelated with its contribution to another. Coupled with sufficient variability in the contributions of different bonds, this “independent bond-level response” paves the way for the design of real materials with unusual and exquisitely tuned properties. To illustrate this, we choose two global perturbations: compression and shear. By applying a bond removal procedure that is both simple and experimentally relevant to remove a very small fraction of bonds, we can drive disordered spring networks to both the incompressible and completely auxetic limits of mechanical behavior."}],"publication_status":"published","month":"06","article_processing_charge":"No","title":"The principle of independent bond-level response: Tuning by pruning to exploit disorder for global behavior","volume":114,"language":[{"iso":"eng"}],"date_published":"2015-06-04T00:00:00Z","publisher":"American Physical Society"},{"issue":"14","month":"02","publication_status":"published","abstract":[{"text":"We study the vibrational properties near a free surface of disordered spring networks derived from jammed sphere packings. In bulk systems, without surfaces, it is well understood that such systems have a plateau in the density of vibrational modes extending down to a frequency scale ω*. This frequency is controlled by ΔZ = 〈Z〉 − 2d, the difference between the average coordination of the spheres and twice the spatial dimension, d, of the system, which vanishes at the jamming transition. In the presence of a free surface we find that there is a density of disordered vibrational modes associated with the surface that extends far below ω*. The total number of these low-frequency surface modes is controlled by ΔZ, and the profile of their decay into the bulk has two characteristic length scales, which diverge as ΔZ−1/2 and ΔZ−1 as the jamming transition is approached.","lang":"eng"}],"volume":11,"title":"Disordered surface vibrations in jammed sphere packings","article_processing_charge":"No","date_published":"2015-02-15T00:00:00Z","language":[{"iso":"eng"}],"publisher":"Royal Society of Chemistry","citation":{"ieee":"D. M. Sussman, C. P. Goodrich, A. J. Liu, and S. R. Nagel, “Disordered surface vibrations in jammed sphere packings,” Soft Matter, vol. 11, no. 14. Royal Society of Chemistry, pp. 2745–2751, 2015.","apa":"Sussman, D. M., Goodrich, C. P., Liu, A. J., & Nagel, S. R. (2015). Disordered surface vibrations in jammed sphere packings. Soft Matter. Royal Society of Chemistry. https://doi.org/10.1039/c4sm02905d","ama":"Sussman DM, Goodrich CP, Liu AJ, Nagel SR. Disordered surface vibrations in jammed sphere packings. Soft Matter. 2015;11(14):2745-2751. doi:10.1039/c4sm02905d","chicago":"Sussman, Daniel M., Carl Peter Goodrich, Andrea J. Liu, and Sidney R. Nagel. “Disordered Surface Vibrations in Jammed Sphere Packings.” Soft Matter. Royal Society of Chemistry, 2015. https://doi.org/10.1039/c4sm02905d.","ista":"Sussman DM, Goodrich CP, Liu AJ, Nagel SR. 2015. Disordered surface vibrations in jammed sphere packings. Soft Matter. 11(14), 2745–2751.","mla":"Sussman, Daniel M., et al. “Disordered Surface Vibrations in Jammed Sphere Packings.” Soft Matter, vol. 11, no. 14, Royal Society of Chemistry, 2015, pp. 2745–51, doi:10.1039/c4sm02905d.","short":"D.M. Sussman, C.P. Goodrich, A.J. Liu, S.R. Nagel, Soft Matter 11 (2015) 2745–2751."},"oa_version":"None","quality_controlled":"1","extern":"1","date_updated":"2021-01-12T08:15:23Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"first_name":"Daniel M.","last_name":"Sussman","full_name":"Sussman, Daniel M."},{"orcid":"0000-0002-1307-5074","last_name":"Goodrich","first_name":"Carl Peter","full_name":"Goodrich, Carl Peter","id":"EB352CD2-F68A-11E9-89C5-A432E6697425"},{"full_name":"Liu, Andrea J.","last_name":"Liu","first_name":"Andrea J."},{"last_name":"Nagel","first_name":"Sidney R.","full_name":"Nagel, Sidney R."}],"publication":"Soft Matter","intvolume":" 11","article_type":"original","type":"journal_article","_id":"7766","date_created":"2020-04-30T11:41:23Z","day":"15","year":"2015","status":"public","doi":"10.1039/c4sm02905d","page":"2745-2751","publication_identifier":{"issn":["1744-683X","1744-6848"]}},{"oa_version":"None","citation":{"short":"R. van Drongelen, A. Pal, C.P. Goodrich, T. Idema, Physical Review E 91 (2015).","mla":"van Drongelen, Ruben, et al. “Collective Dynamics of Soft Active Particles.” Physical Review E, vol. 91, no. 3, 032706, American Physical Society, 2015, doi:10.1103/physreve.91.032706.","ieee":"R. van Drongelen, A. Pal, C. P. Goodrich, and T. Idema, “Collective dynamics of soft active particles,” Physical Review E, vol. 91, no. 3. American Physical Society, 2015.","ista":"van Drongelen R, Pal A, Goodrich CP, Idema T. 2015. Collective dynamics of soft active particles. Physical Review E. 91(3), 032706.","chicago":"Drongelen, Ruben van, Anshuman Pal, Carl Peter Goodrich, and Timon Idema. “Collective Dynamics of Soft Active Particles.” Physical Review E. American Physical Society, 2015. https://doi.org/10.1103/physreve.91.032706.","ama":"van Drongelen R, Pal A, Goodrich CP, Idema T. Collective dynamics of soft active particles. Physical Review E. 2015;91(3). doi:10.1103/physreve.91.032706","apa":"van Drongelen, R., Pal, A., Goodrich, C. P., & Idema, T. (2015). Collective dynamics of soft active particles. Physical Review E. American Physical Society. https://doi.org/10.1103/physreve.91.032706"},"date_updated":"2021-01-12T08:15:24Z","quality_controlled":"1","extern":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"full_name":"van Drongelen, Ruben","first_name":"Ruben","last_name":"van Drongelen"},{"full_name":"Pal, Anshuman","last_name":"Pal","first_name":"Anshuman"},{"first_name":"Carl Peter","last_name":"Goodrich","orcid":"0000-0002-1307-5074","id":"EB352CD2-F68A-11E9-89C5-A432E6697425","full_name":"Goodrich, Carl Peter"},{"last_name":"Idema","first_name":"Timon","full_name":"Idema, Timon"}],"issue":"3","article_number":"032706","abstract":[{"text":"We present a model of soft active particles that leads to a rich array of collective behavior found also in dense biological swarms of bacteria and other unicellular organisms. Our model uses only local interactions, such as Vicsek-type nearest-neighbor alignment, short-range repulsion, and a local boundary term. Changing the relative strength of these interactions leads to migrating swarms, rotating swarms, and jammed swarms, as well as swarms that exhibit run-and-tumble motion, alternating between migration and either rotating or jammed states. Interestingly, although a migrating swarm moves slower than an individual particle, the diffusion constant can be up to three orders of magnitude larger, suggesting that collective motion can be highly advantageous, for example, when searching for food.","lang":"eng"}],"publication_status":"published","month":"03","article_processing_charge":"No","title":"Collective dynamics of soft active particles","volume":91,"language":[{"iso":"eng"}],"publisher":"American Physical Society","date_published":"2015-03-01T00:00:00Z","type":"journal_article","_id":"7767","article_type":"original","date_created":"2020-04-30T11:41:38Z","status":"public","publication_identifier":{"issn":["1539-3755","1550-2376"]},"doi":"10.1103/physreve.91.032706","year":"2015","day":"01","publication":"Physical Review E","intvolume":" 91"},{"year":"2015","status":"public","day":"01","page":"1900 - 1908","main_file_link":[{"url":"http://papers.nips.cc/paper/5897-streaming-min-max-hypergraph-partitioning"}],"_id":"777","type":"conference","date_created":"2018-12-11T11:48:27Z","publist_id":"6879","conference":{"name":"NIPS: Neural Information Processing Systems"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"last_name":"Alistarh","first_name":"Dan-Adrian","orcid":"0000-0003-3650-940X","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","full_name":"Alistarh, Dan-Adrian"},{"first_name":"Jennifer","last_name":"Iglesias","full_name":"Iglesias, Jennifer"},{"full_name":"Vojnović, Milan","first_name":"Milan","last_name":"Vojnović"}],"citation":{"chicago":"Alistarh, Dan-Adrian, Jennifer Iglesias, and Milan Vojnović. “Streaming Min-Max Hypergraph Partitioning,” 2015–January:1900–1908. Neural Information Processing Systems, 2015.","ista":"Alistarh D-A, Iglesias J, Vojnović M. 2015. Streaming min-max hypergraph partitioning. NIPS: Neural Information Processing Systems vol. 2015–January, 1900–1908.","ama":"Alistarh D-A, Iglesias J, Vojnović M. Streaming min-max hypergraph partitioning. In: Vol 2015-January. Neural Information Processing Systems; 2015:1900-1908.","apa":"Alistarh, D.-A., Iglesias, J., & Vojnović, M. (2015). Streaming min-max hypergraph partitioning (Vol. 2015–January, pp. 1900–1908). Presented at the NIPS: Neural Information Processing Systems, Neural Information Processing Systems.","ieee":"D.-A. Alistarh, J. Iglesias, and M. Vojnović, “Streaming min-max hypergraph partitioning,” presented at the NIPS: Neural Information Processing Systems, 2015, vol. 2015–January, pp. 1900–1908.","short":"D.-A. Alistarh, J. Iglesias, M. Vojnović, in:, Neural Information Processing Systems, 2015, pp. 1900–1908.","mla":"Alistarh, Dan-Adrian, et al. Streaming Min-Max Hypergraph Partitioning. Vol. 2015–January, Neural Information Processing Systems, 2015, pp. 1900–08."},"oa_version":"None","extern":"1","date_updated":"2023-02-23T13:17:09Z","title":"Streaming min-max hypergraph partitioning","volume":"2015-January","article_processing_charge":"No","language":[{"iso":"eng"}],"publisher":"Neural Information Processing Systems","date_published":"2015-01-01T00:00:00Z","month":"01","publication_status":"published","abstract":[{"lang":"eng","text":"In many applications, the data is of rich structure that can be represented by a hypergraph, where the data items are represented by vertices and the associations among items are represented by hyperedges. Equivalently, we are given an input bipartite graph with two types of vertices: items, and associations (which we refer to as topics). We consider the problem of partitioning the set of items into a given number of components such that the maximum number of topics covered by a component is minimized. This is a clustering problem with various applications, e.g. partitioning of a set of information objects such as documents, images, and videos, and load balancing in the context of modern computation platforms.Inthis paper, we focus on the streaming computation model for this problem, in which items arrive online one at a time and each item must be assigned irrevocably to a component at its arrival time. Motivated by scalability requirements, we focus on the class of streaming computation algorithms with memory limited to be at most linear in the number of components. We show that a greedy assignment strategy is able to recover a hidden co-clustering of items under a natural set of recovery conditions. We also report results of an extensive empirical evaluation, which demonstrate that this greedy strategy yields superior performance when compared with alternative approaches."}]},{"month":"10","publication_status":"published","abstract":[{"lang":"eng","text":"The fact that a disordered material is not constrained in its properties in\r\nthe same way as a crystal presents significant and yet largely untapped\r\npotential for novel material design. However, unlike their crystalline\r\ncounterparts, disordered solids are not well understood. One of the primary\r\nobstacles is the lack of a theoretical framework for thinking about disorder\r\nand its relation to mechanical properties. To this end, we study an idealized\r\nsystem of frictionless athermal soft spheres that, when compressed, undergoes a\r\njamming phase transition with diverging length scales and clean power-law\r\nsignatures. This critical point is the cornerstone of a much larger \"jamming\r\nscenario\" that has the potential to provide the essential theoretical\r\nfoundation necessary for a unified understanding of the mechanics of disordered\r\nsolids. We begin by showing that jammed sphere packings have a valid linear\r\nregime despite the presence of \"contact nonlinearities.\" We then investigate\r\nthe critical nature of the transition, focusing on diverging length scales and\r\nfinite-size effects. Next, we argue that jamming plays the same role for\r\ndisordered solids as the perfect crystal plays for crystalline solids. Not only\r\ncan it be considered an idealized starting point for understanding disordered\r\nmaterials, but it can even influence systems that have a relatively high amount\r\nof crystalline order. The behavior of solids can thus be thought of as existing\r\non a spectrum, with the perfect crystal and the jamming transition at opposing\r\nends. Finally, we introduce a new principle wherein the contribution of an\r\nindividual bond to one global property is independent of its contribution to\r\nanother. This principle allows the different global responses of a disordered\r\nsystem to be manipulated independently and provides a great deal of flexibility\r\nin designing materials with unique, textured and tunable properties."}],"language":[{"iso":"eng"}],"date_published":"2015-10-29T00:00:00Z","title":"Unearthing the anticrystal: Criticality in the linear response of disordered solids","article_processing_charge":"No","extern":"1","date_updated":"2021-01-12T08:15:28Z","oa_version":"Preprint","citation":{"mla":"Goodrich, Carl Peter. “Unearthing the Anticrystal: Criticality in the Linear Response of Disordered Solids.” ArXiv:1510.08820, 2015.","short":"C.P. Goodrich, ArXiv:1510.08820 (2015).","ieee":"C. P. Goodrich, “Unearthing the anticrystal: Criticality in the linear response of disordered solids,” arXiv:1510.08820. 2015.","apa":"Goodrich, C. P. (2015). Unearthing the anticrystal: Criticality in the linear response of disordered solids. arXiv:1510.08820.","chicago":"Goodrich, Carl Peter. “Unearthing the Anticrystal: Criticality in the Linear Response of Disordered Solids.” ArXiv:1510.08820, 2015.","ista":"Goodrich CP. 2015. Unearthing the anticrystal: Criticality in the linear response of disordered solids. arXiv:1510.08820, .","ama":"Goodrich CP. Unearthing the anticrystal: Criticality in the linear response of disordered solids. arXiv:151008820. 2015."},"author":[{"full_name":"Goodrich, Carl Peter","id":"EB352CD2-F68A-11E9-89C5-A432E6697425","orcid":"0000-0002-1307-5074","last_name":"Goodrich","first_name":"Carl Peter"}],"external_id":{"arxiv":["1510.08820"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","arxiv":1,"publication":"arXiv:1510.08820","oa":1,"date_created":"2020-04-30T12:16:18Z","type":"preprint","_id":"7779","day":"29","page":"242","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1510.08820"}],"year":"2015","status":"public"},{"author":[{"id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","full_name":"Alistarh, Dan-Adrian","first_name":"Dan-Adrian","last_name":"Alistarh","orcid":"0000-0003-3650-940X"},{"last_name":"Kopinsky","first_name":"Justin","full_name":"Kopinsky, Justin"},{"full_name":"Kuznetsov, Petr","last_name":"Kuznetsov","first_name":"Petr"},{"last_name":"Ravi","first_name":"Srivatsan","full_name":"Ravi, Srivatsan"},{"full_name":"Shavit, Nir","last_name":"Shavit","first_name":"Nir"}],"oa_version":"None","quality_controlled":"1","volume":9363,"article_processing_charge":"No","language":[{"iso":"eng"}],"month":"01","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1405.5689"}],"status":"public","type":"conference","_id":"778","date_created":"2018-12-11T11:48:27Z","conference":{"name":"DISC: Distributed Computing"},"external_id":{"arxiv":["1405.5689"]},"alternative_title":["LNCS"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"short":"D.-A. Alistarh, J. Kopinsky, P. Kuznetsov, S. Ravi, N. Shavit, in:, Springer, 2015, pp. 185–199.","mla":"Alistarh, Dan-Adrian, et al. Inherent Limitations of Hybrid Transactional Memory. Vol. 9363, Springer, 2015, pp. 185–99, doi:10.1007/978-3-662-48653-5_13.","apa":"Alistarh, D.-A., Kopinsky, J., Kuznetsov, P., Ravi, S., & Shavit, N. (2015). Inherent limitations of hybrid transactional memory (Vol. 9363, pp. 185–199). Presented at the DISC: Distributed Computing, Springer. https://doi.org/10.1007/978-3-662-48653-5_13","ama":"Alistarh D-A, Kopinsky J, Kuznetsov P, Ravi S, Shavit N. Inherent limitations of hybrid transactional memory. In: Vol 9363. Springer; 2015:185-199. doi:10.1007/978-3-662-48653-5_13","ista":"Alistarh D-A, Kopinsky J, Kuznetsov P, Ravi S, Shavit N. 2015. Inherent limitations of hybrid transactional memory. DISC: Distributed Computing, LNCS, vol. 9363, 185–199.","chicago":"Alistarh, Dan-Adrian, Justin Kopinsky, Petr Kuznetsov, Srivatsan Ravi, and Nir Shavit. “Inherent Limitations of Hybrid Transactional Memory,” 9363:185–99. Springer, 2015. https://doi.org/10.1007/978-3-662-48653-5_13.","ieee":"D.-A. Alistarh, J. Kopinsky, P. Kuznetsov, S. Ravi, and N. Shavit, “Inherent limitations of hybrid transactional memory,” presented at the DISC: Distributed Computing, 2015, vol. 9363, pp. 185–199."},"extern":"1","date_updated":"2023-02-23T13:17:35Z","title":"Inherent limitations of hybrid transactional memory","publisher":"Springer","date_published":"2015-01-01T00:00:00Z","publication_status":"published","abstract":[{"text":"Several Hybrid Transactional Memory (HyTM) schemes have recently been proposed to complement the fast, but best-effort nature of Hardware Transactional Memory (HTM) with a slow, reliable software backup. However, the costs of providing concurrency between hardware and software transactions in HyTM are still not well understood. In this paper, we propose a general model for HyTM implementations, which captures the ability of hardware transactions to buffer memory accesses. The model allows us to formally quantify and analyze the amount of overhead (instrumentation) caused by the potential presence of software transactions.We prove that (1) it is impossible to build a strictly serializable HyTM implementation that has both uninstrumented reads and writes, even for very weak progress guarantees, and (2) the instrumentation cost incurred by a hardware transaction in any progressive opaque HyTM is linear in the size of the transaction’s data set.We further describe two implementations which exhibit optimal instrumentation costs for two different progress conditions. In sum, this paper proposes the first formal HyTM model and captures for the first time the trade-off between the degree of hardware-software TM concurrency and the amount of instrumentation overhead.","lang":"eng"}],"page":"185 - 199","doi":"10.1007/978-3-662-48653-5_13","day":"01","year":"2015","acknowledgement":"P. Kuznetsov-The author is supported by the Agence Nationale de la Recherche, ANR-14-CE35-0010-01, project DISCMAT. N. Shavit-Support is gratfeully acknowledgedfrom the National Science Foundation under grants CCF-1217921, CCF-1201926, and IIS-1447786, the Department of Energy under grant ER26116/DE-SC0008923, and the Oracle and Intel corporations.","oa":1,"arxiv":1,"publist_id":"6880","intvolume":" 9363"},{"language":[{"iso":"eng"}],"publisher":"ACM","date_published":"2015-06-13T00:00:00Z","article_processing_charge":"No","volume":"2015-June","title":"ThreadScan: Automatic and scalable memory reclamation","abstract":[{"text":"The concurrent memory reclamation problem is that of devising a way for a deallocating thread to verify that no other concurrent threads hold references to a memory block being deallocated. To date, in the absence of automatic garbage collection, there is no satisfactory solution to this problem; existing tracking methods like hazard pointers, reference counters, or epoch-based techniques like RCU, are either prohibitively expensive or require significant programming expertise, to the extent that implementing them efficiently can be worthy of a publication. None of the existing techniques are automatic or even semi-automated. In this paper, we take a new approach to concurrent memory reclamation: instead of manually tracking access to memory locations as done in techniques like hazard pointers, or restricting shared accesses to specific epoch boundaries as in RCU, our algorithm, called ThreadScan, leverages operating system signaling to automatically detect which memory locations are being accessed by concurrent threads. Initial empirical evidence shows that ThreadScan scales surprisingly well and requires negligible programming effort beyond the standard use of Malloc and Free.","lang":"eng"}],"publication_status":"published","month":"06","author":[{"orcid":"0000-0003-3650-940X","last_name":"Alistarh","first_name":"Dan-Adrian","full_name":"Alistarh, Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Matveev, Alexander","last_name":"Matveev","first_name":"Alexander"},{"full_name":"Leiserson, William","last_name":"Leiserson","first_name":"William"},{"first_name":"Nir","last_name":"Shavit","full_name":"Shavit, Nir"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2023-02-23T12:35:42Z","extern":"1","citation":{"ieee":"D.-A. Alistarh, A. Matveev, W. Leiserson, and N. Shavit, “ThreadScan: Automatic and scalable memory reclamation,” presented at the SPAA: Symposium on Parallelism in Algorithms and Architectures, 2015, vol. 2015–June, pp. 123–132.","apa":"Alistarh, D.-A., Matveev, A., Leiserson, W., & Shavit, N. (2015). ThreadScan: Automatic and scalable memory reclamation (Vol. 2015–June, pp. 123–132). Presented at the SPAA: Symposium on Parallelism in Algorithms and Architectures, ACM. https://doi.org/10.1145/2755573.2755600","ista":"Alistarh D-A, Matveev A, Leiserson W, Shavit N. 2015. ThreadScan: Automatic and scalable memory reclamation. SPAA: Symposium on Parallelism in Algorithms and Architectures vol. 2015–June, 123–132.","ama":"Alistarh D-A, Matveev A, Leiserson W, Shavit N. ThreadScan: Automatic and scalable memory reclamation. In: Vol 2015-June. ACM; 2015:123-132. doi:10.1145/2755573.2755600","chicago":"Alistarh, Dan-Adrian, Alexander Matveev, William Leiserson, and Nir Shavit. “ThreadScan: Automatic and Scalable Memory Reclamation,” 2015–June:123–32. ACM, 2015. https://doi.org/10.1145/2755573.2755600.","mla":"Alistarh, Dan-Adrian, et al. ThreadScan: Automatic and Scalable Memory Reclamation. Vol. 2015–June, ACM, 2015, pp. 123–32, doi:10.1145/2755573.2755600.","short":"D.-A. Alistarh, A. Matveev, W. Leiserson, N. Shavit, in:, ACM, 2015, pp. 123–132."},"oa_version":"None","conference":{"name":"SPAA: Symposium on Parallelism in Algorithms and Architectures"},"publist_id":"6876","related_material":{"record":[{"id":"6001","relation":"later_version","status":"public"}]},"acknowledgement":"Support is gratefully acknowledged from the National Science Foundation under grants CCF-1217921, CCF-1301926, and IIS-1447786, the Department of Energy under grant ER26116/DE-SC0008923, and the Oracle corporation. In particular, we would like to thank Dave Dice, Alex Kogan, and Mark Moir from the Oracle Scalable Synchronization Research Group for very useful feedback on earlier drafts of this paper.","day":"13","status":"public","year":"2015","doi":"10.1145/2755573.2755600","page":"123 - 132","date_created":"2018-12-11T11:48:27Z","type":"conference","_id":"779"},{"publist_id":"6877","conference":{"name":"ICALP: International Colloquium on Automota, Languages and Programming"},"arxiv":1,"intvolume":" 9135","_id":"780","type":"conference","oa":1,"date_created":"2018-12-11T11:48:28Z","year":"2015","status":"public","day":"01","doi":"10.1007/978-3-662-47666-6_38","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1502.05745"}],"page":"479 - 491","acknowledgement":"Support is gratefully acknowledged from the National Science Foundation under grants CCF-1217921, CCF-1301926, and IIS-1447786, the Department of Energy under grant ER26116/DE-SC0008923, and the Oracle and Intel corporations.”","month":"01","publication_status":"published","abstract":[{"lang":"eng","text":"Population protocols are networks of finite-state agents, interacting randomly, and updating their states using simple rules. Despite their extreme simplicity, these systems have been shown to cooperatively perform complex computational tasks, such as simulating register machines to compute standard arithmetic functions. The election of a unique leader agent is a key requirement in such computational constructions. Yet, the fastest currently known population protocol for electing a leader only has linear convergence time, and it has recently been shown that no population protocol using a constant number of states per node may overcome this linear bound. In this paper, we give the first population protocol for leader election with polylogarithmic convergence time, using polylogarithmic memory states per node. The protocol structure is quite simple: each node has an associated value, and is either a leader (still in contention) or a minion (following some leader). A leader keeps incrementing its value and “defeats” other leaders in one-to-one interactions, and will drop from contention and become a minion if it meets a leader with higher value. Importantly, a leader also drops out if it meets a minion with higher absolute value. While these rules are quite simple, the proof that this algorithm achieves polylogarithmic convergence time is non-trivial. In particular, the argument combines careful use of concentration inequalities with anti-concentration bounds, showing that the leaders’ values become spread apart as the execution progresses, which in turn implies that straggling leaders get quickly eliminated. We complement our analysis with empirical results, showing that our protocol converges extremely fast, even for large network sizes."}],"title":"Polylogarithmic-time leader election in population protocols","volume":9135,"publisher":"Springer","language":[{"iso":"eng"}],"date_published":"2015-01-01T00:00:00Z","citation":{"apa":"Alistarh, D.-A., & Gelashvili, R. (2015). Polylogarithmic-time leader election in population protocols (Vol. 9135, pp. 479–491). Presented at the ICALP: International Colloquium on Automota, Languages and Programming, Springer. https://doi.org/10.1007/978-3-662-47666-6_38","ama":"Alistarh D-A, Gelashvili R. Polylogarithmic-time leader election in population protocols. In: Vol 9135. Springer; 2015:479-491. doi:10.1007/978-3-662-47666-6_38","chicago":"Alistarh, Dan-Adrian, and Rati Gelashvili. “Polylogarithmic-Time Leader Election in Population Protocols,” 9135:479–91. Springer, 2015. https://doi.org/10.1007/978-3-662-47666-6_38.","ista":"Alistarh D-A, Gelashvili R. 2015. Polylogarithmic-time leader election in population protocols. ICALP: International Colloquium on Automota, Languages and Programming vol. 9135, 479–491.","ieee":"D.-A. Alistarh and R. Gelashvili, “Polylogarithmic-time leader election in population protocols,” presented at the ICALP: International Colloquium on Automota, Languages and Programming, 2015, vol. 9135, pp. 479–491.","mla":"Alistarh, Dan-Adrian, and Rati Gelashvili. Polylogarithmic-Time Leader Election in Population Protocols. Vol. 9135, Springer, 2015, pp. 479–91, doi:10.1007/978-3-662-47666-6_38.","short":"D.-A. Alistarh, R. Gelashvili, in:, Springer, 2015, pp. 479–491."},"oa_version":"Preprint","extern":"1","date_updated":"2023-02-23T13:18:11Z","external_id":{"arxiv":["1502.05745"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"last_name":"Alistarh","first_name":"Dan-Adrian","orcid":"0000-0003-3650-940X","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","full_name":"Alistarh, Dan-Adrian"},{"last_name":"Gelashvili","first_name":"Rati","full_name":"Gelashvili, Rati"}]},{"conference":{"name":"PODC: Principles of Distributed Computing"},"publist_id":"6873","day":"21","year":"2015","status":"public","doi":"10.1145/2767386.2767429","page":"47 - 56","type":"conference","_id":"781","date_created":"2018-12-11T11:48:28Z","article_processing_charge":"No","volume":"2015-July","title":"Fast and exact majority in population protocols","date_published":"2015-07-21T00:00:00Z","language":[{"iso":"eng"}],"publisher":"ACM","abstract":[{"lang":"eng","text":"Population protocols, roughly defined as systems consisting of large numbers of simple identical agents, interacting at random and updating their state following simple rules, are an important research topic at the intersection of distributed computing and biology. One of the fundamental tasks that a population protocol may solve is majority: each node starts in one of two states; the goal is for all nodes to reach a correct consensus on which of the two states was initially the majority. Despite considerable research effort, known protocols for this problem are either exact but slow (taking linear parallel time to converge), or fast but approximate (with non-zero probability of error). In this paper, we show that this trade-off between preciasion and speed is not inherent. We present a new protocol called Average and Conquer (AVC) that solves majority ex-actly in expected parallel convergence time O(log n/(sε) + log n log s), where n is the number of nodes, εn is the initial node advantage of the majority state, and s = Ω(log n log log n) is the number of states the protocol employs. This shows that the majority problem can be solved exactly in time poly-logarithmic in n, provided that the memory per node is s = Ω(1/ε + lognlog1/ε). On the negative side, we establish a lower bound of Ω(1/ε) on the expected paraallel convergence time for the case of four memory states per node, and a lower bound of Ω(logn) parallel time for protocols using any number of memory states per node.per node, and a lower bound of (log n) parallel time for protocols using any number of memory states per node."}],"month":"07","publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"orcid":"0000-0003-3650-940X","last_name":"Alistarh","first_name":"Dan-Adrian","full_name":"Alistarh, Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Gelashvili","first_name":"Rati","full_name":"Gelashvili, Rati"},{"first_name":"Milan","last_name":"Vojnović","full_name":"Vojnović, Milan"}],"oa_version":"None","citation":{"short":"D.-A. Alistarh, R. Gelashvili, M. Vojnović, in:, ACM, 2015, pp. 47–56.","mla":"Alistarh, Dan-Adrian, et al. Fast and Exact Majority in Population Protocols. Vol. 2015–July, ACM, 2015, pp. 47–56, doi:10.1145/2767386.2767429.","ieee":"D.-A. Alistarh, R. Gelashvili, and M. Vojnović, “Fast and exact majority in population protocols,” presented at the PODC: Principles of Distributed Computing, 2015, vol. 2015–July, pp. 47–56.","ista":"Alistarh D-A, Gelashvili R, Vojnović M. 2015. Fast and exact majority in population protocols. PODC: Principles of Distributed Computing vol. 2015–July, 47–56.","chicago":"Alistarh, Dan-Adrian, Rati Gelashvili, and Milan Vojnović. “Fast and Exact Majority in Population Protocols,” 2015–July:47–56. ACM, 2015. https://doi.org/10.1145/2767386.2767429.","ama":"Alistarh D-A, Gelashvili R, Vojnović M. Fast and exact majority in population protocols. In: Vol 2015-July. ACM; 2015:47-56. doi:10.1145/2767386.2767429","apa":"Alistarh, D.-A., Gelashvili, R., & Vojnović, M. (2015). Fast and exact majority in population protocols (Vol. 2015–July, pp. 47–56). Presented at the PODC: Principles of Distributed Computing, ACM. https://doi.org/10.1145/2767386.2767429"},"date_updated":"2023-02-23T13:18:35Z","extern":"1"},{"publist_id":"6874","conference":{"name":"PODC: Principles of Distributed Computing"},"type":"conference","_id":"782","date_created":"2018-12-11T11:48:28Z","page":"251 - 260","day":"21","doi":"10.1145/2767386.2767430","year":"2015","status":"public","abstract":[{"text":"In this work, we consider the following random process, mo- Tivated by the analysis of lock-free concurrent algorithms under high memory contention. In each round, a new scheduling step is allocated to one of n threads, according to a distribution p = (p1; p2; : : : ; pn), where thread i is scheduled with probability pi. When some thread first reaches a set threshold of executed steps, it registers a win, completing its current operation, and resets its step count to 1. At the same time, threads whose step count was close to the threshold also get reset because of the win, but to 0 steps, being penalized for almost winning. We are interested in two questions: how often does some thread complete an operation (system latency), and how often does a specific thread complete an operation (individual latency)? We provide asymptotically tight bounds for the system and individual latency of this general concurrency pattern, for arbitrary scheduling distributions p. Surprisingly, a sim- ple characterization exists: in expectation, the system will complete a new operation every Θ(1/p 2) steps, while thread i will complete a new operation every Θ(1/2=p i ) steps. The proof is interesting in its own right, as it requires a careful analysis of how the higher norms of the vector p inuence the thread step counts and latencies in this random process. Our result offers a simple connection between the scheduling distribution and the average performance of concurrent algorithms, which has several applications.","lang":"eng"}],"publication_status":"published","month":"07","article_processing_charge":"No","title":"Lock-Free algorithms under stochastic schedulers","volume":"2015-July","language":[{"iso":"eng"}],"publisher":"ACM","date_published":"2015-07-21T00:00:00Z","citation":{"short":"D.-A. Alistarh, T. Sauerwald, M. Vojnović, in:, ACM, 2015, pp. 251–260.","mla":"Alistarh, Dan-Adrian, et al. Lock-Free Algorithms under Stochastic Schedulers. Vol. 2015–July, ACM, 2015, pp. 251–60, doi:10.1145/2767386.2767430.","apa":"Alistarh, D.-A., Sauerwald, T., & Vojnović, M. (2015). Lock-Free algorithms under stochastic schedulers (Vol. 2015–July, pp. 251–260). Presented at the PODC: Principles of Distributed Computing, ACM. https://doi.org/10.1145/2767386.2767430","ista":"Alistarh D-A, Sauerwald T, Vojnović M. 2015. Lock-Free algorithms under stochastic schedulers. PODC: Principles of Distributed Computing vol. 2015–July, 251–260.","ama":"Alistarh D-A, Sauerwald T, Vojnović M. Lock-Free algorithms under stochastic schedulers. In: Vol 2015-July. ACM; 2015:251-260. doi:10.1145/2767386.2767430","chicago":"Alistarh, Dan-Adrian, Thomas Sauerwald, and Milan Vojnović. “Lock-Free Algorithms under Stochastic Schedulers,” 2015–July:251–60. ACM, 2015. https://doi.org/10.1145/2767386.2767430.","ieee":"D.-A. Alistarh, T. Sauerwald, and M. Vojnović, “Lock-Free algorithms under stochastic schedulers,” presented at the PODC: Principles of Distributed Computing, 2015, vol. 2015–July, pp. 251–260."},"oa_version":"None","date_updated":"2023-02-23T13:18:50Z","extern":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","full_name":"Alistarh, Dan-Adrian","first_name":"Dan-Adrian","last_name":"Alistarh","orcid":"0000-0003-3650-940X"},{"last_name":"Sauerwald","first_name":"Thomas","full_name":"Sauerwald, Thomas"},{"full_name":"Vojnović, Milan","first_name":"Milan","last_name":"Vojnović"}]}]