Rafael Pass
YOU?
Author Swipe
View article: Causality Without Causal Models
Causality Without Causal Models Open
Perhaps the most prominent current definition of (actual) causality is due to Halpern and Pearl. It is defined using causal models (also known as structural equations models). We abstract the definition, extracting its key features, so tha…
View article: Fair Interest Rates Are Impossible for Lending Pools: Results from Options Pricing
Fair Interest Rates Are Impossible for Lending Pools: Results from Options Pricing Open
Cryptocurrency lending pools are services that allow lenders to pool together assets in one cryptocurrency and loan it out to borrowers who provide collateral worth more (than the loan) in a separate cryptocurrency. Borrowers can repay the…
View article: On One-Way Functions from NP-Complete Problems
On One-Way Functions from NP-Complete Problems Open
We present the first natural NP-complete problem whose average-case hardness w.r.t. the uniform distribution over instances is equivalent to the existence of one-way functions (OWFs). The problem, which originated in the 1960s, is the Cond…
View article: I'm Doing as Well as I Can: Modeling People as Rational Finite Automata
I'm Doing as Well as I Can: Modeling People as Rational Finite Automata Open
We show that by modeling people as bounded finite automata, we can capture at a qualitative level the behavior observed in experiments. We consider a decision problem with incomplete information and a dynamically changing world, which can …
View article: Is it Easier to Prove Theorems that are Guaranteed to be True?
Is it Easier to Prove Theorems that are Guaranteed to be True? Open
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-on-average language in NP imply a hard-on-average problem in…
View article: On One-way Functions and Kolmogorov Complexity
On One-way Functions and Kolmogorov Complexity Open
We prove that the equivalence of two fundamental problems in the theory of computing. For every polynomial $t(n)\geq (1+\varepsilon)n, \varepsilon>0$, the following are equivalent: - One-way functions exists (which in turn is equivalent to…
View article: Bucket Oblivious Sort: An Extremely Simple Oblivious Sort
Bucket Oblivious Sort: An Extremely Simple Oblivious Sort Open
We propose a conceptually simple oblivious sort and oblivious random permutation algorithms called bucket oblivious sort and bucket oblivious random permutation. Bucket oblivious sort uses $6n\log n$ time (measured by the number of memory …
View article: Bucket Oblivious Sort: An Extremely Simple Oblivious Sort
Bucket Oblivious Sort: An Extremely Simple Oblivious Sort Open
We propose a conceptually simple oblivious sort and oblivious random permutation algorithms called bucket oblivious sort and bucket oblivious random permutation. Bucket oblivious sort uses 6n log n time (measured by the number of memory ac…
View article: A Conceptually Well-Founded Characterization of Iterated Admissibility Using an "All I Know" Operator
A Conceptually Well-Founded Characterization of Iterated Admissibility Using an "All I Know" Operator Open
Brandenburger, Friedenberg, and Keisler provide an epistemic characterization of iterated admissibility (IA), also known as iterated deletion of weakly dominated strategies, where uncertainty is represented using LPSs (lexicographic probab…
View article: A Round-Collapse Theorem for Computationally-Sound Protocols; or, TFNP is Hard (on Average) in Pessiland
A Round-Collapse Theorem for Computationally-Sound Protocols; or, TFNP is Hard (on Average) in Pessiland Open
Consider the following two fundamental open problems in complexity theory: 1) Does a hard-on-average language in NP imply the existence of one-way functions? 2) Does a hard-on-average language in NP imply a hard problem in TFNP (i.e., the …
View article: Sequential Equilibrium in Computational Games
Sequential Equilibrium in Computational Games Open
We examine sequential equilibrium in the context of computational games (Halpern and Pass 2015), where agents are charged for computation. In such games, an agent can rationally choose to forget, so issues of imperfect recall arise. In thi…
View article: Blind Certificate Authorities
Blind Certificate Authorities Open
We explore how to build a blind certificate authority (CA). Unlike conventional CAs, which learn the exact identity of those registering a public key, a blind CA can simultaneously validate an identity and provide a certificate binding a p…
View article: Paradoxes in Fair Computer-Aided Decision Making
Paradoxes in Fair Computer-Aided Decision Making Open
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 in at least nine states make use of algorithmic tools meant …
View article: Communication Complexity of Byzantine Agreement, Revisited
Communication Complexity of Byzantine Agreement, Revisited Open
As Byzantine Agreement (BA) protocols find application in large-scale decentralized cryptocurrencies, an increasingly important problem is to design BA protocols with improved communication complexity. A few existing works have shown how t…
View article: A Knowledge-Based Analysis of the Blockchain Protocol
A Knowledge-Based Analysis of the Blockchain Protocol Open
At the heart of the Bitcoin is a blockchain protocol, a protocol for achieving consensus on a public ledger that records bitcoin transactions. To the extent that a blockchain protocol is used for applications such as contract signing and m…
View article: A Knowledge-Based Analysis of the Blockchain Protocol
A Knowledge-Based Analysis of the Blockchain Protocol Open
At the heart of the Bitcoin is a blockchain protocol, a protocol for achieving consensus on a public ledger that records bitcoin transactions. To the extent that a blockchain protocol is used for applications such as contract signing and m…
View article: Socially Optimal Mining Pools
Socially Optimal Mining Pools Open
Mining for Bitcoins is a high-risk high-reward activity. Miners, seeking to reduce their variance and earn steadier rewards, collaborate in pooling strategies where they jointly mine for Bitcoins. Whenever some pool participant is successf…
View article: Hybrid Consensus: Efficient Consensus in the Permissionless Model
Hybrid Consensus: Efficient Consensus in the Permissionless Model Open
Consensus, or state machine replication is a foundational building block of distributed systems and modern cryptography. Consensus in the classical, "permissioned" setting has been extensively studied in the 30 years of distributed systems…
View article: Computational Extensive-Form Games
Computational Extensive-Form Games Open
We define solution concepts appropriate for computationally bounded players playing a fixed finite game. To do so, we need to define what it means for a computational game, which is a sequence of games that get larger in some appropriate s…
View article: Bayesian Games with Intentions
Bayesian Games with Intentions Open
We show that standard Bayesian games cannot represent the full spectrum of belief-dependent preferences. However, by introducing a fundamental distinction between intended and actual strategies, we remove this limitation. We define Bayesia…