research
∙
09/11/2023
Combinative Cumulative Knowledge Processes
We analyze Cumulative Knowledge Processes, introduced by Ben-Eliezer, Mi...
share
research
∙
08/29/2023
On k-Mer-Based and Maximum Likelihood Estimation Algorithms for Trace Reconstruction
The goal of the trace reconstruction problem is to recover a string x∈{0...
research
∙
05/08/2023
Low-Degree Testing Over Grids
We study the question of local testability of low (constant) degree func...
research
∙
11/08/2022
Streaming beyond sketching for Maximum Directed Cut
We give an O(√(n))-space single-pass 0.483-approximation streaming algor...
research
∙
07/14/2022
Streaming complexity of CSPs with randomly ordered constraints
We initiate a study of the streaming complexity of constraint satisfacti...
research
∙
05/05/2022
Streaming and Sketching Complexity of CSPs: A survey
In this survey we describe progress over the last decade or so in unders...
research
∙
05/04/2022
Sketching Approximability of (Weak) Monarchy Predicates
We analyze the sketching approximability of constraint satisfaction prob...
research
∙
07/13/2021
Information Spread with Error Correction
We study the process of information dispersal in a network with communic...
research
∙
06/24/2021
Linear Space Streaming Lower Bounds for Approximating CSPs
We consider the approximability of constraint satisfaction problems in t...
research
∙
05/04/2021
Streaming approximation resistance of every ordering CSP
An ordering constraint satisfaction problem (OCSP) is given by a positiv...
research
∙
05/03/2021
Approximability of all finite CSPs in the dynamic streaming setting
A constraint satisfaction problem (CSP), Max-CSP( F), is specified by a ...
research
∙
03/14/2021
Ideal-theoretic Explanation of Capacity-achieving Decoding
In this work, we present an abstract framework for some algebraic error-...
research
∙
02/24/2021
Approximability of all Boolean CSPs in the dynamic streaming setting
A Boolean constraint satisfaction problem (CSP), Max-CSP(f), is a maximi...
research
∙
01/23/2021
Point-hyperplane incidence geometry and the log-rank conjecture
We study the log-rank conjecture from the perspective of incidence geome...
research
∙
12/02/2020
Decoding Multivariate Multiplicity Codes on Product Sets
The multiplicity Schwartz-Zippel lemma bounds the total multiplicity of ...
research
∙
11/27/2020
Limitations of Mean-Based Algorithms for Trace Reconstruction at Small Distance
Trace reconstruction considers the task of recovering an unknown string ...
research
∙
10/02/2019
A Self-contained Analysis of the Lempel-Ziv Compression Algorithm
This article gives a self-contained analysis of the performance of the L...
research
∙
09/08/2019
Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time
We present the first algorithm for maintaining a maximal independent set...
research
∙
09/01/2019
Round Complexity of Common Randomness Generation: The Amortized Setting
We study the effect of rounds of interaction on the common randomness ge...
research
∙
04/21/2019
Communication for Generating Correlation: A Survey
The task of manipulating correlated random variables in a distributed se...
research
∙
10/09/2018
Polar Codes with exponentially small error at finite block length
We show that the entire class of polar codes (up to a natural necessary ...
research
∙
10/03/2018
Algorithmic Polarization for Hidden Markov Models
Using a mild variant of polar codes we design linear compression schemes...
research
∙
08/27/2018
Communication-Rounds Tradeoffs for Common Randomness and Secret Key Generation
We study the role of interaction in the Common Randomness Generation (CR...
research
∙
02/23/2018
Synchronization Strings: List Decoding for Insertions and Deletions
We study codes that are list-decodable under insertions and deletions. S...
research
∙
02/08/2018
General Strong Polarization
Arı kan's exciting discovery of polar codes has provided an altogether n...
research
∙
09/18/2017
Local decoding and testing of polynomials over grids
The well-known DeMillo-Lipton-Schwartz-Zippel lemma says that n-variate ...
research
∙
02/01/2014