Concepedia

Proof Veritability

Proof Veritability is a formal criterion within proof complexity that characterizes the efficiency and reliability with which a proposed proof can be verified by a computational process, distinguishing it from other proof-related properties by its focus on the intrinsic verifiability of proof steps under bounded resources.

28

Publications

2.9K

Citations

54

Authors

45

Institutions

Publications per year

2017–2026

5

Parents

Publications

28

Probabilistic checking of proofs

Sanjeev Arora · Journal of the ACM · 1998 · 1.2K citations · Full text

, , +14

Computationally Sound Proofs

Silvio Micali · SIAM Journal on Computing · 2000 · 412 citations

, , +13

Probabilistic checking of proofs; a new characterization of NP

Sanjeev Arora · 1992 · 278 citations

, , +16

Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding

Eli Ben‐Sasson, Oded Goldreich, Prahladh Harsha et al. · SIAM Journal on Computing · 2006 · 240 citations · Full text

, , +15

On the complexity of interactive proofs with bounded communication

Oded Goldreich, Johan Håstad · Information Processing Letters · 1998 · 84 citations

, , +12

1–5 of 28

Authors

54

  1. MS
    Madhu Sudan

    Massachusetts Institute of Technology, United States

    4 publications · 378 citations

    4

    h-index

  2. JH
    Johan Håstad

    KTH Royal Institute of Technology, Sweden

    3 publications · 172 citations

    3

    h-index

  3. ML
    Marı́a Luisa Bonet

    Universitat Politècnica de Catalunya, Spain

    2 publications · 88 citations

    2

    h-index

  4. AM
    Alexis Maciel

    Clarkson University, United States

    2 publications · 88 citations

    2

    h-index

  5. EB
    Eli Ben‐Sasson

    Technion – Israel Institute of Technology, Israel

    2 publications · 299 citations

    2

    h-index

1–5 of 54

Institutions

45

  1. Massachusetts Institute of Technology

    Cambridge, United States

    4 h-index

    5 publications

    978 citations

  2. Tel Aviv University

    Tel Aviv, Israel

    3 h-index

    4 publications

    147 citations

  3. Weizmann Institute of Science

    Rehovot, Israel

    3 h-index

    3 publications

    363 citations

  4. Princeton University

    Princeton, United States

    2 h-index

    2 publications

    1.2K citations

  5. University of Maryland, College Park

    College Park, United States

    2 h-index

    4 publications

    134 citations

  6. Tokyo Institute of Technology

    Tokyo, Japan

    2 h-index

    2 publications

    88 citations

  7. KTH Royal Institute of Technology

    Stockholm, Sweden

    2 h-index

    2 publications

    120 citations

  8. University of Toronto

    Toronto, Canada

    2 h-index

    2 publications

    88 citations

1–8 of 45

Venues

  1. SIAM Journal on Computing

    3 publications · 704 citations

    3

    h-index

  2. Journal of Automated Reasoning

    1 publications · 21 citations

    1

    h-index

  3. Synthese

    1 publications · 11 citations

    1

    h-index

  4. Mathematical Notes

    1 publications · 27 citations

    1

    h-index

  5. 1

    h-index

1–5