research
∙
04/03/2023
Randomly Punctured Reed-Solomon Codes Achieve the List Decoding Capacity over Polynomial-Size Alphabets
This paper shows that, with high probability, randomly punctured Reed-So...
share
research
∙
11/26/2022
Extractors for Images of Varieties
We construct explicit deterministic extractors for polynomial images of ...
research
∙
04/30/2022
Fast Multivariate Multipoint Evaluation Over All Finite Fields
Multivariate multipoint evaluation is the problem of evaluating a multiv...
research
∙
05/06/2021
Variety Evasive Subspace Families
We introduce the problem of constructing explicit variety evasive subspa...
research
∙
11/11/2020
Efficient List-Decoding with Constant Alphabet and List Sizes
We present an explicit and efficient algebraic construction of capacity-...
research
∙
11/09/2020
Improved List-Decodability of Reed–Solomon Codes via Tree Packings
This paper shows that there exist Reed–Solomon (RS) codes, over large fi...
research
∙
07/01/2020
Factoring Polynomials over Finite Fields with Linear Galois Groups: An Additive Combinatorics Approach
Let f̃(X)∈ℤ[X] be a degree-n polynomial such that f(X):=f̃(X) p factoriz...
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
∙
01/28/2018
Algebraic dependencies and PSPACE algorithms in approximative complexity
Testing whether a set f of polynomials has an algebraic dependence is a ...
research
∙
06/30/2017
P-schemes and Deterministic Polynomial Factoring over Finite Fields
We introduce a family of mathematical objects called P-schemes, where P ...
research
∙
06/14/2016