Exponential lower bounds for depth three Boolean circuits View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2000-11

AUTHORS

R. Paturi, M. E. Saks, F. Zane

ABSTRACT

. We consider the class \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $ \sum^{k}_{3} $\end{document} of unbounded fan-in depth three Boolean circuits, for which the bottom fan-in is limited by k and the top gate is an OR. It is known that the smallest such circuit computing the parity function has \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $ \Omega(2^{\varepsilon n/k}) $\end{document} gates (for k = O(n1/2)) for some \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $ \varepsilon > 0 $\end{document}, and this was the best lower bound known for explicit (P-time computable) functions. In this paper, for k = 2, we exhibit functions in uniform NC1 that require \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $ 2^{n-o(n)} $\end{document} size depth 3 circuits. The main tool is a theorem that shows that any \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $ \sum {2\over3} $\end{document} circuit on n variables that accepts a inputs and has size s must be constant on a projection (subset defined by equations of the form xi = 0, xi = 1, xi = xj or xi = \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $ \bar{x}_i $\end{document}) of dimension at least log(a/s)log n. More... »

PAGES

1-15

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/pl00001598

DOI

http://dx.doi.org/10.1007/pl00001598

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "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/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1702", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Cognitive Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Engineering, University of California, San Diego, La Jolla, CA 92093, USA, e-mail: paturi@cs.ucsd.edu, US", 
          "id": "http://www.grid.ac/institutes/grid.266100.3", 
          "name": [
            "Department of Computer Science and Engineering, University of California, San Diego, La Jolla, CA 92093, USA, e-mail: paturi@cs.ucsd.edu, US"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Paturi", 
        "givenName": "R.", 
        "id": "sg:person.016410340505.67", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016410340505.67"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Mathematics, Rutgers University, New Brunswick, NJ 08903, USA, e-mail: saks@math.rutgers.edu, US", 
          "id": "http://www.grid.ac/institutes/grid.430387.b", 
          "name": [
            "Department of Mathematics, Rutgers University, New Brunswick, NJ 08903, USA, e-mail: saks@math.rutgers.edu, US"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Saks", 
        "givenName": "M. E.", 
        "id": "sg:person.011520224512.05", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011520224512.05"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Engineering, University of California, San Diego, La Jolla, CA 92093, USA, e-mail: francis@cs.ucsd.edu, US", 
          "id": "http://www.grid.ac/institutes/grid.266100.3", 
          "name": [
            "Department of Computer Science and Engineering, University of California, San Diego, La Jolla, CA 92093, USA, e-mail: francis@cs.ucsd.edu, US"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Zane", 
        "givenName": "F.", 
        "id": "sg:person.013422436505.15", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013422436505.15"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2000-11", 
    "datePublishedReg": "2000-11-01", 
    "description": "Abstract. We consider the class \\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}\n$ \\sum^{k}_{3} $\\end{document} of unbounded fan-in depth three Boolean circuits, for which the bottom fan-in is limited by k and the top gate is an OR. It is known that the smallest such circuit computing the parity function has \\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}\n$ \\Omega(2^{\\varepsilon n/k}) $\\end{document} gates (for k = O(n1/2)) for some \\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}\n$ \\varepsilon > 0 $\\end{document}, and this was the best lower bound known for explicit (P-time computable) functions. In this paper, for k = 2, we exhibit functions in uniform NC1 that require \\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}\n$ 2^{n-o(n)} $\\end{document} size depth 3 circuits. The main tool is a theorem that shows that any \\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}\n$ \\sum {2\\over3} $\\end{document} circuit on n variables that accepts a inputs and has size s must be constant on a projection (subset defined by equations of the form xi = 0, xi = 1, xi = xj or xi = \\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}\n$ \\bar{x}_i $\\end{document}) of dimension at least log(a/s)log n.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/pl00001598", 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1136224", 
        "issn": [
          "1016-3328", 
          "1420-8954"
        ], 
        "name": "computational complexity", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "9"
      }
    ], 
    "keywords": [
      "ORs", 
      "function", 
      "NC1", 
      "variables", 
      "projections", 
      "class", 
      "circuit", 
      "tool", 
      "such circuits", 
      "main tool", 
      "input", 
      "dimensions", 
      "fans", 
      "Boolean circuits", 
      "top gate", 
      "gate", 
      "parity function", 
      "paper", 
      "depth-3 circuits", 
      "size s", 
      "lower bounds", 
      "unbounded fan", 
      "explicit function", 
      "theorem", 
      "n variables", 
      "exponential lower bounds", 
      "bounds"
    ], 
    "name": "Exponential lower bounds for depth three Boolean circuits", 
    "pagination": "1-15", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1015369369"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/pl00001598"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/pl00001598", 
      "https://app.dimensions.ai/details/publication/pub.1015369369"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-10-01T06:31", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221001/entities/gbq_results/article/article_332.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/pl00001598"
  }
]
 

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/pl00001598'

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/pl00001598'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/pl00001598'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/pl00001598'


 

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

115 TRIPLES      20 PREDICATES      55 URIs      44 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/pl00001598 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 anzsrc-for:0802
4 anzsrc-for:17
5 anzsrc-for:1702
6 schema:author N523f43b913a54086a3e9873ca579f11b
7 schema:datePublished 2000-11
8 schema:datePublishedReg 2000-11-01
9 schema:description Abstract. We consider the class \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $ \sum^{k}_{3} $\end{document} of unbounded fan-in depth three Boolean circuits, for which the bottom fan-in is limited by k and the top gate is an OR. It is known that the smallest such circuit computing the parity function has \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $ \Omega(2^{\varepsilon n/k}) $\end{document} gates (for k = O(n1/2)) for some \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $ \varepsilon > 0 $\end{document}, and this was the best lower bound known for explicit (P-time computable) functions. In this paper, for k = 2, we exhibit functions in uniform NC1 that require \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $ 2^{n-o(n)} $\end{document} size depth 3 circuits. The main tool is a theorem that shows that any \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $ \sum {2\over3} $\end{document} circuit on n variables that accepts a inputs and has size s must be constant on a projection (subset defined by equations of the form xi = 0, xi = 1, xi = xj or xi = \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $ \bar{x}_i $\end{document}) of dimension at least log(a/s)log n.
10 schema:genre article
11 schema:isAccessibleForFree false
12 schema:isPartOf N24c50f2fbb0143729a7d5be5bf28dfbf
13 N2f7b09bf33424210b5fbeaea9d52a3fb
14 sg:journal.1136224
15 schema:keywords Boolean circuits
16 NC1
17 ORs
18 bounds
19 circuit
20 class
21 depth-3 circuits
22 dimensions
23 explicit function
24 exponential lower bounds
25 fans
26 function
27 gate
28 input
29 lower bounds
30 main tool
31 n variables
32 paper
33 parity function
34 projections
35 size s
36 such circuits
37 theorem
38 tool
39 top gate
40 unbounded fan
41 variables
42 schema:name Exponential lower bounds for depth three Boolean circuits
43 schema:pagination 1-15
44 schema:productId N5ba1e29159a443f98c33d073f64d3fde
45 N89e743aef5dc4ff8ad60047941c546a5
46 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015369369
47 https://doi.org/10.1007/pl00001598
48 schema:sdDatePublished 2022-10-01T06:31
49 schema:sdLicense https://scigraph.springernature.com/explorer/license/
50 schema:sdPublisher Nb4eef0e052e14b7390c72907e84dd217
51 schema:url https://doi.org/10.1007/pl00001598
52 sgo:license sg:explorer/license/
53 sgo:sdDataset articles
54 rdf:type schema:ScholarlyArticle
55 N24c50f2fbb0143729a7d5be5bf28dfbf schema:volumeNumber 9
56 rdf:type schema:PublicationVolume
57 N2f7b09bf33424210b5fbeaea9d52a3fb schema:issueNumber 1
58 rdf:type schema:PublicationIssue
59 N523f43b913a54086a3e9873ca579f11b rdf:first sg:person.016410340505.67
60 rdf:rest N5aa577e8b6424164a699105f987e0344
61 N5aa577e8b6424164a699105f987e0344 rdf:first sg:person.011520224512.05
62 rdf:rest Nc8c6ee3474ba44288036c41d261b9668
63 N5ba1e29159a443f98c33d073f64d3fde schema:name doi
64 schema:value 10.1007/pl00001598
65 rdf:type schema:PropertyValue
66 N89e743aef5dc4ff8ad60047941c546a5 schema:name dimensions_id
67 schema:value pub.1015369369
68 rdf:type schema:PropertyValue
69 Nb4eef0e052e14b7390c72907e84dd217 schema:name Springer Nature - SN SciGraph project
70 rdf:type schema:Organization
71 Nc8c6ee3474ba44288036c41d261b9668 rdf:first sg:person.013422436505.15
72 rdf:rest rdf:nil
73 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
74 schema:name Information and Computing Sciences
75 rdf:type schema:DefinedTerm
76 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
77 schema:name Artificial Intelligence and Image Processing
78 rdf:type schema:DefinedTerm
79 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
80 schema:name Computation Theory and Mathematics
81 rdf:type schema:DefinedTerm
82 anzsrc-for:17 schema:inDefinedTermSet anzsrc-for:
83 schema:name Psychology and Cognitive Sciences
84 rdf:type schema:DefinedTerm
85 anzsrc-for:1702 schema:inDefinedTermSet anzsrc-for:
86 schema:name Cognitive Sciences
87 rdf:type schema:DefinedTerm
88 sg:journal.1136224 schema:issn 1016-3328
89 1420-8954
90 schema:name computational complexity
91 schema:publisher Springer Nature
92 rdf:type schema:Periodical
93 sg:person.011520224512.05 schema:affiliation grid-institutes:grid.430387.b
94 schema:familyName Saks
95 schema:givenName M. E.
96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011520224512.05
97 rdf:type schema:Person
98 sg:person.013422436505.15 schema:affiliation grid-institutes:grid.266100.3
99 schema:familyName Zane
100 schema:givenName F.
101 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013422436505.15
102 rdf:type schema:Person
103 sg:person.016410340505.67 schema:affiliation grid-institutes:grid.266100.3
104 schema:familyName Paturi
105 schema:givenName R.
106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016410340505.67
107 rdf:type schema:Person
108 grid-institutes:grid.266100.3 schema:alternateName Department of Computer Science and Engineering, University of California, San Diego, La Jolla, CA 92093, USA, e-mail: francis@cs.ucsd.edu, US
109 Department of Computer Science and Engineering, University of California, San Diego, La Jolla, CA 92093, USA, e-mail: paturi@cs.ucsd.edu, US
110 schema:name Department of Computer Science and Engineering, University of California, San Diego, La Jolla, CA 92093, USA, e-mail: francis@cs.ucsd.edu, US
111 Department of Computer Science and Engineering, University of California, San Diego, La Jolla, CA 92093, USA, e-mail: paturi@cs.ucsd.edu, US
112 rdf:type schema:Organization
113 grid-institutes:grid.430387.b schema:alternateName Department of Mathematics, Rutgers University, New Brunswick, NJ 08903, USA, e-mail: saks@math.rutgers.edu, US
114 schema:name Department of Mathematics, Rutgers University, New Brunswick, NJ 08903, USA, e-mail: saks@math.rutgers.edu, US
115 rdf:type schema:Organization
 




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


...