Concepedia

Space Complexity Of Boolean Formulas

Space Complexity of Boolean Formulas is a theoretical measure in computational complexity theory that quantifies the minimum amount of memory space required by a computational model to evaluate a given Boolean formula, distinguishing it from other complexity measures by focusing specifically on the spatial resources needed for formula evaluation.

41

Publications

1.3K

Citations

69

Authors

48

Institutions

Publications per year

2017–2026

2

Parents

Publications

41

Partitioned ROBDDs—a compact, canonical and efficiently manipulable representation for Boolean functions

Amit Narayan, Jawahar Jain, Masahiro Fujita et al. · International Conference on Computer Aided Design · 1996 · 96 citations

, , +16

Learning Boolean Functions in an Infinite Attribute Space

Avrim Blum · Machine Learning · 1992 · 86 citations · Full text

, , +7

CREW PRAMS and decision trees

Noam Nisan · 1989 · 83 citations · Full text

, , +17

A faster PSPACE algorithm for deciding the existential theory of the reals

James Renegar · 1988 · 77 citations

, , +15

Partitioned ROBDDs-a compact, canonical and efficiently manipulable representation for Boolean functions

A. Narayan, J. Jain, Masahiro Fujita et al. · 2002 · 63 citations

, , +16

1–5 of 41

Authors

69

  1. AB
    Avrim Blum

    Carnegie Mellon University, United States

    3 publications · 155 citations

    3

    h-index

  2. NT
    Neil Thapen

    Czech Academy of Sciences, Czechia

    3 publications · 69 citations

    3

    h-index

  3. EB
    Eli Ben‐Sasson

    Technion – Israel Institute of Technology, Israel

    2 publications · 75 citations

    2

    h-index

  4. MF
    Masahiro Fujita

    The University of Tokyo, Japan

    2 publications · 159 citations

    2

    h-index

  5. IB
    Ilario Bonacina

    KTH Royal Institute of Technology, Sweden

    2 publications · 24 citations

    2

    h-index

1–5 of 69

Institutions

48

  1. University of Toronto

    Toronto, Canada

    3 h-index

    3 publications

    75 citations

  2. Czech Academy of Sciences

    Prague, Czechia

    3 h-index

    3 publications

    69 citations

  3. Carnegie Mellon University

    Pittsburgh, United States

    3 h-index

    3 publications

    142 citations

  4. University of Waterloo

    Waterloo, Canada

    3 h-index

    5 publications

    91 citations

  5. Centre National de la Recherche Scientifique

    Paris, France

    3 h-index

    5 publications

    92 citations

  6. KTH Royal Institute of Technology

    Stockholm, Sweden

    3 h-index

    3 publications

    67 citations

  7. University of Leeds

    Leeds, United Kingdom

    3 h-index

    5 publications

    110 citations

  8. University of Washington

    Seattle, United States

    2 h-index

    4 publications

    121 citations

1–8 of 48

Venues

  1. SIAM Journal on Computing

    4 publications · 106 citations

    4

    h-index

  2. DROPS (Schloss Dagstuhl – Leibniz Center for Informatics)

    Repository · 2 publications · 26 citations

    2

    h-index

  3. Machine Learning

    2 publications · 116 citations

    2

    h-index

  4. Acta Informatica

    2 publications · 24 citations

    2

    h-index

  5. IEEE Transactions on Computers

    2 publications · 26 citations

    2

    h-index

1–5