Elad Tzalik

activity

20222026

collaborators

13 papers

quant-ph2026

Good Quantum Locally Testable Codes from Lossless Cubical Complexes

Itay Cohen, Itai Leigh, Assaf Reiner +2

Sipser and Spielman constructed LDPC codes from either bipartite \emph{spectral} expanders or one-sided \emph{lossless} expanders. In higher dimensions, \emph{spectral} expansion s…

math.CO2026

The Structure of Cycles in Projective Geometry over $F_{q}$

Ran J. Tessler, Elad Tzalik

A classical geometric result says that every nonzero cycle of the mod- $2$ incidence map from $d$ -subsets to $(d - 1)$ -subsets of $[n]$ has support at least $d + 1$ , with equality attai…

cs.DS2026

New Greedy Spanners and Applications

Elizaveta Popova, Elad Tzalik

We present a simple greedy procedure to compute an $(α, β)$ -spanner for a graph $G$ . We then show that this procedure is useful for building fault-tolerant spanners, as well as span…

cs.DS2026

Greedy Completion for Weighted $(α, β)$ -Spanners

Elad Tzalik

We study $(α, β)$ -spanners for weighted graphs. We propose a simple greedy completion procedure which starts from a sparse initial graph, and repeatedly fixes pairs of vertices with…

math.CO2025

Hypercube minor-universality

Itai Benjamini, Or Kalifa, Elad Tzalik

A graph $G$ is $m$ -minor-universal if every graph with at most $m$ edges (and no isolated vertices) is a minor of $G$ . We prove that the $d$ -dimensional hypercube, $Q_{d}$ , is $Ω\lef…

cs.DS2024

Connectivity Certificate against Bounded-Degree Faults: Simpler, Better and Supporting Vertex Faults

Merav Parter, Elad Tzalik

An $f$ -edge (or vertex) connectivity certificate is a sparse subgraph that maintains connectivity under the failure of at most $f$ edges (or vertices). It is well known that any $n…

cs.DS2024

Parks and Recreation: Color Fault-Tolerant Spanners Made Local

Merav Parter, Asaf Petruschka, Shay Sapir +1

We provide new algorithms for constructing spanners of arbitrarily edge- or vertex-colored graphs, that can endure up to $f$ failures of entire color classes. The failure of even a…

cs.DS2024

Connectivity Labeling in Faulty Colored Graphs

Asaf Petruschka, Shay Sapir, Elad Tzalik

Fault-tolerant connectivity labelings are schemes that, given an $n$ -vertex graph $G = (V, E)$ and $f \geq 1$ , produce succinct yet informative labels for the elements of the graph. Gi…

math.CO2023

On the Number of Shortest Paths in Graphs

Itai Benjamini, Elad Tzalik

It is proved that the number of shortest paths between two vertices of distance $t$ in a graph with degrees bounded by $Δ$ is at most $2 \cdot (\frac{Δ}{2})^{t}$ . This improves upon th…

cs.DS2023

Color Fault-Tolerant Spanners

Asaf Petruschka, Shay Sapir, Elad Tzalik

We initiate the study of spanners in arbitrarily vertex- or edge-colored graphs (with no "legality" restrictions), that are resilient to failures of entire color classes. When a co…

math.CO2023

Topological expansion for posets and the homological $k$ -connectivity of random $q$ -complexes

Ran Tessler, Elad Tzalik

We study high dimensional expansion beyond simplicial complexes (posets) and focus on $q$ -complexes which are complexes whose basic building blocks are linear spaces. We show that…

math.CO2023

The number of tiles of $Z^{d}$

Itai Benjamini, Gady Kozma, Elad Tzalik

It is proved that the number of subsets of $[n]^{d}$ that tile $Z^{d}$ is $(3^{\frac{1}{3}})^{n^{d} \pm o (n^{d})}$ .

math.MG2022

Determining a Points Configuration from a Subset of the Pairwise Distances

Itai Benjamini, Elad Tzalik

We study rigidity without assuming general position. Given $n$ distinct labelled points and a set $P \subseteq (2 [ n ])$ of revealed pairs, we ask when the correspon…

Good Quantum Locally Testable Codes from Lossless Cubical Complexes

The Structure of Cycles in Projective Geometry over Fq​

New Greedy Spanners and Applications

Greedy Completion for Weighted (α,β)-Spanners

Hypercube minor-universality

Connectivity Certificate against Bounded-Degree Faults: Simpler, Better and Supporting Vertex Faults

Parks and Recreation: Color Fault-Tolerant Spanners Made Local

Connectivity Labeling in Faulty Colored Graphs

On the Number of Shortest Paths in Graphs

Color Fault-Tolerant Spanners

Topological expansion for posets and the homological k-connectivity of random q-complexes

The number of tiles of Zd

Determining a Points Configuration from a Subset of the Pairwise Distances

The Structure of Cycles in Projective Geometry over $F_{q}$

Greedy Completion for Weighted $(α, β)$ -Spanners

Topological expansion for posets and the homological $k$ -connectivity of random $q$ -complexes

The number of tiles of $Z^{d}$