9 papers
The Monotone Priority System: Foundations of Contract-Specific Sequencing
Naveen Durvasula
Modern blockchain applications benefit from the ability to specify sequencing constraints on the transactions that interact with them. This paper proposes a principled and axiomati…
Resonance: Transaction Fees for Heterogeneous Computation
Maryam Bahrani, Naveen Durvasula
Blockchain networks are facing increasingly heterogeneous computational demands, and in response, protocol designers have started building specialized infrastructure to supply that…
Observing Context Improves Disparity Estimation when Race is Unobserved
Kweku Kwegyir-Aggrey, Naveen Durvasula, Jennifer Wang +1
In many domains, it is difficult to obtain the race data that is required to estimate racial disparity. To address this problem, practitioners have adopted the use of proxy methods…
Robust Restaking Networks
Naveen Durvasula, Tim Roughgarden
We study the risks of validator reuse across multiple services in a restaking protocol. We characterize the robust security of a restaking network as a function of the buffer betwe…
Stochastic Minimum Vertex Cover in General Graphs: a -Approximation
Mahsa Derakhshan, Naveen Durvasula, Nika Haghtalab
Our main result is designing an algorithm that returns a vertex cover of with size at most times the expected size of the minimum vertex cover, using…
Utility-Based Communication Requirements for Stable Matching in Large Markets
Naveen Durvasula
Results from the communication complexity literature have demonstrated that stable matching requires communication: one cannot find or verify a stable match without having access t…
Extending Universal Approximation Guarantees: A Theoretical Justification for the Continuity of Real-World Learning Tasks
Naveen Durvasula
Universal Approximation Theorems establish the density of various classes of neural network function approximators in , where is compac…
Recommending with Recommendations
Naveen Durvasula, Franklyn Wang, Scott Duke Kominers
Recommendation systems are a key modern application of machine learning, but they have the downside that they often draw upon sensitive user information in making their predictions…
The Muffin Problem
Guangiqi Cui, John Dickerson, Naveen Durvasula +6
You have muffins and students. You want to divide the muffins into pieces and give the shares to students such that every student has muffins. Find a divide-a…