Zobrazeno 1 - 10
of 155
pro vyhledávání: '"Leslie Ann Goldberg"'
Publikováno v:
PLoS ONE, Vol 16, Iss 5, p e0250435 (2021)
We study the effects of two mechanisms which increase the efficacy of contact-tracing applications (CTAs) such as the mobile phone contact-tracing applications that have been used during the COVID-19 epidemic. The first mechanism is the introduction
Externí odkaz:
https://doaj.org/article/245d558dab364ca9a088cac07711bb7b
Publikováno v:
Theoretical Computer Science. 892:48-84
Counting the independent sets of a graph is a classical #P-complete problem, even in the bipartite case. We give an exponential-time approximation scheme for this problem which is faster than the best known algorithm for the exact problem. The runnin
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::c3ec25ea9a279035f7d34df8a5733b91
https://doi.org/10.1016/j.tcs.2021.09.009
https://doi.org/10.1016/j.tcs.2021.09.009
The independent set polynomial is important in many areas. For every integer $\Delta\geq 2$, the Shearer threshold is the value $\lambda^*(\Delta)=(\Delta-1)^{\Delta-1}/\Delta^{\Delta}$ . It is known that for $\lambda < - \lambda^*(\Delta)$, there ar
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::75202b57e45ac52ff744a31b0c8b1cd1
https://ora.ox.ac.uk/objects/uuid:1d19577d-8afa-4c86-a8ca-5da9bc779ba6
https://ora.ox.ac.uk/objects/uuid:1d19577d-8afa-4c86-a8ca-5da9bc779ba6
Publikováno v:
Journal of Computer and System Sciences. 115:187-213
We study the complexity of approximate counting Constraint Satisfaction Problems (#CSPs) in a bounded degree setting. Specifically, given a Boolean constraint language $\Gamma$ and a degree bound $\Delta$, we study the complexity of #CSP$_\Delta(\Gam
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::ced3109673916ff4a71b397d6b5bccb1
https://doi.org/10.1016/j.jcss.2020.08.003
https://doi.org/10.1016/j.jcss.2020.08.003
Publikováno v:
ACM Transactions on Algorithms. 16:1-33
We study the mixing time of random walks on small-world networks modelled as follows: starting with the 2-dimensional periodic grid, each pair of vertices $\{u,v\}$ with distance $d>1$ is added as a "long-range" edge with probability proportional to
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::89711a42e01d4583a8d4421f51b4efa1
https://doi.org/10.1145/3382208
https://doi.org/10.1145/3382208
Autor:
Leslie Ann Goldberg, John Lapinskas, Pascal Pfister, Florian Meier, Konstantinos Panagiotou, Johannes Lengler
Publikováno v:
Theoretical Computer Science. 758:73-93
We study the Moran process as adapted by Lieberman, Hauert and Nowak. This is a model of an evolving population on a graph or digraph where certain individuals, called “mutants” have fitness r and other individuals, called “non-mutants” have
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::6ee55c7fce88165533f7ebc29dfc7b98
https://doi.org/10.1016/j.tcs.2018.08.005
https://doi.org/10.1016/j.tcs.2018.08.005
Publikováno v:
PLoS ONE, Vol 16, Iss 5, p e0250435 (2021)
Goldberg, L A, Jorritsma, J, Komjáthy, J & Lapinskas, J A 2021, ' Increasing efficacy of contact-tracing applications by user referrals and stricter quarantining ', PLoS ONE, vol. 16, no. 5, e0250435 . https://doi.org/10.1371/journal.pone.0250435
PLoS ONE, 16(5):e0250435. Public Library of Science
PLoS ONE
Goldberg, L A, Jorritsma, J, Komjáthy, J & Lapinskas, J A 2021, ' Increasing efficacy of contact-tracing applications by user referrals and stricter quarantining ', PLoS ONE, vol. 16, no. 5, e0250435 . https://doi.org/10.1371/journal.pone.0250435
PLoS ONE, 16(5):e0250435. Public Library of Science
PLoS ONE
We study the effects of two mechanisms which increase the efficacy of contact-tracing applications (CTAs) such as the mobile phone contact-tracing applications that have been used during the COVID-19 epidemic. The first mechanism is the introduction
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::7c13fa301e918884ea4a29c7bd9bd692
https://doi.org/10.1371/journal.pone.0250435
https://doi.org/10.1371/journal.pone.0250435
The polymer model framework is a classical tool from statistical mechanics that has recently been used to obtain approximation algorithms for spin systems on classes of bounded-degree graphs; examples include the ferromagnetic Potts model on expander
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::609e0a554b5fdfe2c5fd3431581e7233
http://arxiv.org/abs/2105.00524
http://arxiv.org/abs/2105.00524
Autor:
Will Perkins, Eric Vigoda, Leslie Ann Goldberg, James Stewart, Zongchen Chen, Andreas Galanis
For spin systems, such as the hard-core model on independent sets weighted by fugacity lambda>0, efficient algorithms for the associated approximate counting/sampling problems typically apply in the high-temperature region, corresponding to low fugac
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::7651ee69569add5701d0888f0e093b40
https://ora.ox.ac.uk/objects/uuid:743b4aff-3278-445d-b3b4-dcde6b0a5d5b
https://ora.ox.ac.uk/objects/uuid:743b4aff-3278-445d-b3b4-dcde6b0a5d5b
Publikováno v:
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA)
We study the problem of computing the parity of the number of homomorphisms from an input graph $G$ to a fixed graph $H$. Faben and Jerrum [Theory Comput., 11 (2015), pp. 35--57] introduced an explicit criterion on the graph $H$ and conjectured that,
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2f62a8cedd0e9d2c32b5752a53048d2c