Ittai Rubinstein
Email: ittai.rubinstein@gmail.com
Hi!
My name is Ittai Rubinstein, and I am a second-year PhD student at MIT, where I am fortunate to be advised by Sam Hopkins and Constantinos Daskalakis.
I am interested in anything related to algorithms!
Currently, my main focus is on data attribution and robust machine learning.
Before coming to MIT, I worked in Qedma, where I led a wonderful research team working on quantum error mitigation. Before joining Qedma, I earned my master's degree in computer science from Tel Aviv University, where I was advised by Muli Safra. Prior to that, I completed my undergraduate studies in mathematics, physics, and computer science at the Technion.
My favorite projects are the ones where we get to go all the way from a difficult mathematical question, through interesting algorithm design, to practical optimizations and adapting to real-world data.
Throughout my first year at MIT, I got to work on a really cool project of this format with Sam Hopkins.
TLDR:
Economists use linear regressions to quantify the correlation between a label and a specific feature controlled for some other features (e.g., to find the correlation between cash stimulus and spending habits controlled for head of household sex/age [1]).
Many papers of this format are brittle, meaning that removing a small number of samples, often fewer than 0.5%, is enough to flip the sign of the regression [2].
We provide the first algorithm that produces non-trivial robustness guarantees on regressions of dimension ≥ 4 in practice, and ran it on several econometrics datasets with tens of thousands of samples and hundreds of dimensions.
Read the full paper on arXiv
Near the end of my master's degree, I worked on another very interesting project with Roni Con.
TLDR:
Asynchronous channels are channels where the channel noise can change the lengths of parts of the input string (e.g., some of the input bits may be deleted or duplicated), causing many of the conventional tools of information and coding theory to break down, thereby introducing additional complexity and challenges.
Perhaps the most studied type of synchronization channel is the binary deletion channel where each bit of the input is deleted i.i.d. with some fixed probability d. A recent series of works by Con and Shpilka, Tal et al., Pernice et al., and myself ([1], [2], [3], [4]) shows that we can construct efficiently decodable, capacity-achieving error-correcting codes for this channel. This motivates the question of estimating the capacities of such channels.
The best previously known upper bounds on the capacity of this channel were generated by Rahmati and Duman [5], who used the results of running the Blahut-Arimoto Algorithm (BAA - an algorithm for estimating the capacity of synchronous channels) on a series of auxiliary channels with exponentially large alphabets. Running the BAA on these channels is computationally difficult, but we designed a more efficient version of this algorithm (and do a lot of low-level optimization), allowing us to compute better upper bounds on the capacity of the deletion channel.
For the lower bounds, we built on the work of Mitzenmacher and Drinea [6], who show how to convert certain candidate distributions into lower bounds on the capacity of the deletion channel. We adapted the BAA to design better candidate distributions for this construction, resulting in improved lower bounds on the capacity of the binary deletion channel.
Read the full paper on arXiv
Robustness Auditing for Linear Regression: To Singularity and Beyond
Ittai Rubinstein, Sam Hopkins
To appear in ICLR 2025
[arxiv] | [github]
The Quasi-Probability Method and Applications for Trace Reconstruction
Ittai Rubinstein
SOSA 2025
[arxiv]
Improved Upper and Lower Bounds on the Capacity of the Binary Deletion Channel
Ittai Rubinstein, Roni Con
ISIT 2023
[arxiv]
Average-Case to (shifted) Worst-Case Reduction for the Trace Reconstruction Problem
Ittai Rubinstein
ICALP 2023
[arxiv]
Explicit and Efficient Construction of (nearly) Optimal Rate Codes for the Binary Deletion Channel and the Poisson Repeat Channel
Ittai Rubinstein
ICALP 2022
[arxiv]
Multivariate Generating Functions for Information Spread on Multi-Type Random Graphs
Yaron Oz, Ittai Rubinstein, Muli Safra
Journal of Statistical Mechanics 2022
[arxiv]
Heterogeneity and Superspreading Effect on Herd Immunity
Yaron Oz, Ittai Rubinstein, Muli Safra
Journal of Statistical Mechanics 2021
[arxiv]
Superspreaders and High Variance Infectious Diseases
Yaron Oz, Ittai Rubinstein, Muli Safra
Journal of Statistical Mechanics 2021
[arxiv]
Deep Learning Reconstruction of Ultrashort Pulses from 2D Spatial Intensity Patterns Recorded by an All-in-Line System in a Single-Shot
Ron Ziv, Alex Dikopoltsev, Tom Zahavy, Ittai Rubinstein, Pavel Sidorenko, Oren Cohen, Mordechai Segev
Optics Express 2020
[arxiv]