research
∙
09/18/2023
Deterministic Algorithms for Low Degree Factors of Constant Depth Circuits
For every constant d, we design a subexponential time deterministic algo...
share
research
∙
04/03/2023
Fast Numerical Multivariate Multipoint Evaluation
We design nearly-linear time numerical algorithms for the problem of mul...
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
∙
12/13/2020
If VNP is hard, then so are equations for it
Assuming that the Permanent polynomial requires algebraic circuits of ex...
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
∙
04/29/2020
On the Existence of Algebraically Natural Proofs
For every constant c > 0, we show that there is a family {P_N, c} of pol...
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
∙
04/30/2019
Derandomization from Algebraic Hardness
A hitting-set generator (HSG) is a polynomial map G:F^k →F^n such that f...
research
∙
04/30/2019
Derandomization from Algebraic Hardness: Treading the Borders
A hitting-set generator (HSG) is a polynomial map Gen:F^k →F^n such that...
research
∙
02/19/2019
Towards Optimal Depth Reductions for Syntactically Multilinear Circuits
We show that any n-variate polynomial computable by a syntactically mult...
research
∙
12/26/2018
Constructing Faithful Homomorphisms over Fields of Finite Characteristic
We study the question of algebraic rank or transcendence degree preservi...
research
∙
07/17/2018
Near-optimal Bootstrapping of Hitting Sets for Algebraic Models
The classical lemma of Ore-DeMillo-Lipton-Schwartz-Zippel [Ore22,DL78,Zi...
research
∙
07/17/2018
Near-optimal Bootstrapping of Hitting Sets for Algebraic Circuits
The classical lemma of Ore-DeMillo-Lipton-Schwartz-Zippel states that an...
research
∙
09/10/2017