research
∙
04/03/2023
Fast Numerical Multivariate Multipoint Evaluation
We design nearly-linear time numerical algorithms for the problem of mul...
share
research
∙
12/16/2022
Criticality of AC^0 formulae
Rossman [In Proc. 34th Comput. Complexity Conf., 2019] introduced the no...
research
∙
09/21/2022
Downward Self-Reducibility in TFNP
A problem is downward self-reducible if it can be solved efficiently giv...
research
∙
05/22/2022
Vanishing Spaces of Random Sets and Applications to Reed-Muller Codes
We study the following natural question on random sets of points in 𝔽_2^...
research
∙
09/26/2021
Mixing of 3-term progressions in Quasirandom Groups
In this note, we show the mixing of three-term progressions (x, xg, xg^2...
research
∙
03/14/2021
Ideal-theoretic Explanation of Capacity-achieving Decoding
In this work, we present an abstract framework for some algebraic error-...
research
∙
12/02/2020
Decoding Multivariate Multiplicity Codes on Product Sets
The multiplicity Schwartz-Zippel lemma bounds the total multiplicity of ...
research
∙
09/11/2020
Explicit SoS lower bounds from high-dimensional expanders
We construct an explicit family of 3XOR instances which is hard for O(√(...
research
∙
08/11/2020
City-Scale Agent-Based Simulators for the Study of Non-Pharmaceutical Interventions in the Context of the COVID-19 Epidemic
We highlight the usefulness of city-scale agent-based simulators in stud...
research
∙
06/05/2020
COVID-19 Epidemic Study II: Phased Emergence From the Lockdown in Mumbai
The nation-wide lockdown starting 25 March 2020, aimed at suppressing th...
research
∙
05/06/2020
Rigid Matrices From Rectangular PCPs
We introduce a variant of PCPs, that we refer to as rectangular PCPs, wh...
research
∙
05/03/2020
Locally testable codes via high-dimensional expanders
Locally testable codes (LTC) are error-correcting codes that have a loca...
research
∙
02/19/2020
A note on the explicit constructions of tree codes over polylogarithmic-sized alphabet
Recently, Cohen, Haeupler and Schulman gave an explicit construction of ...
research
∙
12/24/2019
A note on the elementary HDX construction of Kaufman-Oppenheim
In this note, we give a self-contained and elementary proof of the eleme...
research
∙
12/05/2018
On the Probabilistic Degree of OR over the Reals
We study the probabilistic degree over reals of the OR function on n var...
research
∙
08/01/2018
List Decoding with Double Samplers
We develop the notion of "double samplers", first introduced by Dinur an...
research
∙
04/24/2018
On Multilinear Forms: Bias, Correlation, and Tensor Rank
In this paper, we prove new relations between the bias of multilinear fo...
research
∙
04/22/2018
Boolean functions on high-dimensional expanders
We initiate the study of Boolean function analysis on high-dimensional e...
research
∙
11/26/2017
Low degree almost Boolean functions are sparse juntas
Nisan and Szegedy showed that low degree Boolean functions are juntas. K...
research
∙
11/26/2017
Agreement tests on graphs and hypergraphs
Agreement tests are a generalization of low degree tests that capture a ...
research
∙
06/13/2012