Search Results

Documents authored by Zamir, Or

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.104
Optimal Non-Adaptive Cell Probe Dictionaries and Hashing

Authors: Kasper Green Larsen, Rasmus Pagh, Giuseppe Persiano, Toniann Pitassi, Kevin Yeo, and Or Zamir

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
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 from [u]× [u] using s words of space and answering key lookup queries in t = O(lg(u/n)/lg(s/n)) non-adaptive probes. This generalizes a solution to the membership problem (i.e., where no values are associated with keys) due to Buhrman et al. We also present matching lower bounds for the non-adaptive static membership problem in the deterministic setting. Our lower bound implies that both our dictionary algorithm and the preceding membership algorithm are optimal, and in particular that there is an inherent complexity gap in these problems between no adaptivity and one round of adaptivity (with which hashing-based algorithms solve these problems in constant time). Using the ideas underlying our data structure, we also obtain the first implementation of a n-wise independent family of hash functions with optimal evaluation time in the cell probe model.
Cite as

Kasper Green Larsen, Rasmus Pagh, Giuseppe Persiano, Toniann Pitassi, Kevin Yeo, and Or Zamir. Optimal Non-Adaptive Cell Probe Dictionaries and Hashing. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 104:1-104:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{larsen_et_al:LIPIcs.ICALP.2024.104,
  author =	{Larsen, Kasper Green and Pagh, Rasmus and Persiano, Giuseppe and Pitassi, Toniann and Yeo, Kevin and Zamir, Or},
  title =	{{Optimal Non-Adaptive Cell Probe Dictionaries and Hashing}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{104:1--104:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.104},
  URN =		{urn:nbn:de:0030-drops-202471},
  doi =		{10.4230/LIPIcs.ICALP.2024.104},
  annote =	{Keywords: non-adaptive, cell probe, dictionary, hashing}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.107
The Wrong Direction of Jensen’s Inequality Is Algorithmically Right

Authors: Or Zamir

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
Let 𝒜 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 running time O (e^𝖤[X]), that fully executes 𝒜. In particular, an algorithm whose running time is a random variable T can be converted to one with expected running time O (e^𝖤[ln T]), which is never worse than O(𝖤[T]). No information about the distribution of X is required for the construction of 𝒜'.
Cite as

Or Zamir. The Wrong Direction of Jensen’s Inequality Is Algorithmically Right. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 107:1-107:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{zamir:LIPIcs.ICALP.2023.107,
  author =	{Zamir, Or},
  title =	{{The Wrong Direction of Jensen’s Inequality Is Algorithmically Right}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{107:1--107:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.107},
  URN =		{urn:nbn:de:0030-drops-181593},
  doi =		{10.4230/LIPIcs.ICALP.2023.107},
  annote =	{Keywords: algorithms, complexity, Jensen’s inequality}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.92
Faster Algorithm for Unique (k,2)-CSP

Authors: Or Zamir

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
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 variables such that all constraints are satisfied. The (k,2)-CSP problem generalizes problems like k-coloring and k-list-coloring. In the Unique (k,2)-CSP problem, we add the assumption that the input set of constraints has at most one satisfying assignment. Beigel and Eppstein gave an algorithm for (k,2)-CSP running in time O((0.4518k)^n) for k > 3 and O (1.356ⁿ) for k = 3, where n is the number of variables. Feder and Motwani improved upon the Beigel-Eppstein algorithm for k ≥ 11. Hertli, Hurbain, Millius, Moser, Scheder and Szedl{á}k improved these bounds for Unique (k,2)-CSP for every k ≥ 5. We improve the result of Hertli et al. and obtain better bounds for Unique (k,2)-CSP for k ≥ 5. In particular, we improve the running time of Unique (5,2)-CSP from O (2.254ⁿ) to O (2.232^n) and Unique (6,2)-CSP from O (2.652^n) to O (2.641^n). Recently, Li and Scheder also published an improvement over the algorithm of Hertli et al. in the same regime as ours. Their improvement does not include quantitative bounds, we compare the works in the paper.
Cite as

Or Zamir. Faster Algorithm for Unique (k,2)-CSP. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 92:1-92:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{zamir:LIPIcs.ESA.2022.92,
  author =	{Zamir, Or},
  title =	{{Faster Algorithm for Unique (k,2)-CSP}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{92:1--92:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.92},
  URN =		{urn:nbn:de:0030-drops-170309},
  doi =		{10.4230/LIPIcs.ESA.2022.92},
  annote =	{Keywords: Algorithms, Constraint Satisfaction Problem}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.113
Breaking the 2ⁿ Barrier for 5-Coloring and 6-Coloring

Authors: Or Zamir

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
The coloring problem (i.e., computing the chromatic number of a graph) can be solved in O^*(2ⁿ) time, as shown by Björklund, Husfeldt and Koivisto in 2009. For k = 3,4, better algorithms are known for the k-coloring problem. 3-coloring can be solved in O(1.33ⁿ) time (Beigel and Eppstein, 2005) and 4-coloring can be solved in O(1.73ⁿ) time (Fomin, Gaspers and Saurabh, 2007). Surprisingly, for k > 4 no improvements over the general O^*(2ⁿ) are known. We show that both 5-coloring and 6-coloring can also be solved in O((2-ε) ⁿ) time for some ε > 0. As a crucial step, we obtain an exponential improvement for computing the chromatic number of a very large family of graphs. In particular, for any constants Δ,α > 0, the chromatic number of graphs with at least α⋅ n vertices of degree at most Δ can be computed in O((2-ε) ⁿ) time, for some ε = ε_{Δ,α} > 0. This statement generalizes previous results for bounded-degree graphs (Björklund, Husfeldt, Kaski, and Koivisto, 2010) and graphs with bounded average degree (Golovnev, Kulikov and Mihajlin, 2016). We generalize the aforementioned statement to List Coloring, for which no previous improvements are known even for the case of bounded-degree graphs.
Cite as

Or Zamir. Breaking the 2ⁿ Barrier for 5-Coloring and 6-Coloring. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 113:1-113:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{zamir:LIPIcs.ICALP.2021.113,
  author =	{Zamir, Or},
  title =	{{Breaking the 2ⁿ Barrier for 5-Coloring and 6-Coloring}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{113:1--113:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.113},
  URN =		{urn:nbn:de:0030-drops-141825},
  doi =		{10.4230/LIPIcs.ICALP.2021.113},
  annote =	{Keywords: Algorithms, Graph Algorithms, Graph Coloring}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.95
Dynamic Ordered Sets with Approximate Queries, Approximate Heaps and Soft Heaps

Authors: Mikkel Thorup, Or Zamir, and Uri Zwick

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
We consider word RAM data structures for maintaining ordered sets of integers whose select and rank operations are allowed to return approximate results, i.e., ranks, or items whose rank, differ by less than Delta from the exact answer, where Delta=Delta(n) is an error parameter. Related to approximate select and rank is approximate (one-dimensional) nearest-neighbor. A special case of approximate select queries are approximate min queries. Data structures that support approximate min operations are known as approximate heaps (priority queues). Related to approximate heaps are soft heaps, which are approximate heaps with a different notion of approximation. We prove the optimality of all the data structures presented, either through matching cell-probe lower bounds, or through equivalences to well studied static problems. For approximate select, rank, and nearest-neighbor operations we get matching cell-probe lower bounds. We prove an equivalence between approximate min operations, i.e., approximate heaps, and the static partitioning problem. Finally, we prove an equivalence between soft heaps and the classical sorting problem, on a smaller number of items. Our results have many interesting and unexpected consequences. It turns out that approximation greatly speeds up some of these operations, while others are almost unaffected. In particular, while select and rank have identical operation times, both in comparison-based and word RAM implementations, an interesting separation emerges between the approximate versions of these operations in the word RAM model. Approximate select is much faster than approximate rank. It also turns out that approximate min is exponentially faster than the more general approximate select. Next, we show that implementing soft heaps is harder than implementing approximate heaps. The relation between them corresponds to the relation between sorting and partitioning. Finally, as an interesting byproduct, we observe that a combination of known techniques yields a deterministic word RAM algorithm for (exactly) sorting n items in O(n log log_w n) time, where w is the word length. Even for the easier problem of finding duplicates, the best previous deterministic bound was O(min{n log log n,n log_w n}). Our new unifying bound is an improvement when w is sufficiently large compared with n.
Cite as

Mikkel Thorup, Or Zamir, and Uri Zwick. Dynamic Ordered Sets with Approximate Queries, Approximate Heaps and Soft Heaps. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 95:1-95:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{thorup_et_al:LIPIcs.ICALP.2019.95,
  author =	{Thorup, Mikkel and Zamir, Or and Zwick, Uri},
  title =	{{Dynamic Ordered Sets with Approximate Queries, Approximate Heaps and Soft Heaps}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{95:1--95:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.95},
  URN =		{urn:nbn:de:0030-drops-106712},
  doi =		{10.4230/LIPIcs.ICALP.2019.95},
  annote =	{Keywords: Order queries, word RAM, lower bounds}
}
Document
DOI: 10.4230/OASIcs.SOSA.2019.5
Selection from Heaps, Row-Sorted Matrices, and X+Y Using Soft Heaps

Authors: Haim Kaplan, László Kozma, Or Zamir, and Uri Zwick

Published in: OASIcs, Volume 69, 2nd Symposium on Simplicity in Algorithms (SOSA 2019)

Abstract
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 sorted lists, and from X+Y, where X and Y are two unsorted sets. Our results match, and in some ways extend and improve, classical results of Frederickson (1993) and Frederickson and Johnson (1982). In particular, for selecting the k-th smallest item, or the set of k smallest items, from a collection of m sorted lists we obtain a new optimal "output-sensitive" algorithm that performs only O(m + sum_{i=1}^m log(k_i+1)) comparisons, where k_i is the number of items of the i-th list that belong to the overall set of k smallest items.
Cite as

Haim Kaplan, László Kozma, Or Zamir, and Uri Zwick. Selection from Heaps, Row-Sorted Matrices, and X+Y Using Soft Heaps. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Open Access Series in Informatics (OASIcs), Volume 69, pp. 5:1-5:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{kaplan_et_al:OASIcs.SOSA.2019.5,
  author =	{Kaplan, Haim and Kozma, L\'{a}szl\'{o} and Zamir, Or and Zwick, Uri},
  title =	{{Selection from Heaps, Row-Sorted Matrices, and X+Y Using Soft Heaps}},
  booktitle =	{2nd Symposium on Simplicity in Algorithms (SOSA 2019)},
  pages =	{5:1--5:21},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-099-6},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{69},
  editor =	{Fineman, Jeremy T. and Mitzenmacher, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2019.5},
  URN =		{urn:nbn:de:0030-drops-100315},
  doi =		{10.4230/OASIcs.SOSA.2019.5},
  annote =	{Keywords: selection, soft heap}
}
Document
DOI: 10.4230/LIPIcs.STACS.2016.27
Bottleneck Paths and Trees and Deterministic Graphical Games

Authors: Shiri Chechik, Haim Kaplan, Mikkel Thorup, Or Zamir, and Uri Zwick

Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)

Abstract
Gabow and Tarjan showed that the Bottleneck Path (BP) problem, i.e., finding a path between a given source and a given target in a weighted directed graph whose largest edge weight is minimized, as well as the Bottleneck spanning tree (BST) problem, i.e., finding a directed spanning tree rooted at a given vertex whose largest edge weight is minimized, can both be solved deterministically in O(m * log^*(n)) time, where m is the number of edges and n is the number of vertices in the graph. We present a slightly improved randomized algorithm for these problems with an expected running time of O(m * beta(m,n)), where beta(m,n) = min{k >= 1 | log^{(k)}n <= m/n } <= log^*(n) - log^*(m/n)+1. This is the first improvement for these problems in over 25 years. In particular, if m >= n * log^{(k)} * n, for some constant k, the expected running time of the new algorithm is O(m). Our algorithm, as that of Gabow and Tarjan, work in the comparison model. We also observe that in the word-RAM model, both problems can be solved deterministically in O(m) time. Finally, we solve an open problem of Andersson et al., giving a deterministic O(m)-time comparison-based algorithm for solving deterministic 2-player turn-based zero-sum terminal payoff games, also known as Deterministic Graphical Games (DGG).
Cite as

Shiri Chechik, Haim Kaplan, Mikkel Thorup, Or Zamir, and Uri Zwick. Bottleneck Paths and Trees and Deterministic Graphical Games. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 27:1-27:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{chechik_et_al:LIPIcs.STACS.2016.27,
  author =	{Chechik, Shiri and Kaplan, Haim and Thorup, Mikkel and Zamir, Or and Zwick, Uri},
  title =	{{Bottleneck Paths and Trees and Deterministic Graphical Games}},
  booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
  pages =	{27:1--27:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-001-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{47},
  editor =	{Ollinger, Nicolas and Vollmer, Heribert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.27},
  URN =		{urn:nbn:de:0030-drops-57283},
  doi =		{10.4230/LIPIcs.STACS.2016.27},
  annote =	{Keywords: bottleneck paths, comparison model, deterministic graphical games}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact