BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Qiao-Long Huang

Qiao-Long Huang contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Symbolic Computationmath.RAComputational Complexitymath.NANumerical Analysis

Trust snapshot

Quick read

Trust 17 - UnverifiedVerification L1Unclaimed author
4works
0followers
5topics
2close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

4 published item(s)

preprint2022arXiv

Bit Complexity of Polynomial GCD on Sparse Representation

An input- and output-sensitive GCD algorithm for multi-variate polynomials over finite fields is proposed by combining the modular method with the Ben-Or/Tiwari sparse interpolation. The bit complexity of the algorithm is given and is sensitive to the sparse representation, while for previous sparse GCD algorithms, the complexities were given only in some special cases. It is shown that the new algorithm is superior both in theory and in practice comparing with existing GCD algorithms: the complexity in the degree is decreased from quadratic to linear and the running times are decreased by 1-3 orders of magnitude in various benchmarks.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Skew-sparse matrix multiplication

Based on the observation that $\mathbb{Q}^{(p-1) \times (p-1)}$ is isomorphic to a quotient skew polynomial ring, we propose a new method for $(p-1)\times (p-1)$ matrix multiplication over $\mathbb{Q}$, where $p$ is a prime number. The main feature of our method is the acceleration for matrix multiplication if the product is skew-sparse. Based on the new method, we design a deterministic algorithm with complexity $O(T^{ω-2} p^2)$, where $T\le p-1$ is a parameter determined by the skew-sparsity of input matrices and $ω$ is the asymptotic exponent of matrix multiplication. Moreover, by introducing randomness, we also propose a probabilistic algorithm with complexity $O^\thicksim(t^{ω-2}p^2+p^2\log\frac{1}ν)$, where $t\le p-1$ is the skew-sparsity of the product and $ν$ is the probability parameter.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Sparse Polynomial Interpolation Based on Derivative

In this paper, we propose two new interpolation algorithms for sparse multivariate polynomials represented by a straight-line program(SLP). Both of our algorithms work over any finite fields $F_q$ with large characteristic. The first one is a Monte Carlo randomized algorithm. Its arithmetic complexity is linear in the number $T$ of non-zero terms of $f$, in the number $n$ of variables. If $q$ is $O((nTD)^{(1)})$, where $D$ is the partial degree bound, then our algorithm has better complexity than other existing algorithms. The second one is a deterministic algorithm. It has better complexity than existing deterministic algorithms over a field with large characteristic. Its arithmetic complexity is quadratic in $n,T,\log D$, i.e., quadratic in the size of the sparse representation. And we also show that the complexity of our deterministic algorithm is the same as the one of deterministic zero-testing of Bläser et al. for the polynomial given by an SLP over finite field (for large characteristic).

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Sparse Polynomial Interpolation Based on Diversification

We consider the problem of interpolating a sparse multivariate polynomial over a finite field, represented with a black box. Building on the algorithm of Ben-Or and Tiwari for interpolating polynomials over rings with characteristic zero, we develop a new Monte Carlo algorithm over the finite field by doing additional probes. To interpolate a polynomial $f\in F_q[x_1,\dots,x_n]$ with a partial degree bound $D$ and a term bound $T$, our new algorithm costs $O^\thicksim(nT\log ^2q+nT\sqrt{D}\log q)$ bit operations and uses $2(n+1)T$ probes to the black box. If $q\geq O(nT^2D)$, it has constant success rate to return the correct polynomial. Compared with previous algorithms over general finite field, our algorithm has better complexity in the parameters $n,T,D$ and is the first one to achieve the complexity of fractional power about $D$, while keeping linear in $n,T$. A key technique is a randomization which makes all coefficients of the unknown polynomial distinguishable, producing a diverse polynomial. This approach, called diversification, was proposed by Giesbrecht and Roche in 2011. Our algorithm interpolates each variable independently using $O(T)$ probes, and then uses the diversification to correlate terms in different images. At last, we get the exponents by solving the discrete logarithms and obtain coefficients by solving a linear system. We have implemented our algorithm in Maple. Experimental results shows that our algorithm can applied to sparse polynomials with large degree. We also analyze the success rate of the algorithm.

0 citations0 reviewsNo code linkedOpen access