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

Showing cs.DSShow all

16 papers · 1 filter

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.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.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…

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.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.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.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.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…

cs.DS2021

Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering

Shyam Narayanan, Sandeep Silwal, Piotr Indyk +1

Random dimensionality reduction is a versatile tool for speeding up algorithms for high-dimensional problems. We study its application to two clustering problems: the facility loca…

cs.DS2020

Breaking the $2^{n}$ barrier for 5-coloring and 6-coloring

Or Zamir

The coloring problem (i.e., computing the chromatic number of a graph) can be solved in $O^{*} (2^{n})$ time, as shown by Björklund, Husfeldt and Koivisto in 2009. For $k = 3, 4$ , better a…

cs.DS2018

Selection from heaps, row-sorted matrices and $X + Y$ using soft heaps

Haim Kaplan, László Kozma, Or Zamir +1

We use soft heaps to obtain simpler optimal algorithms for selecting the $k$ -th smallest item, and the set of~ $k$ smallest items, from a heap-ordered tree, from a collection of sor…

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

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

Unbounded Error Correcting Codes

Optimality of Frequency Moment Estimation

Testing Sumsets is Hard

Optimal Non-Adaptive Cell Probe Dictionaries and Hashing

Algorithmic Applications of Hypergraph and Partition Containers

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

Faster algorithm for Unique (k,2)-CSP

Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering

Breaking the 2n barrier for 5-coloring and 6-coloring

Selection from heaps, row-sorted matrices and X+Y using soft heaps

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

Breaking the $2^{n}$ barrier for 5-coloring and 6-coloring

Selection from heaps, row-sorted matrices and $X + Y$ using soft heaps