# Efficient Indexing of Necklaces and Irreducible Polynomials over Finite Fields

Ontology type: schema:Chapter      Open Access: True

### Chapter Info

DATE

2014

AUTHORS ABSTRACT

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]. More... »

PAGES

726-737

### Book

TITLE

Automata, Languages, and Programming

ISBN

978-3-662-43947-0
978-3-662-43948-7

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-662-43948-7_60

DOI

http://dx.doi.org/10.1007/978-3-662-43948-7_60

DIMENSIONS

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

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/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",
"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",
"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"
}
]

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/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].
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf N7d8a6ff17fe64ecaa889e101c0410be1
11 schema:keywords Alon
12 Goldreich
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
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
50 schema:sdPublisher Nef2a7379610f409f8bff66c6f3da967a
51 schema:url https://doi.org/10.1007/978-3-662-43948-7_60
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

Preview window. Press ESC to close (or click here)

...