Explanipedia

Random Reed-Solomon codes achieve list-decoding capacity with linear-sized alphabets Open

Omar Alrabiah, Zeyu Guo, Venkatesan Guruswami, Zihan Zhang · 2025

Improved Decoding of Tanner Codes Open

Zeyu Guo, Zhongliang Zhou · 2025

In this paper, we present improved decoding algorithms for expander-based Tanner codes. We begin by developing a randomized linear-time decoding algorithm that, under the condition that $ δd_0 > 2 $, corrects up to $ αn $ errors for a Tann…

Variety Evasive Subspace Families Open

Zeyu Guo · 2024

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$$ -subspac…

Random Reed-Solomon Codes Achieve the Half-Singleton Bound for Insertions and Deletions over Linear-Sized Alphabets Open

Roni Con, Zeyu Guo, Ray Li, Zihan Zhang · 2024

In this paper, we prove that with high probability, random Reed-Solomon codes approach the half-Singleton bound - the optimal rate versus error tradeoff for linear insdel codes - with linear-sized alphabets. More precisely, we prove that, …

Random Gabidulin Codes Achieve List Decoding Capacity in the Rank Metric Open

Zeyu Guo, Chaoping Xing, Yuan Chen, Zihan Zhang · 2024

Gabidulin codes, serving as the rank-metric counterpart of Reed-Solomon codes, constitute an important class of maximum rank distance (MRD) codes. However, unlike the fruitful positive results about the list decoding of Reed-Solomon codes,…

Fast Multivariate Multipoint Evaluation over All Finite Fields Open

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

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 m…

Optimal Pseudorandom Generators for Low-Degree Polynomials over Moderately Large Fields Open

Ashish Dwivedi, Zeyu Guo, Ben Lee Volk · 2024

We construct explicit pseudorandom generators that fool n-variate polynomials of degree at most d over a finite field 𝔽_q. The seed length of our generators is O(d log n + log q), over fields of size exponential in d and characteristic at …

Randomly Punctured Reed-Solomon Codes Achieve the List Decoding Capacity over Polynomial-Size Alphabets Open

Zeyu Guo, Zihan Zhang · 2023

This paper shows that, with high probability, randomly punctured Reed-Solomon codes over fields of polynomial size achieve the list decoding capacity. More specifically, we prove that for any $ε>0$ and $R\in (0,1)$, with high probability, …

Extractors for Images of Varieties Open

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

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 fro…

Fast Multivariate Multipoint Evaluation Over All Finite Fields Open

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

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 m…

Efficient List-Decoding With Constant Alphabet and List Sizes Open

Zeyu Guo, Noga Ron‐Zewi · 2021

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 $ε>0$, we give an algebraic constructi…

Variety evasive subspace families Open

Zeyu Guo · 2021

We introduce the problem of constructing explicit variety evasive subspace families. Given a family ℱ of subvarieties of a projective or affine space, a collection ℋ of projective or affine k-subspaces is (ℱ,ε)-evasive if for every 𝒱 ∈ ℱ, …

Dust Monitoring and Processing System Based on Stepped Distributed Algorithm Open

Pei Zhang, Xiaolin Ma, Lihui Zhang, Zeyu Guo · 2021

With the rapid development of modern industry, productive dust is almost everywhere in factories, becoming a major hidden danger to industrial production safety. This project will realize real-time monitoring of factory dust, automatic dus…

Dust monitoring and processing system based on WiFi Mesh network distributed backup routing algorithm Open

Lihui Zhang, Xiaolin Ma, Pei Zhang, Zeyu Guo · 2021

This paper proposes a dust monitoring and processing system using WiFi Mesh network distributed backup routing algorithm. The system is based on WiFi Mesh technology to realize real-time dust data monitoring and dust processing, and transm…

A dust sensor monitoring system using Wi-Fi mesh network Open

Zeyu Guo, Xiaolin Ma, Pei Zhang, Zhaoyang Liu · 2021

This paper proposes a dust sensor monitoring system using Wi-Fi mesh network, including wireless dust sensor node and Wi-Fi mesh networking procedure. The wireless sensor node is made by integrating a dust sensor based on GP2Y1010AU0F chip…

Variety Evasive Subspace Families Open

Zeyu Guo · 2021

We introduce the problem of constructing explicit variety evasive subspace families. Given a family ℱ of subvarieties of a projective or affine space, a collection ℋ of projective or affine k-subspaces is (ℱ,ε)-evasive if for every 𝒱 ∈ ℱ, …

Improved List-Decodability of Reed--Solomon Codes via Tree Packings Open

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

This paper shows that there exist Reed--Solomon (RS) codes, over \black{exponentially} large finite fields \black{in the code length}, that are combinatorially list-decodable well beyond the Johnson radius, in fact almost achieving the lis…

Factoring Polynomials over Finite Fields with Linear Galois Groups: An Additive Combinatorics Approach Open

Zeyu Guo · 2020

Let $\tilde{f}(X)\in\mathbb{Z}[X]$ be a degree-$n$ polynomial such that $f(X):=\tilde{f}(X)\bmod p$ factorizes into $n$ distinct linear factors over $\mathbb{F}_p$. We study the problem of deterministically factoring $f(X)$ over $\mathbb{F…

Improved Explicit Hitting-Sets for ROABPs Open

Zeyu Guo, Rohit Gurjar · 2020

We give improved explicit constructions of hitting-sets for read-once oblivious algebraic branching programs (ROABPs) and related models. For ROABPs in an unknown variable order, our hitting-set has size polynomial in (nr)^{(log n)/(max{1,…

Improved List-Decodability of Reed-Solomon Codes via Tree Packings. Open

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

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 …

Factoring Polynomials over Finite Fields with Linear Galois Groups: An Additive Combinatorics Approach. Open

Zeyu Guo · 2020

Let f̃(X) ∈ ℤ[X] be a degree-n polynomial such that f(X): = f̃(X)od p factorizes into n distinct linear factors over 𝔽_p. We study the problem of deterministically factoring f(X) over 𝔽_p given f̃(X). Under the generalized Riemann hypothesis …

Derandomization from Algebraic Hardness Open

Zeyu Guo, Mrinal Kumar, Ramprasad Saptharishi, Noam Solomon · 2019

A hitting-set generator (HSG) is a polynomial map $G:\mathbb{F}^k \to \mathbb{F}^n$ such that for all $n$-variate polynomials $C$ of small enough circuit size and degree, if $C$ is nonzero, then $C\circ G$ is nonzero. In this paper, we giv…

Deterministic polynomial factoring over finite fields: A uniform approach via -schemes Open

Zeyu Guo · 2019

Algebraic dependencies and PSPACE algorithms in approximative complexity Open

Zeyu Guo, Nitin Saxena, Amit Sinhababu · 2018

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 f…

Algebraic Dependencies and PSPACE Algorithms in Approximative Complexity Open

Zeyu Guo, Nitin Saxena, Amit Sinhababu · 2018

Testing whether a set 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…

$\mathcal{P}$-schemes and Deterministic Polynomial Factoring over Finite Fields Open

Zeyu Guo · 2017

We introduce a family of mathematical objects called $\mathcal{P}$-schemes, where $\mathcal{P}$ is a poset of subgroups of a finite group $G$. A $\mathcal{P}$-scheme is a collection of partitions of the right coset spaces $H\backslash G$, …

Algebraic Problems Equivalent to Beating Exponent 3/2 for Polynomial Factorization over Finite Fields Open

Zeyu Guo, Anand Kumar Narayanan, Chris Umans · 2016

The fastest known algorithm for factoring univariate polynomials over finite fields is the Kedlaya-Umans (fast modular composition) implementation of the Kaltofen-Shoup algorithm. It is randomized and takes $\widetilde{O}(n^{3/2}\log q + n…

Algebraic Problems Equivalent to Beating Exponent 3/2 for Polynomial Factorization over Finite Fields Open

Zeyu Guo, Anand Kumar Narayanan, Chris Umans · 2016

The fastest known algorithm for factoring univariate polynomials over finite fields is the Kedlaya-Umans (fast modular composition) implementation of the Kaltofen-Shoup algorithm. It is randomized and takes ~O(n^{3/2}*log(q)+n*log^2(q)) ti…

Zeyu Guo YOU? Author Swipe