research
∙
06/14/2023
Batches Stabilize the Minimum Norm Risk in High Dimensional Overparameterized Linear Regression
Learning algorithms that divide the data into batches are prevalent in m...
share
research
∙
02/07/2023
Planted Bipartite Graph Detection
We consider the task of detecting a hidden bipartite subgraph in a given...
research
∙
06/19/2022
On The Memory Complexity of Uniformity Testing
In this paper we consider the problem of uniformity testing with limited...
research
∙
06/19/2022
Deterministic Finite-Memory Bias Estimation
In this paper we consider the problem of estimating a Bernoulli paramete...
research
∙
02/03/2022
On the Number of Graphs with a Given Histogram
Let G be a large (simple, unlabeled) dense graph on n vertices. Suppose ...
research
∙
11/27/2021
On lossy Compression of Directed Graphs
The method of types presented by Csiszar and Korner is a central tool us...
research
∙
01/29/2021
Learning User Preferences in Non-Stationary Environments
Recommendation systems often use online collaborative filtering (CF) alg...
research
∙
08/04/2020
Simple Modulo can Significantly Outperform Deep Learning-based Deepcode
Deepcode (H.Kim et al.2018) is a recently suggested Deep Learning-based ...
research
∙
06/07/2020
Sharp Thresholds of the Information Cascade Fragility Under a Mismatched Model
We analyze a sequential decision making model in which decision makers (...
research
∙
05/15/2020
Binary Hypothesis Testing with Deterministic Finite-Memory Decision Rules
In this paper we consider the problem of binary hypothesis testing with ...
research
∙
12/31/2019
On the Interactive Capacity of Finite-State Protocols
The interactive capacity of a noisy channel is the highest possible rate...
research
∙
09/09/2019
On the Non-Adaptive Zero-Error Capacity of the Discrete Memoryless Two-Way Channel
We study the problem of communicating over a discrete memoryless two-way...
research
∙
09/03/2019
A Note on the Probability of Rectangles for Correlated Binary Strings
Consider two sequences of n independent and identically distributed fair...
research
∙
08/20/2019
A Lower Bound on the Interactive Capacity of Binary Memoryless Symmetric Channels
The interactive capacity of a channel is defined in this paper as the ma...
research
∙
06/17/2019
Distributed Source Simulation With No Communication
We consider the problem of distributed source simulation with no communi...
research
∙
01/25/2019
Communication Complexity of Estimating Correlations
We characterize the communication complexity of the following distribute...
research
∙
11/20/2018
Minimum Guesswork with an Unreliable Oracle
We study a guessing game where Alice holds a discrete random variable X,...
research
∙
05/31/2018
Distributed Estimation of Gaussian Correlations
We study a distributed estimation problem in which two remotely located ...
research
∙
05/23/2018
Guessing with a Bit of Help
What is the value of a single bit to a guesser? We study this problem in...
research
∙
04/16/2018
A Bound on the Shannon Capacity via a Linear Programming Variation
We prove an upper bound on the Shannon capacity of a graph via a linear ...
research
∙
01/12/2018
Self-Predicting Boolean Functions
A Boolean function g is said to be an optimal predictor for another Bool...
research
∙
12/30/2017