23 citations · 53 across the 26 of their papers we have counts for
8 papers · 1 filter
Parity and Pattern Detection in Permutation Streams
Mark Braverman, Or Zamir
Consider a permutation of whose values arrive one at a time. We resolve two questions about the space needed to decide natural properties of such input: First, computing the…
Linear Hashing is Not That Awesome
Or Zamir
Consider the canonical universal hash family , where are chosen uniformly from , which we call linear hashing, being…
Enumerating Small Cycles
Or Stern, Or Zamir
In a seminal result of Yuster and Zwick, they showed that for any fixed , the even cycle can be detected in an -vertex graph in time . For -cycles, a folk…
Locality in Open Addressing Hash Tables
Or Zamir
Open-addressed hash tables without reordering, such as linear probing and uniform probing, are among the simplest and most widely used data structures. Their performance is traditi…
k-Coloring is Faster than Computing the Chromatic Number
Or Zamir
We prove that -coloring on -vertex graphs has a randomized algorithm running in time , where for every fixed . Previously, only the…
Proofs of Ownership for Machine Learning Models
Ran Canetti, Shafi Goldwasser, Or Zamir
With the increasing adoption of Machine Learning, protecting model ownership has become an essential challenge. We initiate a formal study of Proof of Ownership for machine learnin…
Undetectable Conversations Between AI Agents via Pseudorandom Noise-Resilient Key Exchange
Vinod Vaikuntanathan, Or Zamir
AI agents are increasingly deployed to interact with other agents on behalf of users and organizations. We ask whether two such agents, operated by different entities, can carry ou…
A Note on Non-Composability of Layerwise Approximate Verification for Neural Inference
Or Zamir
A natural and informal approach to verifiable (or zero-knowledge) ML inference over floating-point data is: ``prove that each layer was computed correctly up to tolerance ; ther…