All reports by Author Zeyu Guo:

__
TR24-092
| 16th May 2024
__

Alexander Golovnev, Zeyu Guo, Pooya Hatami, Satyajeet Nagargoje, Chao Yan#### Hilbert Functions and Low-Degree Randomness Extractors

__
TR24-028
| 19th February 2024
__

Ashish Dwivedi, Zeyu Guo, Ben Lee Volk#### Optimal Pseudorandom Generators for Low-Degree Polynomials Over Moderately Large Fields

__
TR22-169
| 26th November 2022
__

Zeyu Guo, Ben Lee Volk, Akhil Jalan, David Zuckerman#### Extractors for Images of Varieties

Revisions: 1

__
TR22-063
| 30th April 2022
__

Vishwas Bhargava, Sumanta Ghosh, Zeyu Guo, Mrinal Kumar, Chris Umans#### Fast Multivariate Multipoint Evaluation Over All Finite Fields

__
TR21-067
| 6th May 2021
__

Zeyu Guo#### Variety Evasive Subspace Families

Revisions: 1

__
TR20-169
| 11th November 2020
__

Zeyu Guo, Noga Ron-Zewi#### Efficient List-Decoding with Constant Alphabet and List Sizes

Revisions: 1

__
TR20-168
| 11th November 2020
__

Zeyu Guo, Ray Li, Chong Shangguan, Itzhak Tamo, Mary Wootters#### Improved List-Decodability of Reedâ€“Solomon Codes via Tree Packings

__
TR18-019
| 28th January 2018
__

Zeyu Guo, Nitin Saxena, Amit Sinhababu#### Algebraic dependencies and PSPACE algorithms in approximative complexity

Revisions: 1

__
TR13-120
| 4th September 2013
__

Zeyu Guo#### Randomness-efficient Curve Samplers

Alexander Golovnev, Zeyu Guo, Pooya Hatami, Satyajeet Nagargoje, Chao Yan

For $S\subseteq \mathbb{F}^n$, consider the linear space of restrictions of degree-$d$ polynomials to $S$. The Hilbert function of $S$, denoted $\mathrm{h}_S(d,\mathbb{F})$, is the dimension of this space. We obtain a tight lower bound on the smallest value of the Hilbert function of subsets $S$ of arbitrary finite grids in $\mathbb{F}^n$ ... more >>>

Ashish Dwivedi, Zeyu Guo, Ben Lee Volk

We construct explicit pseudorandom generators that fool $n$-variate polynomials of degree at most $d$ over a finite field $\mathbb{F}_q$. The seed length of our generators is $O(d \log n + \log q)$, over fields of size exponential in $d$ and characteristic at least $d(d-1)+1$. Previous constructions such as Bogdanov's (STOC ... more >>>

Zeyu Guo, Ben Lee Volk, Akhil Jalan, David Zuckerman

We construct explicit deterministic extractors for polynomial images of varieties, that is, distributions sampled by applying a low-degree polynomial map $f : \mathbb{F}_q^r \to \mathbb{F}_q^n$ to an element sampled uniformly at random from a $k$-dimensional variety $V \subseteq \mathbb{F}_q^r$. This class of sources generalizes both polynomial sources, studied by Dvir, ... more >>>

Vishwas Bhargava, Sumanta Ghosh, Zeyu Guo, Mrinal Kumar, Chris Umans

Multivariate multipoint evaluation is the problem of evaluating a multivariate polynomial, given as a coefficient vector, simultaneously at multiple evaluation points. In this work, we show that there exists a deterministic algorithm for multivariate multipoint evaluation over any finite field $\mathbb{F}$ that outputs the evaluations of an $m$-variate polynomial of ... more >>>

Zeyu Guo

We introduce the problem of constructing explicit variety evasive subspace families. Given a family $\mathcal{F}$ of subvarieties of a projective or affine space, a collection $\mathcal{H}$ of projective or affine $k$-subspaces is $(\mathcal{F},\epsilon)$-evasive if for every $\mathcal{V}\in\mathcal{F}$, all but at most $\epsilon$-fraction of $W\in\mathcal{H}$ intersect every irreducible component of $\mathcal{V}$ ... more >>>

Zeyu Guo, Noga Ron-Zewi

We present an explicit and efficient algebraic construction of capacity-achieving list decodable codes with both constant alphabet and constant list sizes. More specifically, for any $R \in (0,1)$ and $\epsilon>0$, we give an algebraic construction of an infinite family of error-correcting codes of rate $R$, over an alphabet of size ... more >>>

Zeyu Guo, Ray Li, Chong Shangguan, Itzhak Tamo, Mary Wootters

This paper shows that there exist Reed--Solomon (RS) codes, over large finite fields, that are combinatorially list-decodable well beyond the Johnson radius, in fact almost achieving list-decoding capacity. In particular, we show that for any $\epsilon\in (0,1]$ there exist RS codes with rate $\Omega(\frac{\epsilon}{\log(1/\epsilon)+1})$ that are list-decodable from radius of ... more >>>

Zeyu Guo, Nitin Saxena, Amit Sinhababu

Testing whether a set $\mathbf{f}$ of polynomials has an algebraic dependence is a basic problem with several applications. The polynomials are given as algebraic circuits. Algebraic independence testing question is wide open over finite fields (Dvir, Gabizon, Wigderson, FOCS'07). The best complexity known is NP$^{\#\rm P}$ (Mittmann, Saxena, Scheiblechner, Trans.AMS'14). ... more >>>

Zeyu Guo

Curve samplers are sampling algorithms that proceed by viewing the domain as a vector space over a finite field, and randomly picking a low-degree curve in it as the sample. Curve samplers exhibit a nice property besides the sampling property: the restriction of low-degree polynomials over the domain to the ... more >>>