Zobrazeno 1 - 10
of 55
pro vyhledávání: '"Gregory B. Sorkin"'
Publikováno v:
SIAM Journal on Discrete Mathematics. 36:1306-1342
The Ising antiferromagnet is an important statistical physics model with close connections to the {\sc Max Cut} problem. Combining spatial mixing arguments with the method of moments and the interpolation method, we pinpoint the replica symmetry brea
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::1335076b7e66654def5b5b0bf155a92d
https://doi.org/10.1137/20m137999x
https://doi.org/10.1137/20m137999x
Publikováno v:
Random Structures & Algorithms. 57:1205-1247
Consider a complete graph $K_n$ with edge weights drawn independently from a uniform distribution $U(0,1)$. The weight of the shortest (minimum-weight) path $P_1$ between two given vertices is known to be $\ln n / n$, asymptotically. Define a second-
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b234968e274a919738972fb98dccfe55
https://doi.org/10.1002/rsa.20962
https://doi.org/10.1002/rsa.20962
Publikováno v:
SIAM Journal on Discrete Mathematics. 32:2115-2133
We determine, asymptotically in $n$, the distribution and mean of the weight of a minimum-weight $k$-clique (or any strictly balanced graph $H$) in a complete graph $K_n$ whose edge weights are independent random values drawn from the uniform distrib
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::68c38137f3692206fe12dc8e3843aa82
https://doi.org/10.1137/17m1138303
https://doi.org/10.1137/17m1138303
Autor:
Svante Janson, Gregory B. Sorkin
In a complete graph $K_n$ with edge weights drawn independently from a uniform distribution $U(0,1)$ (or alternatively an exponential distribution $\operatorname{Exp}(1)$), let $T_1$ be the MST (the spanning tree of minimum weight) and let $T_k$ be t
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::8fa6a38b45d0f42a6fd320b8bb71f1e5
Autor:
Boris Pittel, Gregory B. Sorkin
Publikováno v:
Combinatorics, Probability and Computing. 25:236-268
We consider "unconstrained" random $k$-XORSAT, which is a uniformly random system of $m$ linear non-homogeneous equations in $\mathbb{F}_2$ over $n$ variables, each equation containing $k \geq 3$ variables, and also consider a "constrained" model whe
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b3fb36d528312a37786473c89b609081
https://doi.org/10.1017/s0963548315000097
https://doi.org/10.1017/s0963548315000097
Autor:
Serge Gaspers, Gregory B. Sorkin
We show a method resulting in the improvement of several polynomial-space, exponential-time algorithms. The method capitalizes on the existence of small balanced separators for sparse graphs, which can be exploited for branching to disconnect an inst
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::8bd727eeb1785ed980921b061b7c40f2
http://eprints.lse.ac.uk/85684/
http://eprints.lse.ac.uk/85684/
Autor:
Gregory B. Sorkin, Alan Frieze
Publikováno v:
Random Structures & Algorithms. 46:160-196
Beautiful formulas are known for the expected cost of random two-dimensional assignment problems, but in higher dimensions even the scaling is not known. In three dimensions and above, the problem has natural “Axial” and “Planar” versions, bo
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::911dd1c1cf880ca61834ce10046b0c81
https://doi.org/10.1002/rsa.20525
https://doi.org/10.1002/rsa.20525
Autor:
Alex Scott, Gregory B. Sorkin
Publikováno v:
Lecture Notes in Computer Science ISBN: 9783540388753
ESA
Scopus-Elsevier
ESA
Scopus-Elsevier
The class Max (r, 2)-CSP consists of constraint satisfaction problems with at most two r-valued variables per clause. For instances with n variables and m binary clauses, we present an (O) over tilde (r(19m/100))-time algorithm. It is the fastest alg
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2ac7269533b17708cd0129263497ab0c
https://ora.ox.ac.uk/objects/uuid:c210e70d-d1e6-4f93-9cfd-b7dda1f6ffb9
https://ora.ox.ac.uk/objects/uuid:c210e70d-d1e6-4f93-9cfd-b7dda1f6ffb9
Autor:
Gregory B. Sorkin, Alex Scott
We show that a maximum cut of a random graph below the giant-component threshold can be found in linear space and linear expected time by a simple algorithm. In fact, the algorithm solves a more general class of problems, namely binary 2-variable con
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::e9b4d5dcee2341abb4d7d02534d0228b
https://ora.ox.ac.uk/objects/uuid:ca2d9546-9d79-4d7b-a4b3-5dec57b7f8d2
https://ora.ox.ac.uk/objects/uuid:ca2d9546-9d79-4d7b-a4b3-5dec57b7f8d2
Autor:
Gregory B. Sorkin, Alex Scott
The class Max (r, 2)-CSP, or simply Max 2-CSP, consists of constraint satisfaction problems with at most two r-valued variables per clause. For instances with n variables and m binary clauses, we present an O (n r 5 + 19 m / 100)-time algorithm which
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::29a132b308739410c980f57f95f3f34f
https://ora.ox.ac.uk/objects/uuid:6fae7644-17dc-43fb-b26d-734530b05803
https://ora.ox.ac.uk/objects/uuid:6fae7644-17dc-43fb-b26d-734530b05803