Or Zamir

activity

20152026

most citedMotion Planning for Unlabeled Discs with Optimality Guarantees

23 citations · 53 across the 26 of their papers we have counts for

collaborators

30 papers

cs.DS2026

Parity and Pattern Detection in Permutation Streams

Mark Braverman, Or Zamir

Consider a permutation of $[n]$ 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…

cs.DS2026

Linear Hashing is Not That Awesome

Or Zamir

Consider the canonical universal hash family $h (x) = ((a x + b) mod p) mod m$ , where $a, b$ are chosen uniformly from $Z_{p}$ , which we call linear hashing, being…

cs.DS2026

Enumerating Small Cycles

Or Stern, Or Zamir

In a seminal result of Yuster and Zwick, they showed that for any fixed $k$ , the even cycle $C_{2 k}$ can be detected in an $n$ -vertex graph in time $O (n^{2})$ . For $4$ -cycles, a folk…

cs.DS2026

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…

cs.DS2026

k-Coloring is Faster than Computing the Chromatic Number

Or Zamir

We prove that $k$ -coloring on $n$ -vertex graphs has a randomized algorithm running in time $(2 - ε_{k})^{n}$ , where $ε_{k} > 0$ for every fixed $k$ . Previously, only the…

cs.LG2026

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…

cs.CR2026

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…

cs.CR2026

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…

cs.AI2025

Consensus Sampling for Safer Generative AI

Adam Tauman Kalai, Yael Tauman Kalai, Or Zamir

Motivated by undetectable risks in generative AI, we study a general robust aggregation problem: how to aggregate several probability distributions to boost safety. We present cons…

cs.DS2025

Tight Bounds for Low-Error Frequency Moment Estimation and the Power of Multiple Passes

Naomi Green-Maimon, Or Zamir

Estimating the second frequency moment $F_{2}$ of a data stream up to a $(1 \pm ε)$ factor is a central problem in the streaming literature. For errors $\varepsilon > Ω(1/\…

cs.CR2025★ 2 cited

Improving Algorithmic Efficiency using Cryptography

Vinod Vaikuntanathan, Or Zamir

Cryptographic primitives have been used for various non-cryptographic objectives, such as eliminating or reducing randomness and interaction. We show how to use cryptography to imp…

cs.DS2024

Unbounded Error Correcting Codes

Klim Efremenko, Or Zamir

Traditional error-correcting codes (ECCs) assume a fixed message length, but many scenarios involve ongoing or indefinite transmissions where the message length is not known in adv…

cs.DS2024

Optimality of Frequency Moment Estimation

Mark Braverman, Or Zamir

Estimating the second frequency moment of a stream up to $(1 \pm ε)$ multiplicative error requires at most $O (lo g n / ε^{2})$ bits of space, due to a seminal resul…

math.CO2024

Sumsets in the Hypercube

Noga Alon, Or Zamir

A subset $S$ of the Boolean hypercube $F_{2}^{n}$ is a sumset if $S = A + A = {a + b ∣ a, b \in A}$ for some $A \subseteq F_{2}^{n}$ . We prove that the number of sumse…

cs.DS2024

Testing Sumsets is Hard

Xi Chen, Shivam Nadimpalli, Tim Randolph +2

A subset $S$ of the Boolean hypercube $F_{2}^{n}$ is a sumset if $S = {a + b : a, b \in A}$ for some $A \subseteq F_{2}^{n}$ . Sumsets are central objects of study in add…

cs.CR2024

Excuse me, sir? Your language model is leaking (information)

Or Zamir

We introduce a cryptographic method to hide an arbitrary secret payload in the response of a Large Language Model (LLM). A secret key is required to extract the payload from the mo…

math.CO2023★ 3 cited

Essentially tight bounds for rainbow cycles in proper edge-colourings

Noga Alon, Matija Bucić, Lisa Sauermann +2

An edge-coloured graph is said to be rainbow if no colour appears more than once. Extremal problems involving rainbow objects have been a focus of much research over the last decad…

cs.DS2023

Optimal Non-Adaptive Cell Probe Dictionaries and Hashing

Kasper Green Larsen, Rasmus Pagh, Giuseppe Persiano +3

We present a simple and provably optimal non-adaptive cell probe data structure for the static dictionary problem. Our data structure supports storing a set of n key-value pairs fr…

cs.CR2023★ 12 cited

Undetectable Watermarks for Language Models

Miranda Christ, Sam Gunn, Or Zamir

Recent advances in the capabilities of large language models such as GPT-4 have spurred increasing concern about our ability to detect AI-generated text. Prior works have suggested…

cs.DS2022

Algorithmic Applications of Hypergraph and Partition Containers

Or Zamir

We present a general method to convert algorithms into faster algorithms for almost-regular input instances. Informally, an almost-regular input is an input in which the maximum de…

cs.CC2022

The wrong direction of Jensen's inequality is algorithmically right

Or Zamir

Let $A$ be an algorithm with expected running time $e^{X}$ , conditioned on the value of some random variable $X$ . We construct an algorithm $A^{'}$ with expected run…

cs.DS2022

Hardness of Approximation in P via Short Cycle Removal: Cycle Detection, Distance Oracles, and Beyond

Amir Abboud, Karl Bringmann, Seri Khoury +1

We present a new technique for efficiently removing almost all short cycles in a graph without unintentionally removing its triangles. Consequently, triangle finding problems do no…

cs.LG2022★ 13 cited

Planting Undetectable Backdoors in Machine Learning Models

Shafi Goldwasser, Michael P. Kim, Vinod Vaikuntanathan +1

Given the computational cost and technical expertise required to train machine learning models, users may delegate the task of learning to a service provider. We show how a malicio…

cs.DS2021

Faster algorithm for Unique $(k, 2)$ -CSP

Or Zamir

In a $(k, 2)$ -Constraint Satisfaction Problem we are given a set of arbitrary constraints on pairs of $k$ -ary variables, and are asked to find an assignment of values to these varia…

Parity and Pattern Detection in Permutation Streams

Linear Hashing is Not That Awesome

Enumerating Small Cycles

Locality in Open Addressing Hash Tables

k-Coloring is Faster than Computing the Chromatic Number

Proofs of Ownership for Machine Learning Models

Undetectable Conversations Between AI Agents via Pseudorandom Noise-Resilient Key Exchange

A Note on Non-Composability of Layerwise Approximate Verification for Neural Inference

Consensus Sampling for Safer Generative AI

Tight Bounds for Low-Error Frequency Moment Estimation and the Power of Multiple Passes

Improving Algorithmic Efficiency using Cryptography

Unbounded Error Correcting Codes

Optimality of Frequency Moment Estimation

Sumsets in the Hypercube

Testing Sumsets is Hard

Excuse me, sir? Your language model is leaking (information)

Essentially tight bounds for rainbow cycles in proper edge-colourings

Optimal Non-Adaptive Cell Probe Dictionaries and Hashing

Undetectable Watermarks for Language Models

Algorithmic Applications of Hypergraph and Partition Containers

The wrong direction of Jensen's inequality is algorithmically right

Hardness of Approximation in P via Short Cycle Removal: Cycle Detection, Distance Oracles, and Beyond

Planting Undetectable Backdoors in Machine Learning Models

Faster algorithm for Unique (k,2)-CSP

Faster algorithm for Unique $(k, 2)$ -CSP