37 citations · 87 across the 19 of their papers we have counts for
24 papers
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:…
Limit theorems for excursion sets of subordinated Gaussian random fields with long-range dependence
Vitalii Makogin, Evgeny Spodarev
This paper considers the asymptotic behaviour of volumes of excursion sets of subordinated Gaussian random fields with (possibly) infinite variance. Actually, we consider integral…
A Conceptually Well-Founded Characterization of Iterated Admissibility Using an "All I Know" Operator
Joseph Y. Halpern, Rafael Pass
Brandenburger, Friedenberg, and Keisler provide an epistemic characterization of iterated admissibility (IA), also known as iterated deletion of weakly dominated strategies, where…
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…
Communication Complexity of Byzantine Agreement, Revisited
Ittai Abraham, T-H. Hubert Chan, Danny Dolev +4
As Byzantine Agreement (BA) protocols find application in large-scale decentralized cryptocurrencies, an increasingly important problem is to design BA protocols with improved comm…
Paradoxes in Fair Computer-Aided Decision Making
Andrew Morgan, Rafael Pass
Computer-aided decision making--where a human decision-maker is aided by a computational classifier in making a decision--is becoming increasingly prevalent. For instance, judges i…