Ontology type: schema:Chapter
2011
AUTHORSPiotr Berman , Arnab Bhattacharyya , Konstantin Makarychev , Sofya Raskhodnikova , Grigory Yaroslavtsev
ABSTRACTWe give an \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O(\sqrt{n}\log n)$\end{document}-approximation algorithm for the problem of finding the sparsest spanner of a given directed graph G on n vertices. A spanner of a graph is a sparse subgraph that approximately preserves distances in the original graph. More precisely, given a graph G = (V,E) with nonnegative edge lengths d: E → ℝ ≥ 0 and a stretchk ≥ 1, a subgraph H = (V,EH) is a k-spanner of G if for every edge (u,v) ∈ E, the graph H contains a path from u to v of length at most k ·d(u,v). The previous best approximation ratio was \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\tilde{O}(n^{2/3})$\end{document}, due to Dinitz and Krauthgamer (STOC ’11).We also present an improved algorithm for the important special case of directed 3-spanners with unit edge lengths. The approximation ratio of our algorithm is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\tilde{O}(n^{1/3})$\end{document} which almost matches the lower bound shown by Dinitz and Krauthgamer for the integrality gap of a natural linear programming relaxation. The best previously known algorithms for this problem, due to Berman, Raskhodnikova and Ruan (FSTTCS ’10) and Dinitz and Krauthgamer, had approximation ratio \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\tilde{O}(\sqrt{n})$\end{document}. More... »
PAGES1-12
Automata, Languages and Programming
ISBN
978-3-642-22005-0
978-3-642-22006-7
http://scigraph.springernature.com/pub.10.1007/978-3-642-22006-7_1
DOIhttp://dx.doi.org/10.1007/978-3-642-22006-7_1
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1036034221
JSON-LD is the canonical representation for SciGraph data.
TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT
[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
"about": [
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Mathematical Sciences",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0103",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Numerical and Computational Mathematics",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Pennsylvania State University, USA",
"id": "http://www.grid.ac/institutes/grid.29857.31",
"name": [
"Pennsylvania State University, USA"
],
"type": "Organization"
},
"familyName": "Berman",
"givenName": "Piotr",
"id": "sg:person.01274506210.27",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Massachusetts Institute of Technology, USA",
"id": "http://www.grid.ac/institutes/grid.116068.8",
"name": [
"Massachusetts Institute of Technology, USA"
],
"type": "Organization"
},
"familyName": "Bhattacharyya",
"givenName": "Arnab",
"id": "sg:person.012357145015.18",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012357145015.18"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "IBM T.J.\u00a0Watson Research Center, USA",
"id": "http://www.grid.ac/institutes/grid.481554.9",
"name": [
"IBM T.J.\u00a0Watson Research Center, USA"
],
"type": "Organization"
},
"familyName": "Makarychev",
"givenName": "Konstantin",
"id": "sg:person.013616666067.80",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013616666067.80"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Pennsylvania State University, USA",
"id": "http://www.grid.ac/institutes/grid.29857.31",
"name": [
"Pennsylvania State University, USA"
],
"type": "Organization"
},
"familyName": "Raskhodnikova",
"givenName": "Sofya",
"id": "sg:person.07502404747.45",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07502404747.45"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Pennsylvania State University, USA",
"id": "http://www.grid.ac/institutes/grid.29857.31",
"name": [
"Pennsylvania State University, USA"
],
"type": "Organization"
},
"familyName": "Yaroslavtsev",
"givenName": "Grigory",
"id": "sg:person.015277345473.26",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015277345473.26"
],
"type": "Person"
}
],
"datePublished": "2011",
"datePublishedReg": "2011-01-01",
"description": "We give an \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$O(\\sqrt{n}\\log n)$\\end{document}-approximation algorithm for the problem of finding the sparsest spanner of a given directed graph G on n vertices. A spanner of a graph is a sparse subgraph that approximately preserves distances in the original graph. More precisely, given a graph G\u2009=\u2009(V,E) with nonnegative edge lengths d:\u00a0E\u2009\u2192\u2009\u211d\u2009\u2265\u20090 and a stretchk\u2009\u2265\u20091, a subgraph H\u2009=\u2009(V,EH) is a k-spanner of G if for every edge (u,v)\u2009\u2208\u2009E, the graph H contains a path from u to v of length at most k \u00b7d(u,v). The previous best approximation ratio was \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\tilde{O}(n^{2/3})$\\end{document}, due to Dinitz and Krauthgamer\u00a0(STOC \u201911).We also present an improved algorithm for the important special case of directed 3-spanners with unit edge lengths. The approximation ratio of our algorithm is \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\tilde{O}(n^{1/3})$\\end{document} which almost matches the lower bound shown by Dinitz and Krauthgamer for the integrality gap of a natural linear programming relaxation. The best previously known algorithms for this problem, due to Berman, Raskhodnikova and Ruan (FSTTCS \u201910) and Dinitz and Krauthgamer, had approximation ratio \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\tilde{O}(\\sqrt{n})$\\end{document}.",
"editor": [
{
"familyName": "Aceto",
"givenName": "Luca",
"type": "Person"
},
{
"familyName": "Henzinger",
"givenName": "Monika",
"type": "Person"
},
{
"familyName": "Sgall",
"givenName": "Ji\u0159\u00ed",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-642-22006-7_1",
"isAccessibleForFree": false,
"isPartOf": {
"isbn": [
"978-3-642-22005-0",
"978-3-642-22006-7"
],
"name": "Automata, Languages and Programming",
"type": "Book"
},
"keywords": [
"approximation ratio",
"graph G",
"natural linear programming relaxation",
"important special case",
"linear programming relaxation",
"best approximation ratio",
"unit edge lengths",
"sparse subgraphs",
"k-spanner",
"programming relaxation",
"original graph",
"sparse spanners",
"approximation algorithm",
"integrality gap",
"graph H",
"special case",
"n vertices",
"subgraph H",
"Krauthgamer",
"spanner problem",
"previous best approximation ratio",
"length d",
"edge length",
"algorithm",
"graph",
"improved algorithm",
"problem",
"Dinitz",
"Raskhodnikova",
"approximation",
"Ruan",
"vertices",
"spanners",
"subgraphs",
"Berman",
"edge",
"relaxation",
"path",
"distance",
"length",
"ratio",
"cases",
"gap"
],
"name": "Improved Approximation for the Directed Spanner Problem",
"pagination": "1-12",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1036034221"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-642-22006-7_1"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-642-22006-7_1",
"https://app.dimensions.ai/details/publication/pub.1036034221"
],
"sdDataset": "chapters",
"sdDatePublished": "2022-08-04T17:17",
"sdLicense": "https://scigraph.springernature.com/explorer/license/",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220804/entities/gbq_results/chapter/chapter_279.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/978-3-642-22006-7_1"
}
]Download the RDF metadata as: json-ld nt turtle xml License info
JSON-LD is a popular format for linked data which is fully compatible with JSON.
curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-22006-7_1'
N-Triples is a line-based linked data format ideal for batch operations.
curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-22006-7_1'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-22006-7_1'
RDF/XML is a standard XML format for linked data.
curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-22006-7_1'
This table displays all metadata directly associated to this object as RDF triples.
146 TRIPLES
22 PREDICATES
68 URIs
61 LITERALS
7 BLANK NODES
| Subject | Predicate | Object | |
|---|---|---|---|
| 1 | sg:pub.10.1007/978-3-642-22006-7_1 | schema:about | anzsrc-for:01 |
| 2 | ″ | ″ | anzsrc-for:0103 |
| 3 | ″ | schema:author | Nfc78ccb31a47480ba747e1930a79c0eb |
| 4 | ″ | schema:datePublished | 2011 |
| 5 | ″ | schema:datePublishedReg | 2011-01-01 |
| 6 | ″ | schema:description | We give an \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O(\sqrt{n}\log n)$\end{document}-approximation algorithm for the problem of finding the sparsest spanner of a given directed graph G on n vertices. A spanner of a graph is a sparse subgraph that approximately preserves distances in the original graph. More precisely, given a graph G = (V,E) with nonnegative edge lengths d: E → ℝ ≥ 0 and a stretchk ≥ 1, a subgraph H = (V,EH) is a k-spanner of G if for every edge (u,v) ∈ E, the graph H contains a path from u to v of length at most k ·d(u,v). The previous best approximation ratio was \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\tilde{O}(n^{2/3})$\end{document}, due to Dinitz and Krauthgamer (STOC ’11).We also present an improved algorithm for the important special case of directed 3-spanners with unit edge lengths. The approximation ratio of our algorithm is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\tilde{O}(n^{1/3})$\end{document} which almost matches the lower bound shown by Dinitz and Krauthgamer for the integrality gap of a natural linear programming relaxation. The best previously known algorithms for this problem, due to Berman, Raskhodnikova and Ruan (FSTTCS ’10) and Dinitz and Krauthgamer, had approximation ratio \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\tilde{O}(\sqrt{n})$\end{document}. |
| 7 | ″ | schema:editor | N44e805dfa48f49619c0fa2aafb8a54fb |
| 8 | ″ | schema:genre | chapter |
| 9 | ″ | schema:isAccessibleForFree | false |
| 10 | ″ | schema:isPartOf | Nb8ba7c87ea664ab09d5cafb5f9d0fc3a |
| 11 | ″ | schema:keywords | Berman |
| 12 | ″ | ″ | Dinitz |
| 13 | ″ | ″ | Krauthgamer |
| 14 | ″ | ″ | Raskhodnikova |
| 15 | ″ | ″ | Ruan |
| 16 | ″ | ″ | algorithm |
| 17 | ″ | ″ | approximation |
| 18 | ″ | ″ | approximation algorithm |
| 19 | ″ | ″ | approximation ratio |
| 20 | ″ | ″ | best approximation ratio |
| 21 | ″ | ″ | cases |
| 22 | ″ | ″ | distance |
| 23 | ″ | ″ | edge |
| 24 | ″ | ″ | edge length |
| 25 | ″ | ″ | gap |
| 26 | ″ | ″ | graph |
| 27 | ″ | ″ | graph G |
| 28 | ″ | ″ | graph H |
| 29 | ″ | ″ | important special case |
| 30 | ″ | ″ | improved algorithm |
| 31 | ″ | ″ | integrality gap |
| 32 | ″ | ″ | k-spanner |
| 33 | ″ | ″ | length |
| 34 | ″ | ″ | length d |
| 35 | ″ | ″ | linear programming relaxation |
| 36 | ″ | ″ | n vertices |
| 37 | ″ | ″ | natural linear programming relaxation |
| 38 | ″ | ″ | original graph |
| 39 | ″ | ″ | path |
| 40 | ″ | ″ | previous best approximation ratio |
| 41 | ″ | ″ | problem |
| 42 | ″ | ″ | programming relaxation |
| 43 | ″ | ″ | ratio |
| 44 | ″ | ″ | relaxation |
| 45 | ″ | ″ | spanner problem |
| 46 | ″ | ″ | spanners |
| 47 | ″ | ″ | sparse spanners |
| 48 | ″ | ″ | sparse subgraphs |
| 49 | ″ | ″ | special case |
| 50 | ″ | ″ | subgraph H |
| 51 | ″ | ″ | subgraphs |
| 52 | ″ | ″ | unit edge lengths |
| 53 | ″ | ″ | vertices |
| 54 | ″ | schema:name | Improved Approximation for the Directed Spanner Problem |
| 55 | ″ | schema:pagination | 1-12 |
| 56 | ″ | schema:productId | N155c50e69d174a28a42ac2e4d344a7d2 |
| 57 | ″ | ″ | N3e88e7b2e88b46c3acb8f473079bb419 |
| 58 | ″ | schema:publisher | N5b833494cdfe4fc199cdf930191c21aa |
| 59 | ″ | schema:sameAs | https://app.dimensions.ai/details/publication/pub.1036034221 |
| 60 | ″ | ″ | https://doi.org/10.1007/978-3-642-22006-7_1 |
| 61 | ″ | schema:sdDatePublished | 2022-08-04T17:17 |
| 62 | ″ | schema:sdLicense | https://scigraph.springernature.com/explorer/license/ |
| 63 | ″ | schema:sdPublisher | N652342ddf6d14c0880e73d2022a8f86f |
| 64 | ″ | schema:url | https://doi.org/10.1007/978-3-642-22006-7_1 |
| 65 | ″ | sgo:license | sg:explorer/license/ |
| 66 | ″ | sgo:sdDataset | chapters |
| 67 | ″ | rdf:type | schema:Chapter |
| 68 | N145ce7fb128f4debac1e1237e32652d2 | rdf:first | sg:person.012357145015.18 |
| 69 | ″ | rdf:rest | Na3d906359db4401880515e5468575fd5 |
| 70 | N155c50e69d174a28a42ac2e4d344a7d2 | schema:name | doi |
| 71 | ″ | schema:value | 10.1007/978-3-642-22006-7_1 |
| 72 | ″ | rdf:type | schema:PropertyValue |
| 73 | N3e88e7b2e88b46c3acb8f473079bb419 | schema:name | dimensions_id |
| 74 | ″ | schema:value | pub.1036034221 |
| 75 | ″ | rdf:type | schema:PropertyValue |
| 76 | N44e805dfa48f49619c0fa2aafb8a54fb | rdf:first | N75a0cca81bcf46979adb2ede06cde420 |
| 77 | ″ | rdf:rest | Ne7f3aac107424f06bcf0b6dd615cc459 |
| 78 | N4d85352472504929a2f6550cba0a2bff | schema:familyName | Sgall |
| 79 | ″ | schema:givenName | Jiří |
| 80 | ″ | rdf:type | schema:Person |
| 81 | N5b833494cdfe4fc199cdf930191c21aa | schema:name | Springer Nature |
| 82 | ″ | rdf:type | schema:Organisation |
| 83 | N652342ddf6d14c0880e73d2022a8f86f | schema:name | Springer Nature - SN SciGraph project |
| 84 | ″ | rdf:type | schema:Organization |
| 85 | N68f5cc1ce92b440fa5a6848b4c5b52ab | rdf:first | sg:person.07502404747.45 |
| 86 | ″ | rdf:rest | Neac9077bd33d441a808b76dc281abe6d |
| 87 | N75a0cca81bcf46979adb2ede06cde420 | schema:familyName | Aceto |
| 88 | ″ | schema:givenName | Luca |
| 89 | ″ | rdf:type | schema:Person |
| 90 | Na3d906359db4401880515e5468575fd5 | rdf:first | sg:person.013616666067.80 |
| 91 | ″ | rdf:rest | N68f5cc1ce92b440fa5a6848b4c5b52ab |
| 92 | Nb8ba7c87ea664ab09d5cafb5f9d0fc3a | schema:isbn | 978-3-642-22005-0 |
| 93 | ″ | ″ | 978-3-642-22006-7 |
| 94 | ″ | schema:name | Automata, Languages and Programming |
| 95 | ″ | rdf:type | schema:Book |
| 96 | Ndbbab76470df4e6082545733f199c976 | rdf:first | N4d85352472504929a2f6550cba0a2bff |
| 97 | ″ | rdf:rest | rdf:nil |
| 98 | Ne2d9a510483240d486c9dfe4731831b4 | schema:familyName | Henzinger |
| 99 | ″ | schema:givenName | Monika |
| 100 | ″ | rdf:type | schema:Person |
| 101 | Ne7f3aac107424f06bcf0b6dd615cc459 | rdf:first | Ne2d9a510483240d486c9dfe4731831b4 |
| 102 | ″ | rdf:rest | Ndbbab76470df4e6082545733f199c976 |
| 103 | Neac9077bd33d441a808b76dc281abe6d | rdf:first | sg:person.015277345473.26 |
| 104 | ″ | rdf:rest | rdf:nil |
| 105 | Nfc78ccb31a47480ba747e1930a79c0eb | rdf:first | sg:person.01274506210.27 |
| 106 | ″ | rdf:rest | N145ce7fb128f4debac1e1237e32652d2 |
| 107 | anzsrc-for:01 | schema:inDefinedTermSet | anzsrc-for: |
| 108 | ″ | schema:name | Mathematical Sciences |
| 109 | ″ | rdf:type | schema:DefinedTerm |
| 110 | anzsrc-for:0103 | schema:inDefinedTermSet | anzsrc-for: |
| 111 | ″ | schema:name | Numerical and Computational Mathematics |
| 112 | ″ | rdf:type | schema:DefinedTerm |
| 113 | sg:person.012357145015.18 | schema:affiliation | grid-institutes:grid.116068.8 |
| 114 | ″ | schema:familyName | Bhattacharyya |
| 115 | ″ | schema:givenName | Arnab |
| 116 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012357145015.18 |
| 117 | ″ | rdf:type | schema:Person |
| 118 | sg:person.01274506210.27 | schema:affiliation | grid-institutes:grid.29857.31 |
| 119 | ″ | schema:familyName | Berman |
| 120 | ″ | schema:givenName | Piotr |
| 121 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27 |
| 122 | ″ | rdf:type | schema:Person |
| 123 | sg:person.013616666067.80 | schema:affiliation | grid-institutes:grid.481554.9 |
| 124 | ″ | schema:familyName | Makarychev |
| 125 | ″ | schema:givenName | Konstantin |
| 126 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013616666067.80 |
| 127 | ″ | rdf:type | schema:Person |
| 128 | sg:person.015277345473.26 | schema:affiliation | grid-institutes:grid.29857.31 |
| 129 | ″ | schema:familyName | Yaroslavtsev |
| 130 | ″ | schema:givenName | Grigory |
| 131 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015277345473.26 |
| 132 | ″ | rdf:type | schema:Person |
| 133 | sg:person.07502404747.45 | schema:affiliation | grid-institutes:grid.29857.31 |
| 134 | ″ | schema:familyName | Raskhodnikova |
| 135 | ″ | schema:givenName | Sofya |
| 136 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07502404747.45 |
| 137 | ″ | rdf:type | schema:Person |
| 138 | grid-institutes:grid.116068.8 | schema:alternateName | Massachusetts Institute of Technology, USA |
| 139 | ″ | schema:name | Massachusetts Institute of Technology, USA |
| 140 | ″ | rdf:type | schema:Organization |
| 141 | grid-institutes:grid.29857.31 | schema:alternateName | Pennsylvania State University, USA |
| 142 | ″ | schema:name | Pennsylvania State University, USA |
| 143 | ″ | rdf:type | schema:Organization |
| 144 | grid-institutes:grid.481554.9 | schema:alternateName | IBM T.J. Watson Research Center, USA |
| 145 | ″ | schema:name | IBM T.J. Watson Research Center, USA |
| 146 | ″ | rdf:type | schema:Organization |