37 citations · 87 across the 19 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
cs.CC2020★ 5 cited
On One-way Functions and Kolmogorov Complexity
Yanyi Liu, Rafael Pass
We prove that the equivalence of two fundamental problems in the theory of computing. For every polynomial , the following are equivalent:…
cs.CC2019
Is it Easier to Prove Theorems that are Guaranteed to be True?
Rafael Pass, Muthuramakrishnan Venkitasubramaniam
Consider the following two fundamental open problems in complexity theory: (a) Does a hard-on-average language in NP imply the existence of one-way functions?, or (b) Does a hard-o…
cs.CC2013
On the Power of Many One-Bit Provers
Per Austrin, Johan Håstad, Rafael Pass
We study the class of languages, denoted by $\MIP[k, 1-ε, s]$, which have -prover games where each prover just sends a \emph{single} bit, with completeness and soundness e…