Ontology type: schema:Chapter Open Access: True
2014
AUTHORSSwastik Kopparty , Mrinal Kumar , Michael Saks
ABSTRACTWe study the problem of indexing necklaces, and give the first polynomial time algorithm for this problem. Specifically, we give a poly(n, log|Σ|)-time computable bijection between \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\{1, \ldots, |\cal N|\}$\end{document} and the set \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\cal N$\end{document} of all necklaces of length n over a finite alphabet Σ.Our main application is to give an explicit indexing of all irreducible polynomials of degree n over the finite field \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathbb{F}_q$\end{document} in time poly(n, logq) (with n logq bits of advice). This has applications in pseudorandomness, and answers an open question of Alon, Goldreich, Håstad and Peralta [2]. More... »
PAGES726-737
Automata, Languages, and Programming
ISBN
978-3-662-43947-0
978-3-662-43948-7
http://scigraph.springernature.com/pub.10.1007/978-3-662-43948-7_60
DOIhttp://dx.doi.org/10.1007/978-3-662-43948-7_60
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1001175768
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/17",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Psychology and Cognitive Sciences",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1701",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Psychology",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Department of Computer Science and Department of Mathematics, Rutgers University, USA",
"id": "http://www.grid.ac/institutes/grid.430387.b",
"name": [
"Department of Computer Science and Department of Mathematics, Rutgers University, USA"
],
"type": "Organization"
},
"familyName": "Kopparty",
"givenName": "Swastik",
"id": "sg:person.014276170447.16",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014276170447.16"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Computer Science, Rutgers University, USA",
"id": "http://www.grid.ac/institutes/grid.430387.b",
"name": [
"Department of Computer Science, Rutgers University, USA"
],
"type": "Organization"
},
"familyName": "Kumar",
"givenName": "Mrinal",
"id": "sg:person.013641113207.82",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013641113207.82"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Mathematics, Rutgers University, USA",
"id": "http://www.grid.ac/institutes/grid.430387.b",
"name": [
"Department of Mathematics, Rutgers University, USA"
],
"type": "Organization"
},
"familyName": "Saks",
"givenName": "Michael",
"id": "sg:person.011520224512.05",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011520224512.05"
],
"type": "Person"
}
],
"datePublished": "2014",
"datePublishedReg": "2014-01-01",
"description": "We study the problem of indexing necklaces, and give the first polynomial time algorithm for this problem. Specifically, we give a poly(n, log|\u03a3|)-time computable bijection between \\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}$\\{1, \\ldots, |\\cal N|\\}$\\end{document} and the set \\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}$\\cal N$\\end{document} of all necklaces of length n over a finite alphabet \u03a3.Our main application is to give an explicit indexing of all irreducible polynomials of degree n over the finite field \\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}$\\mathbb{F}_q$\\end{document} in time poly(n, logq) (with n logq bits of advice). This has applications in pseudorandomness, and answers an open question of Alon, Goldreich, H\u00e5stad and Peralta [2].",
"editor": [
{
"familyName": "Esparza",
"givenName": "Javier",
"type": "Person"
},
{
"familyName": "Fraigniaud",
"givenName": "Pierre",
"type": "Person"
},
{
"familyName": "Husfeldt",
"givenName": "Thore",
"type": "Person"
},
{
"familyName": "Koutsoupias",
"givenName": "Elias",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-662-43948-7_60",
"isAccessibleForFree": true,
"isPartOf": {
"isbn": [
"978-3-662-43947-0",
"978-3-662-43948-7"
],
"name": "Automata, Languages, and Programming",
"type": "Book"
},
"keywords": [
"finite field",
"irreducible polynomials",
"first polynomial-time algorithm",
"polynomial time algorithm",
"time algorithm",
"degree n",
"length n",
"main applications",
"polynomials",
"problem",
"computable bijection",
"open question",
"problem of indexing",
"bijection",
"field",
"pseudorandomness",
"Alon",
"Goldreich",
"indexing",
"necklace",
"algorithm",
"set",
"alphabet \u03a3.",
"applications",
"H\u00e5stad",
"efficient indexing",
"finite alphabet \u03a3.",
"time",
"Peralta",
"questions"
],
"name": "Efficient Indexing of Necklaces and Irreducible Polynomials over Finite Fields",
"pagination": "726-737",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1001175768"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-662-43948-7_60"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-662-43948-7_60",
"https://app.dimensions.ai/details/publication/pub.1001175768"
],
"sdDataset": "chapters",
"sdDatePublished": "2022-08-04T17:19",
"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_360.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/978-3-662-43948-7_60"
}
]
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-662-43948-7_60'
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-662-43948-7_60'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-43948-7_60'
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-662-43948-7_60'
This table displays all metadata directly associated to this object as RDF triples.
122 TRIPLES
22 PREDICATES
55 URIs
48 LITERALS
7 BLANK NODES
Subject | Predicate | Object | |
---|---|---|---|
1 | sg:pub.10.1007/978-3-662-43948-7_60 | schema:about | anzsrc-for:17 |
2 | ″ | ″ | anzsrc-for:1701 |
3 | ″ | schema:author | N02b24469b89040f1b9310100ccc4528e |
4 | ″ | schema:datePublished | 2014 |
5 | ″ | schema:datePublishedReg | 2014-01-01 |
6 | ″ | schema:description | We study the problem of indexing necklaces, and give the first polynomial time algorithm for this problem. Specifically, we give a poly(n, log|Σ|)-time computable bijection between \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\{1, \ldots, |\cal N|\}$\end{document} and the set \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\cal N$\end{document} of all necklaces of length n over a finite alphabet Σ.Our main application is to give an explicit indexing of all irreducible polynomials of degree n over the finite field \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathbb{F}_q$\end{document} in time poly(n, logq) (with n logq bits of advice). This has applications in pseudorandomness, and answers an open question of Alon, Goldreich, Håstad and Peralta [2]. |
7 | ″ | schema:editor | Ned80e21471924a108177d401f9ad56e5 |
8 | ″ | schema:genre | chapter |
9 | ″ | schema:isAccessibleForFree | true |
10 | ″ | schema:isPartOf | N7d8a6ff17fe64ecaa889e101c0410be1 |
11 | ″ | schema:keywords | Alon |
12 | ″ | ″ | Goldreich |
13 | ″ | ″ | Håstad |
14 | ″ | ″ | Peralta |
15 | ″ | ″ | algorithm |
16 | ″ | ″ | alphabet Σ. |
17 | ″ | ″ | applications |
18 | ″ | ″ | bijection |
19 | ″ | ″ | computable bijection |
20 | ″ | ″ | degree n |
21 | ″ | ″ | efficient indexing |
22 | ″ | ″ | field |
23 | ″ | ″ | finite alphabet Σ. |
24 | ″ | ″ | finite field |
25 | ″ | ″ | first polynomial-time algorithm |
26 | ″ | ″ | indexing |
27 | ″ | ″ | irreducible polynomials |
28 | ″ | ″ | length n |
29 | ″ | ″ | main applications |
30 | ″ | ″ | necklace |
31 | ″ | ″ | open question |
32 | ″ | ″ | polynomial time algorithm |
33 | ″ | ″ | polynomials |
34 | ″ | ″ | problem |
35 | ″ | ″ | problem of indexing |
36 | ″ | ″ | pseudorandomness |
37 | ″ | ″ | questions |
38 | ″ | ″ | set |
39 | ″ | ″ | time |
40 | ″ | ″ | time algorithm |
41 | ″ | schema:name | Efficient Indexing of Necklaces and Irreducible Polynomials over Finite Fields |
42 | ″ | schema:pagination | 726-737 |
43 | ″ | schema:productId | N07377706ad3c4816b7bc2f56e137ccc0 |
44 | ″ | ″ | Na051707ece8f48b7a8969815765e21bb |
45 | ″ | schema:publisher | N18fac19fd79b4e3196502a94795aea11 |
46 | ″ | schema:sameAs | https://app.dimensions.ai/details/publication/pub.1001175768 |
47 | ″ | ″ | https://doi.org/10.1007/978-3-662-43948-7_60 |
48 | ″ | schema:sdDatePublished | 2022-08-04T17:19 |
49 | ″ | schema:sdLicense | https://scigraph.springernature.com/explorer/license/ |
50 | ″ | schema:sdPublisher | Nef2a7379610f409f8bff66c6f3da967a |
51 | ″ | schema:url | https://doi.org/10.1007/978-3-662-43948-7_60 |
52 | ″ | sgo:license | sg:explorer/license/ |
53 | ″ | sgo:sdDataset | chapters |
54 | ″ | rdf:type | schema:Chapter |
55 | N02b24469b89040f1b9310100ccc4528e | rdf:first | sg:person.014276170447.16 |
56 | ″ | rdf:rest | N7934021b8a8a47b090cd8331c3d9d934 |
57 | N0473b0ce13ab484487ddffd36dfdc662 | rdf:first | N8462181e87484ce49c13dcb78a960e17 |
58 | ″ | rdf:rest | Ne244a30370fb4b189559fd343d567a6e |
59 | N07377706ad3c4816b7bc2f56e137ccc0 | schema:name | dimensions_id |
60 | ″ | schema:value | pub.1001175768 |
61 | ″ | rdf:type | schema:PropertyValue |
62 | N18fac19fd79b4e3196502a94795aea11 | schema:name | Springer Nature |
63 | ″ | rdf:type | schema:Organisation |
64 | N229d35dd1be24181aa30a26b979d9f5f | schema:familyName | Esparza |
65 | ″ | schema:givenName | Javier |
66 | ″ | rdf:type | schema:Person |
67 | N686b382d8ad842cc9385062affbaac63 | schema:familyName | Koutsoupias |
68 | ″ | schema:givenName | Elias |
69 | ″ | rdf:type | schema:Person |
70 | N7934021b8a8a47b090cd8331c3d9d934 | rdf:first | sg:person.013641113207.82 |
71 | ″ | rdf:rest | Nbdc2854cc854465c8d5c0e6c174bbd57 |
72 | N7d8a6ff17fe64ecaa889e101c0410be1 | schema:isbn | 978-3-662-43947-0 |
73 | ″ | ″ | 978-3-662-43948-7 |
74 | ″ | schema:name | Automata, Languages, and Programming |
75 | ″ | rdf:type | schema:Book |
76 | N7e35f6f6271147439af7bf6cceff9158 | schema:familyName | Fraigniaud |
77 | ″ | schema:givenName | Pierre |
78 | ″ | rdf:type | schema:Person |
79 | N8462181e87484ce49c13dcb78a960e17 | schema:familyName | Husfeldt |
80 | ″ | schema:givenName | Thore |
81 | ″ | rdf:type | schema:Person |
82 | Na051707ece8f48b7a8969815765e21bb | schema:name | doi |
83 | ″ | schema:value | 10.1007/978-3-662-43948-7_60 |
84 | ″ | rdf:type | schema:PropertyValue |
85 | Nb311c1c59da94762b238307095a3b07e | rdf:first | N7e35f6f6271147439af7bf6cceff9158 |
86 | ″ | rdf:rest | N0473b0ce13ab484487ddffd36dfdc662 |
87 | Nbdc2854cc854465c8d5c0e6c174bbd57 | rdf:first | sg:person.011520224512.05 |
88 | ″ | rdf:rest | rdf:nil |
89 | Ne244a30370fb4b189559fd343d567a6e | rdf:first | N686b382d8ad842cc9385062affbaac63 |
90 | ″ | rdf:rest | rdf:nil |
91 | Ned80e21471924a108177d401f9ad56e5 | rdf:first | N229d35dd1be24181aa30a26b979d9f5f |
92 | ″ | rdf:rest | Nb311c1c59da94762b238307095a3b07e |
93 | Nef2a7379610f409f8bff66c6f3da967a | schema:name | Springer Nature - SN SciGraph project |
94 | ″ | rdf:type | schema:Organization |
95 | anzsrc-for:17 | schema:inDefinedTermSet | anzsrc-for: |
96 | ″ | schema:name | Psychology and Cognitive Sciences |
97 | ″ | rdf:type | schema:DefinedTerm |
98 | anzsrc-for:1701 | schema:inDefinedTermSet | anzsrc-for: |
99 | ″ | schema:name | Psychology |
100 | ″ | rdf:type | schema:DefinedTerm |
101 | sg:person.011520224512.05 | schema:affiliation | grid-institutes:grid.430387.b |
102 | ″ | schema:familyName | Saks |
103 | ″ | schema:givenName | Michael |
104 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011520224512.05 |
105 | ″ | rdf:type | schema:Person |
106 | sg:person.013641113207.82 | schema:affiliation | grid-institutes:grid.430387.b |
107 | ″ | schema:familyName | Kumar |
108 | ″ | schema:givenName | Mrinal |
109 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013641113207.82 |
110 | ″ | rdf:type | schema:Person |
111 | sg:person.014276170447.16 | schema:affiliation | grid-institutes:grid.430387.b |
112 | ″ | schema:familyName | Kopparty |
113 | ″ | schema:givenName | Swastik |
114 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014276170447.16 |
115 | ″ | rdf:type | schema:Person |
116 | grid-institutes:grid.430387.b | schema:alternateName | Department of Computer Science and Department of Mathematics, Rutgers University, USA |
117 | ″ | ″ | Department of Computer Science, Rutgers University, USA |
118 | ″ | ″ | Department of Mathematics, Rutgers University, USA |
119 | ″ | schema:name | Department of Computer Science and Department of Mathematics, Rutgers University, USA |
120 | ″ | ″ | Department of Computer Science, Rutgers University, USA |
121 | ″ | ″ | Department of Mathematics, Rutgers University, USA |
122 | ″ | rdf:type | schema:Organization |