---
_id: '11581'
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.
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)"
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Jorryt J
full_name: Matthee, Jorryt J
id: 7439a258-f3c0-11ec-9501-9df22fe06720
last_name: Matthee
orcid: 0000-0003-2871-127X
- first_name: David
full_name: Sobral, David
last_name: Sobral
- first_name: Sérgio
full_name: Santos, Sérgio
last_name: Santos
- first_name: Huub
full_name: Röttgering, Huub
last_name: Röttgering
- first_name: Behnam
full_name: Darvish, Behnam
last_name: Darvish
- first_name: Bahram
full_name: Mobasher, Bahram
last_name: Mobasher
citation:
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'
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'
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.'
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.'
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.'
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.
date_created: 2022-07-14T11:57:03Z
date_published: 2015-07-21T00:00:00Z
date_updated: 2022-08-19T08:25:25Z
day: '21'
doi: 10.1093/mnras/stv947
extern: '1'
external_id:
arxiv:
- '1502.07355'
intvolume: ' 451'
issue: '1'
keyword:
- Space and Planetary Science
- Astronomy and Astrophysics
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1502.07355
month: '07'
oa: 1
oa_version: Preprint
page: 400-417
publication: Monthly Notices of the Royal Astronomical Society
publication_identifier:
eissn:
- 1365-2966
issn:
- 0035-8711
publication_status: published
publisher: Oxford University Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Identification of the brightest Lyα emitters at z = 6.6: implications for
the evolution of the luminosity function in the reionization era'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 451
year: '2015'
...
---
_id: '11668'
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."
article_number: '2'
article_processing_charge: No
article_type: original
author:
- first_name: Riccardo
full_name: Colini-Baldeschi, Riccardo
last_name: Colini-Baldeschi
- first_name: Stefano
full_name: Leonardi, Stefano
last_name: Leonardi
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Martin
full_name: Starnberger, Martin
last_name: Starnberger
citation:
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
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
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.
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.
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.
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).
date_created: 2022-07-27T11:54:56Z
date_published: 2015-12-05T00:00:00Z
date_updated: 2023-02-09T10:03:35Z
day: '05'
doi: 10.1145/2818357
extern: '1'
intvolume: ' 4'
issue: '1'
keyword:
- Algorithms
- Economics
- Clinching ascending auction
- auctions with budgets
- Sponsored search auctions
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://eprints.cs.univie.ac.at/3510/
month: '12'
oa: 1
oa_version: Submitted Version
publication: ACM Transactions on Economics and Computation
publication_identifier:
eissn:
- 2167-8383
issn:
- 2167-8375
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: On multiple keyword sponsored search auctions with budgets
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 4
year: '2015'
...
---
_id: '11669'
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.
article_number: '4'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Paul
full_name: Dütting, Paul
last_name: Dütting
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Martin
full_name: Starnberger, Martin
last_name: Starnberger
citation:
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
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.
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.
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.
short: P. Dütting, M.H. Henzinger, M. Starnberger, ACM Transactions on Economics
and Computation 4 (2015).
date_created: 2022-07-27T12:09:15Z
date_published: 2015-12-05T00:00:00Z
date_updated: 2022-09-09T12:08:37Z
day: '05'
doi: 10.1145/2818351
extern: '1'
external_id:
arxiv:
- '1209.6448'
intvolume: ' 4'
issue: '1'
keyword:
- Algorithmic game theory
- auction theory
- Clinching auction
- Pareto optimality
- Budget limits
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1209.6448
month: '12'
oa: 1
oa_version: Preprint
publication: ACM Transactions on Economics and Computation
publication_identifier:
eissn:
- 2167-8383
issn:
- 2167-8375
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Auctions for heterogeneous items and budget limits
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 4
year: '2015'
...
---
_id: '11670'
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.
acknowledgement: We would like to thank Veronika Loitzenbauer and the anonymous referees
for their valuable feedback.
article_number: '1'
article_processing_charge: No
article_type: original
author:
- first_name: Paul
full_name: Dütting, Paul
last_name: Dütting
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Ingmar
full_name: Weber, Ingmar
last_name: Weber
citation:
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
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
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.
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.
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.
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).
date_created: 2022-07-27T12:43:18Z
date_published: 2015-12-02T00:00:00Z
date_updated: 2023-02-09T10:08:41Z
day: '02'
doi: 10.1145/2716312
extern: '1'
intvolume: ' 4'
issue: '1'
keyword:
- Computational Mathematics
- Marketing
- Economics and Econometrics
- Statistics and Probability
- Computer Science (miscellaneous)
language:
- iso: eng
month: '12'
oa_version: None
publication: ACM Transactions on Economics and Computation
publication_identifier:
eissn:
- 2167-8383
issn:
- 2167-8375
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: An expressive mechanism for auctions on the web
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 4
year: '2015'
...
---
_id: '11773'
abstract:
- lang: eng
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."
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Oren
full_name: Ben-Zwi, Oren
last_name: Ben-Zwi
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Veronika
full_name: Loitzenbauer, Veronika
last_name: Loitzenbauer
citation:
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'
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'
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.'
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.'
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.'
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.
conference:
end_date: 2015-09-12
location: Amsterdam, Netherlands
name: 'WINE: International Conference on Web and Internet Economics'
start_date: 2015-09-09
date_created: 2022-08-08T13:33:56Z
date_published: 2015-12-09T00:00:00Z
date_updated: 2023-02-10T09:06:23Z
day: '09'
doi: 10.1007/978-3-662-48995-6_8
extern: '1'
external_id:
arxiv:
- '1604.05562'
intvolume: ' 9470'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.1604.05562
month: '12'
oa: 1
oa_version: Preprint
page: 104–117
publication: 11th International Conference on Web and Internet Economics
publication_identifier:
eisbn:
- '9783662489956'
isbn:
- '9783662489949'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Ad exchange: Envy-free auctions with mediators'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 9470
year: '2015'
...
---
_id: '11774'
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 \U0001D6FC-approximation mechanism for conflict-free valuations
and yields an \U0001D4AA(\U0001D6FCΔ)-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 \U0001D4AA((Δ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
\U0001D45C(Δ) when the number of items is only logarithmic in the number of bidders."
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Yun Kuen
full_name: Cheung, Yun Kuen
last_name: Cheung
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Martin
full_name: Hoefer, Martin
last_name: Hoefer
- first_name: Martin
full_name: Starnberger, Martin
last_name: Starnberger
citation:
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'
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.
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.
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.'
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.
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.
conference:
end_date: 2015-12-12
location: Amsterdam, Netherlands
name: 'WINE: International Conference on Web and Internet Economics'
start_date: 2015-12-09
date_created: 2022-08-08T13:54:32Z
date_published: 2015-12-09T00:00:00Z
date_updated: 2023-02-10T09:08:30Z
day: '09'
doi: 10.1007/978-3-662-48995-6_17
extern: '1'
external_id:
arxiv:
- '1509.09147'
intvolume: ' 9470'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.1509.09147
month: '12'
oa: 1
oa_version: Preprint
page: 230–243
publication: 11th International Conference on Web and Internet Economics
publication_identifier:
eisbn:
- '9783662489956'
isbn:
- '9783662489949'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Combinatorial auctions with conflict-based externalities
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 9470
year: '2015'
...
---
_id: '11785'
abstract:
- lang: eng
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 \U0001D45C(\U0001D45A\U0001D45B) total update time, where \U0001D45A is the
number of edges and \U0001D45B 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 \U0001D45A vs. \U0001D45B trade-off. For the case of \U0001D45A=Θ(\U0001D45B1.5)
the running time is \U0001D442(\U0001D45B2.47), just barely below \U0001D45A\U0001D45B=Θ(\U0001D45B2.5).
In this paper we simplify the previous algorithm using new algorithmic ideas and
achieve an improved running time of \U0001D442̃ (min(\U0001D45A7/6\U0001D45B2/3,\U0001D45A3/4\U0001D45B5/4+\U0001D45C(1),\U0001D45A2/3\U0001D45B4/3+\U0001D45C(1)+\U0001D45A3/7\U0001D45B12/7+\U0001D45C(1))).
This gives, e.g., \U0001D442(\U0001D45B2.36) for the notorious case \U0001D45A=Θ(\U0001D45B1.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."
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Sebastian
full_name: Krinninger, Sebastian
last_name: Krinninger
- first_name: Danupon
full_name: Nanongkai, Danupon
last_name: Nanongkai
citation:
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'
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'
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.
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.
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.'
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.
short: M.H. Henzinger, S. Krinninger, D. Nanongkai, in:, 42nd International Colloquium
on Automata, Languages and Programming, Springer Nature, 2015, pp. 725–736.
conference:
end_date: 2015-07-10
location: Kyoto, Japan
name: 'ICALP: International Colloquium on Automata, Languages, and Programming'
start_date: 2015-07-06
date_created: 2022-08-11T08:51:32Z
date_published: 2015-01-01T00:00:00Z
date_updated: 2023-02-10T09:10:26Z
day: '01'
doi: 10.1007/978-3-662-47672-7_59
extern: '1'
external_id:
arxiv:
- '1612.03856'
intvolume: ' 9134'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1612.03856
month: '01'
oa: 1
oa_version: Preprint
page: 725 - 736
publication: 42nd International Colloquium on Automata, Languages and Programming
publication_identifier:
isbn:
- '9783662476710'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Improved algorithms for decremental single-source reachability on directed
graphs
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 9134
year: '2015'
...
---
_id: '11786'
abstract:
- lang: eng
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 \U0001D442(\U0001D4532)-approximately
optimal solution in \U0001D442(\U0001D453⋅log(\U0001D45A+\U0001D45B)) amortized
update time, where \U0001D453 is the maximum “frequency” of an element, \U0001D45B
is the number of sets, and \U0001D45A is the maximum number of elements in the
universe at any point in time. (2) For the dynamic \U0001D44F-matching problem,
we maintain an \U0001D442(1)-approximately optimal solution in \U0001D442(log3\U0001D45B)
amortized update time, where \U0001D45B is the number of nodes in the graph."
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Sayan
full_name: Bhattacharya, Sayan
last_name: Bhattacharya
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Giuseppe F.
full_name: Italiano, Giuseppe F.
last_name: Italiano
citation:
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'
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'
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.
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.'
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.
short: S. Bhattacharya, M.H. Henzinger, G.F. Italiano, in:, 42nd International Colloquium
on Automata, Languages and Programming, Springer Nature, 2015, pp. 206–218.
conference:
end_date: 2015-07-10
location: Kyoto, Japan
name: 'ICALP: International Colloquium on Automata, Languages, and Programming'
start_date: 2015-07-06
date_created: 2022-08-11T09:28:49Z
date_published: 2015-01-01T00:00:00Z
date_updated: 2023-02-10T09:13:31Z
day: '01'
doi: 10.1007/978-3-662-47672-7_17
extern: '1'
external_id:
arxiv:
- '1604.05337'
intvolume: ' 9134'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1604.05337
month: '01'
oa: 1
oa_version: Preprint
page: 206 - 218
publication: 42nd International Colloquium on Automata, Languages and Programming
publication_identifier:
isbn:
- '9783662476710'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Design of dynamic algorithms via primal-dual method
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 9134
year: '2015'
...
---
_id: '11787'
abstract:
- lang: eng
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 \U0001D442(\U0001D45B2). For 2-edge strongly connected components our algorithm
gives the first running time improvement in 20 years. Additionally we present
an \U0001D442(\U0001D45A2/log\U0001D45B)-time algorithm for 2-edge strongly connected
components, and thus improve over the O(m n) running time also when \U0001D45A=\U0001D442(\U0001D45B).
Our approach extends to k-edge and k-vertex strongly connected components for
any constant k with a running time of \U0001D442(\U0001D45B2log\U0001D45B) for
k-edge-connectivity and \U0001D442(\U0001D45B3) for k-vertex-connectivity."
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Sebastian
full_name: Krinninger, Sebastian
last_name: Krinninger
- first_name: Veronika
full_name: Loitzenbauer, Veronika
last_name: Loitzenbauer
citation:
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'
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'
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.
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.'
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.
conference:
end_date: 2015-07-10
location: Kyoto, Japan
name: 'ICALP: International Colloquium on Automata, Languages, and Programming'
start_date: 2015-07-06
date_created: 2022-08-11T09:38:34Z
date_published: 2015-07-06T00:00:00Z
date_updated: 2023-02-10T09:21:47Z
day: '06'
doi: 10.1007/978-3-662-47672-7_58
extern: '1'
external_id:
arxiv:
- '1412.6466'
intvolume: ' 9134'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1412.6466
month: '07'
oa: 1
oa_version: Preprint
page: 713 - 724
publication: 2nd International Colloquium on Automata, Languages and Programming
publication_identifier:
isbn:
- '9783662476710'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Finding 2-edge and 2-vertex strongly connected components in quadratic time
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 9134
year: '2015'
...
---
_id: '11788'
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 \U0001D445\U0001D434\U0001D437\U0001D44B+\U0001D445\U0001D434(1−1/\U0001D452),
where \U0001D445\U0001D434\U0001D437\U0001D44B is the revenue that the optimum
algorithm achieves from the ad exchange and \U0001D445\U0001D434 is the revenue
that the optimum algorithm achieves from the contracted advertisers."
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Wolfgang
full_name: Dvořák, Wolfgang
last_name: Dvořák
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
citation:
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'
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'
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.
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.
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.'
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.
conference:
end_date: 2014-09-12
location: Wroclaw, Poland
name: 'WAOA: International Workshop on Approximation and Online Algorithms'
start_date: 2014-09-11
date_created: 2022-08-11T09:43:32Z
date_published: 2015-01-01T00:00:00Z
date_updated: 2023-02-10T09:26:06Z
day: '01'
doi: 10.1007/978-3-319-18263-6_14
extern: '1'
external_id:
arxiv:
- '1604.05603'
intvolume: ' 8952'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1604.05603
month: '01'
oa: 1
oa_version: Preprint
page: 156–167
publication: 12th International Workshop of Approximation and Online Algorithms
publication_identifier:
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Online ad assignment with an ad exchange
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 8952
year: '2015'
...
---
_id: '7765'
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.'
article_number: '225501'
article_processing_charge: No
article_type: original
author:
- first_name: Carl Peter
full_name: Goodrich, Carl Peter
id: EB352CD2-F68A-11E9-89C5-A432E6697425
last_name: Goodrich
orcid: 0000-0002-1307-5074
- first_name: Andrea J.
full_name: Liu, Andrea J.
last_name: Liu
- first_name: Sidney R.
full_name: Nagel, Sidney R.
last_name: Nagel
citation:
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'
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.'
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.'
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).
date_created: 2020-04-30T11:41:08Z
date_published: 2015-06-04T00:00:00Z
date_updated: 2021-01-12T08:15:23Z
day: '04'
doi: 10.1103/physrevlett.114.225501
extern: '1'
intvolume: ' 114'
issue: '22'
language:
- iso: eng
month: '06'
oa_version: None
publication: Physical Review Letters
publication_identifier:
issn:
- 0031-9007
- 1079-7114
publication_status: published
publisher: American Physical Society
quality_controlled: '1'
status: public
title: 'The principle of independent bond-level response: Tuning by pruning to exploit
disorder for global behavior'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 114
year: '2015'
...
---
_id: '7766'
abstract:
- lang: eng
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.
article_processing_charge: No
article_type: original
author:
- first_name: Daniel M.
full_name: Sussman, Daniel M.
last_name: Sussman
- first_name: Carl Peter
full_name: Goodrich, Carl Peter
id: EB352CD2-F68A-11E9-89C5-A432E6697425
last_name: Goodrich
orcid: 0000-0002-1307-5074
- first_name: Andrea J.
full_name: Liu, Andrea J.
last_name: Liu
- first_name: Sidney R.
full_name: Nagel, Sidney R.
last_name: Nagel
citation:
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
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
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.
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.
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.
date_created: 2020-04-30T11:41:23Z
date_published: 2015-02-15T00:00:00Z
date_updated: 2021-01-12T08:15:23Z
day: '15'
doi: 10.1039/c4sm02905d
extern: '1'
intvolume: ' 11'
issue: '14'
language:
- iso: eng
month: '02'
oa_version: None
page: 2745-2751
publication: Soft Matter
publication_identifier:
issn:
- 1744-683X
- 1744-6848
publication_status: published
publisher: Royal Society of Chemistry
quality_controlled: '1'
status: public
title: Disordered surface vibrations in jammed sphere packings
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 11
year: '2015'
...
---
_id: '7767'
abstract:
- lang: eng
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.
article_number: '032706'
article_processing_charge: No
article_type: original
author:
- first_name: Ruben
full_name: van Drongelen, Ruben
last_name: van Drongelen
- first_name: Anshuman
full_name: Pal, Anshuman
last_name: Pal
- first_name: Carl Peter
full_name: Goodrich, Carl Peter
id: EB352CD2-F68A-11E9-89C5-A432E6697425
last_name: Goodrich
orcid: 0000-0002-1307-5074
- first_name: Timon
full_name: Idema, Timon
last_name: Idema
citation:
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
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.
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.
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.
short: R. van Drongelen, A. Pal, C.P. Goodrich, T. Idema, Physical Review E 91 (2015).
date_created: 2020-04-30T11:41:38Z
date_published: 2015-03-01T00:00:00Z
date_updated: 2021-01-12T08:15:24Z
day: '01'
doi: 10.1103/physreve.91.032706
extern: '1'
intvolume: ' 91'
issue: '3'
language:
- iso: eng
month: '03'
oa_version: None
publication: Physical Review E
publication_identifier:
issn:
- 1539-3755
- 1550-2376
publication_status: published
publisher: American Physical Society
quality_controlled: '1'
status: public
title: Collective dynamics of soft active particles
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 91
year: '2015'
...
---
_id: '777'
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.'
article_processing_charge: No
author:
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
- first_name: Jennifer
full_name: Iglesias, Jennifer
last_name: Iglesias
- first_name: Milan
full_name: Vojnović, Milan
last_name: Vojnović
citation:
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.'
chicago: Alistarh, Dan-Adrian, Jennifer Iglesias, and Milan Vojnović. “Streaming
Min-Max Hypergraph Partitioning,” 2015–January:1900–1908. Neural Information Processing
Systems, 2015.
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.'
ista: 'Alistarh D-A, Iglesias J, Vojnović M. 2015. Streaming min-max hypergraph
partitioning. NIPS: Neural Information Processing Systems vol. 2015–January, 1900–1908.'
mla: Alistarh, Dan-Adrian, et al. Streaming Min-Max Hypergraph Partitioning.
Vol. 2015–January, Neural Information Processing Systems, 2015, pp. 1900–08.
short: D.-A. Alistarh, J. Iglesias, M. Vojnović, in:, Neural Information Processing
Systems, 2015, pp. 1900–1908.
conference:
name: 'NIPS: Neural Information Processing Systems'
date_created: 2018-12-11T11:48:27Z
date_published: 2015-01-01T00:00:00Z
date_updated: 2023-02-23T13:17:09Z
day: '01'
extern: '1'
language:
- iso: eng
main_file_link:
- url: http://papers.nips.cc/paper/5897-streaming-min-max-hypergraph-partitioning
month: '01'
oa_version: None
page: 1900 - 1908
publication_status: published
publisher: Neural Information Processing Systems
publist_id: '6879'
status: public
title: Streaming min-max hypergraph partitioning
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2015-January
year: '2015'
...
---
_id: '7779'
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."
article_processing_charge: No
arxiv: 1
author:
- first_name: Carl Peter
full_name: Goodrich, Carl Peter
id: EB352CD2-F68A-11E9-89C5-A432E6697425
last_name: Goodrich
orcid: 0000-0002-1307-5074
citation:
ama: 'Goodrich CP. Unearthing the anticrystal: Criticality in the linear response
of disordered solids. arXiv:151008820. 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.'
ieee: 'C. P. Goodrich, “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, .'
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).
date_created: 2020-04-30T12:16:18Z
date_published: 2015-10-29T00:00:00Z
date_updated: 2021-01-12T08:15:28Z
day: '29'
extern: '1'
external_id:
arxiv:
- '1510.08820'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1510.08820
month: '10'
oa: 1
oa_version: Preprint
page: '242'
publication: arXiv:1510.08820
publication_status: published
status: public
title: 'Unearthing the anticrystal: Criticality in the linear response of disordered
solids'
type: preprint
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...
---
_id: '778'
abstract:
- lang: eng
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.
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.
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
- first_name: Justin
full_name: Kopinsky, Justin
last_name: Kopinsky
- first_name: Petr
full_name: Kuznetsov, Petr
last_name: Kuznetsov
- first_name: Srivatsan
full_name: Ravi, Srivatsan
last_name: Ravi
- first_name: Nir
full_name: Shavit, Nir
last_name: Shavit
citation:
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'
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'
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.'
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.'
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.
short: D.-A. Alistarh, J. Kopinsky, P. Kuznetsov, S. Ravi, N. Shavit, in:, Springer,
2015, pp. 185–199.
conference:
name: 'DISC: Distributed Computing'
date_created: 2018-12-11T11:48:27Z
date_published: 2015-01-01T00:00:00Z
date_updated: 2023-02-23T13:17:35Z
day: '01'
doi: 10.1007/978-3-662-48653-5_13
extern: '1'
external_id:
arxiv:
- '1405.5689'
intvolume: ' 9363'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1405.5689
month: '01'
oa: 1
oa_version: None
page: 185 - 199
publication_status: published
publisher: Springer
publist_id: '6880'
quality_controlled: '1'
status: public
title: Inherent limitations of hybrid transactional memory
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 9363
year: '2015'
...
---
_id: '779'
abstract:
- lang: eng
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.'
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.
article_processing_charge: No
author:
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
- first_name: Alexander
full_name: Matveev, Alexander
last_name: Matveev
- first_name: William
full_name: Leiserson, William
last_name: Leiserson
- first_name: Nir
full_name: Shavit, Nir
last_name: Shavit
citation:
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'
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'
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.'
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.'
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.'
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.
conference:
name: 'SPAA: Symposium on Parallelism in Algorithms and Architectures'
date_created: 2018-12-11T11:48:27Z
date_published: 2015-06-13T00:00:00Z
date_updated: 2023-02-23T12:35:42Z
day: '13'
doi: 10.1145/2755573.2755600
extern: '1'
language:
- iso: eng
month: '06'
oa_version: None
page: 123 - 132
publication_status: published
publisher: ACM
publist_id: '6876'
related_material:
record:
- id: '6001'
relation: later_version
status: public
status: public
title: 'ThreadScan: Automatic and scalable memory reclamation'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2015-June
year: '2015'
...
---
_id: '780'
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.'
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.”
arxiv: 1
author:
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
- first_name: Rati
full_name: Gelashvili, Rati
last_name: Gelashvili
citation:
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'
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'
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.
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.'
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.'
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.
conference:
name: 'ICALP: International Colloquium on Automota, Languages and Programming'
date_created: 2018-12-11T11:48:28Z
date_published: 2015-01-01T00:00:00Z
date_updated: 2023-02-23T13:18:11Z
day: '01'
doi: 10.1007/978-3-662-47666-6_38
extern: '1'
external_id:
arxiv:
- '1502.05745'
intvolume: ' 9135'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1502.05745
month: '01'
oa: 1
oa_version: Preprint
page: 479 - 491
publication_status: published
publisher: Springer
publist_id: '6877'
status: public
title: Polylogarithmic-time leader election in population protocols
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 9135
year: '2015'
...
---
_id: '781'
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.'
article_processing_charge: No
author:
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
- first_name: Rati
full_name: Gelashvili, Rati
last_name: Gelashvili
- first_name: Milan
full_name: Vojnović, Milan
last_name: Vojnović
citation:
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'
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.
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.'
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.
short: D.-A. Alistarh, R. Gelashvili, M. Vojnović, in:, ACM, 2015, pp. 47–56.
conference:
name: 'PODC: Principles of Distributed Computing'
date_created: 2018-12-11T11:48:28Z
date_published: 2015-07-21T00:00:00Z
date_updated: 2023-02-23T13:18:35Z
day: '21'
doi: 10.1145/2767386.2767429
extern: '1'
language:
- iso: eng
month: '07'
oa_version: None
page: 47 - 56
publication_status: published
publisher: ACM
publist_id: '6873'
status: public
title: Fast and exact majority in population protocols
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2015-July
year: '2015'
...
---
_id: '782'
abstract:
- lang: eng
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.'
article_processing_charge: No
author:
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
- first_name: Thomas
full_name: Sauerwald, Thomas
last_name: Sauerwald
- first_name: Milan
full_name: Vojnović, Milan
last_name: Vojnović
citation:
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'
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'
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.'
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.'
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.
short: D.-A. Alistarh, T. Sauerwald, M. Vojnović, in:, ACM, 2015, pp. 251–260.
conference:
name: 'PODC: Principles of Distributed Computing'
date_created: 2018-12-11T11:48:28Z
date_published: 2015-07-21T00:00:00Z
date_updated: 2023-02-23T13:18:50Z
day: '21'
doi: 10.1145/2767386.2767430
extern: '1'
language:
- iso: eng
month: '07'
oa_version: None
page: 251 - 260
publication_status: published
publisher: ACM
publist_id: '6874'
status: public
title: Lock-Free algorithms under stochastic schedulers
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2015-July
year: '2015'
...