Concepedia

Boolean Formula Size

Boolean Formula Size is a complexity measure in computational theory that denotes the minimum number of logical connectives and variables required to express a given Boolean function as a formula, distinguishing it from other complexity measures by its focus on the syntactic size of formulaic representations rather than circuit depth, communication rounds, or decision tree complexity.

96

Publications

3.5K

Citations

158

Authors

89

Institutions

Publications per year

2017–2026

10

Parents

Publications

96

Negative weights make adversaries stronger

Troy Lee, Robert Špalek · 2007 · 222 citations · Full text

, , +16

On the OBDD-representation of general Boolean functions

Heh-Tyan Liaw, Chen-Shang Lin · IEEE Transactions on Computers · 1992 · 138 citations

, , +14

Any AND-OR Formula of Size N can be Evaluated in time N^{1/2 + o(1)} on a Quantum Computer

Andris Ambainis, Andrew M. Childs, Ben W. Reichardt et al. · 2007 · 133 citations · Full text

, , +14

Testing for Concise Representations

Ilias Diakonikolas, Homin K. Lee, Kevin Matulef et al. · 2007 · 106 citations

, , +13

A Boolean function requiring 3n network size

Norbert Blüm · Theoretical Computer Science · 1983 · 104 citations · Full text

, , +13

1–5 of 96

Authors

158

  1. RR
    Ran Raz

    Weizmann Institute of Science, Israel

    5 publications · 123 citations

    5

    h-index

  2. TP
    Toniann Pitassi

    University of Toronto, Canada

    4 publications · 190 citations

    4

    h-index

  3. IW
    Ingo Wegener

    TU Dortmund University, Germany

    4 publications · 114 citations

    4

    h-index

  4. AD
    Arnaud Durand

    Université Paris Cité, France

    4 publications · 136 citations

    4

    h-index

  5. RŠ
    Robert Špalek

    University of California, Berkeley, United States

    4 publications · 397 citations

    4

    h-index

1–5 of 158

Institutions

89

  1. Czech Academy of Sciences

    Prague, Czechia

    6 h-index

    6 publications

    205 citations

  2. University of Washington

    Seattle, United States

    5 h-index

    16 publications

    700 citations

  3. Rutgers, The State University of New Jersey

    New Brunswick, United States

    5 h-index

    6 publications

    193 citations

  4. Massachusetts Institute of Technology

    Cambridge, United States

    4 h-index

    7 publications

    273 citations

  5. Czech Academy of Sciences, Institute of Computer Science

    Prague, Czechia

    4 h-index

    4 publications

    117 citations

  6. TU Dortmund University

    Dortmund, Germany

    4 h-index

    5 publications

    162 citations

  7. Weizmann Institute of Science

    Rehovot, Israel

    4 h-index

    7 publications

    215 citations

  8. Centrum Wiskunde & Informatica

    Amsterdam, The Netherlands

    4 h-index

    4 publications

    148 citations

1–8 of 89

Venues

  1. SIAM Journal on Computing

    10 publications · 428 citations

    10

    h-index

  2. Random Structures and Algorithms

    5 publications · 186 citations

    5

    h-index

  3. Theoretical Computer Science

    4 publications · 242 citations

    4

    h-index

  4. arXiv (Cornell University)

    Repository · 4 publications · 64 citations

    4

    h-index

  5. Computational Complexity

    CC · 3 publications · 149 citations

    3

    h-index

1–5