# The Power and Limitations of Uniform Samples in Testing Properties of Figures

Ontology type: schema:ScholarlyArticle      Open Access: True

### Article Info

DATE

2018-07-31

AUTHORS ABSTRACT

We investigate testing of properties of 2-dimensional figures that consist of a black object on a white background. Given a parameter ϵ∈(0,1/2)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\epsilon }\in (0,1/2)$$\end{document}, a tester for a specified property has to accept with probability at least 2/3 if the input figure satisfies the property and reject with probability at least 2/3 if it is ϵ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\epsilon }$$\end{document}-far from satisfying the property. In general, property testers can query the color of any point in the input figure. We study the power of testers that get access only to uniform samples from the input figure. We show that for the property of being a half-plane, the uniform testers are as powerful as general testers: they require only O(ϵ-1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O({\epsilon }^{-1})$$\end{document} samples. In contrast, we prove that convexity can be tested with O(ϵ-1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O({\epsilon }^{-1})$$\end{document} queries by testers that can make queries of their choice while uniform testers for this property require Ω(ϵ-5/4)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varOmega ({\epsilon }^{-5/4})$$\end{document} samples. Previously, the fastest known tester for convexity needed Θ(ϵ-4/3)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varTheta ({\epsilon }^{-4/3})$$\end{document} queries. More... »

PAGES

1247-1266

### References to SciGraph publications

• 1999. Improved Testing Algorithms for Monotonicity in RANDOMIZATION, APPROXIMATION, AND COMBINATORIAL OPTIMIZATION. ALGORITHMS AND TECHNIQUES
• 2000. Property Testing in Computational Geometry in ALGORITHMS - ESA 2000
• 2016-07-12. Fast-Match: Fast Affine Template Matching in INTERNATIONAL JOURNAL OF COMPUTER VISION
• 2016-04-22. Linearity Testing/Testing Hadamard Codes in ENCYCLOPEDIA OF ALGORITHMS
• 2000-03. Testing Monotonicity in COMBINATORICA
• 2016-04-22. Testing if an Array Is Sorted in ENCYCLOPEDIA OF ALGORITHMS
• 2001-08-17. Property Testing with Geometric Queries in ALGORITHMS — ESA 2001
• 1987. Algorithms in Combinatorial Geometry in NONE
• 2009-08-29. Testing Periodicity in ALGORITHMICA
• 2010. Property Testing, Current Research and Surveys in NONE
• 2003. Approximate Testing of Visual Properties in APPROXIMATION, RANDOMIZATION, AND COMBINATORIAL OPTIMIZATION.. ALGORITHMS AND TECHNIQUES
• 2002-02. Property Testing in Bounded Degree Graphs in ALGORITHMICA
• 1992. Learning convex sets under uniform distribution in DATA STRUCTURES AND EFFICIENT ALGORITHMS
• 2004. Testing Geometric Convexity in FSTTCS 2004: FOUNDATIONS OF SOFTWARE TECHNOLOGY AND THEORETICAL COMPUTER SCIENCE

TITLE

Algorithmica

ISSUE

3

VOLUME

81

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00453-018-0467-9

DOI

http://dx.doi.org/10.1007/s00453-018-0467-9

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1105927114

Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service:

[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/21",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "History and Archaeology",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/2103",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Historical Studies",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Pennsylvania State University, University Park, USA",
"id": "http://www.grid.ac/institutes/grid.29857.31",
"name": [
"Pennsylvania State University, University Park, 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": "Pennsylvania State University, University Park, USA",
"id": "http://www.grid.ac/institutes/grid.29857.31",
"name": [
"Pennsylvania State University, University Park, USA"
],
"type": "Organization"
},
"familyName": "Murzabulatov",
"givenName": "Meiram",
"id": "sg:person.011013132114.05",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011013132114.05"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Boston University, Boston, USA",
"id": "http://www.grid.ac/institutes/grid.189504.1",
"name": [
"Boston University, Boston, USA"
],
"type": "Organization"
},
"givenName": "Sofya",
"id": "sg:person.07502404747.45",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07502404747.45"
],
"type": "Person"
}
],
"citation": [
{
"id": "sg:pub.10.1007/3-540-44676-1_22",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1053500578",
"https://doi.org/10.1007/3-540-44676-1_22"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s004930070011",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1033268083",
"https://doi.org/10.1007/s004930070011"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-61568-9",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1049996833",
"https://doi.org/10.1007/978-3-642-61568-9"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-16367-8",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1035758014",
"https://doi.org/10.1007/978-3-642-16367-8"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-45253-2_15",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1052879480",
"https://doi.org/10.1007/3-540-45253-2_15"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-48413-4_10",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1049264838",
"https://doi.org/10.1007/978-3-540-48413-4_10"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s00453-001-0078-7",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1004175003",
"https://doi.org/10.1007/s00453-001-0078-7"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-45198-3_31",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1004005510",
"https://doi.org/10.1007/978-3-540-45198-3_31"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s00453-009-9351-y",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1015498195",
"https://doi.org/10.1007/s00453-009-9351-y"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s11263-016-0926-1",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1013038437",
"https://doi.org/10.1007/s11263-016-0926-1"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-30538-5_39",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1041646269",
"https://doi.org/10.1007/978-3-540-30538-5_39"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-55488-2_28",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1052476962",
"https://doi.org/10.1007/3-540-55488-2_28"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-1-4939-2864-4_700",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1112905245",
"https://doi.org/10.1007/978-1-4939-2864-4_700"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-1-4939-2864-4_202",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1043023640",
"https://doi.org/10.1007/978-1-4939-2864-4_202"
],
"type": "CreativeWork"
}
],
"datePublished": "2018-07-31",
"datePublishedReg": "2018-07-31",
"description": "We investigate testing of properties of 2-dimensional figures that consist of a black object on a white background. Given a parameter \u03f5\u2208(0,1/2)\\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}$${\\epsilon }\\in (0,1/2)$$\\end{document}, a tester for a specified property has to accept with probability at least 2/3 if the input figure satisfies the property and reject with probability at least 2/3 if it is \u03f5\\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}$${\\epsilon }$$\\end{document}-far from satisfying the property. In general, property testers can query the color of any point in the input figure. We study the power of testers that get access only to uniform samples from the input figure. We show that for the property of being a half-plane, the uniform testers are as powerful as general testers: they require only O(\u03f5-1)\\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({\\epsilon }^{-1})$$\\end{document} samples. In contrast, we prove that convexity can be tested with O(\u03f5-1)\\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({\\epsilon }^{-1})$$\\end{document} queries by testers that can make queries of their choice while uniform testers for this property require \u03a9(\u03f5-5/4)\\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}$$\\varOmega ({\\epsilon }^{-5/4})$$\\end{document} samples. Previously, the fastest known tester for convexity needed \u0398(\u03f5-4/3)\\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}$$\\varTheta ({\\epsilon }^{-4/3})$$\\end{document} queries.",
"genre": "article",
"id": "sg:pub.10.1007/s00453-018-0467-9",
"isAccessibleForFree": true,
"isFundedItemOf": [
{
"id": "sg:grant.3580787",
"type": "MonetaryGrant"
}
],
"isPartOf": [
{
"id": "sg:journal.1047644",
"issn": [
"0178-4617",
"1432-0541"
],
"name": "Algorithmica",
"publisher": "Springer Nature",
"type": "Periodical"
},
{
"issueNumber": "3",
"type": "PublicationIssue"
},
{
"type": "PublicationVolume",
}
],
"keywords": [
"black objects",
"uniform samples",
"probability",
"property tester",
"convexity",
"testing properties",
"properties",
"testing of properties",
"objects",
"parameters",
"input figures",
"point",
"power",
"figures",
"choice",
"background",
"samples",
"queries",
"limitations",
"testing",
"white background",
"tester",
"color",
"contrast",
"access"
],
"name": "The Power and Limitations of Uniform Samples in Testing Properties of Figures",
"pagination": "1247-1266",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1105927114"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/s00453-018-0467-9"
]
}
],
"sameAs": [
"https://doi.org/10.1007/s00453-018-0467-9",
"https://app.dimensions.ai/details/publication/pub.1105927114"
],
"sdDataset": "articles",
"sdDatePublished": "2022-08-04T17:05",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220804/entities/gbq_results/article/article_767.jsonl",
"type": "ScholarlyArticle",
"url": "https://doi.org/10.1007/s00453-018-0467-9"
}
]

HOW TO GET THIS DATA PROGRAMMATICALLY:

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/s00453-018-0467-9'

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/s00453-018-0467-9'

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-018-0467-9'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-018-0467-9'

This table displays all metadata directly associated to this object as RDF triples.

157 TRIPLES      21 PREDICATES      63 URIs      41 LITERALS      6 BLANK NODES

Subject Predicate Object
2 anzsrc-for:2103
4 schema:citation sg:pub.10.1007/3-540-44676-1_22
5 sg:pub.10.1007/3-540-45253-2_15
6 sg:pub.10.1007/3-540-55488-2_28
7 sg:pub.10.1007/978-1-4939-2864-4_202
8 sg:pub.10.1007/978-1-4939-2864-4_700
9 sg:pub.10.1007/978-3-540-30538-5_39
10 sg:pub.10.1007/978-3-540-45198-3_31
11 sg:pub.10.1007/978-3-540-48413-4_10
12 sg:pub.10.1007/978-3-642-16367-8
13 sg:pub.10.1007/978-3-642-61568-9
14 sg:pub.10.1007/s00453-001-0078-7
15 sg:pub.10.1007/s00453-009-9351-y
16 sg:pub.10.1007/s004930070011
17 sg:pub.10.1007/s11263-016-0926-1
18 schema:datePublished 2018-07-31
19 schema:datePublishedReg 2018-07-31
20 schema:description We investigate testing of properties of 2-dimensional figures that consist of a black object on a white background. Given a parameter ϵ∈(0,1/2)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\epsilon }\in (0,1/2)$$\end{document}, a tester for a specified property has to accept with probability at least 2/3 if the input figure satisfies the property and reject with probability at least 2/3 if it is ϵ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\epsilon }$$\end{document}-far from satisfying the property. In general, property testers can query the color of any point in the input figure. We study the power of testers that get access only to uniform samples from the input figure. We show that for the property of being a half-plane, the uniform testers are as powerful as general testers: they require only O(ϵ-1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O({\epsilon }^{-1})$$\end{document} samples. In contrast, we prove that convexity can be tested with O(ϵ-1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O({\epsilon }^{-1})$$\end{document} queries by testers that can make queries of their choice while uniform testers for this property require Ω(ϵ-5/4)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varOmega ({\epsilon }^{-5/4})$$\end{document} samples. Previously, the fastest known tester for convexity needed Θ(ϵ-4/3)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varTheta ({\epsilon }^{-4/3})$$\end{document} queries.
21 schema:genre article
22 schema:isAccessibleForFree true
23 schema:isPartOf N8ce86f17c1e64988ae57e16a3625e23f
24 Ndcd9945ea0394f5f8455bae745c4de42
25 sg:journal.1047644
26 schema:keywords access
27 background
28 black objects
29 choice
30 color
31 contrast
32 convexity
33 figures
34 input figures
35 limitations
36 objects
37 parameters
38 point
39 power
40 probability
41 properties
42 property tester
43 queries
44 samples
45 tester
46 testing
47 testing of properties
48 testing properties
49 uniform samples
50 white background
51 schema:name The Power and Limitations of Uniform Samples in Testing Properties of Figures
52 schema:pagination 1247-1266
53 schema:productId N4348e79ce1e84d1f94d7a5e2282d5788
54 Na7cc2db6029c4b73b0800df8562d0d35
55 schema:sameAs https://app.dimensions.ai/details/publication/pub.1105927114
56 https://doi.org/10.1007/s00453-018-0467-9
57 schema:sdDatePublished 2022-08-04T17:05
59 schema:sdPublisher Na514dcea8218438d93ed311d1b701370
60 schema:url https://doi.org/10.1007/s00453-018-0467-9
62 sgo:sdDataset articles
63 rdf:type schema:ScholarlyArticle
65 rdf:rest N0604e8dc08bb460babefef98963c347e
66 N0604e8dc08bb460babefef98963c347e rdf:first sg:person.011013132114.05
67 rdf:rest Nd4934d5b45ef4de9b3febb749877412d
68 N4348e79ce1e84d1f94d7a5e2282d5788 schema:name doi
69 schema:value 10.1007/s00453-018-0467-9
70 rdf:type schema:PropertyValue
72 rdf:type schema:PublicationVolume
73 Na514dcea8218438d93ed311d1b701370 schema:name Springer Nature - SN SciGraph project
74 rdf:type schema:Organization
75 Na7cc2db6029c4b73b0800df8562d0d35 schema:name dimensions_id
76 schema:value pub.1105927114
77 rdf:type schema:PropertyValue
78 Nd4934d5b45ef4de9b3febb749877412d rdf:first sg:person.07502404747.45
79 rdf:rest rdf:nil
80 Ndcd9945ea0394f5f8455bae745c4de42 schema:issueNumber 3
81 rdf:type schema:PublicationIssue
82 anzsrc-for:21 schema:inDefinedTermSet anzsrc-for:
83 schema:name History and Archaeology
84 rdf:type schema:DefinedTerm
85 anzsrc-for:2103 schema:inDefinedTermSet anzsrc-for:
86 schema:name Historical Studies
87 rdf:type schema:DefinedTerm
88 sg:grant.3580787 http://pending.schema.org/fundedItem sg:pub.10.1007/s00453-018-0467-9
89 rdf:type schema:MonetaryGrant
90 sg:journal.1047644 schema:issn 0178-4617
91 1432-0541
92 schema:name Algorithmica
93 schema:publisher Springer Nature
94 rdf:type schema:Periodical
95 sg:person.011013132114.05 schema:affiliation grid-institutes:grid.29857.31
96 schema:familyName Murzabulatov
97 schema:givenName Meiram
98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011013132114.05
99 rdf:type schema:Person
100 sg:person.01274506210.27 schema:affiliation grid-institutes:grid.29857.31
101 schema:familyName Berman
102 schema:givenName Piotr
103 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27
104 rdf:type schema:Person
105 sg:person.07502404747.45 schema:affiliation grid-institutes:grid.189504.1
107 schema:givenName Sofya
108 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07502404747.45
109 rdf:type schema:Person
110 sg:pub.10.1007/3-540-44676-1_22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053500578
111 https://doi.org/10.1007/3-540-44676-1_22
112 rdf:type schema:CreativeWork
113 sg:pub.10.1007/3-540-45253-2_15 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052879480
114 https://doi.org/10.1007/3-540-45253-2_15
115 rdf:type schema:CreativeWork
116 sg:pub.10.1007/3-540-55488-2_28 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052476962
117 https://doi.org/10.1007/3-540-55488-2_28
118 rdf:type schema:CreativeWork
119 sg:pub.10.1007/978-1-4939-2864-4_202 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043023640
120 https://doi.org/10.1007/978-1-4939-2864-4_202
121 rdf:type schema:CreativeWork
122 sg:pub.10.1007/978-1-4939-2864-4_700 schema:sameAs https://app.dimensions.ai/details/publication/pub.1112905245
123 https://doi.org/10.1007/978-1-4939-2864-4_700
124 rdf:type schema:CreativeWork
125 sg:pub.10.1007/978-3-540-30538-5_39 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041646269
126 https://doi.org/10.1007/978-3-540-30538-5_39
127 rdf:type schema:CreativeWork
128 sg:pub.10.1007/978-3-540-45198-3_31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004005510
129 https://doi.org/10.1007/978-3-540-45198-3_31
130 rdf:type schema:CreativeWork
131 sg:pub.10.1007/978-3-540-48413-4_10 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049264838
132 https://doi.org/10.1007/978-3-540-48413-4_10
133 rdf:type schema:CreativeWork
134 sg:pub.10.1007/978-3-642-16367-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035758014
135 https://doi.org/10.1007/978-3-642-16367-8
136 rdf:type schema:CreativeWork
137 sg:pub.10.1007/978-3-642-61568-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049996833
138 https://doi.org/10.1007/978-3-642-61568-9
139 rdf:type schema:CreativeWork
140 sg:pub.10.1007/s00453-001-0078-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004175003
141 https://doi.org/10.1007/s00453-001-0078-7
142 rdf:type schema:CreativeWork
143 sg:pub.10.1007/s00453-009-9351-y schema:sameAs https://app.dimensions.ai/details/publication/pub.1015498195
144 https://doi.org/10.1007/s00453-009-9351-y
145 rdf:type schema:CreativeWork
146 sg:pub.10.1007/s004930070011 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033268083
147 https://doi.org/10.1007/s004930070011
148 rdf:type schema:CreativeWork
149 sg:pub.10.1007/s11263-016-0926-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013038437
150 https://doi.org/10.1007/s11263-016-0926-1
151 rdf:type schema:CreativeWork
152 grid-institutes:grid.189504.1 schema:alternateName Boston University, Boston, USA
153 schema:name Boston University, Boston, USA
154 rdf:type schema:Organization
155 grid-institutes:grid.29857.31 schema:alternateName Pennsylvania State University, University Park, USA
156 schema:name Pennsylvania State University, University Park, USA
157 rdf:type schema:Organization