Concepedia

Formula Complexity

Formula Complexity is a measure in circuit complexity that quantifies the minimum number of logical connectives required to express a Boolean function as a formula, distinguished from general circuit complexity by its restriction to tree-like structures without shared subformulas.

192

Publications

9.5K

Citations

313

Authors

186

Institutions

Publications per year

2017–2026

9

Parents

Publications

192

The complexity of satisfiability problems

Thomas J. Schaefer · 1978 · 1.8K citations · Full text

, , +12

∑11-Formulae on finite structures

Miklós Ajtai · Annals of Pure and Applied Logic · 1983 · 586 citations

, , +7

On the Decision Problem for Two-Variable First-Order Logic

Erich Grädel, Phokion G. Kolaitis, Moshe Y. Vardi · Bulletin of Symbolic Logic · 1997 · 324 citations

, , +12

Query evaluation via tree-decompositions

Jörg Flum, Markus Frick, Martin Grohe · Journal of the ACM · 2002 · 219 citations

, , +9

The complexity of first-order and monadic second-order logic revisited

Markus Frick, Martin Grohe · Annals of Pure and Applied Logic · 2004 · 209 citations

, , +12

1–5 of 192

Authors

313

  1. NH
    Nader H. Bshouty

    University of Calgary, Canada

    6 publications · 131 citations

    6

    h-index

  2. LH
    Lisa Hellerstein

    Northwestern University, United States

    5 publications · 295 citations

    5

    h-index

  3. PH
    Petr Hájek

    University of Pardubice, Czechia

    4 publications · 94 citations

    4

    h-index

  4. NI
    Neil Immerman

    University of Massachusetts Amherst, United States

    4 publications · 207 citations

    4

    h-index

  5. RC
    Richard Cleve

    University of Calgary, Canada

    3 publications · 58 citations

    3

    h-index

1–5 of 313

Institutions

186

  1. Czech Academy of Sciences

    Prague, Czechia

    10 h-index

    12 publications

    307 citations

  2. TU Wien

    Vienna, Austria

    8 h-index

    12 publications

    355 citations

  3. Harvard University Press

    Cambridge, United States

    6 h-index

    8 publications

    332 citations

  4. University of Toronto

    Toronto, Canada

    6 h-index

    7 publications

    226 citations

  5. Centre National de la Recherche Scientifique

    Paris, France

    6 h-index

    6 publications

    136 citations

  6. Université Paris Cité

    Paris, France

    5 h-index

    5 publications

    134 citations

  7. Technion – Israel Institute of Technology

    Haifa, Israel

    5 h-index

    6 publications

    262 citations

  8. Czech Academy of Sciences, Institute of Computer Science

    Prague, Czechia

    5 h-index

    5 publications

    157 citations

1–8 of 186

Venues

  1. SIAM Journal on Computing

    14 publications · 444 citations

    13

    h-index

  2. Journal of Computer and System Sciences

    5 publications · 414 citations

    5

    h-index

  3. Random Structures and Algorithms

    5 publications · 234 citations

    5

    h-index

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

    Repository · 5 publications · 71 citations

    5

    h-index

  5. Information Processing Letters

    5 publications · 215 citations

    5

    h-index

1–5