BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Zeyu Guo

Zeyu Guo appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Computational ComplexityData Structures and AlgorithmsSymbolic ComputationDistributed, Parallel, and Cluster Computingmath.AGmath.NTmath.PRSocial and Information Networks

Catalog footprint

What is connected

7works
8topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

7 published item(s)

preprint2023arXiv

Extractors for Images of Varieties

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, Gabizon and Wigderson (FOCS 2007, Comput. Complex. 2009), and variety sources, studied by Dvir (CCC 2009, Comput. Complex. 2012). Assuming certain natural non-degeneracy conditions on the map $f$ and the variety $V$, which in particular ensure that the source has enough min-entropy, we extract almost all the min-entropy of the distribution. Unlike the Dvir-Gabizon-Wigderson and Dvir results, our construction works over large enough finite fields of arbitrary characteristic. One key part of our construction is an improved deterministic rank extractor for varieties. As a by-product, we obtain explicit Noether normalization lemmas for affine varieties and affine algebras. Additionally, we generalize a construction of affine extractors with exponentially small error due to Bourgain, Dvir and Leeman (Comput. Complex. 2016) by extending it to all finite prime fields of quasipolynomial size.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Derandomization from Algebraic Hardness

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 give a new construction of such an HSG assuming that we have an explicit polynomial of sufficient hardness. Formally, we prove the following over any field of characteristic zero: Let $k\in \mathbb{N}$ and $δ> 0$ be arbitrary constants. Suppose $\{P_d\}_{d\in \mathbb{N}}$ is an explicit family of $k$-variate polynomials such that $\operatorname{deg} P_d = d$ and $P_d$ requires algebraic circuits of size $d^δ$. Then, there are explicit hitting sets of polynomial size for $\mathsf{VP}$. This is the first HSG in the algebraic setting that yields a complete derandomization of polynomial identity testing (PIT) for general circuits from a suitable algebraic hardness assumption. As a direct consequence, we show that even saving a single point from the "trivial" explicit, exponential sized hitting sets for constant-variate polynomials of low individual degree which are computable by small circuits, implies a deterministic polynomial time algorithm for PIT. More precisely, we show the following: Let $k\in \mathbb{N}$ and $δ> 0$ be arbitrary constants. Suppose for every $s$ large enough, there is an explicit hitting set of size at most $((s+1)^k - 1)$ for the class of $k$-variate polynomials of individual degree $s$ that are computable by size $s^δ$ circuits. Then there is an explicit hitting set of size $\operatorname{poly}(s)$ for the class of $s$-variate polynomials, of degree $s$, that are computable by size $s$ circuits. As a consequence, we give a deterministic polynomial time construction of hitting sets for algebraic circuits, if a strengthening of the $τ$-Conjecture of Shub and Smale is true.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

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

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}_p$ given $\tilde{f}(X)$. Under the generalized Riemann hypothesis (GRH), we give an improved deterministic algorithm that computes the complete factorization of $f(X)$ in the case that the Galois group of $\tilde{f}(X)$ is (permutation isomorphic to) a linear group $G\leq \mathrm{GL}(V)$ on the set $S$ of roots of $\tilde{f}(X)$, where $V$ is a finite-dimensional vector space over a finite field $\mathbb{F}$ and $S$ is identified with a subset of $V$. In particular, when $|S|=|V|^{Ω(1)}$, the algorithm runs in time polynomial in $n^{\log n/(\log\log\log\log n)^{1/3}}$ and the size of the input, improving Evdokimov's algorithm. Our result also applies to a general Galois group $G$ when combined with a recent algorithm of the author. To prove our main result, we introduce a family of objects called linear $m$-schemes and reduce the problem of factoring $f(X)$ to a combinatorial problem about these objects. We then apply techniques from additive combinatorics to obtain an improved bound. Our techniques may be of independent interest.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

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

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 \log^2 q)$ time to factor polynomials of degree $n$ over the finite field $\mathbb{F}_q$ with $q$ elements. A significant open problem is if the $3/2$ exponent can be improved. We study a collection of algebraic problems and establish a web of reductions between them. A consequence is that an algorithm for any one of these problems with exponent better than $3/2$ would yield an algorithm for polynomial factorization with exponent better than $3/2$.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Gossip vs. Markov Chains, and Randomness-Efficient Rumor Spreading

We study gossip algorithms for the rumor spreading problem which asks one node to deliver a rumor to all nodes in an unknown network. We present the first protocol for any expander graph $G$ with $n$ nodes such that, the protocol informs every node in $O(\log n)$ rounds with high probability, and uses $\tilde{O}(\log n)$ random bits in total. The runtime of our protocol is tight, and the randomness requirement of $\tilde{O}(\log n)$ random bits almost matches the lower bound of $Ω(\log n)$ random bits for dense graphs. We further show that, for many graph families, polylogarithmic number of random bits in total suffice to spread the rumor in $O(\mathrm{poly}\log n)$ rounds. These results together give us an almost complete understanding of the randomness requirement of this fundamental gossip process. Our analysis relies on unexpectedly tight connections among gossip processes, Markov chains, and branching programs. First, we establish a connection between rumor spreading processes and Markov chains, which is used to approximate the rumor spreading time by the mixing time of Markov chains. Second, we show a reduction from rumor spreading processes to branching programs, and this reduction provides a general framework to derandomize gossip processes. In addition to designing rumor spreading protocols, these novel techniques may have applications in studying parallel and multiple random walks, and randomness complexity of distributed algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Randomness-efficient Curve Samplers

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 sampled curve is still low-degree. This property is often used in combination with the sampling property and has found many applications, including PCP constructions, local decoding of codes, and algebraic PRG constructions. The randomness complexity of curve samplers is a crucial parameter for its applications. It is known that (non-explicit) curve samplers using $O(\log N+\log(1/δ))$ random bits exist, where $N$ is the domain size and $δ$ is the confidence error. The question of explicitly constructing randomness-efficient curve samplers was first raised in \cite{TU06} where they obtained curve samplers with near-optimal randomness complexity. We present an explicit construction of low-degree curve samplers with {\em optimal} randomness complexity (up to a constant factor), sampling curves of degree $\left(m\log_q(1/δ)\right)^{O(1)}$ in $\mathbb{F}_q^m$. Our construction is a delicate combination of several components, including extractor machinery, limited independence, iterated sampling, and list-recoverable codes.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Randomness-Efficient Rumor Spreading

We study the classical rumor spreading problem, which is used to spread information in an unknown network with $n$ nodes. We present the first protocol for any expander graph $G$ with $n$ nodes and minimum degree $Θ(n)$ such that, the protocol informs every node in $O(\log n)$ rounds with high probability, and uses $O(\log n\log\log n)$ random bits in total. The runtime of our protocol is tight, and the randomness requirement of $O(\log n\log\log n)$ random bits almost matches the lower bound of $Ω(\log n)$ random bits. We further study rumor spreading protocols for more general graphs, and for several graph topologies our protocols are as fast as the classical protocol and use $\tilde{O}(\log n)$ random bits in total, in contrast to $O(n\log^2n)$ random bits used in the well-known rumor spreading push protocol. These results together give us almost full understanding of the randomness requirement for this basic epidemic process. Our protocols rely on a novel reduction between rumor spreading processes and branching programs, and this reduction provides a general framework to derandomize these complex and distributed epidemic processes. Interestingly, one cannot simply apply PRGs for branching programs as rumor spreading process is not characterized by small-space computation. Our protocols require the composition of several pseudorandom objects, e.g. pseudorandom generators, and pairwise independent generators. Besides designing rumor spreading protocols, the techniques developed here may have applications in studying the randomness complexity of distributed algorithms.

0 citations0 reviewsNo code linkedOpen access