Efficient Indexing of Necklaces and Irreducible Polynomials over Finite Fields View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2014

AUTHORS

Swastik Kopparty , Mrinal Kumar , Michael Saks

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

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: 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", 
    "inLanguage": "en", 
    "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", 
      "main applications", 
      "polynomials", 
      "problem", 
      "computable bijection", 
      "length n", 
      "open question", 
      "problem of indexing", 
      "bijection", 
      "field", 
      "pseudorandomness", 
      "Alon", 
      "Goldreich", 
      "indexing", 
      "necklace", 
      "algorithm", 
      "set", 
      "alphabet \u03a3.", 
      "applications", 
      "H\u00e5stad", 
      "efficient indexing", 
      "finite alphabet \u03a3.", 
      "Peralta", 
      "time", 
      "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-06-01T22:34", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220601/entities/gbq_results/chapter/chapter_4.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

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.

123 TRIPLES      23 PREDICATES      56 URIs      49 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 N3c1bd9ef9dc54f9a8f9cc64d3955cc3b
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 N8c82fb89ce0b418db67a0cfc54b11c2f
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N47bcb3685de845109834e1097c798ac7
12 schema:keywords Alon
13 Goldreich
14 Håstad
15 Peralta
16 algorithm
17 alphabet Σ.
18 applications
19 bijection
20 computable bijection
21 degree n
22 efficient indexing
23 field
24 finite alphabet Σ.
25 finite field
26 first polynomial-time algorithm
27 indexing
28 irreducible polynomials
29 length n
30 main applications
31 necklace
32 open question
33 polynomial time algorithm
34 polynomials
35 problem
36 problem of indexing
37 pseudorandomness
38 questions
39 set
40 time
41 time algorithm
42 schema:name Efficient Indexing of Necklaces and Irreducible Polynomials over Finite Fields
43 schema:pagination 726-737
44 schema:productId N9cd1c5968007455999abc44561874d0a
45 Nfd9b0170a54b46fa8d5a4e50deac9b0e
46 schema:publisher N64746d4669b647859ce2afbcfbf6a447
47 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001175768
48 https://doi.org/10.1007/978-3-662-43948-7_60
49 schema:sdDatePublished 2022-06-01T22:34
50 schema:sdLicense https://scigraph.springernature.com/explorer/license/
51 schema:sdPublisher Na40880ad996242498cfe800e0d178ffc
52 schema:url https://doi.org/10.1007/978-3-662-43948-7_60
53 sgo:license sg:explorer/license/
54 sgo:sdDataset chapters
55 rdf:type schema:Chapter
56 N019359c7aca94c91acad473d1f5dc01e schema:familyName Husfeldt
57 schema:givenName Thore
58 rdf:type schema:Person
59 N1d559d57e212459faffc408d482a2377 rdf:first sg:person.011520224512.05
60 rdf:rest rdf:nil
61 N287af86a120b42ffa4fc86c8154c13c7 schema:familyName Esparza
62 schema:givenName Javier
63 rdf:type schema:Person
64 N3c1bd9ef9dc54f9a8f9cc64d3955cc3b rdf:first sg:person.014276170447.16
65 rdf:rest N4476f6d18a3143a6b261b808fd68e629
66 N4476f6d18a3143a6b261b808fd68e629 rdf:first sg:person.013641113207.82
67 rdf:rest N1d559d57e212459faffc408d482a2377
68 N47bcb3685de845109834e1097c798ac7 schema:isbn 978-3-662-43947-0
69 978-3-662-43948-7
70 schema:name Automata, Languages, and Programming
71 rdf:type schema:Book
72 N64746d4669b647859ce2afbcfbf6a447 schema:name Springer Nature
73 rdf:type schema:Organisation
74 N8c82fb89ce0b418db67a0cfc54b11c2f rdf:first N287af86a120b42ffa4fc86c8154c13c7
75 rdf:rest Nedaf8d23a0e94629a57bd7c7f94184e4
76 N8df3f33003cc4748a1f59576f87923bc schema:familyName Koutsoupias
77 schema:givenName Elias
78 rdf:type schema:Person
79 N9cd1c5968007455999abc44561874d0a schema:name doi
80 schema:value 10.1007/978-3-662-43948-7_60
81 rdf:type schema:PropertyValue
82 Na40880ad996242498cfe800e0d178ffc schema:name Springer Nature - SN SciGraph project
83 rdf:type schema:Organization
84 Nb71e015dd38443af9edbd1167cab24ea schema:familyName Fraigniaud
85 schema:givenName Pierre
86 rdf:type schema:Person
87 Nd1fdd9b2b5c14491bdfe0495bac6f963 rdf:first N8df3f33003cc4748a1f59576f87923bc
88 rdf:rest rdf:nil
89 Nedaf8d23a0e94629a57bd7c7f94184e4 rdf:first Nb71e015dd38443af9edbd1167cab24ea
90 rdf:rest Nf0dcea2457554c5aadc77ab92b53f41b
91 Nf0dcea2457554c5aadc77ab92b53f41b rdf:first N019359c7aca94c91acad473d1f5dc01e
92 rdf:rest Nd1fdd9b2b5c14491bdfe0495bac6f963
93 Nfd9b0170a54b46fa8d5a4e50deac9b0e schema:name dimensions_id
94 schema:value pub.1001175768
95 rdf:type schema:PropertyValue
96 anzsrc-for:17 schema:inDefinedTermSet anzsrc-for:
97 schema:name Psychology and Cognitive Sciences
98 rdf:type schema:DefinedTerm
99 anzsrc-for:1701 schema:inDefinedTermSet anzsrc-for:
100 schema:name Psychology
101 rdf:type schema:DefinedTerm
102 sg:person.011520224512.05 schema:affiliation grid-institutes:grid.430387.b
103 schema:familyName Saks
104 schema:givenName Michael
105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011520224512.05
106 rdf:type schema:Person
107 sg:person.013641113207.82 schema:affiliation grid-institutes:grid.430387.b
108 schema:familyName Kumar
109 schema:givenName Mrinal
110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013641113207.82
111 rdf:type schema:Person
112 sg:person.014276170447.16 schema:affiliation grid-institutes:grid.430387.b
113 schema:familyName Kopparty
114 schema:givenName Swastik
115 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014276170447.16
116 rdf:type schema:Person
117 grid-institutes:grid.430387.b schema:alternateName Department of Computer Science and Department of Mathematics, Rutgers University, USA
118 Department of Computer Science, Rutgers University, USA
119 Department of Mathematics, Rutgers University, USA
120 schema:name Department of Computer Science and Department of Mathematics, Rutgers University, USA
121 Department of Computer Science, Rutgers University, USA
122 Department of Mathematics, Rutgers University, USA
123 rdf:type schema:Organization
 




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


...