Next

__
TR20-007
| 19th December 2019
__

Claude CrÃ©peau, Arnaud Massenet, Louis Salvail, Lucas Stinchcombe, Nan Yang#### Practical Relativistic Zero-Knowledge for NP

__
TR20-006
| 22nd January 2020
__

Anup Rao, Amir Yehudayoff#### The Communication Complexity of the Exact Gap-Hamming Problem

__
TR20-005
| 17th January 2020
__

Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan#### Hardness Characterisations and Size-Width Lower Bounds for QBF Resolution

Next

Claude CrÃ©peau, Arnaud Massenet, Louis Salvail, Lucas Stinchcombe, Nan Yang

In this work we consider the following problem: in a Multi-Prover environment, how close can we get to prove the validity of an NP statement in Zero-Knowledge ? We exhibit a set of two novel Zero-Knowledge protocols for the 3-COLorability problem that use two (local) provers or three (entangled) provers ... more >>>

Anup Rao, Amir Yehudayoff

We prove a sharp lower bound on the distributional communication complexity of the exact gap-hamming problem.

more >>>Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan

We provide a tight characterisation of proof size in resolution for quantified Boolean formulas (QBF) by circuit complexity. Such a characterisation was previously obtained for a hierarchy of QBF Frege systems (Beyersdorff & Pich, LICS 2016), but leaving open the most important case of QBF resolution. Different from the Frege ... more >>>

Next