Concepedia

Completeness-soundness Gap

The Completeness-Soundness Gap is the quantitative separation between the completeness and soundness thresholds in an interactive proof system, representing the minimum difference that ensures a verifier can reliably distinguish between valid proofs for true statements and any attempt to prove false statements.

4

Publications

73

Citations

6

Authors

2

Institutions

Publications per year

2017–2026

0

Parents

Publications

4

Robust self-testing of many-qubit states

Anand Natarajan, Thomas Vidick · arXiv (Cornell University) · 2016 · 23 citations · Full text

, , +17

Entanglement-Resistant Two-Prover Interactive Proof Systems and Non-Adaptive Private Information Retrieval Systems

Richard Cleve, Dmitry Gavinsky, Rahul Jain · ArXiv.org · 2007 · 22 citations · Full text

, , +14

Entanglement-resistant two-Prover interactive proof systems and non-adaptive PIRs

Richard Cleve, Dmitry Gavinsky, Rahul Jain · Quantum Information and Computation · 2009 · 15 citations

, , +9

Multi-Prover Quantum Merlin-Arthur Proof Systems with Small Gap

Attila Pereszlényi · arXiv (Cornell University) · 2012 · 13 citations · Full text

, , +13

1–4 of 4

Authors

6

  1. RC
    Richard Cleve

    University of Calgary, Canada

    2 publications · 37 citations

    2

    h-index

  2. DG
    Dmitry Gavinsky

    University of Calgary, Canada

    2 publications · 37 citations

    2

    h-index

  3. RJ
    Rahul Jain

    National University of Singapore, Singapore

    2 publications · 37 citations

    2

    h-index

  4. AN
    Anand Natarajan

    California Institute of Technology, United States

    1 publications · 23 citations

    1

    h-index

  5. TV
    Thomas Vidick

    California Institute of Technology, United States

    1 publications · 23 citations

    1

    h-index

1–5 of 6

Institutions

2

  1. University of Waterloo

    Waterloo, Canada

    2 h-index

    4 publications

    74 citations

  2. Quantum Technologies (Sweden)

    Uppsala, Sweden

    1 h-index

    1 publications

    15 citations

1–2 of 2

Venues

  1. arXiv (Cornell University)

    Repository · 2 publications · 36 citations

    2

    h-index

  2. Quantum Information and Computation

    QIC · 1 publications · 15 citations

    1

    h-index

  3. ArXiv.org

    Repository · 1 publications · 22 citations

    1

    h-index

1–3