Name
Abstract | ||
|---|---|---|
We present three protocols for verifying all languages: (i) For any unary (binary) language, there is a log-space (linear-space) interactive proof system (IPS); (ii) for any language, there is a constant-space weak-IPS (the non-members may not be rejected with high probability); and, (iii) for any language, there is a constant-space IPS with two provers where the verifier reads the input once. Additionally, we show that uncountably many binary (unary) languages can be verified in constant space and in linear (quadratic) expected time. |
Year | Venue | Field |
|---|---|---|
2018 | arXiv: Computational Complexity | Discrete mathematics,Unary operation,Interactive proof system,Quadratic equation,Probabilistic logic,Mathematics,Binary number |
DocType | Volume | Citations |
Journal | abs/1807.04735 | 0 |
PageRank | References | Authors |
0.34 | 5 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Maksims Dimitrijevs | 1 | 3 | 3.14 |
| Abuzer Yakaryilmaz | 2 | 168 | 25.31 |