Concepedia

Proof Complexity Connections

Proof Complexity Connections is a theoretical framework within computational complexity theory that distinguishes itself by establishing formal relationships between the lengths of propositional proofs and the sizes of Boolean circuits, thereby enabling mutual lower bound analyses in proof and circuit complexity.

15

Publications

1.5K

Citations

24

Authors

19

Institutions

Publications per year

2017–2026

2

Parents

Publications

15

Interactive proofs and the hardness of approximating cliques

Uriel Feige, Shafi Goldwasser, László Lovász et al. · Journal of the ACM · 1996 · 524 citations · Full text

, , +16

The Complexity of Propositional Proofs

Alasdair Urquhart · Bulletin of Symbolic Logic · 1995 · 225 citations

, , +16

The Complexity of Propositional Proofs

Nathan Segerlind · Bulletin of Symbolic Logic · 2007 · 182 citations

, , +16

On the weak pigeonhole principle

Jan Krajı́ček · Fundamenta Mathematicae · 2001 · 167 citations · Full text

, , +15

Sum-of-squares proofs and the quest toward optimal algorithms

Boaz Barak, David Steurer · arXiv (Cornell University) · 2014 · 96 citations · Full text

, , +12

1–5 of 15

Authors

24

  1. OB
    Olaf Beyersdorff

    University of Leeds, United Kingdom

    2 publications · 88 citations

    2

    h-index

  2. NS
    Nathan Segerlind

    University of California San Diego, United States

    2 publications · 214 citations

    2

    h-index

  3. TM
    Tsuyoshi Morioka

    University of Toronto, Canada

    2 publications · 31 citations

    2

    h-index

  4. LC
    Leroy Chew

    University of Leeds, United Kingdom

    2 publications · 88 citations

    2

    h-index

  5. JN
    Jakob Nordstr”öm

    KTH Royal Institute of Technology, Sweden

    2 publications · 81 citations

    2

    h-index

1–5 of 24

Institutions

19

  1. University of Toronto

    Toronto, Canada

    3 h-index

    4 publications

    285 citations

  2. KTH Royal Institute of Technology

    Stockholm, Sweden

    3 h-index

    3 publications

    135 citations

  3. University of Leeds

    Leeds, United Kingdom

    2 h-index

    3 publications

    142 citations

  4. AT&T (United States)

    Bedminster, United States

    1 h-index

    1 publications

    524 citations

  5. University of Washington

    Seattle, United States

    1 h-index

    1 publications

    32 citations

  6. TU Wien

    Vienna, Austria

    1 h-index

    2 publications

    80 citations

  7. University of California San Diego

    San Diego, United States

    1 h-index

    2 publications

    64 citations

  8. Portland State University

    Portland, United States

    1 h-index

    1 publications

    182 citations

1–8 of 19

Venues

  1. Bulletin of Symbolic Logic

    2 publications · 407 citations

    2

    h-index

  2. arXiv (Cornell University)

    Repository · 1 publications · 96 citations

    1

    h-index

  3. Fundamenta Mathematicae

    1 publications · 167 citations

    1

    h-index

  4. Theoretical Computer Science

    1 publications · 57 citations

    1

    h-index

  5. Journal of the ACM

    JACM · 1 publications · 524 citations

    1

    h-index

1–5