Next

__
TR20-158
| 26th October 2020
__

Eric Allender, Azucena Garvia Bosshard, Amulya Musipatla#### A Note on Hardness under Projections for Graph Isomorphism and Time-Bounded Kolmogorov Complexity

__
TR20-157
| 21st October 2020
__

Guy Rothblum, Ron Rothblum#### Batch Verification and Proofs of Proximity with Polylog Overhead

__
TR20-156
| 22nd October 2020
__

Sankeerth Rao Karingula, Shachar Lovett#### Codes over integers, and the singularity of random matrices with large entries

Revisions: 1

Next

Eric Allender, Azucena Garvia Bosshard, Amulya Musipatla

This paper focuses on a variant of the circuit minimization problem (MCSP), denoted MKTP, which studies resource-bounded Kolmogorov complexity in place of circuit size. MCSP is not known to be hard for any complexity class under any kind of m-reducibility, but recently MKTP was shown to be hard for DET ... more >>>

Guy Rothblum, Ron Rothblum

Suppose Alice wants to convince Bob of the correctness of k NP statements. Alice could send k witnesses to Bob, but as k grows the communication becomes prohibitive. Is it possible to convince Bob using smaller communication (without making cryptographic assumptions or bounding the computational power of a malicious Alice)? ... more >>>

Sankeerth Rao Karingula, Shachar Lovett

The prototypical construction of error correcting codes is based on linear codes over finite fields. In this work, we make first steps in the study of codes defined over integers. We focus on Maximum Distance Separable (MDS) codes, and show that MDS codes with linear rate and distance can be ... more >>>

Next