Source author record

Ittai Rubinstein

Ittai Rubinstein appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Information Theory math.IT cond-mat.stat-mech Data Structures and Algorithms Machine Learning math.PR physics.optics physics.soc-ph Populations and Evolution

Catalog footprint

What is connected

4works

9topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2022arXiv

Average-Case to (shifted) Worst-Case Reduction for the Trace Reconstruction Problem

The {\em insertion-deletion channel} takes as input a binary string $x \in\{0, 1\}^n$, and outputs a string $\widetilde{x}$ where some of the bits have been deleted and others inserted independently at random. In the {\em trace reconstruction problem}, one is given many outputs (called {\em traces}) of the insertion-deletion channel on the same input message $x$, and asked to recover the input message. Nazarov and Peres (STOC 2017), and De, O'Donnell and Servedio (STOC 2017) showed that any string $x$ can be reconstructed from $\exp(O(n^{1/3}))$ traces. Holden, Pemantle, Peres and Zhai (COLT 2018) adapt the techniques used to prove this upper bound, to an algorithm for the average-case trace reconstruction with a sample complexity of $\exp(O(\log^{1/3} n))$. However, it is not clear how to apply their techniques more generally and in particular for the recent worst-case upper bound of $\exp(\widetilde{O}(n^{1/5}))$ shown by Chase (STOC 2021) for the deletion-channel. We prove a general reduction from the average-case to smaller instances of a problem similar to worst-case. Using this reduction and a generalization of Chase's bound, we construct an improved average-case algorithm with a sample complexity of $\exp(\widetilde{O}(\log^{1/5} n))$. Additionally, we show that Chase's upper-bound holds for the insertion-deletion channel as well.

preprint2022arXiv

Explicit and Efficient Construction of (nearly) Optimal Rate Codes for Binary Deletion Channel and the Poisson Repeat Channel

Two of the most common models for channels with synchronisation errors are the Binary Deletion Channel with parameter $p$ ($\text{BDC}_p$) -- a channel where every bit of the codeword is deleted i.i.d with probability $p$, and the Poisson Repeat Channel with parameter $λ$ ($\text{PRC}_λ$) -- a channel where every bit of the codeword is repeated $\text{Poisson}(λ)$ times. Previous constructions based on synchronisation strings yielded codes with rates far lower than the capacities of these channels [CS19, GL18], and the only efficient construction to achieve capacity on the BDC at the time of writing this paper is based on the far more advanced methods of polar codes [TPFV21]. In this work, we present a new method for concatenating synchronisation codes and use it to construct simple and efficient encoding and decoding algorithms for both channels with nearly optimal rates.

preprint2021arXiv

Heterogeneity and Superspreading Effect on Herd Immunity

We model and calculate the fraction of infected population necessary to reach herd immunity, taking into account the heterogeneity in infectiousness and susceptibility, as well as the correlation between those two parameters. We show that these cause the effective reproduction number to decrease more rapidly, and consequently have a drastic effect on the estimate of the necessary percentage of the population that has to contract the disease for herd immunity to be reached. We quantify the difference between the size of the infected population when the effective reproduction number decreases below 1 vs. the ultimate fraction of population that had contracted the disease. This sheds light on an important distinction between herd immunity and the end of the disease and highlights the importance of limiting the spread of the disease even if we plan to naturally reach herd immunity. We analyze the effect of various lock-down scenarios on the resulting final fraction of infected population. We discuss implications to COVID-19 and other pandemics and compare our theoretical results to population-based simulations. We consider the dependence of the disease spread on the architecture of the infectiousness graph and analyze different graph architectures and the limitations of the graph models.

preprint2019arXiv

Deep learning reconstruction of ultrashort pulses from 2D spatial intensity patterns recorded by an all-in-line system in a single-shot

We propose a simple all-in-line single-shot scheme for diagnostics of ultrashort laser pulses, consisting of a multi-mode fiber, a nonlinear crystal and a CCD camera. The system records a 2D spatial intensity pattern, from which the pulse shape (amplitude and phase) are recovered, through a fast Deep Learning algorithm. We explore this scheme in simulations and demonstrate the recovery of ultrashort pulses, robustness to noise in measurements and to inaccuracies in the parameters of the system components. Our technique mitigates the need for commonly used iterative optimization reconstruction methods, which are usually slow and hampered by the presence of noise. These features make our concept system advantageous for real time probing of ultrafast processes and noisy conditions. Moreover, this work exemplifies that using deep learning we can unlock new types of systems for pulse recovery.